Page 415 - A Course in Linear Algebra with Applications

10.4: The Simplex Algorithm 3 9 9

10.4 The Simplex Algorithm

We are now in a position to describe the simplex algo-
rithm, which is a practical method for solving linear program-
ming problems, based on the theory developed in the preced-
ing sections. The method starts with a basic feasible solution
and, by changing one basic variable at a time, seeks to find
an optimal solution of the problem. It should be kept in mind
that there are finitely many basic feasible solutions.
Consider a linear programming problem in standard form
with variables x\,X2,... ,x n and m constraints:

T
maximize: z = C X

subject to: <^ x >0

Thus A is an mxn matrix. For the present we will assume
that B > 0, which is likely to be true in many applications:
just what to do if this condition does not hold will be discussed
later.
Convert the program to one in canonical form by intro-
ducing slack variables x n+i,..., x n+rn:

T
maximize: z = C X

J A'X = B
subject to:
1 *>0
where
A' = (A\ l m ) ,

an m x (n + m) matrix. Also I = (ii X2 • • • x n+rn) T and
T
.
C = (ci C2 .. c n 0 .. 0) . Notice that A' has rank m since
.
columns n + l,n + 2,...,n + m are linearly independent.