R

in contradiction to the smallest index rule.

Remark 5.2. Computational experience indicates that using the smallest sub-

script rule or the lexicographic rule instead of the max d rule considerably

G

increases the time required for the simplex method or the revised simplex

method to ¬nd an optimal solution. Since very few instances of cycling have

been reported, some computer codes do not incorporate any anticycling

routines. Other computer codes introduce an anticycling routine only after a

sequence of speci¬ed length of degenerate bases occurs. The anticycling routine

will then lead to a nondegenerate basis, at which point the use of the largest

coef¬cient rule can be resumed.

Exercise 5.1. Carry out the iterations of the simplex method for Example 5.1

and show that cycling occurs at the sixth iteration. Note: :( , , ) :

(0, 0, 1) is a basic feasible solution.

Exercise 5.2. Solve the problem in Example 5.1 using the simplex method and

Bland™s rule.

PHASE I OF SIMPLEX METHOD 251

6. PHASE I OF SIMPLEX METHOD

As noted in Section 3, phase I of the simplex method either determines a basic

feasible solution or determines that none exists, in which case the problem has

no optimal solution.

We begin with the linear programming problem in standard form (SLP):

Maximize 1b, x2

(1)

subject to Ax - c, x . 0.

Let us ¬rst suppose that the vector c is nonnegative. We then put the problem

in canonical form (CLP) by adjoining a vector of slack variables,

x : (x , . . . , x ), x . 0, i : 1, . . . , m,

1 L> L>K L>G

and write the problem as

Maximize 1b, x2

(2)

x

subject to (A, I) : c, x . 0, x . 0.

1

x

1

Since c . 0, the vector (x, x ) : (0 , c), where 0 is the zero vector in RL, is a

Q L L

basic feasible solution for the problem in (2). We then immediately pass to

phase II with initial basic feasible solution ( , ) : (0 , c).

1 L

If some of the components of c are negative, the vector (0 , c) is still a basic

L

solution of the system of equations in (2), but it is not feasible. We therefore

resort to another device and introduce an auxiliary problem.

Auxiliary Problem

Minimize x subject to

x

(A, I, 9e) x : c

1 (3)

x

x . 0, x . 0, x . 0,

1

where e : (1, . . . , 1) and I is the m ; m identity matrix.

In component form the system in (3) is

L

a x ;x 9x :c , i : 1, . . . , m,

GH H L>G G

H

x . 0, j : 0, 1, . . . , n ; m.

H

252 SIMPLEX METHOD

A vector ( , ) is feasible for relation (2) if and only if ( , , 0) is feasible for

1 1

the auxiliary problem. Therefore, ( , ) is feasible for relation (2) if and only if

1

( , , 0) is optimal for the auxiliary problem.

1

If we write the objective function of the auxiliary problem as ˜˜Maximize

w : 9x ,™™ then the auxiliary problem becomes a linear programming problem

in canonical form to which we can apply phase II of the simplex method,

provided we can get an initial basic feasible solution. A basic solution to the

system (3) is ( , , ) : (0, c, 0). This solution, however, is not feasible since

1

some components of c are negative. We can obtain a basic feasible solution

from this solution by replacing an appropriate basic variable by x . Before we

do this in general, we shall illustrate using Example 4.1.

In solving Example 4.1, we obtained an initial feasible solution from Figure

6.1. We now ignore the ¬gure and write the auxiliary problem in canonical

form: Maximize w : 9x subject to

9x 9x ;x 9 x : 91,

9x ;x ;x 9 x : 0,

(4)

x ; 2x ; x 9 x : 4,

x . 0, i : 0, 1, . . . , 5.

G

The vector ( , , , , , ) : (0, 0, 0, 91, 0, 4) is a basic solution but is

not feasible. The only negative entry on the right-hand side is 91 and occurs

in the ¬rst equation. Therefore, if in the augmented coef¬cient matrix of (4) we

pivot on x in row 1, then the right-hand side of the resulting system should

be positive. Performing the indicated pivot gives

xx x xxxc

1 1 91 0 0 1 1

(5)

0 2 91 1 0 0 1

2 3 91 0 1 0 5

Thus, ( , , , , , ) : (1, 0, 0, 0, 1, 5) is a basic feasible solution. From

(5) we also get that

w : 9x : 91 ; x ; x 9 x . (6)

