A simplex pivot changes the basis. It need not change the feasible point. This distinction is easy to overlook when every example has a positive ratio-test step: the objective then improves at every pivot, so returning to an old basis is impossible. At a degenerate point, however, a basic variable can leave at value zero. The objective stays unchanged even though the entering reduced cost is positive.
The earlier simplex notes proved termination for a lexicographic perturbation. Bland's rule offers a different remedy: retain the original problem and consistently use the smallest variable indices. The rule is short; its proof explains why the entering and leaving choices must cooperate. We will prove that cooperation directly rather than borrowing a strict-improvement argument that fails at zero steps.
A basis, its point, and its direction
Consider the finite-dimensional standard-form problem
where has row rank . Assume a feasible initial basis has already been found. Fix the labels once, including labels for slack or other model variables. Those labels will never change with tableau row order.
Definition 15.1.1
(Dictionary indexed by variable labels)
A basis is a set of column indices for which the basis matrix is nonsingular. Order its columns consistently, and let be its complementary index set. Solving the equations gives
Here , , , and . A row indexed by means the row whose basic variable is . Setting gives the basic point; the basis is feasible when every .
Several bases may give the same point, because a zero coordinate can be basic in one dictionary and nonbasic in another. The basis records which columns we solve for; the point records the values of all variables. A feasible basis is degenerate if at least one basic value is zero; its point then has fewer than positive coordinates. A cycle is a nonempty sequence of pivots that returns to the same basis.
Suppose has . Increasing from zero while holding the other nonbasic variables at zero follows the direction defined by
It satisfies and . The ratio test permits the step
If no exists, all basic components of are nonnegative; is feasible for every and its objective tends to infinity. Otherwise the minimum is attained, and replacing a minimizing basic column by gives another nonsingular feasible basis. Indeed, in basis coordinates the replacement matrix has determinant equal, up to column-order sign, to . The objective increase is , which can vanish only when .
Definition 15.1.2
(The two choices in Bland's rule)
At every feasible dictionary:
- If all nonbasic reduced costs satisfy , stop at an optimum. Otherwise let be the smallest index with .
- If the entering column has no positive dictionary coefficient, stop with the improving ray above. Otherwise apply the ratio test and let the smallest basic-variable index among its minimizers leave.
Use exact signs and exact comparisons. Choosing the first printed row among tied ratio-test minimizers is equivalent only when it contains the smallest basic-variable label among those minimizers.
The optimality stopping test follows from the dictionary itself. Every feasible point has nonnegative nonbasic coordinates, so when all . The current basic point attains . Zero reduced costs may allow other optima, but the rule need not pivot through them to certify the maximum.
A cost identity that survives a change of basis
The proof will inspect one direction using two different dictionaries. Their individual reduced costs may look unrelated, so we first identify the quantity they calculate.
Proposition 15.1.3
(Reduced costs evaluate every null-space direction)
For any basis , with nonbasic set and reduced costs , and any vector satisfying ,
The vector need not be a feasible forward direction from this basis's basic point.
Proof
(Eliminating the basic coordinates)
The homogeneous constraint gives , hence . Substituting into the objective dot product gives
This is an algebraic identity. At a zero-step pivot the entering direction may immediately violate a zero basic coordinate for every positive step; that does not prevent us using the identity.
The finite termination theorem
Theorem 15.1.4
(Bland pivots cannot repeat a basis)
Assume finitely many variables, full row rank, a feasible initial basis, exact arithmetic, fixed variable labels, and both choices in Bland's rule. Primal simplex never repeats a basis. It therefore terminates after finitely many pivots, either with an optimal basic feasible point or with an improving feasible ray certifying unboundedness above.
Proof
(A largest changing index gives a sign contradiction)
Suppose a basis repeats. Restrict attention to the nonempty finite sequence from one occurrence to the next, including the return pivot. We derive a contradiction in four steps.
1. Every pivot in this sequence has step zero. Each entering reduced cost is strictly positive, and every ratio-test step is nonnegative. Objective values therefore never decrease. A basis determines its basic point and objective uniquely; returning to it returns to the same value. The sum of the nonnegative changes must be zero. Each is consequently zero, so every dictionary in this sequence represents one common point .
Call a variable changing for this sequence if it is basic in some dictionaries and nonbasic in others. Every entering and leaving variable is changing. Moreover, every changing variable has , because it is nonbasic somewhere and the point never changes.
2. Choose the largest changing index. Let be the largest such index. Choose a dictionary immediately before leaves, and let enter at this pivot. Both variables are changing, and , so . Let be this pivot's direction. In particular,
Read the restricted sequence as a closed cycle starting at , wrapping past its originally listed end if necessary. Because it returns to its starting basis, must reenter after its departure. Let be the dictionary immediately before such a reentry; write its nonbasic set as and reduced costs as . Bland's entering choice implies
3. Determine the relevant signs of the old direction . If and , its membership never changes, by maximality of . Thus was also nonbasic in . Since , the direction definition gives .
Now take with . If was nonbasic in , then is zero or, when , one. In either case . If was basic in , it is a changing variable, hence . Were , we would have , making its ratio . The leaving variable also has ratio zero. Thus would be a tied ratio-test minimizer with smaller index than , contradicting the leaving choice in . We conclude that
4. Evaluate the same cost change in . Since , the preceding identity gives
For each term is nonpositive. For each term is zero. The term with is strictly negative, because and . Hence , contradicting its strictly positive value in .
No basis can repeat. There are at most column sets of size , so there are finitely many eligible bases. Every nonterminal iteration performs a well-defined feasible pivot. The algorithm must therefore reach one of its two stopping conditions. Their certificates were established above.
Proof X-ray
Where each hypothesis enters
Strictly positive entering reduced costs force all pivots of a supposed cycle to have zero step. Fixed labels let us select one largest changing variable. The entering choice controls the signs of smaller-index reduced costs at its reentry. The leaving choice controls the signs of the old direction at its departure. The cost identity then makes those sign statements incompatible. Finitely many bases become useful only after this contradiction excludes repetition.
No rationality assumption was used: the theorem concerns exact real comparisons. It also does not assert a polynomial pivot bound. The coarse count can grow exponentially with problem size. An anti-cycling rule addresses logical termination; the practical speed of a pivot strategy is a separate question.
Worked example: two zero pivots, then progress
Worked example 15.1.5
(The point can stay fixed while the useful basis changes)
Maximize subject to
Add slacks in that order. The initial dictionary and objective are
The basis is and the point is . Only has positive reduced cost. Its ratios are for basic labels , respectively. Bland selects label from the zero tie, so enters and leaves with step zero. Solving for gives
Now enters. The decreasing basic variables are and , whose ratios are zero and one. Thus leaves at another zero step. The next dictionary is
Worked example 15.1.6
(Leaving the degenerate point and certifying optimality)
Continue from the third dictionary of the previous example. The three bases so far all represent . Now enters with reduced cost one. Both and increase; only limits the step, at one. Pivoting out gives
The nonbasic variables are , with reduced costs zero and minus one. The solution is with value one. Independently, the constraint proves that this value is optimal. Increasing while produces further optima with ; a zero reduced cost is consistent with stopping.
| Basis before the decision | Enter | Leave | Step | Objective after pivot |
|---|---|---|---|---|
| 1 | 3 | |||
| 2 | 4 | |||
| 3 | 5 |
The first two pivots did not improve the point, but they did not revisit a basis either. The termination theorem allows precisely this behavior.
Counterexample mode
A zero step does not certify optimality
At the initial point in this example the first allowed step is zero, yet the feasible point has larger objective. Declaring an optimum after a zero step would return the wrong answer. Conversely, a zero reduced cost is not an eligible Bland entry: eligibility requires strict positivity. Merely choosing the smallest label without checking that sign would abandon the objective monotonicity used in the proof.
The other stopping condition, an improving ray, arises when the entering column has no positive dictionary coefficient.
Worked example 15.1.7
(Termination with an improving ray)
Maximize subject to and . With slack the initial dictionary is
Bland enters , the only variable with positive reduced cost. Its single ratio is , so leaves with step one:
Now and , so enters. Its coefficient in the only row is , which is not positive, so the ratio test has no candidates and the rule stops. The direction has , and , that is, . It satisfies , so the points are feasible for every , with objective . The problem is unbounded above, and this ray is the certificate.
Common points of confusion
Common mistake
(A smallest leaving label alone does not prevent cycling)
A small leaving label alone is insufficient. The earlier six-pivot cycling example already breaks leaving ties by smallest basic-variable index while selecting the largest positive reduced cost for entry. Bland's theorem requires the smallest eligible entering label as well.
Common mistake
(Expecting the rule to supply Phase I or a tolerance policy)
The theorem starts from a feasible basis. It does not provide Phase I or justify applying the primal ratio test to negative basic values. It also does not remove floating-point ambiguity: replacing exact zero by a numerical tolerance changes eligibility and tie sets. A program may need numerical safeguards, but they require their own analysis.
Common mistake
(Reading nonrepetition as a statement about points)
A basis need not be unique at an optimum or at any degenerate point. The theorem excludes a repeated basis along this pivot sequence, rather than excluding repeated points. Relabeling variables once before the run yields another fixed order to which the same proof applies. Relabeling them between pivots does not preserve its hypotheses.
Exercises
Quick check
(In a feasible dictionary, the nonbasic labels are with reduced costs . For the chosen entering column, the basic labels have equal to . Select the Bland pivot. Would the last row limit a positive step?)
Solution · Answer
The smallest positive-cost label is , not . Labels and tie at ratio zero, so label leaves and the step is zero. The coefficient at label is negative, so that basic variable increases as the entering variable increases; it gives no upper limit on the step. Only rows with compete in the minimum; zero or negative coefficients impose no limit.
Quick check
(In the degenerate worked example, after the first pivot, write the full five-coordinate entering direction for . Explain why its objective slope is positive even though no positive forward step is feasible from that dictionary.)
Solution · Answer
With coordinates ordered , the direction is . Since the objective is , . But at the current point and , so any positive step would make negative. The direction gives an algebraic objective slope; the ratio test supplies the separate feasibility restriction .
Quick check
(In the termination proof, why is it valid to set for a nonbasic index in ? Explain why the same claim cannot simply be made for every .)
Solution · Answer
A label larger than is not changing, so its nonbasic membership in implies the same membership in . The only nonzero nonbasic component of the old direction is the entering label . For a smaller label, membership may change; it can be basic in , and its direction component is then determined by a dictionary coefficient. The leaving tie-break, together with its zero basic value, is needed to prove this component nonnegative.
Quick check
(Suppose and the initial feasible basis is fixed. What coarse upper bound on the number of pivots follows from nonrepetition? Does this count prove efficient behavior for arbitrary dimensions?)
Solution · Answer
There are at most basis sets, including the starting basis. Each pivot visits another set, so there can be at most nine pivots before a terminal basis is reached. Singular or infeasible sets can only reduce this count. The corresponding binomial count in general dimensions can be exponential, so it is not a polynomial complexity guarantee.
Quick check
(Change the degenerate worked example's objective to . Apply the Bland stopping test at the initial slack basis. Explain why forcing to enter anyway is outside the theorem, even though its label is smallest.)
Solution · Answer
The initial nonbasic reduced costs are . Neither is positive, so the current point is optimal with value zero, also certified by . Forcing to enter violates strict positive-cost eligibility. The first forced zero step happens not to change the value, but that coincidence does not satisfy the hypothesis used to prove monotonicity and noncycling.