Question

1. Use the Simplex method to solve the following problem:
     Max  Z = x1 + 2x2 + 3x3
     s. to2x1 + x2 + x3 <= 20
   x1 + 2x2 - x3 <= 20
           3x2 + x3 <= 10
          x1, x2, x3 >= 0
   Clearly specify the optimal values of all variables ya used in your procedure as well as the optimal value of the objective function.

2. In part a), say what corner point was analyzed in each iteration and give the corresponding value of the objective function. Include iteration 0, that is, the one that gives the starting corner point.

Answer 1

Solution:
Problem is

Max Z = x1 + 2 x2 + 3 x3

subject to

2 x1 + x2 + x3 ≤ 20 x1 + 2 x2 - x3 ≤ 20 3 x2 + x3 ≤ 10

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 = x1 + 2 x2 + 3 x3 + 0 S1 + 0 S2 + 0 S3

subject to

2 x1 + x2 + x3 + S1 = 20 x1 + 2 x2 - x3 + S2 = 20 3 x2 + x3 + S3 = 10

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

Iteration-1		Cj	1	2	3	0	0	0
B	CB	XB	x1	x2	x3	S1	S2	S3	MinRatio XBx3
S1	0	20	2	1	1	1	0	0	201=20
S2	0	20	1	2	-1	0	1	0	---
S3	0	10	0	3	(1)	0	0	1	101=10→
Z=0		Zj	0	0	0	0	0	0
		Zj-Cj	-1	-2	-3↑	0	0	0

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

Minimum ratio is 10 and its row index is 3. So, the leaving basis variable is S3.

∴ The pivot element is 1.

Entering =x3, Departing =S3, Key Element =1

R3(new)=R3(old)

R3(old) =	10	0	3	1	0	0	1
R3(new)=R3(old)	10	0	3	1	0	0	1

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

R1(old) =	20	2	1	1	1	0	0
R3(new) =	10	0	3	1	0	0	1
R1(new)=R1(old) - R3(new)	10	2	-2	0	1	0	-1

R2(new)=R2(old) + R3(new)

R2(old) =	20	1	2	-1	0	1	0
R3(new) =	10	0	3	1	0	0	1
R2(new)=R2(old) + R3(new)	30	1	5	0	0	1	1

Iteration-2		Cj	1	2	3	0	0	0
B	CB	XB	x1	x2	x3	S1	S2	S3	MinRatio XBx1
S1	0	10	(2)	-2	0	1	0	-1	102=5→
S2	0	30	1	5	0	0	1	1	301=30
x3	3	10	0	3	1	0	0	1	---
Z=30		Zj	0	9	3	0	0	3
		Zj-Cj	-1↑	7	0	0	0	3

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

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

∴ The pivot element is 2.

Entering =x1, Departing =S1, Key Element =2

R1(new)=R1(old)÷2

R1(old) =	10	2	-2	0	1	0	-1
R1(new)=R1(old)÷2	5	1	-1	0	0.5	0	-0.5

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

R2(old) =	30	1	5	0	0	1	1
R1(new) =	5	1	-1	0	0.5	0	-0.5
R2(new)=R2(old) - R1(new)	25	0	6	0	-0.5	1	1.5

R3(new)=R3(old)

R3(old) =	10	0	3	1	0	0	1
R3(new)=R3(old)	10	0	3	1	0	0	1

Iteration-3		Cj	1	2	3	0	0	0
B	CB	XB	x1	x2	x3	S1	S2	S3	MinRatio
x1	1	5	1	-1	0	0.5	0	-0.5
S2	0	25	0	6	0	-0.5	1	1.5
x3	3	10	0	3	1	0	0	1
Z=35		Zj	1	8	3	0.5	0	2.5
		Zj-Cj	0	6	0	0.5	0	2.5

Since all Zj-Cj≥0

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

Max Z=35