Question

The objective function can be maximization or minimization.

The LP must have at least three decision variables.

The LP must have at least three constraints.

a) Solve the LP you create by using the Simplex Method. You can use Big-M or Two-Phase Method if needed. Show each iteration in detail. You should have at least 2 iterations and at most five iterations. If your model is not obeying this rule, please change your model and randomly generate a new model. Make sure that you obtain a single optimal solution.

b) Indicate clearly the optimal basic and nonbasic variables and their values and write the reduced cost of each optimal nonbasic variable.

c) Find the dual of the primal problem you have on hand.  

d) Find the optimal dual solution by using the two methods you have learned in class.

e) Verify that your primal and dual solutions are indeed optimal using the Complementary Slackness theorem. Show your work clearly.

f) For the basic variables at the optimal solution, create your optimal tableau this time by using matrix operations.

g) Change the right-hand-side value of one of the constraints. Make sure that your current solution becomes infeasible and you apply the Dual Simplex Method to recover feasibility.

h) Change the objective function coefficient of one basic variable and one nonbasic variable if all nonbasic variables are not slack variables. If you do not have a nonbasic variable which is an original variable for your problem, then change the objective function coefficient of two basic variables. Make sure that your current solution becomes nonoptimal and you apply the Primal Simplex Method to recover optimality.

i) Add a new constraint into your model. Make sure that the new constraint is not satisfied by the current optimal solution and you apply the Dual Simplex Method to recover feasibility.

j) Add a new activity (a new decision variable) into your model. Make sure that your current solution becomes non-optimal and you apply the Primal Simplex Method to recover optimality.

Hint 1: Please use this theorem for question d)

Theorem 1 (Sufficient Optimality Criterion): If x0 and y0 are feasible solutions to the primal and dual problems such that z = cx0 = y0b = w, then x0 and y0 are optimal solutions to their respective problems.

Theorem 2 (Strong Duality): In a primal-dual pair of LPs, if either the primal or the dual problem has an optimal feasible solution, then the other problem does also have an optimal solution and the two optimal objective values are equal.

I really can't solve and these questions are connected to each other so please help as much as you can! It's also for my learning. Thanks for your effort!

Answer 1

a) Maximize Z = 5x1 + 10x2 + 8x3

Subject to Constraints,

3x1 + 5x2 + 2x3 <= 60
4x1 + 4x2 + 4x3 <= 72
2x1 + 4x2 + 5x3 <= 100
and x1,x2,x3 >= 0

The problem is converted to canonical form by adding slack, surplus and artificial variables as appropiate

1. As the constraint-1 is of type '≤' we should add slack variable S1

2. As the constraint-2 is of type '≤' we should add slack variable S2

3. As the constraint-3 is of type '≤' we should add slack variable S3

After introducing slack variables

Max Z = 5 x1 + 10 x2 + 8 x3 + 0 S1 + 0 S2 + 0 S3

subject to

3 x1 + 5 x2 + 2 x3 + S1 = 60 4 x1 + 4 x2 + 4 x3 + S2 = 72 2 x1 + 4 x2 + 5 x3 + S3 = 100

and x1,x2,x3,S1,S2,S3≥0

Iteration-1		Cj	5	10	8	0	0	0
B	CB	XB	x1	x2	x3	S1	S2	S3	MinRatio XB / x2
S1	0	60	3	(5)	2	1	0	0	605=12→
S2	0	72	4	4	4	0	1	0	724=18
S3	0	100	2	4	5	0	0	1	1004=25
Z=0		Zj	0	0	0	0	0	0
		Zj-Cj	-5	-10↑	-8	0	0	0

Negative minimum Zj-Cj is -10 and its column index is 2. So, the entering variable is x2.

Minimum ratio is 12 and its row index is 1. So, the leaving basis variable is S1.

∴ The pivot element is 5.

Entering =x2, Departing =S1, Key Element =5

R1(new)=R1(old)÷5

R2(new)=R2(old) - 4R1(new)

R3(new)=R3(old) - 4R1(new)

Iteration-2		Cj	5	10	8	0	0	0
B	CB	XB	x1	x2	x3	S1	S2	S3	MinRatio XB / x3
x2	10	12	0.6	1	0.4	0.2	0	0	120.4=30
S2	0	24	1.6	0	(2.4)	-0.8	1	0	242.4=10→
S3	0	52	-0.4	0	3.4	-0.8	0	1	523.4=15.2941
Z=120		Zj	6	10	4	2	0	0
		Zj-Cj	1	0	-4↑	2	0	0

Negative minimum Zj-Cj is -4 and its column index is 3. So, the entering variable is x3.

Minimum ratio is 10 and its row index is 2. So, the leaving basis variable is S2.

∴ The pivot element is 2.4.

Entering =x3, Departing =S2, Key Element =2.4

R2(new)=R2(old)÷2.4

R1(new)=R1(old) - 0.4R2(new)

R3(new)=R3(old) - 3.4R2(new)

Iteration-3		Cj	5	10	8	0	0	0
B	CB	XB	x1	x2	x3	S1	S2	S3	MinRatio
x2	10	8	0.3333	1	0	0.3333	-0.1667	0
x3	8	10	0.6667	0	1	-0.3333	0.4167	0
S3	0	18	-2.6667	0	0	0.3333	-1.4167	1
Z=160		Zj	8.6667	10	8	0.6667	1.6667	0
		Zj-Cj	3.6667	0	0	0.6667	1.6667	0

Since all Zj - Cj ≥ 0

b) Hence, optimal solution is arrived with value of variables as :
x1 = 0, x2 = 8,x3 = 10

Max Z=160

c) Dual is :

Minimize y = 60 y1 + 72 y2 + 100 y3

Subject to Constraints,

3 y1 + 4 y2 + 2 y3 ≥ 5 5 y1 + 4 y2 + 4 y3 ≥ 10 2 y1 + 4 y2 + 5 y3 ≥ 8

and y1,y2,y3≥0;

d) Method is not mentioned in the question

Please reupload the rest of the questions separately