Page 410 - A Course in Linear Algebra with Applications

394 Chapter Ten: Linear Programming

Since U G S, we have AU = B, so that

u' 1A' l + -.. + u' mA! m = B

and
+ • • • + — B,
x 1A 1 x mA rn
since AX = B. Therefore, on subtracting, we find that

K - x'M'i + • • • + K - 4 ) 4 = o.

However A^...,N m are linearly independent, which means
that u[ = x[, ..., u' m = x' m, i.e., U = X, which is a contra-
diction.

The converse of this result is true.

Theorem 10.3.2
An extreme point of the set of feasible solutions of a linear
programming problem in canonical form is a basic feasible so-
lution.

Proof
Let the linear programming problem be

T
maximize: z = C X
, . . . (AX = B
subject to: < x >Q

where A is an m x n matrix of rank m. Let X be an extreme
point of the set of feasible solutions.
Suppose that X has s non-zero entries and label the vari-
ables so that the last s entries of X are non-zero, say

T
.
X = (0 .. Oii ... x' s) .
Let A'j be the column of A which corresponds to the entry x'j.
We will prove that A[,..., A' are linearly independent.