Page 422 - A Course in Linear Algebra with Applications

406 Chapter Ten: Linear Programming

The next entering variable is x 2; however all the entries
in the X2-column are negative, which means that x 2 can be in-
creased without limit. Therefore this problem has no optimal
solution.
Geometrically, what happened here is that the set of fea-
sible solutions is the infinite region of the plane lying between
the lines x 1 - x 2 = 2, -2x ± + x 2 = 2, x ± = 0, x 2 = 0. In this
region z = bxi — 4x 2 can take arbitrarily large values.

Degeneracy

Up to this point we have not taken into account the pos-
sibility that the simplex algorithm may fail to terminate: in
fact this could happen.
To see how it might occur, suppose that at some stage
in the simplex algorithm the entering variable has two equal
smallest non-negative 9-values. Then after pivoting one of the
basic variables will have the value zero, a phenomenon called
degeneracy. If in the next tableau the basic variable whose
value was 0 is the departing variable, the objective function
will not increase in value. This raises the possibility that at
some point we might return to this tableau, in which event
the simplex algorithm will run forever.
In practice the simplex algorithm very seldom fails to ter-
minate. In any case there is a simple adjustment to the algo-
rithm which avoids the possibility of non-termination. These
adjustments involve different choices of entering and departing
variables, as indicated below.

(i) To select the entering variable, choose the variable
with a negative entry in the objective row which has the
smallest subscript.
(ii) To select the departing variable choose the basic
variable with smallest non-negative 8-value and smallest
subscript.
This procedure is known as Bland's Rule. It can be shown