Page 419 - A Course in Linear Algebra with Applications

10.4: The Simplex Algorithm 403

the objective row. The variable for this column, say Xj,
is the entering variable.
4. If all the entries in column j are negative, then there
are no optimal solutions. Stop.
5. Find the row with the smallest non-negative 9-value
of Xj. If this corresponds to Xi, then X, is the departing
variable.
6. Pivot about the (i, ) entry, i.e., apply row operations
j
to the tableau to obtain 1 as the (i, j) entry, with all other
entries in column j equal to 0.

7. Replace Xi by Xj in the tableau obtained in step 6.
This is the new tableau. Return to Step 2.

Example 10.4.1

maximize: z = 8xi + 9x2 + 5x

x\ + x 2 + 2^3 < 2
2JCI + 3x 2 + 4x 3 < 3
subject to:
3xi + 3x2 + £3 < 4
> 0
xi,x 2 ,x 3
Convert the problem to canonical form by introducing
slack variables X4,X5,X6:

maximize: z = 8x1 + 9x2 + 5x3

Xi + x 2 + 2x 3 + x 4 = 2
2xi + 3x 2 + 4x 3 + x 5 = 3
subject to:
3x x + 3x2 + x s + x e = 4
Xj > 0,

The initial basic feasible solution is X\ = X2 = x 3 = 0,
= 2, X5 = 3, XQ = 4, with basic variables x 4 ,X5,x 6 . The
x 4
initial tableau is: