Page 421 - A Course in Linear Algebra with Applications

10.4: The Simplex Algorithm 405

Since there are no negative entries in the objective row,
this tableau is optimal. The optimal solution is therefore x\ =
1, x 2 = §, x 3 = 0, giving z = 11.
The next example shows how the simplex method can
detect a case where there are no optimal solutions.

Example 10.4.2

maximize: z = 5xi — 4x2
£1 — £2 < 2
subject to: 2xi +x 2<2
> 0
xi,x 2
Introduce slack variables X3 and X4 and pass to canonical
form:
maximize: z = 5xi — 4x 2
xi - x 2 + x 3 = 2
subject to: < —2xi + X2 + X4 = 2
Xi,X 2,X3,X 4 > 0
The initial basic feasible solution is xi = 0 = X2, X3 = 2,
X4 = 2, with basic variables X3,X4. The initial tableau is
therefore

*Xi %2 x 3 X4
* * X3 1 -1 1 0 2
X4 -2 1 0 1 2
-5 4 0 0 0

The entering variable is x\ and the departing variable X3.
The second tableau is:

Xi *x 2 X3 X4
Xi 1 -1 1 0 2
X4 0 -1 2 1 6
0 -1 5 0 10