Page 425 - A Course in Linear Algebra with Applications

10.4: The Simplex Algorithm 409

Phase Two
Starting with the basic feasible solution obtained in Phase
One, use the simplex algorithm to find an optimal solution of
(I) or show that none exists.
In conclusion, the Two Phase Method can be applied to
any linear programming problem in canonical form.
Example 10.4.3

maximize: z — 2x\ — 2x2 — 3x 3 + 2x4
( xi + 2x 2 + x 3 + x 4 = 18
subject to: < 3xi + 6x2 + 2x 3 = 24
1 Xi >0
This problem is given in canonical form. The Two Phase
Method will be applied, the first phase being to find a basic
feasible solution. To this end we set up the auxiliary problem:

maximize: z = -y\ — 2/2 — J/3
( Xi + 2x 2 + 2X 3 + Vi = 12
u . , , 1 xi + 2x 2 + x 3 + x 4 + V2 = 18
a b j G C t t 0 :
3x, + 6x 2 + 2x3 + V3 = 24
I Xi,yj > 0

The initial tableau for this problem is:

Xi X2 X3 X 4 Vi 2/2 2/3
yi 1 2 2 0 1 0 0 12
V2 1 2 1 1 0 1 0 18
2/3 3 6 2 0 0 0 1 24
0 0 0 0 - 1 - 1 - 1 - 5 4

Here the initial basic feasible solution is y\ = 12, yi = 18, yz =
24, with z = —54. But notice that the entries in the objective