In 1977 R.G. Bland proposed the pivoting rule
of the least index.
When Bland's rule is adopted,
then the simplex method is guaranteed not to cycle.

- When more non-basic variables are candidates for entering the basis
(positive reduced cost),
then we choose among them the variable of smallest index.
- When more basic variables are candidates for leaving the basis (hence degeneracy will result, since even the ones among them which will remain basic will have value in the basic solution associated to the next dictionary), then we choose among them the variable of smallest index.

Note that Bland's rule uniquely specifies
both the entering and the leaving variable
(contrary to what happens with the anti-degenerative
methods like the perturbation method or the lexicographic method,
where only the exiting variable is decided by the method
and we are left free choice on the entering variable).
In fact, this drawback delayed (at least in a first time)
its adoption.

Here follows a formal proof of the following result.

Moreover, the objective function takes
the same value in the basic solutions associated
to and .
Therefore, last row of dictionary
can be written as:

where whenever is basic for . Since this last equation has been obtained from the equations describing through pivoting operations, it must admit any solution which is admitted from . In particular, it must be satisfied by the following choice of values:

Therefore, , which, after simple rewriting becomes:

Since the second term of this equation is a constant independent from we can conclude that . Moreover, since is entering in . Furthermore since and nevertheless and not is the variable entering in . We therefore conclude that

Since , the variable is not basic for and is hence fickle. However since : since enters for , then ; since exits for , then . Therefore, and since does not enter in in the place of , we can conclude that can not be positive. Therefore

Since all iterations in the cycle are degenerate, to and precisely the same solution is associated. And all fickle variables are set to zero in this solution. In particular , which is non-basic for , will have zero value also in the solution associated to and therefore . But then was a candidate to leave the basis in . This is at odds with the least index rule, since we preferred to .

2001-12-07 |
© Dipartimento di Matematica - Università di Trento |