Page 412 - A Course in Linear Algebra with Applications

396 Chapter Ten: Linear Programming

Theorem 10.3.3
In a linear programming problem there are finitely many ex-
treme points in the set of feasible solutions.
Proof
We assume that the linear programming problem is in canon-
ical form:
T
maximize: z = C X
( AX = B
subject to:
1 A>0

We can further assume here that A is an m x n matrix
with rank m. Let X be an extreme point of S, the set of feasi-
ble solutions. Then X is a basic feasible solution by 10.3.2. In
fact, if the non-zero entries of X are Xj l,..., Xj s, the proof of
the theorem shows that the corresponding columns of A, that
is, Aj 1,..., Aj 3, are linearly independent and thus s < m. In
addition we have

x x
ji An + ^ j sAj s = B.
By 2.2.1 this equation has a unique solution for Xj x,... ,Xj s.
Therefore X is uniquely determined by j±,... ,j s. Now there
n
are at most ( ) choices for ji,. • • ,j s, so the total number of
extreme points is at most ^2™ =0 (") •

The last theorem shows that in order to find an optimal
solution of a linear programming problem in canonical form,
one can determine the finite set of basic feasible solutions and
test the value of the objective function at each one. The sim-
plex algorithm provides a practical method for doing this and
is discussed in the next section.
In conclusion, we present an example of small order which
illustrates how the basic feasible solutions can be determined.