Page 78 - 35Linear Algebra

78 The Simplex Method

Precisely because we chose the second row to perform our row operations, all entries
in the last column remain positive. This allows us to continue the algorithm.
We now repeat the above procedure: There is a −1 in the first column of the last
row. We want to zero it out while adding as little to f as possible. This is achieved
by adding twice the first row to the last row:

1 0 − 1 0 0 2 c 1 − c 2 = 2
 
1
2 2 2

 1 2 3 2 0 6  c 2 = 6

0 7 6 0 1 16 f = 16 − 7y − 6z .
The Dantzig algorithm terminates if all the coefficients in the last row (save perhaps
for the last entry which encodes the value of the objective) are positive. To see why
we are done, lets write out what our row operations have done in terms of the function
f and the constraints (c 1 , c 2 ). First we have

f = 16 − 7y − 6z

with both y and z positive. Hence to maximize f we should choose y = 0 = z. In
which case we obtain our optimum value

f = 16 .

Finally, we check that the constraints can be solved with y = 0 = z and positive
(x, w). Indeed, they can by taking x = 4, w = 1.

3.4 Pablo Meets Dantzig

Oftentimes, it takes a few tricks to bring a given problem into the standard
form of example 39. In Pablo’s case, this goes as follows.

Example 42 Pablo’s variables x and y do not obey x i ≥ 0. Therefore define new
variables
x 1 = x − 5 , x 2 = y − 7 .
The conditions on the fruit 15 ≤ x + y ≤ 25 are inequalities,

x 1 + x 2 ≥ 3 , x 1 + x 2 ≤ 13 ,
so are not of the form Mx = v. To achieve this we introduce two new positive
variables x 3 ≥ 0, x 4 ≥ 4 and write

c 1 := x 1 + x 2 − x 3 = 3 , c 2 := x 1 + x 2 + x 4 = 13 .

78