Linear Programming and the Simplex Method

A factory makes tables and chairs. Each table earns \$3 and each chair \$2; a table needs 1 hour of cutting and 1 of assembly, a chair 1 of cutting and 3 of assembly; there are 4 cutting-hours and 6 assembly-hours a day. How many of each to build for the most profit? Nothing here is curved — profit, hours, and limits are all linear in the quantities. That is a linear program (LP), and it is the workhorse of applied optimization: airline scheduling, diet planning, oil-refinery blending, network routing all reduce to one.

Every LP has the same shape — a linear objective over a region cut out by linear inequalities:

\max_{\mathbf{x}} \; \mathbf{c}^{\!\top}\mathbf{x} \quad\text{subject to}\quad A\mathbf{x} \le \mathbf{b}, \quad \mathbf{x} \ge \mathbf{0}.

Our factory is \max\, 3x + 2y subject to x + y \le 4 (cutting), x + 3y \le 6 (assembly), and x, y \ge 0. Each inequality is a half-plane; the feasible region is their intersection — a convex polygon (in higher dimensions, a polytope).

The optimum sits at a corner

The objective 3x + 2y = k is a family of parallel lines, one for each profit level k. Maximizing profit means pushing that line as far in the direction of increasing k as it can go while still touching the feasible region. The last place it touches — barring a fluke — is a single vertex.

If a linear program has an optimal solution, then an optimum is attained at a vertex (corner) of the feasible polytope.

Slide the profit level below. The moving line is 3x + 2y = k; watch it sweep across the polygon. It leaves the region for good exactly at the vertex (4, 0), where profit is 12 — the LP's answer: 4 tables, no chairs.

Checking the corners by hand

With only four vertices we can just enumerate them. Find each corner as the meeting of two boundary lines, then read off the profit:

The winner is (4, 0) with P = 12. Enumerating corners works for a toy problem, but a polytope in n dimensions with m constraints can have astronomically many vertices — we need something smarter than brute force.

The simplex method: walk the edges uphill

George Dantzig's simplex method (1947) is the classic algorithm. Rather than visit every vertex, it treats the polytope like a diamond and walks along its edges, always to an adjacent vertex with a better objective value, until no neighbouring vertex improves — at which point, by convexity, it has the global optimum.

The machinery underneath is pure linear algebra. Slack variables turn each inequality into an equation (x + y + s_1 = 4), giving a system A\mathbf{x} = \mathbf{b}. A vertex is a basic feasible solution: set enough variables to zero, solve the rest. Moving to an adjacent vertex swaps one variable in and one out — a pivot, which is exactly one step of Gaussian elimination on the tableau. Simplex is Gaussian elimination given a compass: pivot in the direction that most improves the objective, repeat until you can't.

In practice simplex is astonishingly fast — usually a small multiple of m pivots — even though, remarkably, a fiendishly-shaped polytope can force it to visit exponentially many vertices in the worst case.

In 1939, a graduate student arrived late to Jerzy Neyman's statistics class at Berkeley and copied two problems from the blackboard, assuming they were homework. They seemed harder than usual, but a few days later he handed in solutions, apologising that they had taken so long. They were not homework — they were two famous unsolved problems in statistics. The student was George Dantzig, who a few years later would invent the simplex method and effectively found the field of linear programming. The tale later became an urban legend and even a scene in Good Will Hunting — but this one is true, and Dantzig told it himself.