Page 407 - A Course in Linear Algebra with Applications

10.3: Basic Solutions and Extreme Points 391

7. Let S be a convex subset of R n and let T be a linear
n
operator on R . Define T(S) to be {T(X) \ X e S}. Prove
that T(S) is convex.

8. Suppose that X\ and Xi are distinct feasible solutions
of a linear programming problem in standard form. If the
objective function has the same values at X\ and X2, prove
that this is the value of the objective function at any point on
the line segment joining X\ and X<i-

10.3 Basic Solutions and Extreme Points

We have seen in 10.2 that the extreme points for a linear
programming problem are the key to obtaining an optimal
solution. In this section we describe a method for finding the
extreme points which is the basis of the Simplex Algorithm.
Consider a linear programming problem in canonical form
- remember that any problem can be put in this form:

maximize: z = C X

AX = B
subject to:
X>0

Suppose that the problem has n variables xi,..., x n and
rn constraints, which means that A is an m x n matrix, while
n m
X,C ER a n d B 6 R
The linear system AX = B must be consistent if there is
to be any chance of a feasible solution, so we assume this to be
the case; thus the matrix A and the augmented matrix (A | B)
have the same rank r. Hence the linear system AX = B is
equivalent to a system whose augmented matrix has rank r,
with its final m — r rows zero. These rows correspond to
constraints of the form 0 = 0, which are negligible. Therefore