<<

. 54
( 59 .)



>>


 : 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

<<

. 54
( 59 .)



>>