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)