1
Set up a tableau and read it
Build it from standard form; read the current basic feasible solution, the basis and the objective value off it without solving anything.
Course · Operations Research
The Simplex Method
“Systems and Matrices” declined the simplex algorithm by name. This is it. Each step is a Gauss–Jordan pivot, the entering variable is chosen by a rate and the leaving one by a ratio that keeps every variable non-negative, and the method stops on the licence “Convexity, and Why a Local Optimum Is Global” gave it. Everything is exact, which is what makes the two famous pathologies — a tableau that returns to itself after six pivots, and a cube that forces 2ⁿ - 1 of them — reproducible on your screen rather than described in a footnote.
tableau = [A | b] of standard form, plus a z-row z - cᵀx = 0
pivot = one Gauss-Jordan step on a column, z-row included
enter a column whose reduced cost improves z (a rate)
leave min b_i / a_ij over a_ij > 0 (the step length)
Δz = rate × step
stop no improving reduced cost ⟹ optimal, by the convexity licence
every tableau on the path = B⁻¹[A | b]
What this course is about
- Subject
- Operations Research
- Lessons
- 9
- Format
- Interactive
Overview
What you will be able to do
By the end you can run the method by hand on a small problem, choose both variables for the right reasons, start from a problem that gives you no obvious basis, name what a tableau is telling you when it refuses to finish, and write any tableau as a product involving the original data.
2
Choose both variables and pivot exactly
Entering by reduced cost, leaving by the ratio test, the pivot as a Gauss–Jordan step with the objective row included — and a stated reason for stopping.
3
Manufacture a start, or prove there is none
Artificial variables and a first-phase objective; a first-phase optimum of zero hands a basis to the second phase, and a positive one is a proof of infeasibility with the value as the certificate.
4
Diagnose the three awkward tableaux
An improving column with no positive entry, a zero reduced cost on a nonbasic variable at optimality, and a tie in the ratio test — each recognised from the tableau and each answered.
5
Write the tableau as a matrix product
Extract B, invert it, and reproduce the body and the objective row as B⁻¹[A | b] and c_BᵀB⁻¹[A | b] - [c | 0] — the identity “Duality and Sensitivity Analysis” reads the dual solution out of.
6
Say honestly how fast the method is
Finite by a smallest-index rule, exponential in the worst case on a constructed example, and fast in practice — three statements that are each true and none of which implies another.
Lessons
9 lessons
The idea first, in two variables where the walk can still be seen; then the three mechanical pieces — the tableau, the ratio test, the reduced cost — one lesson each, because each is separately a place readers go wrong; then starting, then the three diagnoses, then the matrix view that makes the next course possible, and last the honest account of speed.
Adjacent Corners and the Simplex IdeaTrace a simplex path corner by corner, naming the basis at each and the single variable exchanged between them.Not marked
The Simplex TableauBuild the initial tableau from standard form, read its basic feasible solution off it, and carry out one named pivot exactly.Not marked
The Ratio TestCompute every ratio with its reason, choose the leaving row, and show which basic variable goes negative under any other choice.Not marked
Reduced Costs and the Optimality TestRead the reduced costs off a tableau, choose an entering column, and state the stopping condition and what licences it.Not marked
Artificial Variables and Two-Phase SimplexSet up and run a first phase on a mixed-constraint programme, and either hand a basis to the second phase or certify infeasibility.Not marked
Unbounded and Alternative Optima in the TableauDiagnose an unbounded objective and a non-unique optimum from the tableau, and produce either the ray or the second corner.Not marked
Degeneracy, Cycling and Bland's RuleIdentify a degenerate tableau, reproduce a cycle that returns to its own starting tableau, and break it with a smallest-index rule.Not marked
The Tableau as a Matrix ProductExtract the basis matrix from a tableau, invert it, and rebuild the tableau body and objective row by multiplication.Not marked
Termination and the Klee-Minty CubeCount the pivots on a deformed cube under two rules, and say what the worst case does and does not imply.Not marked
Recommended background
The whole of Linear Programming Models, and from the Algebra path Gaussian Elimination, Matrices and Row Operations, Matrix Products, Inverse Matrices and Systems in Three Variables. Still nothing from Discrete Mathematics: “Termination and the Klee–Minty Cube” borrows three words from P, NP and NP-Completeness and says so in a note, which is a citation and not a prerequisite.
Practice suggestions
Pivot by hand at least twice before letting the lab do it. The lab traces every row operation for exactly this purpose, and a reader who has never carried an objective row through a pivot will drop it later under pressure.
Whenever you make a choice, make the other one too. Both the ratio-test and the entering-rule labs let you override the correct choice, and the point of each is the wreckage that follows — a negative basic variable, or an extra twenty pivots.
After each pivot, read the basic feasible solution off the tableau and locate it on the region. In two variables you can always do this, and it is the habit that makes four variables survivable.
Treat the exactness as load-bearing, not as tidiness. Beale’s example returns to its starting tableau entry for entry; in floating point it would return to something that merely looks like it, and the lesson would be a story.
What it does not cover
Interior-point methods. They need limits, they are floating-point by nature, and they cannot be made exact — which would teach the opposite of this library’s promise. Their existence is named in “Termination and the Klee–Minty Cube” and nothing more.
The revised simplex method as a separate algorithm. “The Tableau as a Matrix Product” gives the identity it is built on; the data structures that exploit it are an implementation subject.
Bounded-variable simplex, and upper bounds handled implicitly. Bounds here are ordinary constraints with ordinary slacks.
Floating-point stability, conditioning and pivot-size heuristics. Nothing on this path floats, so none of it applies; the trade-off that makes those heuristics necessary is worth a sentence and gets one.
Anticycling by perturbation or the lexicographic rule. Bland’s rule is enough to prove termination and is the one a reader can execute.