Linear Programming and LP 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,