Question

Use the simplex algorithm to solve the following LP

??? ?=4?1 +4?2
?.?.
?1−2?2 ≤3

2?1 + ?2 ≤ 5
5?1 + ?2 >= 7
?1, ?2 ≥ 0

Answer 1

The given problem has to be converted to canonical form by including Slack, Surplus and Artificial variables as required:

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 subtract Surplus variable S3 and add Artificial variable A1

After including Slack, Surplus and Artificial variables:

Max Z = 4x1 + 4x2 + 0S1 + 0S2 + 0S3 – M A1

s.t.

x1 – 2 x2 + S1 =3

2x1 + x2 + S2 = 5

5x1 + x2 - S3 + A1 = 7

x1, x2, x3, S1, S2, S3, A1 >= 0

Iteration No. 1		Cj	4	4	0	0	0	-M
B	CB	XB	x1	x2	S1	S2	S3	A1	Minimum Ratio= XB / X1
S1	0	3	1	-2	1	0	0	0	3/1=3
S2	0	5	2	1	0	1	0	0	5/2=2.5
A1	-M	7	5	1	0	0	-1	1	7/5=1.4
Z= -7M		Zj	-5M	-M	0	0	M	-M
		Zj-Cj	-5M-4	-M-4	0	0	M	0

The negative minimum Zj-Cj is -5M-4, and the column index is 1. Hence, x1 is the entering variable.

The minimum ratio is 1.4 and its row index is 3. Hence, A1 is the departing variable.

So, the pivot element is 5.

R3(new) = R3(old) / 5

R1(new) = R1(old) – R3(new)

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

Iteration No. 2		Cj	4	4	0	0	0
B	CB	XB	x1	x2	S1	S2	S3	Minimum Ratio= XB / X2
S1	0	1.6	0	-2.2	1	0	0.2	-
S2	0	2.2	0	0.6	0	1	0.4	2.2 / 0.6=3.6667
x1	4	1.4	1	0.2	0	0	-0.2	1.4 / 0.2=7
Z=5.6		Zj	4	0.8	0	0	-0.8
		Zj-Cj	0	-3.2	0	0	-0.8

The negative minimum Zj-Cj is -3.2 and the column index is 2. Hence, x2 is the entering variable.

The minimum ratio is 3.6667 and the row index is 2. Hence, S2 is the departing variable.

So, the pivot element is 0.6.

R2(new) = R2(old) / 0.6

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

R3(new) = R3(old) – 0.2 R2(new)

Iteration No.3		Cj	4	4	0	0	0
B	CB	XB	x1	x2	S1	S2	S3	Minimum Ratio
S1	0	9.6667	0	0	1	3.6667	1.6667
x2	4	3.6667	0	1	0	1.6667	0.6667
x1	4	0.6667	1	0	0	-0.3333	-0.3333
Z=17.3333		Zj	4	4	0	5.3333	1.3333
		Zj-Cj	0	0	0	5.3333	1.3333

Since all Zj-Cj >= 0

Hence, optimal solution is arrived with value of variables as follows:

x1=0.6667, x2=3.6667
and, Max Z=17.3333