Question

Use duality to solve problem 4 4. Minimize z-8x1 + 4x2 + 16x3 subject to 2x1 + 2x2 + 3x3 216 3x1 +x2 t 4xs 2 14 3x +x2 + 5x3 2 12 xi,x2, x320

Answer 1

Min Z = 8 x1 + 4 x2 + 16 x3

subject to

2 x1 + 2 x2 + 3 x3 ≥ 16 3 x1 + x2 + 4 x3 ≥ 14 3 x1 + x2 + 5 x3 ≥ 12

and x1,x2,x3≥0; unrestricted in sign

In order to apply the dual simplex method, convert Min Z to Max Z and all ≥ constraint to ≤ constraint by multiply -1.

Problem is

Max Z = - 8 x1 - 4 x2 - 16 x3

subject to

- 2 x1 - 2 x2 - 3 x3 ≤ -16 - 3 x1 - x2 - 4 x3 ≤ -14 - 3 x1 - x2 - 5 x3 ≤ -12

and x1,x2,x3≥0; unrestricted in sign

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

After introducing slack variables

Max Z = - 8 x1 - 4 x2 - 16 x3 + 0 S1 + 0 S2 + 0 S3

subject to

- 2 x1 - 2 x2 - 3 x3 + S1 = -16 - 3 x1 - x2 - 4 x3 + S2 = -14 - 3 x1 - x2 - 5 x3 + S3 = -12

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

Iteration-1		Cj	-8	-4	-16	0	0	0
B	CB	XB	x1	x2	x3	S1	S2	S3
S1	0	-16	-2	(-2)	-3	1	0	0
S2	0	-14	-3	-1	-4	0	1	0
S3	0	-12	-3	-1	-5	0	0	1
Z=0		Zj	0	0	0	0	0	0
		Zj-Cj	8	4	16	0	0	0
		Ratio=Zj-Cj / S1,j and S1,j<0	-4	-2↑	-5.3333	---	---	---

Minimum negative XB is -16 and its row index is 1. So, the leaving basis variable is S1.

Maximum negative ratio is -2 and its column index is 2. So, the entering variable is x2.

∴ The pivot element is -2.

Entering =x2, Departing =S1, Key Element =-2

R1(new)=R1(old)÷(-2)

R2(new)=R2(old) + R1(new)

R3(new)=R3(old) + R1(new)

Iteration-2		Cj	-8	-4	-16	0	0	0
B	CB	XB	x1	x2	x3	S1	S2	S3
x2	-4	8	1	1	3/2	-1/2	0	0
S2	0	-6	(-2)	0	-5/2	-1/2	1	0
S3	0	-4	-2	0	-7/2	-1/2	0	1
Z=-32		Zj	-4	-4	-6	2	0	0
		Zj-Cj	4	0	10	2	0	0
		Ratio=Zj-Cj / S2,j and S2,j<0	-2↑	---	-4	-4	---	---

Minimum negative XB is -6 and its row index is 2. So, the leaving basis variable is S2.

Maximum negative ratio is -2 and its column index is 1. So, the entering variable is x1.

∴ The pivot element is -2.

Entering =x1, Departing =S2, Key Element =-2

R2(new)=R2(old)÷(-2)

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

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

Iteration-3		Cj	-8	-4	-16	0	0	0
B	CB	XB	x1	x2	x3	S1	S2	S3
x2	-4	5	0	1	1/4	-3/4	1/2	0
x1	-8	3	1	0	5/4	1/4	-1/2	0
S3	0	2	0	0	-1	0	-1	1
Z=-44		Zj	-8	-4	-11	1	2	0
		Zj-Cj	0	0	5	1	2	0
		Ratio	---	---	---	---	---	---

Since all Zj-Cj≥0 and all XBi≥0 thus the current solution is the optimal solution.

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

x2 = 5

x3 = 0

Max Z = -44

∴ Min Z = 44