Page 80 - 35Linear Algebra

80 The Simplex Method

The first row operation uses the 1 in the top of the first column to zero out the most
negative entry in the last row:

 
1 1 −1 0 1 0 0 3
1 1 0 1 0 1 0 13
 
0 5 −5 −10 15 0 1 −115
 
1 1 1 0 1 0 0 3
0
R =R 2 −R 1
2
∼  0 0 1 1 −1 1 0 10 
0 5 −5 −10 15 0 1 −115
 
1 1 1 0 1 0 0 3
0
R =R 3 +10R 2
3
∼  0 0 1 1 −1 1 0 10  .
0 5 5 0 5 10 1 −15
Now the variables (x 2 , x 3 , x 5 , x 6 ) have zero coefficients so must be set to zero to
maximize f. The optimum value is f = −15 so s = −f + 95 = 110 exactly as before.
Finally, to solve the constraints x 1 = 3 and x 4 = 10 so that x = 8 and y = 7 which
also agrees with our previous result.

Clearly, performed by hand, the simplex algorithm was slow and complex
for Pablo’s problem. However, the key point is that it is an algorithm that
can be fed to a computer. For problems with many variables, this method is
much faster than simply checking all vertices as we did in section 3.2.

3.5 Review Problems

1. Maximize f(x, y) = 2x + 3y subject to the constraints

x ≥ 0 , y ≥ 0 , x + 2y ≤ 2 , 2x + y ≤ 2 ,

by

(a) sketching the region in the xy-plane defined by the constraints
and then checking the values of f at its corners; and,
(b) the simplex algorithm (hint: introduce slack variables).

2. Conoil operates two wells (well A and well B) in southern Grease (a
small Mediterranean country). You have been employed to figure out
how many barrels of oil they should pump from each well to maximize

80