Maximization of a Linear Function of Variables Subject to Linear Inequalities
The best answer to a linear plan always sits at a corner — so walk the corners to find it.
Behind every well-run supply chain and flight schedule sits a 1947 insight: the best plan always lives at a corner.
The big idea
Imagine you must make a plan under limits — a budget, a number of hours, a stock of materials — and you want to squeeze the most out of it. If everything is “linear” (twice the ingredients, twice the cost; twice the work, twice the output), then the rules carve out a many-sided shape of all the plans you're allowed, and your goal points in some direction across it.
George Dantzig proved something both surprising and useful: the very best plan is never somewhere vague in the middle — it always sits at a corner of that shape. So instead of testing endless possibilities, you can hop from corner to corner, always uphill, until no neighbouring corner is better. That corner is the answer. He called the procedure the simplex method, and it made “find the best plan” something a machine could actually do.
How it came about
In 1947 Dantzig was a mathematician for the U.S. Air Force, working on how to schedule the training, supply and deployment of an entire military — what planners then called a “program.” He distilled these puzzles into a single mathematical form, then invented the simplex method to solve it. When he described the problem to the great John von Neumann that October, von Neumann instantly recognized its skeleton: it was the same minimax structure as the theory of games he had just written a book about, and he sketched its hidden twin, the “dual,” on the spot.
There is a tangle of credit around it. In the Soviet Union, Leonid Kantorovich had found linear programming back in 1939, but his work stayed unknown in the West for years. When the 1975 Nobel Prize in Economics honoured linear programming, it went to Kantorovich and Tjalling Koopmans — and not to Dantzig, whose algorithm had made the field practical; Koopmans thought that unfair. (Dantzig is also the real student behind a famous legend: as a graduate student he arrived late to class, copied two problems off the board as homework, and solved them — only to learn they were two famous unsolved problems in statistics.)
Why it mattered
Almost any question of the form “what is the best way to use what we have?” can be cast as a linear program, and the simplex method answered a vast number of them for the first time. It turned planning — for armies, factories, airlines, power grids, whole economies — from guesswork and rules of thumb into a calculation that also tells you the value of each scarce resource you're up against.
A way to picture it
Picture a flat-sided field fenced off by straight walls, and tilt the whole field gently in some direction. A ball set loose rolls downhill and comes to rest — never in the open middle, but jammed into a corner where two walls meet. Because both the walls and the slope are perfectly straight, the lowest point (or, flip it over, the highest) is guaranteed to be a corner. The simplex method is just a clever way to walk to that corner along the fences, instead of searching the whole field.
Where it sits
Linear programming grew out of an old strand of mathematics about linear inequalities (Fourier had toyed with it a century earlier) and arrived alongside von Neumann and Morgenstern's theory of games — the same minimax idea wearing two hats. From here the line runs to Bellman's dynamic programming, to Karmarkar's interior-point methods, and into the optimization that quietly powers logistics and machine learning today; the value-of-a-constraint idea, the shadow price, became part of the everyday language of economics.