Question

24. Maximize   

π = 36x₁ + 28x₂ + 32 x₃

Subject to

2x₁ + 2x₂ + 8x₃≤ 3

3x₁ + 2x₂ + 2x₃≤ 4

      x₁, x₂, x₃≥ 0

25. Write down the economic interpretations of the dual of the problem (24).

Answer 1

24 & 25

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 = 36 x1 + 28 x2 + 32 x3 + 0 S1 + 0 S2

subject to

2 x1 + 2 x2 + 8 x3 + S1 = 3 3 x1 + 2 x2 + 2 x3 + S2 = 4

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

Iteration-1		Cj	36	28	32	0	0
B	CB	XB	x1	x2	x3	S1	S2	MinRatio XBx1
S1	0	3	2	2	8	1	0	32=1.5
S2	0	4	(3)	2	2	0	1	43=1.3333→
Z=0		Zj	0	0	0	0	0
		Zj-Cj	-36↑	-28	-32	0	0

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

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

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

R1(old) =	3	2	2	8	1	0
R2(new) =	1.3333	1	0.6667	0.6667	0	0.3333
2×R2(new) =	2.6667	2	1.3333	1.3333	0	0.6667
R1(new)=R1(old) - 2R2(new)	0.3333	0	0.6667	6.6667	1	-0.6667

R2(old) =	4	3	2	2	0	1
R2(new)=R2(old)÷3	1.3333	1	0.6667	0.6667	0	0.3333

Iteration-2		Cj	36	28	32	0	0
B	CB	XB	x1	x2	x3	S1	S2	MinRatio XBx3
S1	0	0.3333	0	0.6667	(6.6667)	1	-0.6667	0.33336.6667=0.05→
x1	36	1.3333	1	0.6667	0.6667	0	0.3333	1.33330.6667=2
Z=48		Zj	36	24	24	0	12
		Zj-Cj	0	-4	-8↑	0	12

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

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

∴ The pivot element is 6.6667.

Entering =x3, Departing =S1, Key Element =6.6667

R1(old) =	0.3333	0	0.6667	6.6667	1	-0.6667
R1(new)=R1(old)÷6.6667	0.05	0	0.1	1	0.15	-0.1

R2(old) =	1.3333	1	0.6667	0.6667	0	0.3333
R1(new) =	0.05	0	0.1	1	0.15	-0.1
0.6667×R1(new) =	0.0333	0	0.0667	0.6667	0.1	-0.0667
R2(new)=R2(old) - 0.6667R1(new)	1.3	1	0.6	0	-0.1	0.4

teration-3		Cj	36	28	32	0	0
B	CB	XB	x1	x2	x3	S1	S2	MinRatio XBx2
x3	32	0.05	0	(0.1)	1	0.15	-0.1	0.050.1=0.5→
x1	36	1.3	1	0.6	0	-0.1	0.4	1.30.6=2.1667
Z=48.4		Zj	36	24.8	32	1.2	11.2
		Zj-Cj	0	-3.2↑	0	1.2	11.2

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

Minimum ratio is 0.5 and its row index is 1. So, the leaving basis variable is x3.

∴ The pivot element is 0.1.

Entering =x2, Departing =x3, Key Element =0.1

R1(old) =	0.05	0	0.1	1	0.15	-0.1
R1(new)=R1(old)÷0.1	0.5	0	1	10	1.5	-1

R2(old) =	1.3	1	0.6	0	-0.1	0.4
R1(new) =	0.5	0	1	10	1.5	-1
0.6×R1(new) =	0.3	0	0.6	6	0.9	-0.6
R2(new)=R2(old) - 0.6R1(new)	1	1	0	-6	-1	1

Iteration-4		Cj	36	28	32	0	0
B	CB	XB	x1	x2	x3	S1	S2	MinRatio
x2	28	0.5	0	1	10	1.5	-1
x1	36	1	1	0	-6	-1	1
Z=50		Zj	36	28	64	6	8
		Zj-Cj	0	0	32	6	8

Since all Zj-Cj≥0

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

Max Z=50