: and the updated value of z is not changed. From (4.22) we get that the

updated basic feasible solution is

: ( , , ) : ( , , ) : (1, 0, 3).

G G‚ G

Y

Looking at (1), we see that t* : 0 because : 0. In other words, t* : 0 is a

consequence of the current basic feasible solution being degenerate. In this

example, the updated basic solution is also degenerate. In the next example we

show that a degenerate basic solution need not lead to another degenerate

solution with no increase in the value of z.

Let us now suppose that at the end of Step 2 we arrived at the system

described by

x x x xx z

x 1 1 000 0 1

x 0 92 91 1 0 0 0.

x 0 1 101 0 3

3 91 0 0 91

0 1

The current basic feasible solution ( , , ) : (1, 0, 3) is again degenerate.

The entering variable is again x . Now, however, the ratios used to determine

t* are

G : : 1, G : : 3.

v v v v

TERMINATION AND CYCLING 247

Thus t* : 1 and the leaving variable is x . Since d : 3, : 91, and t* : 1,

O

from (4.20) we get

: 91 ; 3(1) : 2.

Thus the value of z is increased. From (4.22) we calculate the new basic feasible

solution to be

: ( , , ) : ( , , ) : (1, 2, 2),

G G‚ G

Y

which is nondegenerate.

We now consider the general situation. Let be a basic degenerate feasible

. If the corresponding component v of the

solution with zero component

GN N

leaving column v is positive, then t* : 0, the updated basic feasible solution

will be degenerate, and the updated value of the objective function will be

unchanged. This follows from (4.21), (4.22), and (4.20).

The following question now arises: Can there exist a sequence of iterations

I , I ,...,I , j : 0, 1, . . . , p, are

such that the basic feasible solutions

I>H

I I> I>N

:

all degenerate and such that ? If this occurs, then all current values

I>N I

,...,

, of the objective will be equal and the sequence of degenerate

I I> I>N

basic solutions , ,..., will repeat in¬nitely often. Thus, the

I I> I>N

simplex method will not terminate. The phenomenon just described is called

cycling and the simplex method is said to cycle.

The bad news is that cycling can occur. The good news is that cycling

appears to be extremely rare in problems arising in applications, and there are

modi¬cations to the simplex method that prevent cycling.

The following example due Beale [1955] cycles in six iterations.

Example 5.1. Minimize z : 22x 9 93x 9 21x ; 24x subject to

9 4x ; 8x ; 2x ; x 9 9x : 0,

x 9 x 9 x ; x ; x ; x : 0,

x ; x : 1,

x . 0, i : 1, . . . , 7.

G

From the preceding discussion and from Section 4 we have the following:

L 5.1. Phase II of the simplex method does one of the following:

(i) determines an optimal solution in a ¬nite number of steps,

(ii) determines that no solution exists in a ¬nite number of steps, or

(iii) cycles.

248 SIMPLEX METHOD

We shall present a very simple rule for the selection of entering and leaving

variables that makes cycling impossible. This rule is the smallest index rule or

Bland™s rule, named after its originator R. G. Bland [1977]. Other methods for

preventing cycling are the perturbation method and the related lexicographic

ordering rule. For a discussion of these methods see Chvatal [1983], Dantzig

´

[1963], and Gass [1985].

Before stating the smallest index rule, we recall that we pointed out in

Remark 4.3 that the choice of entering variable could be any variable

corresponding to a positive component of d . Also, it is possible to choose any

,

variable x at which t* in (21) of Section 4 is attained.

GP

De¬nition 5.1 (Smallest Index Rule). From among all possible entering

variables, choose the one with smallest index. From among all possible leaving

variables, choose the one with smallest index.

Remark 5.1. According to the smallest index rule, the choice of entering

variable will, in general, be different from the choice of index such that d is a

G

maximum. The choice of leaving variable is the same as that previously used.

T 5.1. If at each iteration of the simplex method the smallest index rule

is used, then cycling will not occur.

Proof. We shall prove the theorem by showing that the use of the smallest

index rule and the assumption of cycling lead to a contradiction. The argument

that we shall give follows the one by Chvatal [1983].

´

Let us assume that cycling occurs and that B , B , . . . , B is a sequence

I I> I>N