We can now start phase II for the problem of minimizing (6) subject to the

constraining equations given by (5). We leave this to the reader and return to

the general situation.

We now obtain a system equivalent to (3) and having a basic feasible

solution. Let c denote the most negative component of c. Thus,

N

c : min+c : i : 1, . . . , m,.

N G

PHASE I OF SIMPLEX METHOD 253

If there are more than one such components, choose the one with smallest

index. Next, pivot on x in the pth row of the system (3). The result will be an

equivalent system

x

(A, e , . . . , e , 9e, e , . . . , e , e ) x : c, (7)

N\ N> KN 1

x

where e : (1, . . . , 1) and

c : 9c . 0, c : c 9 c . 0, i : 1, . . . , p 9 1, p ; 1, . . . , m.

N G

N G N

The system (7) in component form is

L

a x 9 x ; x : c , i " p,

GH H G

L>N L>G

H

L

a x 9 x ; x : c .

NH H N

L>N

H

Thus a basic feasible solution to (7) is

: c , : c, i : 1, . . . , p 9 1, p ; 1, . . . , m,

N G

L>G (8)

: 0, i : 1, . . . , n, n ; p,

G

and

L

w : 9x : 9c 9 x ; a x . (9)

N NH H

L>N

H

The basic variables are

x ,...,x ,x ,x ,...,x (10)

.

L>N\ L>N> L>K

L>

We have transformed the auxiliary problem (3) to the following problem.

Maximize w as given in (9) subject to (8) and x . 0, i : 0, 1, . . . , n ; m. For

G

this problem we have determined a basic feasible solution given by (8) with

basic variables given by (10). We can now apply phase II to the problem in

this form. If we incorporate an anticycling subroutine in our implementation

of Phase II, then according to Lemma 5.1, we shall, in a ¬nite number of steps,

determine that the auxiliary problem either has no solution or determine an

optimal solution to the auxiliary problem. If the auxiliary problem has no

solution, then the original linear programming problem (1) has no feasible

solution. For, as we saw, a vector ( , ) is feasible for the original problem if

1

and only if ( , , 0) is optimal for the auxiliary problem.

1

The remaining alternative is that the auxiliary problem has a solution. We

now explore the possibilities for this alternative. The variable x is basic

initially. In applying phase II of the simplex method to the auxiliary problem,

254 SIMPLEX METHOD

we note that our rule for choosing the leaving variable is such that if at some

iteration x is a candidate for leaving the basis, then x will be chosen to be

the leaving variable. If at some iteration I the variable x leaves the basis, then

I

at the iteration I , the variable x will have the value zero. The solution

I>

( , , ) of the constraining equations at I will also be a solution of (3).

1 I>

Hence if : 0, then w : 0 and ( , ) is optimal for relation (1). Thus, if x

1

ever leaves the basis at an iteration I , at the next iteration I , we will have

I I>

a solution to the auxiliary problem and hence a basic feasible solution for

relation (2). We can then begin phase II with this basic feasible solution.

An optimal solution could also conceivably occur under the following

circumstances:

(i) x basic, w : 0, and

(ii) x basic, w " 0.

If (ii) occurs, then the original problem has no feasible solution. We now show

that (i) is impossible. If (i) did occur, then x : 9w : 0. Since the previous

iteration did not end in an optimal solution, x " 0 at the start of the previous

iteration and became zero in the previous iteration. If this happened, then x

was a candidate for leaving the basis but did not do so. This contradicts the

rule for determining whether x leaves the basis.

The next lemma follows from the discussion in this section.

L 6.1. If an anticycling routine is included, then phase I of the simplex

method either determines that no feasible solution exists or determines a basic

feasible solution.

Lemmas 5.1 and 6.1 imply the following.

T 6.1. T he simplex method incorporating an anticycling routine applied

to a linear programming problem determines one of the following in a ¬nite

number of iterations:

(i) No feasible solutions exist.

(ii) T he problem does not have an optimal solution.

(iii) An optimal solution.

Exercise 6.1. Complete the solution of the illustrative example.

Exercise 6.2. Let the linear programming problem be given originally in

canonical form:

Maximize 1b, x2

subject to Ax : c, x . 0.

REVISED SIMPLEX METHOD 255

Show that an appropriate auxiliary problem for phase I is

K

Maximize w : 9 y