The Simplex Method
The graphical method runs out of dimensions at two variables; real problems have thousands. The simplex method — George Dantzig's 1947 masterpiece — solves them all with the same geometric idea made algebraic: start at a corner of the feasible region, then hop to an adjacent corner that improves the objective, and repeat until no neighbour is better. This chapter builds the tableau that carries out that walk, the optimality test that says when to stop, and the pivot that takes each step, all traced through a full example.
- Why the simplex method scales where the graphical method cannot, and its vertex-hopping idea.
- How to reach standard form with slack variables and read off the initial basic feasible solution.
- The anatomy of the simplex tableau and the meaning of the \(z\)-row (reduced costs).
- The optimality test and how to choose the entering variable.
- The minimum-ratio test for the leaving variable and the pivot operation.
- How to read the final tableau — solution, slacks, shadow prices — and recognise degeneracy.
Why an Algebraic Method?
Chapter 6 proved that an LP optimum sits at a vertex, and Chapter 7 exploited that for two variables by drawing the corners. But a problem with \(n\) variables and \(m\) constraints can have up to \(\binom{n}{m}\) corners — an astronomical number even for modest sizes. Checking them all is hopeless.
The simplex method is the intelligent alternative. Rather than enumerate every vertex, it starts at one, then moves only to an adjacent vertex that improves the objective, ignoring the rest. Because each move strictly improves (or the problem is degenerate), it never revisits a corner and terminates after a modest number of steps in practice. Everything is done in a table of numbers — the tableau — so it needs no picture and no bound on dimension.
Standard Form and the Initial Basis
The simplex method requires standard form — equalities and non-negative variables — reached by adding a slack to every "\(\le\)" constraint. We will carry the running example through the whole chapter:
The three slack variables hand us a free starting corner. Set the "real" variables \(x_1 = x_2 = 0\) (non-basic); then \(s_1 = 4,\ s_2 = 12,\ s_3 = 18\) (basic), and \(z = 0\). This is the origin \((0,0)\) — an obvious basic feasible solution because each slack appears in exactly one equation with coefficient \(+1\), forming a ready-made identity basis. The simplex method begins here and improves.
The Simplex Tableau
The tableau arranges the coefficients so each iteration is pure bookkeeping. Rows hold the constraint equations (one per basic variable); the bottom \(z\)-row holds the objective, written \(z - 3x_1 - 5x_2 = 0\) so its entries start as \(-c_j\). The last column is the right-hand side (the current values of the basic variables and of \(z\)).
| Basis | x₁ | x₂ | s₁ | s₂ | s₃ | RHS | Ratio |
|---|---|---|---|---|---|---|---|
| s₁ | 1 | 0 | 1 | 0 | 0 | 4 | — |
| s₂ | 0 | 2 | 0 | 1 | 0 | 12 | 6 ← |
| s₃ | 3 | 2 | 0 | 0 | 1 | 18 | 9 |
| z | −3 | −5 | 0 | 0 | 0 | 0 |
The Optimality Test
The \(z\)-row entries are the reduced costs — how much \(z\) would change per unit increase of each non-basic variable. With the objective written as \(z - \sum c_j x_j = 0\), a negative entry means bringing that variable into the basis would still raise \(z\), so we are not yet optimal.
If any \(z\)-row entry is negative, the current corner can be improved — pick one to enter the basis. If all are \(\ge 0\), no non-basic variable can raise \(z\) and the current basic feasible solution is optimal. (For minimization the test flips: stop when all \(z\)-row entries are \(\le 0\).)
The Simplex Iteration
Each iteration performs three actions: choose which variable enters the basis, choose which leaves, and pivot to update the tableau.
| Step | Rule | Purpose |
|---|---|---|
| Entering variable | Most negative \(z\)-row entry → its column is the pivot column | Steepest improvement of \(z\) |
| Leaving variable | Minimum ratio \(\dfrac{\text{RHS}}{\text{pivot-column entry}}\) over positive entries → pivot row | Stay feasible (no variable goes negative) |
| Pivot | Gauss–Jordan on the pivot element to make its column a unit vector | Move to the adjacent vertex |
Only positive pivot-column entries \(a_{ik}\) are considered; a zero or negative entry places no limit on the entering variable. If no entry is positive, the entering variable can grow without bound — the problem is unbounded.
A Full Worked Solution
Iteration 1. In the initial tableau (Section 8-3) the most negative \(z\)-row entry is \(-5\) under \(x_2\) — so \(x_2\) enters. The ratios are \(12/2 = 6\) (row \(s_2\)) and \(18/2 = 9\) (row \(s_3\)); row \(s_1\) is skipped (zero entry). The minimum \(6\) makes \(s_2\) leave, with pivot element \(2\). Dividing the \(s_2\) row by \(2\) and clearing the \(x_2\) column gives:
| Basis | x₁ | x₂ | s₁ | s₂ | s₃ | RHS | Ratio |
|---|---|---|---|---|---|---|---|
| s₁ | 1 | 0 | 1 | 0 | 0 | 4 | 4 |
| x₂ | 0 | 1 | 0 | 1/2 | 0 | 6 | — |
| s₃ | 3 | 0 | 0 | −1 | 1 | 6 | 2 ← |
| z | −3 | 0 | 0 | 5/2 | 0 | 30 |
Now \(z = 30\) at the corner \((0,6)\). Iteration 2. The only negative \(z\)-row entry is \(-3\) under \(x_1\) — \(x_1\) enters. Ratios: \(4/1 = 4\) (row \(s_1\)) and \(6/3 = 2\) (row \(s_3\)); the minimum \(2\) makes \(s_3\) leave, pivot element \(3\). Dividing the \(s_3\) row by \(3\) and clearing the \(x_1\) column:
| Basis | x₁ | x₂ | s₁ | s₂ | s₃ | RHS |
|---|---|---|---|---|---|---|
| s₁ | 0 | 0 | 1 | 1/3 | −1/3 | 2 |
| x₂ | 0 | 1 | 0 | 1/2 | 0 | 6 |
| x₁ | 1 | 0 | 0 | −1/3 | 1/3 | 2 |
| z | 0 | 0 | 0 | 3/2 | 1 | 36 |
Every \(z\)-row entry is now \(\ge 0\), so we stop. The solution \((2,6)\) with \(z = 36\) matches the graphical answer of Chapter 7 exactly. As a bonus, the \(z\)-row entries under the slacks are the shadow prices of the constraints: \(0\) for constraint 1 (it had slack), \(3/2\) for constraint 2, and \(1\) for constraint 3 — the same marginal values Chapter 5 defined with multipliers.
Degeneracy, Cycling, and Practical Notes
A tie in the minimum-ratio test produces a degenerate basic feasible solution — one where a basic variable equals zero. Geometrically, more than the minimum number of constraints pass through the same vertex. Degeneracy is harmless in itself, but in rare theoretical cases it can cause cycling: the algorithm pivots among bases of equal objective value without progressing. Simple anti-cycling rules — most famously Bland's rule (always choose the lowest-indexed eligible variable) — guarantee termination.
Worked Examples
Problem. Put \(\max\ z = 5x_1 + 4x_2\) s.t. \(6x_1 + 4x_2 \le 24,\ x_1 + 2x_2 \le 6,\ x \ge 0\) into a starting tableau.
Solution. Add slacks: \(6x_1 + 4x_2 + s_1 = 24,\ x_1 + 2x_2 + s_2 = 6\). Initial basis \(s_1 = 24,\ s_2 = 6\), \(z\)-row \([-5, -4, 0, 0\ |\ 0]\). The most negative entry \(-5\) means \(x_1\) enters first; ratios \(24/6 = 4\) and \(6/1 = 6\) make \(s_1\) leave (pivot element \(6\)).
Problem. A \(z\)-row reads \([-2, 0, -6, 0\ |\ 40]\) and the \(x_3\) column (over the two constraint rows) is \([4, 2]^{\mathsf T}\) with RHS \([16, 18]^{\mathsf T}\). Which variable enters, and which leaves?
Solution. The most negative reduced cost is \(-6\) under \(x_3\), so \(x_3\) enters. Ratios: \(16/4 = 4\) and \(18/2 = 9\); the minimum \(4\) selects the first row to leave. The pivot element is \(4\).
Problem. With pivot element \(2\) in the \(x_2\) column, \(s_2\) row \([0, 2, 0, 1, 0\ |\ 12]\), perform the pivot on the \(s_3\) row \([3, 2, 0, 0, 1\ |\ 18]\).
Solution. Normalize the pivot row: \(x_2\) row \(= [0, 1, 0, 1/2, 0\ |\ 6]\). Then subtract \(2 \times\) it from the \(s_3\) row:
which is exactly the updated \(s_3\) row from Iteration 1.
Problem. A final tableau has basic variables \(x_1 = 3,\ x_2 = 1.5\), non-basic \(s_1 = s_2 = 0\), and \(z\)-row \([0, 0, 0.5, 1.5\ |\ 21]\). State the solution and the shadow prices.
Solution. All \(z\)-row entries are \(\ge 0\), so it is optimal: \(x_1 = 3,\ x_2 = 1.5,\ z^\star = 21\). Both slacks are zero, so both constraints are binding. Their shadow prices are the \(z\)-row entries under the slacks: \(0.5\) for constraint 1 and \(1.5\) for constraint 2.
Problem. During an iteration, the entering variable's column is \([-2, -1]^{\mathsf T}\) with RHS \([5, 8]^{\mathsf T}\). What happens?
Solution. No pivot-column entry is positive, so the minimum-ratio test has no eligible row. The entering variable can increase indefinitely without any basic variable turning negative — the objective grows without bound and the LP is unbounded. The algorithm stops and reports this.
Problem. An optimal tableau has all \(z\)-row entries \(\ge 0\), but the reduced cost of the non-basic variable \(x_2\) is exactly \(0\). What does this mean?
Solution. Bringing \(x_2\) into the basis would leave \(z\) unchanged, so there is a second optimal basic feasible solution — and the whole edge between the two is optimal. The LP has alternative optima, the algebraic signature of the parallel-objective case seen graphically in Chapter 7.
Chapter Summary
Simplex moves from corner to improving adjacent corner — never enumerating them all.
Add slacks for standard form; the slacks give the initial BFS at the origin.
Stop when every \(z\)-row entry is \(\ge 0\) (maximization).
Most negative reduced cost enters; minimum ratio test picks the leaving row.
Gauss–Jordan on the pivot element moves to the next vertex; repeat.
Zero reduced cost → alternative optima; no positive ratio → unbounded; slacks → bottlenecks.
Problems
Set up each tableau carefully and carry out every pivot; check your final answer against a quick sketch where possible. Difficulty rises down the list.
- Convert to standard form and write the initial tableau: \(\max\ 4x_1 + 3x_2\) s.t. \(2x_1 + x_2 \le 10,\ x_1 + 3x_2 \le 15,\ x \ge 0\).
- For Problem 1, identify the first entering and leaving variables and the pivot element.
- Solve \(\max\ 5x_1 + 4x_2\) s.t. \(6x_1 + 4x_2 \le 24,\ x_1 + 2x_2 \le 6,\ x \ge 0\) by simplex; report \(x^\star\), \(z^\star\), and all slacks.
- Solve \(\max\ 2x_1 + 3x_2\) s.t. \(x_1 + x_2 \le 4,\ x_1 + 3x_2 \le 6,\ x \ge 0\) and confirm the answer graphically.
- In a tableau, the entering column is \([3, -2, 1]^{\mathsf T}\) with RHS \([9, 5, 4]^{\mathsf T}\). Determine the leaving row.
- Explain why only positive pivot-column entries are used in the ratio test.
- Perform a single pivot: pivot element \(4\) at row 1, column \(x_1\); row 1 is \([4, 1, 1, 0\ |\ 12]\), row 2 is \([2, 3, 0, 1\ |\ 10]\). Update both rows.
- Given a final \(z\)-row \([0, 0, 2, 0, 5\ |\ 48]\), state the optimal objective value and the shadow prices of the constraints.
- How can you tell from a tableau that an LP is unbounded? Give a small example.
- How does a zero reduced cost for a non-basic variable at optimality reveal alternative optima?
- Define a degenerate basic feasible solution and explain how it can arise from a tie in the ratio test.
- A firm maximizes \(z = 6x_1 + 5x_2\) subject to \(x_1 + x_2 \le 5,\ 3x_1 + 2x_2 \le 12,\ x \ge 0\). Solve by the simplex method, showing every tableau; then state \(x^\star\), \(z^\star\), which constraints are binding, the shadow price of each, and whether the optimum is unique.