Motivation
Suppose an optimization model has already been solved when one workload requirement increases. Its old basis still describes the same columns and prices, but a recomputed basic value may become negative. Restarting from an unrelated basis discards useful information. Dual simplex keeps the price certificate feasible and repairs the decision point instead.
This reverses the earlier primal-simplex invariant. Primal simplex keeps a feasible point while using reduced costs to improve the objective. Dual simplex keeps feasible reduced costs while repairing basic values. A negative basic value is temporarily permitted during the calculation; it is never reported as an implementable decision. The method finishes when both sides are feasible, or constructs a multiplier proving that the revised constraints cannot be satisfied.
A change of costs behaves differently from a change of requirements. Costs do not alter the old point's feasibility, but can invalidate its prices. Choosing an algorithm by the phrase “reoptimization” alone is therefore insufficient. We will derive the invariants first and use them to decide which calculation is justified after each kind of change.
Definitions
Definition 21.1.1
(A dual-feasible minimization dictionary)
Use , with of full row rank. For basis and remaining columns , write
Here , , and . A basis is dual feasible when , equivalently . Primal feasibility additionally requires .
When both inequalities hold, setting nonbasic variables to zero gives a primal point with value , equal to its dual bound, hence optimal.
Even when the current basic point is infeasible, the dual multiplier still bounds the cost of every genuinely primal-feasible point. The lower bound does not require that a feasible point has already been found; it requires only that all multiplier inequalities hold. This explains why information survives during the repair. Conversely, if a cost change makes some reduced cost negative, the lower-bound argument no longer applies, even if every current basic value is positive. Check both sides separately before choosing an algorithm, rather than judging only whether the objective value looks reasonable.
If a basic coordinate , its row is
A nonbasic column can repair this row only when . The basic position is a row position, while the leaving variable has its own original column index. Keeping these labels distinct matters when a basis is reordered. The vector selects the transformed row; multiplying by returns its certificate to the original constraint coordinates. A transformed row number alone is not an original multiplier vector.
For such columns define the dual ratio . This is not the primal step-length ratio: its numerator is a reduced cost, and the chosen row has a negative basic value. Copying the signs of a solved row without first writing the canonical row easily reverses which directions are eligible.
Theorem/proposition
Theorem 21.1.2
(The dual ratio test preserves the certificate)
Choose a row with . If eligible columns exist, take one attaining
Let . Pivot that column into the basis in place of . Its new multiplier is , remains dual feasible, and has value . The entering basic value is .
Theorem 21.1.3
(A failed row gives a Farkas certificate)
If but every nonbasic coefficient , then satisfies and . The primal system is infeasible. This conclusion is independent of its objective coefficients.
The minimum ratio can be zero, producing a dual-degenerate pivot without increasing the bound. Arbitrary choices can then cycle. A strictly positive ratio at every pivot gives finite termination because the dual value strictly increases through finitely many bases. “Finite bases” alone is not a proof; the following theorem supplies a finite exact rule.
Concept lensGeometric
Dual simplex as an edge walk on the dual polyhedron
The dual problem is , and its slacks at the basis multiplier are the reduced costs. A dual-feasible basis is a vertex of this polyhedron at which the constraints of the basic columns are tight. The step moves along an edge: it loosens only the constraint of and changes the objective at rate . A negative basic value is therefore an improving edge, the dual ratio is the distance until a nonbasic constraint becomes tight, and an empty eligible set is an improving ray on which the dual is unbounded.
Theorem 21.1.4
(Lexicographic cost perturbation makes dual simplex finite)
Start from a dual-feasible basis, order its nonbasic indices as , and formally replace by . Run the dual ratio test in the lexicographic order of polynomials in . Then no basis repeats, and after finitely many pivots the method reaches either a basis that is primal–dual optimal for the original problem or a failed row whose Farkas certificate proves the original system infeasible.
Proof sketch or proof idea
Proof
(Reduced costs after the dual ratio step)
For every current nonbasic column , changing the multiplier to gives new reduced cost . Nonnegative row coefficients increase it. Negative row coefficients keep it nonnegative precisely when . The selected ratio makes the entering reduced cost zero. The old leaving basic column has new reduced cost ; all other basic columns stay tight because their inner product with is zero. Thus the new multiplier is dual feasible and tight on the new basis, so it is that basis's multiplier.
The bound changes by . Solving the pivot row with the new nonbasic variables zero gives the positive entering value claimed. Other basic values can still be negative, so this does not yet prove primal feasibility. Recompute the dictionary and repeat until no negative basic value remains.
This does not prove that the number of negative basic values decreases at every step, nor that every basic value moves closer to zero. The first exercise below shows another row becoming negative after one row is repaired. What is genuinely monotone is the dual lower bound, strengthened to strict monotonicity by the formal objective in degenerate cases; taking a false claim that the number of violations must decrease as the progress measure misreads the termination proof.
Proof X-ray
What each hypothesis of the pivot rule secures
The proof checks three things, and each rests on a different hypothesis. The sign condition makes the entering value positive, so the exchange repairs row . The minimum in the ratio keeps every reduced cost nonnegative: only columns with a negative row coefficient can lose, and the smallest ratio is exactly the largest step that all of them can withstand. The leaving column gains reduced cost because has inner product one with it and zero with every other basic column; this is why is exactly the multiplier of the new basis, not merely some dual-feasible vector.
What the argument does not give is primal progress. Other basic values may become more negative, and the bound rises strictly only when . Optimality is concluded only at the end, when every basic value is nonnegative and the equal primal and dual values certify each other. Degenerate steps with are why the perturbation theorem is needed.
Proof
(The failed row is a Farkas certificate)
If no eligible column exists, the displayed row has a nonnegative left side at every nonnegative decision, but a negative right side. In original coordinates, on basic columns and on nonbasic columns. Meanwhile . These are exactly the alternative's certificate inequalities. A zero ratio and an empty eligible set are different events: the former permits a pivot; the latter proves infeasibility.
A finite exact rule for degenerate cases
Proof
(Lexicographic cost perturbation never revisits a basis)
There is a cost-side counterpart of the earlier right-hand-side perturbation. Let be the initial nonbasic indices, ordered as . Keep initial basic costs fixed and formally replace by . Initial reduced costs become , strictly positive in the lexicographic order. Use the dual ratio test in the lexicographically ordered polynomial ring, or its fraction field; choose any negative basic row, with a fixed row-selection rule if a deterministic trace is desired.
For any basis, the map from cost vectors modulo the row space of to its nonbasic reduced-cost vector is an isomorphism. Indeed, zero reduced costs mean precisely that the whole cost vector equals for its basis multiplier; conversely such a row-space cost has zero reduced costs. Both spaces have dimension . Changing the basis therefore transforms initial reduced costs by an invertible linear map.
Consequently each new reduced cost has a nonzero perturbation polynomial: its coefficients form a nonzero row of that invertible map, applied to distinct powers of . Dual feasibility makes it strictly positive in the formal order. Every eligible ratio is therefore positive, so each pivot strictly increases the formal dual objective because the chosen basic value is a negative real number. A basis determines its formal objective uniquely; no basis can recur. Finitely many bases force termination at primal feasibility or a failed-row certificate.
Taking constant terms preserves nonnegative reduced costs. Basic values depend only on the unchanged right-hand side and basis, so a terminal feasible basis is an original primal-dual optimum. A failed-row certificate also uses only that unchanged system. As before, a formal perturbation is not interchangeable with an arbitrary floating-point tolerance; a tolerance would erase the information the proof uses to distinguish zero values.
Worked examples
Worked example 21.1.5
(Two dual pivots build a feasible optimum)
Minimize subject to , , and nonnegativity. With surplus variables, use
The slack basis has , , and . Its reduced costs are nonnegative, though both basic values are negative. Choose the first row. Ratios are three for and two for , so enters:
The second row is still negative. Its eligible ratios are one for and two for , so enters:
Now is feasible and every nonbasic reduced cost is nonnegative. The original equality multiplier is , with bound . Both certificates agree.
Worked example 21.1.6
(A right-hand-side change needs one repairing pivot)
Raise only the first requirement from three to five. The old basis now gives
Reduced costs remain one and one, but is infeasible. In its row, only has a negative canonical coefficient and can enter. Pivoting gives
Thus has minimum ten. Multiplier is feasible for the unchanged costs and has revised bound ten. An old dual multiplier remained a valid lower bound of nine, but lost exactness when its primal basis became infeasible.
Worked example 21.1.7
(A cost change calls for primal repair instead)
Return to requirements three and four, but change the objective to . The old feasible basis gives . Its negative reduced cost on invalidates dual feasibility. Dual simplex cannot start with that broken invariant.
Primal simplex can: increase while keeping . Then and , so leaves at step two. The new dictionary is , , and . Hence is optimal, value three. Multiplier verifies the same lower bound. Changing a cost did not make the old decision infeasible; it made the old optimality test fail.
Worked example 21.1.8
(The failed-row certificate is explicit)
Require and , with nonnegative variables and objective minimize . The slack-start equations are and . Pivoting into the first row gives and .
The negative second row has no eligible negative canonical coefficient. Its original-coordinate certificate is : both decision-column products are zero, slack-column products are one, and . This proves infeasibility rather than merely a failure of the current objective search.
Which invariant survives a perturbation?
For , the old multiplier and reduced costs do not change, while basic values become . For , basic values do not change, while the multiplier becomes and reduced costs become . These formulas give exact basis regions for each kind of reoptimization. If both costs and requirements change, neither feasibility invariant need survive; use a justified feasibility phase before choosing a simplex direction.
Common mistakes
Common mistake
(Reading ratio-test signs from a solved row)
The dual ratio test uses negative row coefficients in the convention . In the right-hand-side example the solved row reads , so has entry for and for . Copying the plus sign on directly into the test would make look eligible and ineligible, reversing the correct choice. Write the canonical equation before taking ratios.
Common mistake
(Treating a negative basic value or a rising bound as a better plan)
A negative basic value is not a negative decision accepted by the model. Nor does an increasing dual bound mean the infeasible basic point has become physically better. It means the lower certificate has strengthened. A genuine primal solution is available only after all basic values pass the sign check.
Common mistake
(Confusing a zero dual step with infeasibility)
A zero dual step is not a certificate of infeasibility. Empty eligibility is the failure that produces the separating row. Degeneracy instead needs a proven anti-cycling policy; a fixed tie-break alone should not be described as sufficient without its proof.
The minimum in the ratio test is not a convenience either, as the next computation shows.
Counterexample mode
Any eligible column will not do
Claim: in the dual ratio test any column with a negative row coefficient may enter. In the first worked example, row one has eligible columns with ratio and with ratio . Entering instead of gives , and . The reduced cost of is , so the new multiplier is not dual feasible, and its value is not a lower bound: the true minimum is . Taking the minimum ratio is exactly what keeps the certificate valid.
Summary
Dual simplex protects the multiplier inequalities and repairs negative basic values. Its ratio test follows directly from reduced-cost changes, and a failed row becomes a Farkas certificate. Right-hand-side changes naturally preserve its starting invariant; cost changes generally preserve the primal invariant instead. Exact formal cost perturbation supplies a finite anti-cycling rule when ordinary dual steps can be zero.
Exercises
Quick check
(In the first example, change the requirements to and . Starting from the slack basis and choosing the first row, perform the dual pivots and find the minimum of .)
Solution · Answer
The first row gives , followed by and . The second pivot enters , giving , , and . Now the negative row allows only to enter, with canonical coefficient minus two and ratio . This gives , , and . The optimum is , value .
Quick check
(At the original final basis, replace the cost of by , keeping the cost of equal to three. Find the exact interval of for which this basis remains optimal.)
Solution · Answer
Substituting and gives constant and reduced costs , . Both are nonnegative exactly when . Basic values remain throughout, so the basis is optimal on this closed interval.
Quick check
(A negative dictionary row has , coefficients , and reduced costs . Find the entering column, dual step, and bound improvement.)
Solution · Answer
Only the first two columns are eligible. Ratios are three and one, so column two enters with . The dual bound increases by . Updated old nonbasic reduced costs are and the leaving variable's reduced cost is one, confirming dual feasibility.
Quick check
(For equations and , construct a Farkas vector proving nonnegative infeasibility. Why does it not depend on the objective?)
Solution · Answer
Take . The decision-column product is zero and both slack-column products are one, so . The right-hand-side product is . These inequalities concern only the feasible system and contradict any nonnegative solution; no cost vector appears.