Page 418 - A Course in Linear Algebra with Applications

402 Chapter Ten: Linear Programming

is called a 6-ratio for Xj. Hence the value of Xj cannot be
increased by more than the smallest non-negative #-ratio of
XJ; for otherwise one of the constraints will be violated.
Suppose that the smallest non-negative #-ratio for Xj oc-
curs in the ith row: this is called the pivotal row. One then
applies row operations to the tableau, with the aim of making
the ith entry of column j equal to 1 and all other entries of the
column equal to 0. (This is called pivoting about (i,j) entry).
The choice of i and j guarantees that no negative entries will
appear in the right most column. Replace Xi (the departing
variable) by Xj (the entering variable). Now Xj becomes a
basic variable with value —*-, replacing X{. With this value of
Xj, the value of z will increase by biCj/aij, at least if 6; > 0.
After substituting Xj for Xi in the list of basic variables,
we obtain the second tableau. This is treated in the same way
as the first tableau, and if it is not optimal, one proceeds to a
third tableau. If at some point in the procedure all the entries
of the objective row become non-negative, an optimal solution
has been reached and the algorithm stops.

Summary of the simplex algorithm
Assume that a linear programming problem is given in
standard form
maximize: z = C X
, . . . (AX<B
subject to: < x > Q

where B > 0. Then the following procedure is to be applied.
1. Convert the program to canonical form by introducing
slack variables. With the slack variables as basic
variables, construct the initial tableau.
2. If no negative entries appear in the objective row, the
solution is optimal. Stop.
3. Choose the column with the most negative entry in