<<

. 49
( 59 .)



>>

the problem had a solution and there was an extreme point of the constraint
set at which the solution was attained. There is, of course, a third possibility,
224 SIMPLEX METHOD




Figure 6.2.



namely that the feasible set is empty. In the next section we shall show that in
a linear programming problem these are the only possibilities.
The simplex method is applied to problems in canonical form, CLP (see
Section 4 of Chapter IV for de¬nitions). To put the problem in Example 1.1 in
canonical form we introduce additional slack variables x , x , x and write the

problem as
Minimize f (x) : x 9 2x
 
subject to 9x 9 x ; x : 91,
   (2)
9x ; x ; x : 0,
  
x ; 2x ; x : 4.
  
EXTREME POINTS OF FEASIBLE SET 225


Since the variables x , x , x do not appear in the formula for f, the problem

with feasible set de¬ned by (2) has its minimum attained at

x : , x : x : , x : 0, x : 0.
    
It is readily veri¬ed that this point is an extreme point of the set de¬ned by (2).
We shall leave it to the reader to show that the extreme points of the constraint
set in problem SLP corresponds to the extreme points in the problem CLP
obtained by introducing slack variables.

Exercise 1.1. Solve the following linear programming problem graphically.
Maximize f (x) : x ; 2x subject to
 
x ; x - 5,
 
9x ; x - 1,
 
x 9 x - 0,
 
93x 9 x - 9 1,
 
x . 0, x . 0.
 
Exercise 1.2. Let x be a feasible point for problem SLP and let (x , ) be the
 
corresponding feasible point for the related problem CLP; then

Ax - c, Ax ; I : c,
  
x . 0, . 0.
 
Show that x is an extreme point of the feasible set for problem SLP if and

only if (x , ) is an extreme point for problem CLP.

Exercise 1.3. In problem LPI, which is Minimize 19b, x2 subject to Ax - c,
show that if the feasible set is compact, then the problem has a solution and
there exists an extreme point of the feasible set at which the minimum is
attained.


2. EXTREME POINTS OF FEASIBLE SET

In this section we shall show that if a linear programming problem has a
solution, then there exists an extreme point at which the minimum is attained.
We shall prove this for problems in canonical form without assuming that the
feasible set is compact, as was done in Exercise 1.3. By virtue of Exercise 1.2
this also holds for problem SLP. We shall also give an analytic characterization
of the extreme points of the feasible set for CLP problems. The signi¬cance of
226 SIMPLEX METHOD


these results is that in looking for a solution to a linear programming problem
we can con¬ne ourselves to the extreme points of the feasible set, points for
which we have an analytic characterization. The simplex method is an
algorithm for ef¬ciently determining whether a solution exists and, if so, for
¬nding an extreme point which solves the problem.
We now consider the linear programming problem in canonical form:

Maximize 1b, x2
(1)
subject to Ax : c, x . 0.

In keeping with much of the linear programming literature we have replaced
the objective of minimizing 19b, x2 by the equivalent objective of maximizing
1b, x2. We assume that x and b are in RL, that c is in RK, that A is m ; n, and
that

(i) m : n, (ii) rank A : m. (2)

The rationale for the assumption (2) is precisely the same as given in Remark
V.1.2 for the assumption that the k ; n matrix A de¬ning the af¬ne constraints
in the convex programming problem CPII has rank k and that k : n.
Before presenting the principal results of this section, we emphasize that the
reader should keep in mind that the constraint x . 0 implies that the
components x of x are either positive or zero.
H
T 2.1. A feasible point x is an extreme point of the feasible set if and

only if the columns A of the matrix A that correspond to positive components of
H
x are linearly independent.

Proof. Suppose that the columns A of A that correspond to positive
H
components of x are linearly independent. We shall show that x is an extreme
 
point of the feasible set.
If x were not an extreme point of the feasible set, there would exist two

distinct feasible points x and x and a scalar such that 0 : : 1 and
 
x : x ; (1 9 )x . (3)
  
Let B denote the submatrix of A formed by the columns of A that correspond
to positive components of x and let N denote the submatrix of A formed by
the columns of A corresponding to zero components of x. To simplify notation,
let us assume that B consists of the ¬rst k columns of A and that N consist of
the remaining n 9 k columns. There is no loss of generality in making this
assumption since it can be achieved by a relabeling of the coordinates. Since
the columns of B are linearly independent, it follows from (2) that k - m. It
then further follows from (2) that n 9 k 9 0. For x in RL, let

