LP Simplex Lab

I made LP Simplex Lab to study for the final exam of Combinatorics and Algorithm Design (Tsinghua, Master in Advanced Computing). Building it helped me understand what every step of the resolution is for: why we substitute the variables, why the largest λ enters, why the smallest β leaves. The graphical view shows what the simplex is really doing: walking from one corner of the feasible region to a better one.

Explain shows every step of a problem with its calculations. Practice gives you a new exam-style problem to solve yourself, one line at a time. Cheat sheet has the rules on one page.

Problem

Example Size

x constraints

Random problems are exam-style: bounds like x₁ ≤ −2, the last x free.

The solution on the right updates as you edit.

0 · The exam question (Q5)

New variables (all ≥ 0): x ≥ L → x = y + L; x ≤ U → x = U − y (all its coefficients change sign); free x → x = y′ − y″; L ≤ x ≤ U → x = y + L and add the row y ≤ U − L.
Objective: min z → max Z′ = −z. Substitute, collect, keep the constant aside.
Constraints: substitute, move constants to the right; if b < 0 multiply the row by −1; add a slack s_i to each “≤” row.
Tableau T0: the slacks are the basis, C_B = 0, λ_j = c_j.
Two iterations: largest λ enters, smallest β leaves, pivot, new λ row.
Read the solution: basic = P₀, others 0; back to x; Z = −(corner cell) + constant, and z = −Z′ for a min.

1 · What is an LP?

Linear programming finds the best value (max profit, min cost) of a linear objective, subject to a finite number of linear constraints. It is one kind of mathematical programming (others: quadratic, integer, nonlinear, stochastic, convex programming).

max (min) Z = Σ c_jx_j s.t. Σ a_ijx_j ≤ (=, ≥) b_i, x_j ≥ 0

Matrix form: max Z = CX, AX ≤ b, X ≥ 0. A = coefficient matrix, C = cost row, b = right-hand side, P_j = column j of A.

Diet problem (Polly): choose servings x₁…x₆ of 6 foods to reach energy, protein and calcium at minimum cost. It is preset #10 in the solver.

2 · Graphical method (2 variables)

Draw each constraint line in the x₁x₂ plane.
Shade the feasible region, where all constraints hold at once.
Slide the objective line Z = c₁x₁ + c₂x₂ in the improving direction. The last point it touches is the optimum.

5 possible outcomes: no feasible solution · unbounded · one optimal solution at an extreme point · infinite optimal solutions (objective parallel to a boundary edge) · several optimal extreme points.

With 3 variables each constraint is a plane and the region is a polyhedron. Beyond that we can't draw, so we need the simplex method.

3 · Augmented (standard) form

max Z = Σ c_jx_j, Σ a_ijx_j = b_i, b_i ≥ 0, x_j ≥ 0

Objective: min Z → max Z′ = −Z (multiply costs by −1).
Variables: free x_k → x_k = x_k′ − x_k″, both ≥ 0.
Constant term: if b_i < 0, multiply the row by −1 (the sign flips).
Constraints: “≤” → + slack x_n+i; “≥” → − surplus x_n+i. Both have cost 0.

4 · Key theorems

If an optimal solution exists, one can be found at an extreme point (vertex) of the feasible region.
X is an extreme point ⇔ the columns of its non-zero variables are linearly independent.
There are finitely many extreme points: at most C(m+n, n) basic solutions. The search is finite, but this number can still be huge.
Basic variables are the ones whose columns form the basis B (start: I). Non-basic variables = 0, so X_B = B⁻¹b.

5 · Simplex method (Dantzig, 1947)

Start at an extreme point (a basic feasible solution).
Check whether moving to an adjacent extreme point improves Z. If not, the current point is optimal.
Move to the adjacent extreme point with the most improvement.
Repeat until optimal, or until you can show the problem is unbounded or infeasible.

Geometrically, the method walks along the edges of the polytope from vertex to vertex, and Z never decreases.

6 · Tableau formulas

λ_j = c_j − C_B·P_j (−Z cell = −C_B·P₀)

Optimal when every λ_j ≤ 0.
Entering column k: λ_k = max λ_j > 0 (slides' rule).
Leaving row: β = min { b_i/a_ik : a_ik > 0 }, which keeps P₀ ≥ 0.
Unbounded: λ_k > 0 but every a_ik ≤ 0.
Infinite optima: at the optimum, a non-basic variable has λ_j = 0.
Pivot: divide the pivot row by the pivot element, then use Gaussian elimination so the entering column becomes a unit vector.

7 · Pivot rules & degeneracy

The “most improvement” (largest λ) rule does not guarantee the fewest iterations. In preset #5, largest λ takes 3 pivots and smallest λ takes 1.
Bland's rule (Robert G. Bland, Cornell): choose the lowest-numbered (leftmost) non-basic column with a positive λ. It prevents cycling.
Degeneracy (“degradation”): a tie in β, so a basic variable becomes 0. Z may stay the same for a step.

8 · No identity matrix? Two-phase

Rows that were “≥” or “=” have no ready-made +1 column. Add artificial variables to them to get I.

Phase 1: minimize the sum of the artificials (here written as max W = −Σ artificials).
If the minimum is > 0, an artificial cannot be removed → no feasible solution. This answers the slide's “What if the slack variables are not 0?”.
If it is 0, drop the artificial columns and run Phase 2 with the real objective.

9 · History & tools

Fourier: systems of linear inequalities (Fourier–Motzkin elimination).
WWII military planning, kept secret until 1947. US Air Force project SCOOP (June 1947): Dantzig's general LP model and the simplex method.
Founders: Dantzig, von Neumann, Kantorovich. The simplex method is listed as one of the top 10 algorithms of the 20th century (Computing in Science and Engineering).
Solvers: Lindo/Lingo, Matlab, GLPK, Excel.