Question

MAX Z = 2x1 + 8x2 + 4x3
subject to
2x1 + 3x2 <= 8
2x2 + 5x3 <= 12
3x1 + x2 + 4x3 <= 15
x1 + x3 = 11
and x1,x2,x3 >= 0

apply the Dual Simplex Method to recover feasibility.

Answer 1

Solution by DUAL SIMPLEX METHOD:
Problem is

Max Z = 2 x1 + 8 x2 + 4 x3

subject to

2 x1 + 3 x2 ≤ 8 2 x2 + 5 x3 ≤ 12 3 x1 + x2 + 4 x3 ≤ 15 x1 + x3 = 11

and x1,x2,x3≥0;

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

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

4. As the constraint-4 is of type '=' we should add artificial variable A1

After introducing slack,artificial variables

Max Z = 2 x1 + 8 x2 + 4 x3 + 0 S1 + 0 S2 + 0 S3 - M A1

subject to

2 x1 + 3 x2 + S1 = 8 2 x2 + 5 x3 + S2 = 12 3 x1 + x2 + 4 x3 + S3 = 15 x1 + x3 + A1 = 11

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

Iteration-1		Cj	2	8	4	0	0	0	-M
B	CB	XB	x1	x2	x3	S1	S2	S3	A1
S1	0	8	2	3	0	1	0	0	0
S2	0	12	0	2	5	0	1	0	0
S3	0	15	3	1	4	0	0	1	0
A1	-M	11	1	0	1	0	0	0	1
Z = -11M		Zj	-M	0	-M	0	0	0	-M
		Zj-Cj	-M-2	-8	-M-4	0	0	0	0
		Ratio	---	---	---	---	---	---	---

Here not all Zj-Cj≥0. (Because Z1-C1=-M-2)

Hence, the method fails to get an optimal basic feasible solution.

---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

Then, I have solved it using SIMPLEX METHOD

Problem is

Max Z = 5 x1 + 10 x2 + 8 x3

subject to

3 x1 + 5 x2 + 2 x3 ≤ 60 4 x1 + 4 x2 + 4 x3 ≤ 72 2 x1 + 4 x2 + 5 x3 ≤ 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 XBx2
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(old) =	60	3	5	2	1	0	0
R1(new)=R1(old)÷5	12	0.6	1	0.4	0.2	0	0

R2(old) =	72	4	4	4	0	1	0
R1(new) =	12	0.6	1	0.4	0.2	0	0
4×R1(new) =	48	2.4	4	1.6	0.8	0	0
R2(new)=R2(old) - 4R1(new)	24	1.6	0	2.4	-0.8	1	0

R3(old) =	100	2	4	5	0	0	1
R1(new) =	12	0.6	1	0.4	0.2	0	0
4×R1(new) =	48	2.4	4	1.6	0.8	0	0
R3(new)=R3(old) - 4R1(new)	52	-0.4	0	3.4	-0.8	0	1

Iteration-2		Cj	5	10	8	0	0	0
B	CB	XB	x1	x2	x3	S1	S2	S3	MinRatio XBx3
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(old) =	24	1.6	0	2.4	-0.8	1	0
R2(new)=R2(old)÷2.4	10	0.6667	0	1	-0.3333	0.4167	0

R1(old) =	12	0.6	1	0.4	0.2	0	0
R2(new) =	10	0.6667	0	1	-0.3333	0.4167	0
0.4×R2(new) =	4	0.2667	0	0.4	-0.1333	0.1667	0
R1(new)=R1(old) - 0.4R2(new)	8	0.3333	1	0	0.3333	-0.1667	0

R3(old) =	52	-0.4	0	3.4	-0.8	0	1
R2(new) =	10	0.6667	0	1	-0.3333	0.4167	0
3.4×R2(new) =	34	2.2667	0	3.4	-1.1333	1.4167	0
R3(new)=R3(old) - 3.4R2(new)	18	-2.6667	0	0	0.3333	-1.4167	1

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

Hence, the optimal solution has arrived with the value of variables as :
x1=0,x2=8,x3=10

Max Z=160