Question

Problem #7: Consider the linear program st. max z = 5x, + 3x2 + xz x + x2 + x3 56 5x2 + 3x2 +6x3 =15 X1, X2, xz 20 and an associated tableau N X1 X2 X3 S1 S2 RHS 1 0 0 5 0 1 15 0 0 0.4 -0.2 1 -0.2 3 0 1 0.6 1.2 0 0.2 3 (a) What basic solution does this tableau represent? Is this solution optimal? Why or why not? (b) Does this tableau represent a unique optimum? If not, find an alternative optimal solution.

Answer 1

Using Simplex method,

Max Z = 5 x1 + 3 x2 + x3

subject to

x1 + x2 + x3 ≤ 6 5 x1 + 3 x2 + 6 x3 ≤ 15

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

After introducing slack variables

Max Z = 5 x1 + 3 x2 + x3 + 0 S1 + 0 S2

subject to

x1 + x2 + x3 + S1 = 6 5 x1 + 3 x2 + 6 x3 + S2 = 15

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

Iteration-1		Cj	5	3	1	0	0
B	CB	XB	x1	x2	x3	S1	S2	MinRatio XBx1
S1	0	6	1	1	1	1	0	61=6
S2	0	15	(5)	3	6	0	1	155=3→
Z=0		Zj	0	0	0	0	0
		Zj-Cj	-5↑	-3	-1	0	0

Negative minimum Zj-Cj is -5 and its column index is 1. So, the entering variable is x1.

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

∴ The pivot element is 5.

Entering =x1, Departing =S2, Key Element =5

R2(new)=R2(old)÷5

R2(old) =	15	5	3	6	0	1
R2(new)=R2(old)÷5	3	1	0.6	1.2	0	0.2

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

R1(old) =	6	1	1	1	1	0
R2(new) =	3	1	0.6	1.2	0	0.2
R1(new)=R1(old) - R2(new)	3	0	0.4	-0.2	1	-0.2

Iteration-2		Cj	5	3	1	0	0
B	CB	XB	x1	x2	x3	S1	S2	MinRatio
S1	0	3	0	0.4	-0.2	1	-0.2
x1	5	3	1	0.6	1.2	0	0.2
Z=15		Zj	5	3	6	0	1
		Zj-Cj	0	0	5	0	1

Since all Zj-Cj≥0

Hence, optimal solution is arrived with value of variables as :
x1=3,x2=0,x3=0

Max Z=15