Page 426 - A Course in Linear Algebra with Applications

410 Chapter Ten: Linear Programming

row corresponding to the basic variables are not 0; this is
because z is expressed as —y\ — y 2 — y 3. We need to replace
2/1,2/2,2/3 by expressions in x±, x 2 , x 3, x 4 and thereby eliminate
the offending entries. Note that —y\ = x\ + 2^2 + 2x 3 — 12,
-2/2 = x 1 + 2x 2 + x 3 + x 4 - 18 and y 3 = 3xi + 6x 2 + 2x 3 - 24.
-
Adding these, we obtain

z = -2/i - 2/2 - 2/3 = 5xi + 10£ 2 + 5x 3 + X4 - 54.

The next step is to use this expression to form the new
objective row:

Xi *x 2 Z 3 X4 2/i 2/2 2/3
2/1 1 2 2 0 1 0 0 12
2/2 1 2 1 1 0 1 0 18
* *2/3 3 6 2 0 0 0 1 24
- 5 -10 - 5 - 1 0 0 0 -54

This is the first tableau for the auxiliary problem. The enter-
ing variable is x 2 and the departing variable y 3. The second
tableau is:

X i X2 *x 3 x 4 2/1 2/2 2/3
* * 2 / i 0 0 4/3 0 1 0 - 1 / 3 4
2/2 0 0 1/3 1 0 1 - 1 / 3 10
%2 1/2 1 1/3 0 0 0 1/6 4
0 0 - 5 / 3 - 1 0 0 5/3 -14

The entering variable is x 3 and the departing variable is
y\. The third tableau is:

xi x 2 x 3 *x 4 j/i y 2 2/3
X3 0 0 1 0 3/4 0 -1/4 3
* * 2/2 0 0 0 1 -1/4 0 1/4 9
Xi 1/2 1 0 0 -1/4 0 1/4 3
0 0 0 - 1 5/4 0 5/4 - 9