A tie in the ratio test leaves a basic variable at zero, so the next pivot can change the basis without moving the point at all. A sequence of such pivots can return to a basis already visited, and then the method runs for ever: on one four-variable programme the tableau comes back to its starting form after six pivots, entry for entry. Bland's smallest-index rule makes that impossible, and since there are finitely many bases, that is what proves the method terminates.
Core ideas
The hard idea is that a pivot can be perfectly correct and accomplish nothing, and that a run of such pivots is not a stall but a loop.
When two rows achieve the same minimum ratio, the step takes both of their basic variables to zero and only one of them leaves. The other stays in the basis at value zero, which is what degenerate means. Geometrically it is more constraint boundaries through one corner than the corner has dimensions: three lines through one point in two variables.
From a degenerate basis the ratio test can return a step of zero, because the winning row already has a right-hand entry of zero. The pivot is carried out, the basis changes, the objective does not move and neither does the point. Nothing is wrong: the method is walking between two bases that describe the same corner.
If the basis returns to one already visited with the same tableau, the method will make the same choices again and run for ever. That is cycling, it happens on constructed programmes with the most-negative rule, and it is defeated by choosing the entering column and the leaving row by lowest index instead.
The material
Where degeneracy comes from, what it does to a pivot, a programme that returns to its own first tableau, and why a smallest-index rule terminates.
A basic feasible solution is degenerate when some basic variable has value zero. Equivalently, more than n of the constraint boundaries of an n-variable problem pass through the point, so two or more different bases name it. A pivot from a degenerate basis may have step zero.
Take maximise 3x₁ + 9x₂ subject to x₁ + 4x₂ ≤ 8 and x₁ + 2x₂ ≤ 4. Both boundaries pass through (0, 2), and so does the axis x₁ = 0: three lines, one point, two variables. The ratio test on the entering column x₂ gives 8 ÷ 4 = 2 and 4 ÷ 2 = 2, a tie.
Two pivots, one of which moved nothing. The point was (0, 2) after the first pivot and (0, 2) after the second; the objective was 18 both times. What changed was the basis, from {x₂, s₂} to {x₂, x₁}, and the second of those is the one whose objective row certifies optimality. The zero-length pivot was not wasted: it was the step that produced the certificate.
If zero-length pivots can go on for a while, can they go round? They can. The standard example is due to Beale, and it is worth stating in full because the claim about it is exact:
The right-hand sides of the first two rows are zero, so the starting basic feasible solution is already degenerate, and every pivot after that has step zero. Six pivots later the method is exactly where it began, with the same tableau and therefore the same choices ahead of it. Left alone it runs for ever at z = 0, and the true optimum of the programme is 1/20.
That the sixth tableau equals the first is a claim about equality of numbers, and it is the reason this course carries exact fractions. The entries include 1/50 and -1/25; in floating point the sixth tableau would come back nearly equal to the first and the lesson would be a story about what nearly means. The comparison the lab makes has no tolerance in it: four rows by eight columns plus the objective row, entry for entry, and a difference of one millionth in one entry is a difference.
Among the columns with z_j < 0, enter the one with the lowest index. Among the rows achieving the minimum ratio, leave from the one whose basic variable has the lowest index. Neither choice looks at the size of a coefficient.
The simplex method with Bland’s rule, started from a basic feasible solution, reaches an optimal basis or a certificate of unboundedness after finitely many pivots. On the programme above it takes six pivots and stops at 1/20.
There are at most n choose m bases, which is a finite number. Each pivot moves to a different basis, and no basis under Bland’s rule is ever visited twice — that is the rule’s content, and it is a case analysis on the lowest-indexed column that leaves and re-enters, which this course states and does not carry out.
Granting it, termination follows immediately: a walk through a finite set that never repeats a member must stop, and it can only stop where the method stops, which is at an optimal tableau or at a column with no positive entry. Note what this does not claim — nothing about how many of those finitely many bases get visited, which is the subject of “Termination and the Klee–Minty Cube”.
□
On Beale’s programme the two rules agree for four pivots and then part company. Bland’s fifth pivot brings x₁ back in leaving row 3 — a step of 2/125, the first pivot of the run that moves the point at all — and its sixth reaches x = (1/25, 0, 1, 0) with z = 1/20. Six pivots either way: the same count, a different ending, and that contrast is the lesson. Greatest improvement and the largest-index rule both reach 1/20 in two.
It is not rounding, and it is not a symptom of arithmetic trouble. Every number in the cycle above is an exact fraction and the cycle is still there; degeneracy is three constraint boundaries through one corner, which is a geometric fact about the constraints you wrote down. It is also extremely common in practice — any model with redundant rows or coincident boundaries has it — while cycling itself is rare enough that many implementations do not defend against it until a problem turns out to need it.
Interactive
A tie in the ratio test, a pivot that moves nothing, and a tableau that comes back identical
Method
Watch the ratio test, not the objective. A tie is the announcement, and it arrives one pivot before anything looks wrong.
Two rows at the same minimum means the next basis is degenerate whichever row you take. Write down which one you took and which variable is left basic at zero; that variable is the one the next pivot may expel for nothing.
A zero entry on a basic row is the signature of a degenerate basis. It is not an error, and nothing needs correcting — it is the warning that a step of length zero is now possible.
A pivot with step zero leaves the objective exactly where it was. The stopping test is the objective row, never the objective value: keep pivoting while an improving column exists, however long the value has been still.
Compare bases rather than objective values, since the value is constant through a cycle. Under the lowest-index rule for both the entering column and the leaving row, no basis can repeat, so the run terminates.
A basic variable at zero in the final tableau is fine. What it does mean is that the optimal basis is not unique, so anything read off the objective row — the dual values in “Duality and Sensitivity Analysis”, for instance — may depend on which of the tied bases you stopped at.
The right-hand sides of the first two rows are zero, so the run is degenerate from the first tableau onwards and every step has length zero. Follow the basis rather than the objective value, which never changes.
The first four pivots are identical under both rules, which is worth noticing: cycling is not caused by a run of bad choices but by the last one. At the fifth pivot the most-negative rule picks s₁ and the lowest-index rule picks x₁, and that single difference is the difference between a loop and an answer.
The claim that tableau 6 equals tableau 0 is checked, not asserted. The comparison covers the basis, all four rows including the right-hand column, and the objective row, with no tolerance: perturb one entry by a millionth and it reports a difference. In floating point the entries 1/50 and -1/25 are not represented exactly at all, so the sixth tableau would come back almost equal and the exact claim could not be made in either direction. This is the clearest case on the path where exactness is the content rather than the presentation.
For a faded rehearsal, go back to maximise 3x₁ + 9x₂ with x₁ + 4x₂ ≤ 8 and x₁ + 2x₂ ≤ 4 and take the other row on the tie: leave from row 2 at the first pivot instead of row 1. The supplied first move is that the step is 2 either way, so the point is (0, 2) after the first pivot in both runs. Say which variable is left basic at zero this time, whether the second pivot moves the point, and whether the optimum or the number of pivots changes.
You should be able to spot a degenerate basis from the right-hand column, carry out a pivot of length zero and say what it accomplished, follow a cycle by its bases rather than its objective value, state Bland’s rule and the termination argument it supports, and say why the exactness is load-bearing here.
Something to change about this lesson? Write it down, tick it off when it is handled, and export the list when you want to act on it. Kept in this browser only: nothing is sent anywhere, and nobody is notified.
No recommendations yet for this lesson.