Linear Programming and Optimization Problems: Data Science Assignment

This document provides a comprehensive solution to a data science assignment focusing on linear programming. The solution covers various aspects of linear programming, including formulating linear programs, solving them using the simplex method, and analyzing the feasible region. The document addresses primal and dual problems, network flow optimization, and bin packing problems. It also includes a proof demonstrating the relationship between the primal and dual linear programs. The assignment explores different scenarios and constraints, providing detailed explanations and step-by-step solutions. This resource is valuable for students seeking assistance with their linear programming assignments, offering clear and concise solutions to complex problems.

Question 1:
a)
i) The linear program is given by,
Maximize z = 5x1 + 3x2
Subject to,
5x1 -2x2 >= 0
x1 + x2 <=7
x1 <= 5
x1, x2 >= 0
At first, x1 = x2 = 0 and choosing the slack variables x3, x4 and x5 the LP becomes
z = 5x1+ 3x2
Subject to,
x3 = -5x1 + 2x2
x4 = 7- x1 – x2
x5 = 5- x1
Let, entering variable is x2.
Hence, max(x2) = min(∞,7,∞)
Leaving variable is x4.
So, x2 = 7-x1-x4
Objective function, z = 5x1 + 3(7-x1-x4) = 21 +2x1 -3x4
Subject to,
x2 = 7-x1-x4
x3 = -5x1 + 2(7-x1-x4) = -5x1 + 14 -2x1-2x4 = -7x1 + 14-2x4
x5 = 5-x1

Now, entering variable is x1
Hence, max(x1) = min(7,5, 2)
Leaving variable is x3
Hence, x1 = -x3/7 +2 – (2/7)*x4
So, objective function becomes,
z = 21 + 2(-x3/7 +2 – (2/7)*x4) – 3x4
= 21 – (2/7)x3 + 4- (4/7)x4 – 3x4 = 25 - (2/7)x3 - (25/7)x4
Subject to,
x2 = 7 +x3/7 -2 +(2/7)*x4 – x4
x1 = -x3/7 +2 – (2/7)*x4
and x5 = 5-x1
Now, for maximizing z as all the coefficients of the basic variables became negative
hence it is the optimal solution.
Now, putting x3=x4 = 0
Hence, the values of the variables for the optimal solution is x3 =0 ,x4 =0, x2 = 5, x1
= 2 and x5 = 3.
So, the maximum value of z = 5x1 + 3x2 by simplex method subjected to the
constraints given above is z = 5*2 + 3*5 = 25.
ii) The feasible region of the objective function is the solution set which satisfies all the
conditions of the constraints.
The linear program is given by,
Maximize z = 5x1 + 3x2
Subject to,
5x1 -2x2 >= 0

x1 + x2 <=7
x1 <= 5, x1, x2 >= 0
Feasible region:
The feasible region is shown in Desmos graphing calculator, which is the area bounded by
the points (2,5),(0,0),(5,2) and (5,0). Here, (x,y) is equivalent to (x1,x2).
Q1.(b)
The LP problem is given as,
Maximize x+y
Subject to,
2x+y <= 3
x+3y <= 5
x,y => 0.
a) Now, the dual of the above LP problem is given by,

Minimize 3x1 + 5y1
Subject to,
2x1 + y1 => 1
x1 + 3y1 => 1
x1,y1>= 0
b) Now, the both primal and dual solution can be solved using the above simplex
method.
The solution of the primal problem that is (x,y) that maximizes x+y with the
constraints condition is (0.8, 1.4).
Max value of z = x+y = 0.8 + 1.4 = 2.2
Similarly, the solution of the dual problem is (x1,y1) = (0.4,0.2).
Hence, the minimum value of objective function z = 3x1 + 5y1 = 3*0.4 + 5*0.2 = 2.2
Hence, the dual of any LP problem will have the different solution set but the value of
the objective function will be same.
Question 2:
a) The graph is G = (V,E;c,l) where V = number of vertex set, E = number of edges set.
Now, the source node is s and the destination node are t. Maximizing the total flow is
the objective. Also, the flow in edge e ‘fe’ must be greater than or equals with le
Hence, the LP problem is given by,
Maximize ∑
v ∈V
fsv−∑
v ∈V
fvs
Subjected to,
f uv ≤ c (u , v) for each (u,v) ∈ E
∑
v ∈V
fuv=∑
v ∈V
fvu for each u ∈V −{s , t }
fuv ≥lefor each u,v ∈V

b) Given network G = (V,E;c;ε).
Source = s, destination node = t, every edge e has the capacity ce => 0 and outgoing
flow is smaller by a factor ( 1−εv ) and ε v is a given constant for each of the vertex in
V.
Hence, the maximum flow will be,
Maximize
∑
v ∈V
fsv−∑
v ∈V
fvs
f uv ≤ ce(u , v) for each (u,v) ∈ E
∑
v ∈V
fuv=
∑
v∈V
fvu
( 1−εv ) for each u ∈V −{s , t }
fuv ≥0for each u,v ∈V
c) Number of bins is given by B1, B2,….Bk and the capacity of Ck with 1<=k<=K.
The profit is p(i,k) for packing the bin into Bk. The objective is to maximize the
profit.
Hence, the LP problem is
Maximize ∑
k =1
K
∑
i=1
n
p (i, k )
Subject to,
Ck – wi => 0 when ai item is going into Bk bin for all k = 1(1)K and i = 1(1)n
Ck > 0 and wi>0
d) Given that P is a primal linear program with the minimization problem and D is the
dual linear program of P which will be a maximization problem. It is needed to be
shown that the value of the optimal solution of the D is the lower bound of the
optimal solution of P.
Let, the primal Linear program P is

Minimize (x,y) z = px + qy
Subject to,
x+y >= 2, x>= 0 and y>= 0
The lower bound of the primal LP is 2 to satisfy x+y >= 2 or the objective function of
the problem need to have a minimum value of 2.
Now, the Dual of the primal program is P is D which given by,
Maximize (a,b,c) 2a
Subject to
a+b = p
a+c = q
and a>=0,b>=0, c>=0
Hence, the optimal solution is obtained when b = 1- p, c= 1- q and a =1
Hence, the optimal solution is 2a=2*1 = 2.
This is the lower bound of the primal problem P.
Hence, with the increase of the number of variables in the primal problem P the
number of variables in D will also increase proportionally and by the method of
induction it can be shown that the lower bound of P will be equal to optimal solution
of D(Proved).
Question 3:
Given that, A is an (m*n) matrix and c is an n-vector of constants (n*1).
x = vector of (n*1), y = vector of (m*1)
Now, let the first pair of inequalities is the Primal problem and the second set of
inequalities is the Dual problem.
Hence, constraints of the Primal problem will be
Ax <=0 and c^T*x>0

and constraints of the dual problem is given as
A^Ty = c,
y=> 0
Now, in the dual of the primal linear problem the constraints matrix is transpose and
the inequality reverses. Now, as the inequality didn’t reverse in the second set of
equation, hence the second set of inequalities are not the dual of the first.
Now, in the first set of equations Ax is a (m*1) matrix and (c^T)*x is a (1*1) element.
Now, as both equations are inequalities and vector(x) = 0 do not satisfy the second
constraint, hence 1st system of equations are unsolvable.
Now, in the second system (A^T)*y is a (n*1) matrix and the y variables are exactly
determined from the equality sign. This satisfies the second equation y=>0. Hence,
the second system is solvable.
Hence, it can be concluded that between the two given systems exactly one of them is
solvable. (Proved)