Page 417 - A Course in Linear Algebra with Applications

10.4: The Simplex Algorithm 401

Entering and departing variables
Consider the initial tableau above. Suppose that all the
entries in the objective row are non-negative. Then Cj < 0
n
and, since z = ^2 CjXj = 0, if we change the value of one of
the non-basic variables x\,... ,x n by making it positive, the
value of z will decrease or remain the same. Therefore the
value of z cannot be increased from 0 and thus the solution is
optimal.
On the other hand, suppose that the objective row con-
tains a negative entry —Cj, so Cj > 0. Since z = C\X\ + • • • +
d 1 < j < n, it may be possible to increase z by in-
creasing Xj; however this must be done in a manner that does
not violate any of the constraints.
Suppose that the most negative entry in the objective
row is — Cj. The question of interest is: by how much can we
increase the value of Xjl Since all other non-basic variables
equal 0, the zth constraint requires that

so that x n+j = bi — ciijXj > 0. Hence

for i = 1,2,..., m. Now if a^- < 0, this imposes no restriction
on Xj since bi > 0. Thus if a^- < 0 for all i, then Xj can be
increased without limit, so there are no optimal solutions.
If aij > 0 for some i, on the other hand, we must ensure
that
bi
0<Xj < — .

The number
h_