GHAPTER 10

FINITENESS OF THE SIMPLEX METHOD UNDER PERTURBATION

10-1.   THE POSSIBILITY OF CIRCLING IN THE SIMPLEX ALGORITHM

We have seen that if degeneracy does occur, then it is possible to have a sequence of iterations with no decrease in thè value of z. Under such circumstances, may it not happen that a basic set will be repeated, thereby initiating an endless cirele of such repetitions? If so, can we devise an efficient procedure to prevent such a circling possibility? In thè early days of linear programming this was an unsolved problem.

In 1951, A. J. Hoffman constructed an example, shown in Table 10-1-1, involving three equations and eleven variables. He showed that if one resolved thè ambiguity of choice regarding which variable to drop from thè basic set by selecting the first among them, then the tableau at cycle 9 would by thè same as at cycle 0. It follows in this case that the same basic set would be repeated every nine iterations and thè simplex method would never terminate. This phenomenon is usually referred to as cycling in thè simplex algorithm. We prefer, however, thè term "circling," because we use thè term "cycle" for a single iteration of thè simplex algorithm.
Later, E. M. L. Beale [1955-1] constructed a second example, a version of which is shown in Table 10-1-II, that is remarkable for its simplicity. It also has three equations but only seven variables. Using thè same rule for resolving a tie, thè tableau at cycle 6 is thè same at cycle 0. It is conjectured that this is thè simplest example ; to be precise, it is believed that no other example of circling can be constructed involving fewer variables regardless of thè number of equations.
Since circling in thè simplex algorithm is only possible under degeneracy, it is pertinent to ask how degeneracy can occur, how frequently it is en-countered in practice and how often it implies circling. Degenerate solutions are possible only when thè constants, b_i, of thè originai right-hand side bear a special relation to thè coefficients of thè basic variables. This is clear since thè procèss of reduction to one of thè finite set of canonical forms depends only on thè coefficients and not on thè right-hand side ; thè final values, \bar b_i, are weighted sums of thè originai b_i's where thè weights depend only on thè coefficients. If ali thè b_i's were selected at random, it would be something of a miracle if one or more of thè constants \bar b_i of thè canonical system should vanish.
					[ 228 ]