Linear programming — maximise a linear objective under linear constraints — is the workhorse of planning, logistics, and economics. The simplex method walks the corners of the feasible region, each step moving to a neighbour that improves the objective, until none does. Dantzig’s 1947 method is a genuine “top-10 algorithm” — and its inventor never got the Nobel the field did.
THE TECHNIQUE pivot corner to corner, uphill
The feasible region is a polytope; the optimum sits at a corner. Start at one vertex, and each pivot moves along an edge to a neighbouring corner with a better objective (choose the most-improving direction, stop when no neighbour helps). Below: a 2-D feasible region and the simplex walking to the optimum. live demo
HISTORY & CREDIT the algorithm is Dantzig’s; the Nobel wasn’t
“Kantorovich invented the simplex method” — true false; he invented linear programming (the field), Dantzig invented the simplex algorithm. Don’t swap them. cited
1939 · Leonid Kantorovich (USSR) formulates linear programming for production planning — independently, and unknown in the West for years. 1947 · George Dantzig invents the simplex method (the actual corner-walking algorithm) while at the US Air Force — the eponym here is correct. 1972 · Klee & Minty build a distorted cube where simplex visits every one of 2n corners — exponential worst case, though it is famously fast in practice. 1975 · the Nobel in Economics goes to Kantorovich & Koopmans — not Dantzig, a famous omission.
Fast almost always, exponential in the worst case, and the reason interior-point methods (with proven polynomial bounds) exist. Dantzig 1947
RECOMMEND FOR I-13 a tableau and row operations
Every pivot is ratios and Gaussian row operations on a tableau — and the tiny LP lands on the optimum:
$ i13 run simplex.i13 # max 3x+5y s.t. x<=4, 2y<=12, 3x+2y<=18
optimum (2,6) z = 36 # path (0,0)->(0,6)->(2,6), two pivots
Recommend: the whole inner loop is f64 — reduced costs, the minimum-ratio test (divide-and-compare down a column), and the pivot (scale a row, subtract multiples from the others: plain Gaussian elimination) — verified optimum 36 at (2,6). The tableau is a 2-D array — PS-004 — flattened row-major. Note: a natural companion to Gauss/Householder (089) — the same row-operation machinery, pointed at optimisation instead of solving.