of bases corresponding to iterations I , I , . . . , I and such that B :B .

I I> I>N I>N I

Since cycling occurs, all of these bases are degenerate.

Let J denote the set of variables that are basic in some iterations and

nonbasic in others. Let x denote the variable in J with the greatest index. If

R

x is basic in I , then there must exist an iteration I with 0 : i : p such that

R I I>G

x leaves B and is nonbasic at the next iteration. If x is nonbasic in I , then

R I>G R I

there must exist a basis B with 0 : i : p such that x enters B . Since

I>G R I>G

B : B , there exists a basis B with i : j : p such that x leaves B and

I>N I I>H R I>H

is nonbasic at the next iteration. In conclusion, we have shown that there is a

basis B in the sequence B , . . . , B such that x leaves B at the iteration I

I I>N R

corresponding to B and becomes nonbasic in the next basis. Let x denote the

Q

entering variable at the iteration I. Thus, x , B and x is in the next basis. Since

Q Q

cycling occurs, there is basis B* at an iteration I* beyond I and in the sequence

B , B ,...,B , B ,...,B such that x enters the basis at I*. That

I I> I>N I>N> I>N R

is, x is not in B* but is in the succeeding basis.

R

We shall write i + B to mean that x is a basic variable in the basis B and

G

i , B to mean that x is nonbasic. If we denote the elements of the matrix B\N

G

TERMINATION AND CYCLING 249

in relation (4) of Section 4 by v , then we can write (4) and (8) of Section 4 as

GH

x: 9v x, i + B,

G G GH H

HA (2)

z: ; d x .

HH

HA

Since x enters at B, s , B. A solution of (2) is then given by

Q

x : y, y arbitrary,

Q

x : 0, i , B, i " s,

G (3)

x : 9 v y, i + B,

G G GQ

z : ; d y.

Q

For the basis B* equations (4) and (8) in Section 4 become

9 (B*)\N*x * ,

x:

,

1 1

(4)

L

z : * ; d* x ,

HH

H

where d* : 0 for j + B*.

H

The systems (2) and (4) are equivalent; that is, they have the same solution

sets. In particular, (3) is a solution of (4). Since all of the bases from B to B*

are degenerate, the value of the objective function does not change from

iteration to iteration. Hence, * : . Equating the expressions for z in (2) and

(4) and using (3) and * : give

; d y : ; d*y ; d*( 9 v y).

Q GG

Q GQ

GZ

Hence

d 9 d* ; d*v y : d* for all y.

Q G GQ GG

Q

GZ GZ

Since the right-hand side is constant and the left-hand side holds for all y, we

must have

d 9 d* ; d*v : 0. (5)

Q G GQ

Q

GZ

Since x enters B at iteration I, d 9 0. Also, since x is leaving, s " t. Hence

Q Q R

s : t. Since x is not entering at I* and s : t, it follows that d* - 0. For

Q

Q

250 SIMPLEX METHOD

otherwise, by the smallest index rule, x would not be the entering variable at

R

I*. It then follows from (5) that there exists an index r in B such that

d*v : 0. (6)

P PQ

Since d* " 0, the variable x is not in the basis B*. But r + B, so x + J. Hence

P P P

r - t.

It follows from (21) in Section 4 that since x is leaving in B and x is

R Q

entering, v 9 0. Since x is entering at B*, it follows that d* 9 0. Hence

R

RQ R

d*v 9 0. Comparing this with (6) shows that r " t. Hence r : t. Since r : t,

R RQ

since the variable x is not in B*, and since x enters B*, we conclude from the

P R

smallest index rule that d* - 0. From (6) we conclude that d* : 0 and

P P

v 9 0.

PQ

Since x , B*, the basic feasible solution * at B* has component * : 0. Let

P

P

denote the rth component of the basic feasible solution corresponding to

P

the basis B. We assert that : 0. To prove this assertion, we note that because

P

all the bases B . . .B* are degenerate, it follows from (21) of Section 4 that t* : 0

at all the iterations I . . . I*. Hence if 9 0, then x would not leave any of the

P P

bases B . . .B*. This contradicts the fact that x , B*, and this proves the

P

assertion.

Since v 9 0 and : 0, it follows from (21) of Section 4 that x is a

PQ P P