Page 408 - A Course in Linear Algebra with Applications

392 Chapter Ten: Linear Programming

there is no loss in supposing that A is an m x n matrix with
rank m; of course now m < n.
Since A has rank m, this matrix has m linearly indepen-
dent columns, say A h, A h,... ,A jm, (j t < j 2 < • • • < j m ) -
Define
A = (Aj 1 Aj 2 ... Aj m),

which is an m x m matrix of rank m, so that (A')~ 1 exists.
The linear system

A (XJ 1 Xj 2 ... Xj m) = B

T
therefore has a unique solution for (XJ X Xj 2 ... Xj m) ,
l
namely {A')- B.
m
n
This solution is in R , not R . To remedy this, define
X = (xi x 2 ... x n) by putting x i = 0 if j ^ j uj 2,.. .,j m.
Then
AX = A{x x x 2 ... x n) T = x jlA jl + x hA h + ••• + x jmA jm
= B.

Therefore X is a solution of AX = B with the property that
all entries of X, except perhaps those in positions i , . . . , j m ,
j
are zero. Such a solution is called a basic solution of the
linear programming problem; if in addition all the
non-negative, it is a basic feasible solution. The called
the basic variables.
The next step is to relate the basic feasible solutions to
the extreme points of a linear programming problem in canon-
ical form.
Theorem 10.3.1
A basic feasible solution of a linear programming problem in
canonical form is an extreme point of the set of feasible solu-
tions.