Question

1. Apply the simplex method to solve the following LP. Use the tableau format. You should show that you know the simplex method, standard forms and optimality criteria. Don't worry about arithmetic and do not do more than 2 iterations. Comment on an optimal solution. maximize subject to 21 + 2x2 – x1 + x2 = 2 —2x1 + x2 <1 x1, x2 > 0

Answer 1

Standard form:

Max Z = 1x1 + 2x2 + 0s1 + 0s2
s.t.
-1x1 + 1x2 + 1s1 = 2
-2x1 + 1x2 + 1s2 = 1
x1, x2, s1, s2 >= 0

Iteration-1		Cj	1	2	0	0
B	CB	XB	x1	x2	S1	S2	Min Ratio XB / x2
S1	0	2	-1	1	1	0	2 / 1=2
S2	0	1	-2	(1)	0	1	1 / 1=1→
Z=0		Zj	0	0	0	0
		Zj-Cj	-1	-2↑	0	0

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

The minimum ratio is 1 and its row index is 2. So, the leaving basic variable is S2.

So, the pivot element is 1.

Entering =x2, Departing =S2, Key Element =1

Row operations:

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

Iteration-2		Cj	1	2	0	0
B	CB	XB	x1	x2	S1	S2	Min Ratio XB / x1
S1	0	1	(1)	0	1	-1	1 / 1=1→
x2	2	1	-2	1	0	1	---
Z=2		Zj	-4	2	0	2
		Zj-Cj	-5↑	0	0	2

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

The minimum ratio is 1 and its row index is 1. So, the leaving basic variable is S1.

So, the pivot element is 1.

Entering =x1, Departing =S1, Key Element =1

Row operations:

• R1(new)=R1(old)
• R2(new)=R2(old) + 2 * R1(new)

Iteration-3		Cj	1	2	0	0
B	CB	XB	x1	x2	S1	S2	Min Ratio XB / S2
x1	1	1	1	0	1	-1	---
x2	2	3	0	1	2	-1	---
Z=7		Zj	1	2	5	-3
		Zj-Cj	0	0	5	-3↑

Variable S2 should enter into the basic but this is becoming impossible for none of the ratio XB / S2 is > 0 for all the S2 column elements are < 0.

So, there exists no feasible solution to this problem.