Page 79 - 35Linear Algebra

3.4 Pablo Meets Dantzig 79

These are called slack variables because they take up the “slack” required to convert
inequality to equality. This pair of equations can now be written as Mx = v,

 
x 1

1 1 −1 0  x 2  3
  = .
1 1 0 1  x 3  13
x 4
Finally, Pablo wants to minimize sugar s = 5x + 10y, but the standard problem
maximizes f. Thus the so-called objective function f = −s + 95 = −5x 1 − 10x 2 .
(Notice that it makes no difference whether we maximize −s or −s + 95, we choose
the latter since it is a linear function of (x 1 , x 2 ).) Now we can build an augmented
matrix whose last row reflects the objective function equation 5x 1 + 10x 2 + f = 0:

 
1 1 −1 0 0 3
1 1 0 1 0 13 .
 
5 10 0 0 1 0
Here it seems that the simplex algorithm already terminates because the last row only
has positive coefficients, so that setting x 1 = 0 = x 2 would be optimal. However, this
does not solve the constraints (for positive values of the slack variables x 3 and x 4 ).
Thus one more (very dirty) trick is needed. We add two more, positive, (so-called)
artificial variables x 5 and x 6 to the problem which we use to shift each constraint

c 1 → c 1 − x 5 , c 2 → c 2 − x 6 .

The idea being that for large positive α, the modified objective function

f − αx 5 − αx 6

is only maximal when the artificial variables vanish so the underlying problem is un-
changed. Lets take α = 10 (our solution will not depend on this choice) so that our
augmented matrix reads

 
1 1 −1 0 1 0 0 3
1 1 0 1 0 1 0 13
 
5 10 0 0 10 10 1 0
 
1 1 −1 0 1 0 0 3
0
R =R 3 −10R 1 −10R 2
3
∼  1 1 0 1 0 1 0 13  .
−15 −10 10 −10 0 0 1 −160
Here we performed one row operation to zero out the coefficients of the artificial
variables. Now we are ready to run the simplex algorithm exactly as in section 3.3.

79