This unit addresses the parts of the simplex method that a ready-made feasible slack basis concealed in the earlier simplex unit: finding a starting point, maintaining a basis economically, and preventing repeated degenerate pivots.
Motivation
A simplex dictionary is easy to inspect on paper, but updating every entry becomes expensive when the constraint matrix is large. Most entries are only needed when their variable is considered for entry. Revised simplex calculates these quantities from a factorization of the current basis, so the mathematical operation stays the same while the stored information changes.
There is a more basic obstacle. A lower requirement or an equality constraint need not provide a feasible slack basis. Inventing a starting point is not an acceptable repair: an infeasible start invalidates the primal ratio test. Phase I solves a separate optimization problem whose value certifies whether the original constraints can be met.
Finally, a legal pivot need not move the decision point. If a basic variable is already zero, the permitted step can be zero even when the entering reduced cost is positive. A finite number of possible bases proves termination only if a rule prevents returning to a previous basis. We will exhibit an actual six-pivot cycle, then prove why lexicographic perturbation rules it out.
Definitions
Definition 4.1.1
(Revised simplex data)
Write a maximization problem as , , with of full row rank. For a feasible basis , solve
The reduced cost of nonbasic column is . If it is positive, increasing by changes the basic vector to . The leaving row minimizes among .
These are linear solves, not instructions to form an explicit inverse. The transpose solve gives every reduced cost through a column dot product. After selecting the entering column, one additional solve provides its direction. A basis factorization can be updated after replacement; occasional refactorization is a numerical issue beyond the exact-arithmetic proof here.
The revised representation also separates primal and dual information. The basic values test primal feasibility, while the reduced costs test whether the current basis supplies an upper bound. A tiny basic value is not a reduced cost, and a tiny reduced cost is not a violated capacity. In exact arithmetic both signs have precise meanings. In a floating-point implementation, any tolerance must be tied to scaling and independently rechecked before a certificate is reported. The proof below concerns exact pivots; it does not turn an ill-conditioned basis factorization into a numerically reliable one merely by changing the tie-breaking rule.
Once the entering column is chosen, rows with nonpositive direction entries do not limit the step, because their basic values do not decrease. If every direction entry is nonpositive and the reduced cost is strictly positive, there is an improving ray that preserves the equations and nonnegativity; this is not an algorithmic failure to find a leaving variable but a certificate that the objective is unbounded. Conversely, a row with a zero basic value and a positive direction entry forces the step to zero. Keeping these two cases apart explains why degeneracy and unboundedness need entirely different treatment.
Definition 4.1.2
(Phase I problem and artificial variables)
Multiply equality rows by minus one when necessary so that . Add nonnegative artificial variables , one per row, and solve
The artificial identity columns give the feasible initial basis .
For inequalities, first add ordinary slacks or subtract surplus variables, then introduce artificial columns only where needed. Artificial variables have a computational role and are not new decisions in the original model.
Definition 4.1.3
(Degenerate basis and cycling)
A basic feasible solution is degenerate if at least one basic coordinate is zero. A sequence of pivots cycles if it returns to a basis it has already visited.
These concepts differ: a degenerate pivot can be harmless, and several different bases can represent the same point without forming a cycle.
Theorem/proposition
Theorem 4.1.4
(What Phase I certifies)
The original nonnegative equality system is feasible if and only if the Phase I minimum is zero. If the minimum is positive, the original system is infeasible. At a zero minimum, zero-valued artificial basic variables can be removed by zero-step pivots on nonzero structural coefficients or by deleting redundant transformed equations. The resulting structural basis starts Phase II.
Theorem 4.1.5
(Lexicographic perturbation prevents cycling)
Assume exact arithmetic and a feasible initial basis . Replace the right-hand side formally by
where is positive and smaller than every positive real constant. Compare steps by their first nonzero coefficient in ascending powers of . Primal simplex with positive entering reduced cost and this lexicographic ratio test cannot repeat a basis. It terminates at an optimal basis or an improving unbounded ray. Taking constant terms of a terminal optimal basis gives an optimum of the original problem.
This perturbation is tied to the initial basis. Adding the same positive vector directly to an arbitrary right-hand side need not make its initial basic coordinates positive. Nor should a computer replace the formal symbol by an arbitrary small floating-point number and call the result an exact anti-cycling guarantee.
Concept lensGeometric
Perturbation pulls a degenerate vertex apart
At a degenerate vertex more constraint hyperplanes pass through one point than its position requires, so several feasible bases name the same point and a pivot between them has step zero. In the perturbed problem no basic coordinate vanishes, so distinct feasible bases give distinct vertices: the crowded vertex is pulled apart into nearby vertices, each with exactly one basis. Every pivot then travels along a genuine edge of positive formal length, which is the geometric content of strict improvement.
Proof sketch or proof idea
Proof
(Phase I value and the cleanup pivots)
Every feasible Phase I point has . If the original system has a solution, adjoining gives value zero. Conversely, a zero sum of nonnegative artificial coordinates forces every coordinate to vanish, leaving an original feasible point. A positive optimal value therefore excludes original feasibility. Phase I is itself feasible and bounded below, so a finite optimum is attained; finite-dimensional LP attainment is proved in the next unit.
At zero optimum, a basic artificial variable has value zero. In its transformed row, after the other basic variables have been eliminated and all artificial variables are set to zero, pivot on any nonzero nonbasic structural coefficient. The entering value and leaving value are both zero, so the represented feasible point is unchanged even if the pivot coefficient is negative. If no structural coefficient remains, the row is the identity and can be deleted. Repeat until the basis contains only original variables, including ordinary slack or surplus variables. Restore their original objective coefficients and recompute the transpose solve and reduced costs; the auxiliary objective must not survive into Phase II.
Proof
(Formal nondegeneracy gives strict improvement)
For the anti-cycling theorem, the initial perturbed basic vector is , strictly positive in the formal order. At any basis , each basic coordinate has polynomial form given by a row of . It cannot be identically zero: its perturbation coefficients form a row of the invertible matrix .
Thus every feasible perturbed basis is nondegenerate in the ordered field. Ratios from two different rows cannot be identical either: equality would make their rows of proportional, contradicting invertibility. The least positive ratio is unique and positive. Every bounded pivot therefore strictly improves the formal objective. Each basis determines its objective polynomial uniquely, so a previously visited basis cannot return. There are finitely many bases; hence the method terminates or detects an improving ray.
At termination, the reduced costs are nonpositive real numbers, since the perturbation changes only the right-hand side. The constant terms of the basic coordinates are nonnegative: a negative real constant would dominate every perturbation term. They therefore give an original feasible basis with a nonpositive reduced-cost certificate, proving original optimality. An improving ray depends on and the reduced cost, not on the perturbed right-hand side, so it also certifies original unboundedness.
The proof turns a finite search into a terminating one by attaching to each basis a quantity that strictly increases. The dissection below records where each hypothesis enters.
Proof X-ray
Why finite bases alone are not enough
The engine is a quantity that is determined by the basis and strictly increases at every bounded pivot. A strictly increasing sequence taking values in a finite set cannot repeat a value, so no basis can return. Ordinary objective value is determined by the basis but does not strictly increase at a zero step; the six-pivot cycle below is exactly this failure.
The hypotheses enter at separate points. Feasibility of and the factor in the perturbation make the initial vector formally positive. Invertibility of is used twice: no basic coordinate is identically zero, and no two rows give the same ratio, so the leaving row is unique and every step is formally positive. The positive entering reduced cost then converts into a strict formal increase . Exact arithmetic matters because the comparison reads coefficients of ; rounding can erase the first coefficient at which two ratios differ.
The closing move returns to the real problem. The reduced costs never involve , and a negative constant term would dominate every perturbation term, so the constant terms of the final basis give an original feasible point with an optimality certificate.
Worked examples
Worked example 4.1.6
(Phase I finds the starting point and Phase II improves it)
Maximize subject to , , and nonnegativity. Use surplus , slack , and artificial :
Initially , , and . Let enter to reduce ; the limiting ratios are two and four, so leaves. The dictionary becomes
Setting nonbasic to zero gives , hence original feasibility. Delete the artificial column. The restored objective is . Let enter: grows, while falls and reaches zero at step two. Substitution gives
The optimum is with value twelve. The auxiliary objective found feasibility; the original objective selected a better feasible point.
Worked example 4.1.7
(The same Phase II pivot without a full tableau)
After Phase I, order the basic variables as . The original equality columns for give
Solving gives . The reduced costs are and . For the entering surplus column, gives . Only the second row limits the step, so . The old basic coordinates become , with entering and leaving. These small solves reproduce the dictionary pivot exactly.
Worked example 4.1.8
(An exact six-pivot cycle)
Maximize with nonnegative variables and inequalities
Label the ordinary slacks . Choose the largest positive reduced cost for entry, breaking entering ties by smallest variable index; among minimum-ratio ties, let the smallest-index basic variable leave. Exact basis solves produce:
| Current basis, in row order | Enter | Leave | Entering reduced cost | Step |
|---|---|---|---|---|
| 1 | 5 | |||
| 2 | 6 | |||
| 3 | 1 | |||
| 4 | 2 | |||
| 5 | 3 | |||
| 6 | 4 |
The basis returns to , always representing the origin in decision variables and objective zero. Every pivot obeyed the stated ordinary rule. A lexicographic ratio test instead distinguishes the tied zero ratios and prevents this return. Degeneracy is therefore a real obstruction, not merely a roundoff phenomenon.
Common mistakes
Common mistake
(Artificial variables are not decisions)
Artificial variables cannot remain as unrestricted physical decisions in the final model. A positive artificial value measures a failure to meet the original equations, not a permissible violation. A zero-valued artificial variable can still occupy a basis column, so “Phase I value zero” does not by itself complete the cleanup.
The last point is easy to underestimate, so here it is on a concrete system.
Counterexample mode
A zero Phase I value can leave an artificial variable basic
Claim: when the Phase I minimum is zero, the final Phase I basis consists of original variables and can start Phase II at once. Take the redundant system , with and artificial variables :
Let enter. Both ratios equal one; let leave. Substitution gives
The coefficients of are for and for , so no entering variable decreases , and the minimum has been reached. Yet is still basic, with value zero, so the claim is false. The repair is the cleanup in the theorem: with the artificial variables set to zero, the row of reads . It has no structural coefficient and is deleted, leaving the structural basis for the remaining equation .
Common mistake
(Redundant rows versus inconsistent rows)
A redundant row is detected in the transformed system after eliminating other basic variables, not by noticing repeated coefficients informally. If the transformed row becomes with nonzero constant, it is inconsistent rather than redundant. Rank checks and row deletion must preserve this distinction.
Common mistake
(A small leaving index alone does not prevent cycling)
The largest reduced cost rule can cycle, as the table demonstrates. Bland's rule is another exact anti-cycling option: choose the smallest-index eligible entering variable and the smallest-index basic variable among leaving ties. Its proof is different from the lexicographic proof given here. Choosing a small leaving index alone is insufficient, because the cycling example already does that.
Summary
Revised simplex replaces full dictionary updates with basis solves. Phase I obtains or rejects a feasible start, including the cleanup needed before restoring the original objective. Degenerate pivots require an explicit anti-cycling rule; lexicographic perturbation supplies a strictly improving formal quantity and therefore a finite-basis termination proof in exact arithmetic.
Exercises
Quick check
(For , , and , write a Phase I model using one artificial variable and find its minimum.)
Solution · Answer
Use , , and nonnegative , minimizing . The second equation forces , so . Taking attains one. The positive minimum proves original infeasibility.
Quick check
(In the revised example, suppose the objective is . Compute the reduced costs of and at basis and decide which can improve the maximum.)
Solution · Answer
The basic cost is now , so . Hence and . Either is eligible. Entering gives direction and step two, reaching with value four; entering reaches with the same value. This objective has multiple optima.
Quick check
(Compare the formal ratios and . Why can rounding both to zero defeat the intended rule?)
Solution · Answer
Their coefficients first differ at power two, where one is smaller than three, so the first ratio is smaller. They are distinct positive formal quantities. A floating-point threshold that replaces both by zero erases precisely the information used to distinguish leaving rows, and the exact termination proof no longer applies.
Quick check
(Explain what to do with a zero artificial basic row that, after eliminating other basic variables and setting artificials to zero, reads . Contrast this with .)
Solution · Answer
Pivot the artificial variable out using either nonzero structural coefficient. The new entering value is zero, so feasibility is preserved even with a negative pivot coefficient. The row still imposes a structural relation and cannot be deleted. By contrast, imposes no restriction and can be removed as redundant.