Learning outcomes
- Say what basic solution, basic feasible solution (BFS), basis and degenerate BFS mean, and point to each one on a picture of a two-variable region.
- Translate between the two languages in both directions: "the point lies on constraint i" is "sᵢ = 0", and "corner" is "basic feasible solution".
- State the theorem that a BFS is exactly an extreme point, and reconstruct why it is true.
- Count the maximum number of basic solutions, C(n, m), and explain why total enumeration is hopeless.
- Derive — not merely quote — the optimality criterion (the zⱼ − cⱼ row) and the feasibility criterion (the minimum-ratio test), both from a single equation.
- Run the simplex algorithm on a small tableau, explain why it terminates, and say exactly where degeneracy breaks that argument.
Start here
L03 told you the best point sits at a corner, and in two dimensions you can simply look at the picture and read the corners off. In thirty dimensions there is no picture to look at. So the simplex method has to replace looking with bookkeeping, and everything below follows from how it does that.
Start with the question the method has to answer: what is special about a corner, said in words a machine can check? Look at the two-variable picture again. A corner is a place where two boundary lines cross — the point sits on two constraints instead of comfortably inside them. Now recall what adding a slack variable did in L02. It turned the inequality 6x₁ + 4x₂ ≤ 24 into the equation 6x₁ + 4x₂ + s₁ = 24, where s₁ is the amount of that resource left unused. Sitting exactly on that constraint means using the resource up entirely, and using it up entirely means s₁ = 0. Sitting on the axis x₁ = 0 means, just as directly, that the variable x₁ is zero.
So "two lines cross here" and "two of the variables are zero" are the same sentence in two languages. That is the whole bridge from L03 to this lesson. A corner becomes a choice of which variables are allowed to be non-zero, and stepping to a neighbouring corner becomes swap one variable out, swap one in.
Which one to bring in, and which to throw out? Bring in the variable that pays most per unit; throw out whichever one is driven down to zero first as you push. Repeat until no incoming variable pays. That last stopping rule only checks the corners next door, so it looks far too weak to prove anything — but because the feasible region is convex, "no neighbour is better" really does force "no corner anywhere is better". Section 5 derives the two rules and Problem 5 justifies the stopping.
1. From geometry to algebra
L03 established that an optimum, if it exists, occurs at a corner of the feasible region. That is a satisfying result and a useless algorithm, because in n dimensions you cannot draw the region and there is no obvious way to list its corners. The achievement of the simplex method is to describe corners algebraically and then to move between them systematically, uphill, one at a time. This section builds that description; it is the hinge the rest of the lesson turns on.
1.1 A corner is a pattern of zeros
Take the example from L03 — maximise Z = 5x₁ + 4x₂ subject to 6x₁ + 4x₂ ≤ 24, x₁ + 2x₂ ≤ 6, x₁, x₂ ≥ 0 — and add a slack to each inequality as in L02:
Two equations cannot pin down four unknowns. The solutions form a whole two-dimensional sheet, so to isolate a single point you must impose n − m = 2 extra conditions, and the simplex method always imposes them in the same cheap way: force two of the four variables to be zero. What remains is two equations in two unknowns, which normally has exactly one solution.
Setting a variable to zero is not an arbitrary manoeuvre. Each of the four variables owns one boundary line of the picture you drew in L03, and setting it to zero is the instruction "stand on that line".
| Set to zero | Geometric instruction |
|---|---|
| x₁ = 0 | stand on the vertical axis |
| x₂ = 0 | stand on the horizontal axis |
| s₁ = 0 | consume all 24 units of resource 1: stand on the line 6x₁ + 4x₂ = 24 |
| s₂ = 0 | consume all 6 units of resource 2: stand on the line x₁ + 2x₂ = 6 |
Choosing which two variables to zero out is therefore choosing which two of those lines to stand on, and the point the equations then hand back is where those two lines cross. That is precisely what you did by hand in L03 — you simply did it with a ruler instead of with algebra. The zeroed variables will be called non-basic; the remaining two, free to take whatever values the equations force on them, will be called basic. Section 2 makes both words precise.
One caution before the formal definitions. Crossing lines are not always corners of the region: two constraint lines can meet at a point that lies outside the feasible set entirely. Algebra catches those without any picture, because one of the remaining variables comes out negative — a resource used more than fully. Section 3 shows two such points for this very example.
Step the picture below forward and watch two things at once: the point moves from corner to corner, and the set of variables allowed to be non-zero — printed in braces at each step — changes by exactly one member.
The walk begins at {s₁, s₂}, which is the origin: both slacks are non-zero because nothing has been produced and nothing consumed, and both decision variables sit at zero. That starting corner comes free whenever every constraint is ≤ with a non-negative right-hand side, which is why §6 has to treat other constraint types separately. Two pivots later the walk stops at (3, 1.5), having never touched (0, 3). Skipping corners is typical, and it is why simplex is fast.
2. Basic solutions, bases and degeneracy
Now the same story in general. Work in standard form: A x⃗ = b⃗ with x⃗ ≥ 0, where A is m × n with m < n and rank(A) = m. Slacks have already been added, which is why n exceeds m, and rank(A) = m says no equation is a redundant copy of the others. The system is underdetermined — m equations in n unknowns — so it has infinitely many solutions. Zeroing n − m variables, as in §1.1, cuts that infinity down to a finite list of candidate points.
Choose m of the n variables to be basic; set the remaining n − m non-basic variables to zero. If the resulting m × m submatrix B — the basis matrix, whose columns are the columns of A belonging to the basic variables — is non-singular, solve B x⃗_B = b⃗, so that x⃗_B = B⁻¹ b⃗. The resulting x⃗ is a basic solution.
A basic solution in which x⃗_B ≥ 0⃗, that is, one in which no basic variable came out negative.
A BFS in which at least one basic variable equals zero. It is still a perfectly legal BFS — the point is in the region and the basis is non-singular — but note the oddity: more than n − m variables are now at zero, so the point is standing on more lines than it strictly needs. The trouble that causes is discussed in §6.1.
Basis names the chosen set of m variables, and interchangeably the matrix B they form. Two bases are adjacent when they differ in exactly one member. Adjacency in the algebra is adjacency in the geometry, and it is worth seeing why: two bases differing in one member agree on the other n − m − 1 variables they hold at zero, so both points lie on those same n − m − 1 boundary surfaces, and the set of all points lying on them is a one-dimensional edge of the region. Swapping a single basic variable therefore slides you along one edge from one endpoint to the other. That single move is the only move simplex ever makes.
2.1 How many basic solutions are there?
The number of ways to choose which m of the n variables are basic is the binomial coefficient
| m | n | C(n, m) |
|---|---|---|
| 2 | 4 | 6 |
| 3 | 6 | 20 |
| 5 | 10 | 252 |
| 10 | 20 | 184 756 |
| 20 | 40 | 1.4 × 10¹¹ |
| 50 | 100 | 1.0 × 10²⁹ |
Read C(n, m) as an upper bound on the number of corners, not as the number itself, and for three separate reasons. A choice of m columns can be linearly dependent, making B singular, so it defines no point at all. Many choices that do define a point define an infeasible one, sitting outside the region — you will meet two of them in §3. And a degenerate corner is described by several different bases at once, so distinct choices can name the identical point. The true count of corners is smaller than the table says. It is still hopeless.
Total enumeration is hopeless. At 10⁹ solutions per second the m = 50, n = 100 case would take 3 × 10¹² years. Yet problems of that size are solved in milliseconds.
3. The central theorem
The theorem uses the term extreme point, so fix its meaning first, because the proof leans on the exact wording. A point of the feasible region is an extreme point if it is not the midpoint of any two other points of the region. Said as an experiment: stand at the point, take a small step in some direction and then the same small step in the exactly opposite direction; if you can find a direction where both steps stay inside the region, the point is not extreme.
In two dimensions that test picks out precisely the corners. From an interior point every direction has a usable opposite. From a point partway along an edge you can slide either way along the edge. But from a corner, every direction that keeps you inside has an opposite that takes you straight out. Extreme point is therefore the honest general definition of the word "corner" — one that still works in thirty dimensions, where "corner" has no picture to point at.
x⃗ is a basic feasible solution of A x⃗ = b⃗, x⃗ ≥ 0 if and only if x⃗ is an extreme point of the feasible region.
Proof sketch (⟸): every extreme point is a BFS. Argue by contradiction. Let x⃗ be an extreme point, and let x_{j₁}, …, x_{j_k} be its strictly positive components. Suppose the corresponding columns a⃗_{j₁}, …, a⃗_{j_k} of A were linearly dependent. Follow that supposition in four steps.
- Dependence means some coefficients, not all zero, combine those columns to give 0⃗. Collect the coefficients into a vector d⃗ that is zero in every other position. Then A d⃗ = 0⃗ by construction.
- Because A d⃗ = 0⃗, we get A(x⃗ ± ε d⃗) = A x⃗ ± ε · 0⃗ = b⃗ for every ε. The equations survive the perturbation in both directions.
- Non-negativity survives too, provided ε is small enough. The reason d⃗ was built to be zero outside the positive components is exactly this: components of x⃗ that are already zero are not moved at all, and components that are strictly positive can absorb a small enough nudge either way without crossing zero.
- So x⃗ + ε d⃗ and x⃗ − ε d⃗ are two distinct feasible points, and x⃗ is their midpoint. By the definition above, x⃗ is not an extreme point — a contradiction.
Hence the columns are independent. Independent columns in an m-row matrix number at most m, so k ≤ m; and since rank(A) = m there are enough further independent columns to pad the set out to exactly m. Those m columns form a non-singular B, the variables outside them are all zero, and x⃗ ≥ 0⃗ by assumption. That is the definition of a basic feasible solution. ∎
The picture plots all six basic solutions of the two-equation, four-variable system from §1.1 — one for each way of choosing two variables to zero out. Four come out non-negative, and those four are exactly the corners of the shaded region. The other two are honest crossings of two boundary lines, and so are honest basic solutions, but they lie outside the region and the algebra says so by handing back a negative slack. Problem 1 computes all six by hand.
4. The tableau and the zⱼ row
Everything the algorithm needs at a given basis fits into one array, the simplex tableau: the constraint coefficients already transformed by B⁻¹, the current values of the basic variables in the RHS column, and one extra row carrying the objective information. Write c_B for the objective coefficients of the basic variables, in the order those variables appear.
4.1 What a tableau row is actually saying
Before reading the array, be clear about what one of its rows asserts, because every formula in the rest of the lesson is read straight off it. Multiply A x⃗ = b⃗ through by B⁻¹. The m columns belonging to the basic variables become the columns of the identity matrix — that is what B⁻¹B = I means — so row i of the transformed system contains a single 1, sitting under its own basic variable:
Rearranged to put the basic variable on its own:
Read that as an exchange rate, and two facts follow at once. First, every non-basic variable currently sits at zero, so the sum vanishes and x_Bᵢ = bᵢ — which is why the RHS column can simply be read off as the current solution, with no further work. Second, and this is the part to remember: aᵢⱼ is the price row i charges for xⱼ. Raise the non-basic xⱼ by one unit and the basic variable in row i must fall by exactly aᵢⱼ to keep the equation true. Both criteria in §5 are consequences of that single line, and nothing beyond it is needed.
Laid out as a grid, with one row per equation and one column per variable, that is the tableau:
| Basis | c_B | x₁ | ⋯ | xₙ | RHS |
|---|---|---|---|---|---|
| x_B₁ | c_B₁ | a₁₁ | ⋯ | a₁ₙ | b₁ |
| ⋮ | |||||
| x_Bₘ | c_Bₘ | aₘ₁ | ⋯ | aₘₙ | bₘ |
| zⱼ − cⱼ | Z |
zⱼ = ∑ᵢ c_Bᵢ aᵢⱼ = c_Bᵀ B⁻¹ a⃗ⱼ, the inner product of the objective coefficients of the basic variables with column j of the transformed tableau.
Δⱼ = zⱼ − cⱼ. The bottom row of the tableau holds these numbers, one per column, and the current objective value Z in the RHS position.
4.2 Deriving what zⱼ − cⱼ means
The definition above tells you how to compute zⱼ but not why anyone would want it. Here is where it comes from. Take a non-basic variable xⱼ, currently zero, and push it up by exactly one unit while every other non-basic variable stays at zero. Two things happen at once, and §4.1 supplies both.
- You gain cⱼ directly. That is simply what one unit of xⱼ is worth in the objective — it is the definition of cⱼ.
- You lose zⱼ indirectly. The equations must keep holding, so by x_Bᵢ = bᵢ − aᵢⱼ xⱼ each basic variable falls by aᵢⱼ. Basic variable i is worth c_Bᵢ per unit, so row i gives back c_Bᵢ aᵢⱼ of objective, and adding up the rows gives back ∑ᵢ c_Bᵢ aᵢⱼ in total — which is exactly zⱼ.
So zⱼ is not a mysterious inner product. It is the replacement cost of one unit of xⱼ: the objective value you have to hand back from the basic variables in order to make room for it. The net effect is the difference between the two:
Two sanity checks that this is the right quantity. If xⱼ is already basic, its column is a column of the identity, so zⱼ equals the c_B of the row holding it, which is cⱼ itself, giving Δⱼ = 0: a variable already in the basis offers nothing new, exactly as it should. And if aᵢⱼ happens to be negative in some row, that row's basic variable rises instead of falling, and the term c_Bᵢ aᵢⱼ enters as a negative cost — that is, as extra gain. The one formula covers both cases without a special rule.
The sign convention trips everyone up once. The tableau row stores zⱼ − cⱼ, the rate at which Z worsens per unit, so a negative entry is the good news for a maximisation. There is a second reading of the same number: in a slack column, zⱼ − cⱼ is the shadow price of that resource — what one more unit of it would be worth in extra profit. Problem 2 computes one and interprets it; duality theory later turns that reading into a full theory.
5. The two criteria and the pivot
5.1 Optimality criterion, for maximisation
The criterion now writes itself. Every move available from the current corner consists of raising one non-basic variable, and §4.2 priced each such move at cⱼ − zⱼ per unit. If not a single move pays, there is nothing to do:
Why a test this local is allowed to stop the search. All the criterion literally says is that no neighbouring corner is better; on its own that would be a very weak claim, since a better corner could sit somewhere else entirely. Convexity is what upgrades it. In a convex region a corner that beats all of its neighbours beats every point of the region, so a check on the adjacent columns certifies a global optimum. Problem 5 spells that argument out, and it is worth reading before you trust the algorithm, because it is the single step that makes simplex legitimate rather than merely plausible.
Entering variable, by Dantzig's rule. Choose j* = argminⱼ (zⱼ − cⱼ), the most negative reduced cost, since it promises the steepest improvement per unit brought in. Basic columns always have Δⱼ = 0, as §4.2 showed, so they can never win the minimum and the rule is effectively a choice among the non-basic columns. For a minimisation, either negate the objective and maximise, or reverse the test: optimal when all zⱼ − cⱼ ≤ 0, and enter the most positive.
5.2 Feasibility criterion: the minimum-ratio test
The entering variable has been chosen; call it x_{j*}. Every unit of it is worth −Δ_{j*} > 0, so we want it as large as we can get it. The only thing that can stop us is feasibility, and §4.1 says exactly how. Raise x_{j*} to a value t, leave the other non-basic variables at zero, and row i reduces to a single term:
So row i demands bᵢ − aᵢⱼ* t ≥ 0. When aᵢⱼ* > 0 you may divide by it without flipping the inequality, and the demand becomes a ceiling on t:
Every such row hands you one ceiling and all of them must hold at the same time, so the largest legal t is the smallest of the ceilings. That, and nothing more mysterious, is the minimum-ratio test:
Now notice what has happened at t = θ, because this is the step most readers skip. The row r that achieved the minimum satisfies b_r ⁄ a_rⱼ* = θ, so its basic variable becomes b_r − a_rⱼ* θ = 0 exactly. A variable sitting at zero is a non-basic variable, so x_Br steps out of the basis and x_{j*} takes its place at the value θ. The ratio test does not merely bound the step; it also names the swap, and it names only one. Push a single unit further and that variable goes negative, which is why θ is the precise stopping distance rather than a cautious estimate.
Three consequences drop out immediately, and between them they are the whole of the algorithm's error handling.
- Rows with aᵢⱼ* ≤ 0 are skipped. In such a row, raising x_{j*} makes x_Bᵢ = bᵢ − aᵢⱼ* t larger, not smaller, so that row never threatens to go negative and imposes no ceiling at all. Dividing by a non-positive aᵢⱼ* would also flip or destroy the inequality, so the resulting "ratio" would mean nothing.
- If no aᵢⱼ* > 0 exists anywhere in the column, the problem is unbounded. With no ceilings, no value of t is illegal; x_{j*} grows forever and, since it pays −Δ_{j*} > 0 per unit, Z grows with it. Problem 3 works an instance.
- A tie implies degeneracy at the next iteration. Only one of the tied rows can leave. The other stays basic, but its ratio was also θ, so by the same calculation its variable is likewise driven to exactly zero — a basic variable at zero, which is the definition of a degenerate BFS.
5.3 The pivot operation
Pivoting is Gauss–Jordan elimination on the entering column, arranged so that column becomes a unit vector with its 1 in the leaving row. This is not a new idea so much as a bookkeeping obligation: §4.1 showed that the tableau is only readable when the basic columns form the identity, and after the swap x_{j*} is basic and must therefore be made to look like one. Afterwards the RHS column again shows the values of the basic variables directly, and the reduced costs can be recomputed from it.
6. The algorithm, termination and degeneracy
Assembled, the pieces give the algorithm in eight lines, and every one of them has now been derived rather than asserted. When every constraint is ≤ with bᵢ ≥ 0, the slacks form a ready-made starting basis at the origin — set the decision variables to zero and each slack simply equals its own bᵢ ≥ 0, so the basic solution is feasible without any work. That is why the walk in §1 begins at (0, 0). Problems with ≥ or = constraints have no such free starting corner and need an artificial start, handled in L06.
Why it terminates. The argument has three parts and each is worth checking separately. First, every iteration moves to an adjacent BFS whose objective value is strictly better, because the entering variable pays −Δ_{j*} > 0 per unit and enters at the value θ > 0. Second, no basis can ever be revisited: the objective values are strictly increasing, so a repeat would mean a value both greater than and equal to itself. Third, §2.1 counted the bases and found finitely many. A strictly increasing walk over a finite set must run out of places to go, and the only way this walk stops is by the optimality test — so it stops at an optimum.
6.1 The degeneracy caveat
The soft spot is the phrase "enters at the value θ > 0". At a degenerate BFS some basic variable already sits at zero, so its ratio bᵢ ⁄ aᵢⱼ* is 0 ⁄ aᵢⱼ* = 0, and if that row has a positive entry the minimum is θ = 0. The entering variable then enters at zero. The pivot changes the basis without changing the solution or the objective, so the second leg of the termination argument collapses: values no longer strictly increase, and a basis can be revisited. The algorithm stalls, shuffling different descriptions of one geometric corner, and if the shuffle ever returns to a basis already visited it will repeat that loop forever. That is cycling.
| Rule | Statement | Cost |
|---|---|---|
| Bland's rule | Among eligible entering columns take the smallest index; among tied leaving rows take the variable with the smallest index. | Provably terminates, but often needs many more pivots. |
| Lexicographic (perturbation) rule | Perturb bᵢ → bᵢ + εⁱ, which makes every ratio distinct so no tie can occur. | Provably terminates, more bookkeeping. |
In practice cycling is vanishingly rare — floating-point noise breaks exact ties by itself — so commercial solvers run Dantzig's rule, watch for the objective failing to improve over many iterations, and fall back to Bland's rule only when stalling is detected.
6.2 Complexity: theory against practice
| Measure | Result |
|---|---|
| Worst case | Exponential — the Klee–Minty cube (1972) forces 2ⁿ − 1 iterations |
| Average case | O(m) to O(m log n) pivots (Borgwardt, Smale; smoothed analysis by Spielman and Teng, 2004) |
| Practical rule of thumb | 2m to 3m iterations |
| Guaranteed polynomial alternatives | Ellipsoid (Khachiyan 1979, impractical); interior point (Karmarkar 1984, practical) |
7. Solved problems
m = 2, n = 4, so there are C(4, 2) = 6 ways to choose the basis and hence at most 6 basic solutions. Take each pair of variables as the basis, set the other two to zero, and solve. By §1.1, each choice of the two zeroed variables is a choice of which two boundary lines to stand on, so this enumeration is the algebraic version of listing every crossing of two lines in the L03 picture.
x₁ = x₂ = 0 gives s₁ = 24, s₂ = 6, at the point (0, 0). Both non-negative: feasible.
x₂ = s₁ = 0 gives 6x₁ = 24 so x₁ = 4, and 4 + s₂ = 6 so s₂ = 2. Point (4, 0): feasible.
x₁ = s₁ = 0 gives 4x₂ = 24 so x₂ = 6, and 12 + s₂ = 6 so s₂ = −6. Point (0, 6) is a genuine basic solution but infeasible.
x₂ = s₂ = 0 gives x₁ = 6, and 36 + s₁ = 24 so s₁ = −12. Point (6, 0): infeasible.
x₁ = s₂ = 0 gives 2x₂ = 6 so x₂ = 3, and 12 + s₁ = 24 so s₁ = 12. Point (0, 3): feasible.
s₁ = s₂ = 0, so solve 6x₁ + 4x₂ = 24 with x₁ + 2x₂ = 6: x₁ = 3, x₂ = 1.5. Feasible.
| Basis | (x₁, x₂) | Feasible? | Z = 5x₁ + 4x₂ |
|---|---|---|---|
| {s₁, s₂} | (0, 0) | ✓ | 0 |
| {x₁, s₂} | (4, 0) | ✓ | 20 |
| {x₂, s₁} | (0, 3) | ✓ | 12 |
| {x₁, x₂} | (3, 1.5) | ✓ | 21 |
| {x₂, s₂} | (0, 6) | ✗ | — |
| {x₁, s₁} | (6, 0) | ✗ | — |
The four feasible ones are exactly the four corners found graphically in L03, confirming the BFS ⟺ extreme-point theorem; the two infeasible ones are intersections of constraint lines lying outside the region.
zⱼ = ∑ᵢ c_Bᵢ aᵢⱼ = 5a₁ⱼ + 0 · a₂ⱼ = 5a₁ⱼ, since the second basic variable is a slack with zero cost.
| j | a₁ⱼ | zⱼ = 5a₁ⱼ | cⱼ | zⱼ − cⱼ |
|---|---|---|---|---|
| x₁ | 1 | 5 | 5 | 0 |
| x₂ | 2/3 | 10/3 | 4 | 10/3 − 4 = −2/3 |
| s₁ | 1/6 | 5/6 | 0 | 5/6 |
| s₂ | 0 | 0 | 0 | 0 |
Z = c_Bᵀ b⃗ = 5(4) + 0(2) = 20.
z₂ − c₂ = −2/3 < 0, so this BFS is not optimal.
Use §4.2 rather than the formula. One unit of x₂ earns c₂ = 4 directly. Row 1 says x₁ = 4 − (2/3)x₂, so that unit forces x₁ down by 2/3, and x₁ is worth 5 each, a loss of (2/3) × 5 = 10/3. Row 2 says s₂ = 2 − (4/3)x₂, so s₂ falls too, but a slack is worth c = 0, so it costs nothing. Net: 4 − 10/3 = 2/3 > 0 per unit, an improvement — and 2/3 is exactly −(z₂ − c₂), as it must be.
z_{s₁} − c_{s₁} = 5/6 is the shadow price of resource 1: an extra unit of it is worth ₹5/6 of profit. Equivalently, forcing a unit of slack back in costs 5/6.
Entering x₂, column (2/3, 4/3). Both entries are positive, so both rows impose a ceiling: row 1 allows x₂ ≤ 4 ÷ (2/3) = 6, row 2 allows x₂ ≤ 2 ÷ (4/3) = 1.5. Both must hold, so θ = min{6, 1.5} = 1.5, achieved in row 2. At x₂ = 1.5 the row-2 variable becomes 2 − (4/3)(1.5) = 0, so s₂ is the one driven to zero and s₂ leaves. Row 1 gives x₁ = 4 − (2/3)(1.5) = 3, so the new point is (3, 1.5) — the graphical optimum of L03, reached by arithmetic alone.
No entry in the pivot column is positive, so there is no row over which to take a minimum.
The basic variables update as x_B₁ = 5 − (−2)x₂ = 5 + 2x₂ and x_B₂ = 8 − (−3)x₂ = 8 + 3x₂. Both increase as x₂ grows, so as x₂ → ∞ both stay ≥ 0 and feasibility is never violated. Since z₂ − c₂ < 0 — that is why x₂ was chosen — Z increases without bound.
The ray is x⃗(t) = x⃗⁽⁰⁾ + t d⃗, where d⃗ carries 1 in the x₂ position and 2 and 3 in the two basic positions.
Report the ray to the modeller. It names exactly which activity can grow without limit, which almost always identifies the missing constraint. If the model claims infinite profit from more of product 2, you forgot product 2's capacity limit.
The minimum θ = 4 is attained in two rows, rows 2 and 3. Either may leave; the ratio test does not decide between them, and any tie-breaking rule is an addition to the algorithm, not part of it.
Suppose row 2 is chosen to leave, so the entering variable enters at θ = 4. Row 3 stays in the basis, and its value updates by the usual rule x_B₃ = b₃ − a₃ⱼ* θ. But row 3 tied, which means precisely that b₃ ⁄ a₃ⱼ* = 4 = θ, so b₃ = 4a₃ⱼ* and
x_B₃ = b₃ − a₃ⱼ* θ = 4a₃ⱼ* − 4a₃ⱼ* = 0.
A tie is not a coincidence that might produce a zero; the tie is the statement that the second row reaches zero at the same instant. Whichever tied row is chosen to leave, the other stays basic at the value zero. The new BFS is degenerate.
Three or more constraints pass through the same corner — in two dimensions, more lines meet at that point than the two needed to fix it. Section 1.1 explains why that produces the zero: standing on three lines means three variables are zero, one more than the n − m the definition asks for, so the extra zero has to appear among the basic variables. It also explains why one corner can then correspond to several different bases: you can pick which two of the three coincident lines to call the defining pair.
At a degenerate vertex the next ratio may be θ = 0, so the pivot changes the basis but not the solution or the objective. If such pivots return to a previously visited basis, the algorithm cycles forever.
Beale (1955): maximise (3/4)x₁ − 150x₂ + (1/50)x₃ − 6x₄ subject to (1/4)x₁ − 60x₂ − (1/25)x₃ + 9x₄ ≤ 0, (1/2)x₁ − 90x₂ − (1/50)x₃ + 3x₄ ≤ 0, x₃ ≤ 1. With Dantzig's rule this cycles after 6 pivots, returning to the starting basis.
Bland's rule and the lexicographic rule both provably terminate (§6.1). Degeneracy is common, especially in transportation and assignment problems, but cycling is essentially never seen on real data, because floating-point noise breaks the exact ties.
C(80, 30) = 80! ⁄ (30! 50!) ≈ 8.87 × 10²¹ basic solutions.
Each candidate needs a 30 × 30 system solved, roughly (2/3)(30)³ ≈ 18 000 floating-point operations.
8.87 × 10²¹ × 1.8 × 10⁴ = 1.6 × 10²⁶ flops. At 10¹² flops per second on a fast workstation, t = 1.6 × 10¹⁴ s ≈ 5 million years.
Empirically simplex needs 2m to 3m pivots, about 2.5 × 30 = 75 iterations. Each pivot is a Gauss–Jordan sweep, O(mn) = 30 × 80 = 2400 operations. Total 75 × 2400 = 1.8 × 10⁵ flops, so t ≈ 0.18 µs.
5 × 10⁶ years divided by 1.8 × 10⁻⁷ s is a factor of about 10²¹. Simplex visits about 75 of 8.9 × 10²¹ corners — a fraction of 10⁻²⁰.
Because of convexity. The criterion zⱼ − cⱼ ≥ 0 is a purely local test: it examines only the corners adjacent to the current one and says nothing directly about the other 8.9 × 10²¹. The gap is closed by the shape of the region. An LP feasible set is an intersection of half-spaces and so is convex, and in a convex set the straight segment from the current corner to any rival corner lies entirely inside the region. If the rival were better, the objective would have to increase somewhere along that segment, and a linear objective increasing along a segment must already be increasing at its start — that is, along one of the edges leaving the current corner. But the test just certified that no leaving edge improves. So no rival can be better, and simplex never needs to look further. Convexity converts a global search into a local one, and that is the whole trick. It is also why the idea fails for integer programming (L16–L18) and for non-convex non-linear programming: without convexity the segment to a better point can leave the region, the argument breaks, and local optimality no longer implies global optimality.
8. Where this theory is used
Refinery blending
Crude streams blended into fuels under octane, sulphur and volume limits. The shadow prices in the zⱼ − cⱼ row tell the planner which specification is costing money.
Airline crew assignment
The LP relaxations inside crew-pairing systems are massively degenerate — exactly where anti-cycling safeguards and stalling detection earn their keep.
Transportation and assignment
Every basic solution is a spanning tree of the supply-demand network, and degeneracy is the norm rather than the exception. The specialised transportation and assignment algorithms are this theory rewritten to exploit that structure.
Production planning at scale
Multi-plant, multi-period plans with tens of thousands of variables are re-solved nightly. The 2m-to-3m pivot rule is what makes that possible.
Sensitivity and re-optimisation
Because the final basis is stored, a changed price or capacity re-optimises in a handful of pivots rather than from scratch — the payoff of representing a corner as a basis.
Inside branch and bound
Integer solvers call simplex thousands of times on slightly modified LPs. Warm-started dual simplex on a stored basis is why modern MIP solvers are usable.
9. Common mistakes
10. Practice problems
- How many basic solutions are there for m = 3, n = 7? [Ans: 35]
- Given c_B = (3, 5) and column a⃗ⱼ = (2, 1)ᵀ with cⱼ = 8, compute zⱼ − cⱼ. [Ans: 11 − 8 = 3]
- The ratios are {8, 3, 12} — which row leaves, and what is θ? [Ans: row 2, θ = 3]
- The pivot column is (−1, 0, −4)ᵀ. What do you conclude? [Ans: unbounded]
- State the optimality criterion for a minimisation problem in simplex form.
- Prove that increasing a non-basic variable changes Z at the rate cⱼ − zⱼ.
- Explain, in two sentences, why convexity lets a local test certify global optimality.
11. Summary
If this has landed, here is what you can now do without looking anything up.
- Turn a corner into algebra. Put the problem in standard form, m equations in n > m variables. Set n − m variables to zero — that is the statement of which boundary lines you are standing on — and solve for the rest. The result is a basic solution, a BFS if it comes out non-negative, and degenerate if a basic variable comes out zero.
- Justify searching only corners. Quote BFS ⟺ extreme point, and reconstruct the midpoint argument behind it. It is what turns an optimisation over infinitely many points into a search over a finite list.
- Show why that list cannot simply be read out. There are at most C(n, m) bases — already 10²⁹ at m = 50, n = 100 — so enumeration is out and a directed walk is the only option left.
- Derive zⱼ − cⱼ instead of quoting it. Start from x_Bᵢ = bᵢ − ∑ⱼ aᵢⱼ xⱼ: one unit of xⱼ earns cⱼ and costs the basic variables zⱼ = ∑ᵢ c_Bᵢ aᵢⱼ. Then state the test — optimal for a maximisation when every zⱼ − cⱼ ≥ 0, entering the most negative by Dantzig's rule — and read the same number in a slack column as a shadow price.
- Derive the minimum-ratio test. Each row with aᵢⱼ* > 0 imposes x_{j*} ≤ bᵢ ⁄ aᵢⱼ*; all the ceilings must hold, so θ is the smallest; and the row achieving it is driven to exactly zero, which is why that variable leaves. No positive entry in the column means unbounded; a tie means the next BFS is degenerate.
- Carry out a pivot. Gauss–Jordan on the entering column until it is a column of the identity, plus one swap in the basis list, at a cost of O(mn) per pivot.
- Argue that the method terminates, and say where the argument fails. Strictly increasing Z over a finite set of bases forces a stop — unless θ = 0 at a degenerate BFS, which permits stalling and, in principle, cycling. Bland's rule and the lexicographic rule repair it, at a price.
- Answer "is it fast?" honestly. Exponential in the worst case (Klee–Minty), 2m to 3m pivots in practice, roughly 10²¹ times faster than enumeration on a 30 × 80 problem — and explain why those two facts are not in conflict.
- Name the one property doing the work. Convexity, which is what entitles a local test to certify a global optimum, and whose absence is why integer and non-convex problems are hard.