Page 423 - A Course in Linear Algebra with Applications
P. 423
10.4: The Simplex Algorithm 407
that the simplex method, when combined with Bland's Rule,
will always terminate, even if degeneracy occurs.
The Two Phase Method
The reader may have noticed that our version of the sim-
plex algorithm does not work if some constraints have nega-
tive numbers on the right side. We consider briefly how this
situation can be remedied.
Consider a linear program in standard form:
rp
maximize: z = C X
subject to: <^ x >0
where A is m x n. As usual we introduce slack variables
x n +i,..., x n+m to obtain a problem in canonical form:
rp
maximize: z = C X
A'X = B
subject to:
X > 0
where A' = [A | l m]. If some bi is negative, we can multiply
that constraint by —1 to get an entry — bi > 0 on the right
hand side. The problem now is that we do not have a basic
feasible solution — for the obvious solution x n+i = bi is not
feasible. What is called for at this point is a general method
for finding an initial basic feasible solution for any linear pro-
gramming problem in canonical form.
Suppose we have a linear programming problem in canon-
ical form:
rp
maximize: z = C X
subject to: I x >0 ®
where A is m x n. The problem is to find an initial basic
feasible solution. Once this is found, the simplex algorithm
