Question

Work through the simplex method (in algebraic form) step by step to solve the following problem.

Maximize Z = 4?1 + 3?2 + 6?3,
Subject to
3?1 + ?2 + 3?3 ≤ 30
2?1 + 2?2 + 3?3 ≤ 40
and
?1 ≥ 0, ?2≥ 0, ?3 ≥ 0.

Answer 1

Solution:
Problem is

Max Z = 4 x1 + 3 x2 + 6 x3

subject to

3 x1 + x2 + 2 x3 ≤ 30 2 x1 + 2 x2 + 3 x3 ≤ 40

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

subject to

3 x1 + x2 + 2 x3 + S1 = 30 2 x1 + 2 x2 + 3 x3 + S2 = 40

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

Iteration-1		Cj	4	3	6	0	0
B	CB	XB	x1	x2	x3	S1	S2	MinRatio XB/x3
S1	0	30	3	1	2	1	0	30/2=15
S2	0	40	2	2	(3)	0	1	40/3=13.3333→
Z=0		Zj	0	0	0	0	0
		Zj-Cj	-4	-3	-6↑	0	0

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

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

∴ The pivot element is 3.

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

R2(old) =	40	2	2	3	0	1
R2(new)=R2(old)÷3	13.3333	0.6667	0.6667	1	0	0.3333

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

R1(old) =	30	3	1	2	1	0
R2(new) =	13.3333	0.6667	0.6667	1	0	0.3333
2×R2(new) =	26.6667	1.3333	1.3333	2	0	0.6667
R1(new)=R1(old) - 2R2(new)	3.3333	1.6667	-0.3333	0	1	-0.6667

Iteration-2		Cj	4	3	6	0	0
B	CB	XB	x1	x2	x3	S1	S2	MinRatio
S1	0	3.3333	1.6667	-0.3333	0	1	-0.6667
x3	6	13.3333	0.6667	0.6667	1	0	0.3333
Z=80		Zj	4	4	6	0	2
		Zj-Cj	0	1	0	0	2

Since all Zj-Cj≥0

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

Max Z=80

Please comment if any doubt

Rate me

Thanks