x : (x , . . . , x ), x : (x , . . . , x ).
 I , I> L
EXTREME POINTS OF FEASIBLE SET 227


Then

x : (x , x ) : (x , 0 )
  , ,
x : (x , x ), i : 1, 2,
G G G,
where x , x , and x are as in (3) and 0 is the zero vector in RL\I.
  ,
Since 9 0 and 1 9 9 0, it follows from (3) that a component of x is

equal to zero if and only if the corresponding components of x and x are
 
zero. Hence x : x : x : 0 and we may write
, , , ,
x : (x , 0 ), i : 0, 1, 2.
G G,
Since x is feasible,

x
c : Ax : (B, N)  : Bx .
 
0
,
Similarly, we get that c : Bx . Hence

B(x 9 x ) : 0. (4)
 
Since x " x and x : x , we have that x 9 x " 0. But this cannot be,
  , ,  
since the columns of B are linearly independent. This contradiction shows that
x is an extreme point.

Now let us suppose that x is an extreme point of the feasible set. To

simplify notation, we suppose that the ¬rst k components of x are positive and

the remaining components are zero. We shall show that the ¬rst k columns
A , . . . , A of A are linearly independent. If these columns were not linearly
 I
independent, there would exist constants , . . . , not all zero such that
 I
A ; % ; A : 0.
 II
Let the n-vector a be de¬ned by

a : ( , . . . , , 0, . . . , 0).
 I
Then for any real ,

I
Aa :  A : 0. (5)
HH
H
For 9 0 and suf¬ciently small the vectors x ; a and x 9 a have their ¬rst
 
k components positive and the remaining n 9 k components equal to zero.
Also

A(x < a) : Ax < Aa : c,
 
228 SIMPLEX METHOD


where the last equality follows from (5) and the feasibility of x . Thus for

suf¬ciently small 9 0 the vectors x ; a and x 9 a are distinct and feasible.
 
But then the relation

x : (x ; a) ; (x 9 a)
  
contradicts the hypothesis that x is an extreme point. Hence the vectors

A , . . . , A are linearly independent.
 I
The following corollary is an immediate consequence of the theorem and
the fact that A has rank m.

C¬¬ 1. An extreme point of the feasible set has at most m positive
components.

C¬¬ 2. T he number of extreme points of the feasible set is less than or
equal to

n n!
: .
m m!(n 9 m)!

Proof. If x is an extreme point of the feasible set, then x has k - m positive
components. These k positive components correspond to k linearly indepen-
dent columns of A. We assert that if x is another extreme point with the same
nonzero components as x, then x : x. To see this, let B denote the submatrix
of A corresponding to the nonzero components of x and x, let x : (x , 0), and
let x : (x  , 0). Then by the argument used to establish (4), we get that
B(x 9 x ) : 0. Since the columns of B are linearly independent, x : x , and
so x : x.
If k : m, then since rank A : m, we can adjoin an additional m 9 k columns
of A to obtain a set of m linearly independent columns associated with x. If
k : m, then this certainly holds. Hence the number of extreme points cannot
exceed the number of ways in which m columns can be selected from among n
columns.

T 2.2. L et the canonical linear programming problem as stated in (1) have
a solution x . T hen there exists an extreme point z of the feasible set that is also

a solution.
Proof. By Theorem 2.1, if the columns of A that correspond to positive
components of x are linearly independent, then x is an extreme point of the
 
feasible set and we let z : x .

Let us now suppose that the columns of A that correspond to the positive
components of x are linearly dependent. To simplify notation, we suppose that

the ¬rst p components of x are positive and that the remaining n 9 p com-

EXTREME POINTS OF FEASIBLE SET 229


ponents are equal to zero. Then the ¬rst p columns of A are linearly dependent
and there exist scalars , . . . , not all zero such that
 N
N
 A : 0. (6)
HH
H
de¬ne a vector z( ) as follows:
For each real number

x9 j : 1, . . . , p,
,
z ( ) : H H (7)

<<

. 49
( 59 .)



>>