Linear programming and simplex algorithm
Programación lineal y algoritmo símplex
- Date
- 1947 · confidence high
- Place
- Washington, D.C. (the Pentagon), United States
- Credited to
- George Dantzig (simplex, 1947); Leonid Kantorovich (Leningrad, 1939); duality by von Neumann
- People
- 👤 George Dantzig1914–2005👤 Leonid Kantoróvich1912–1986
- Field
- Knowledge & symbols
⚠️ Disputed: the sources disagree.
What was discovered
The formulation of the optimisation of a linear objective under linear constraints, and a practical method for solving it by moving between vertices of the feasible polyhedron. It is the central tool of operations research.
Kantorovich developed it in the USSR in 1939 to plan plywood production, without it becoming known in the West; he received the Nobel Prize in Economics in 1975, with Koopmans.
What it led to
- operations research
- convex optimisation
- the interior-point method (Karmarkar, 1984)
- complexity theory (simplex is exponential in the worst case)
Built on
- game theory (duality)
- Fourier (linear inequalities)
Made possible
- Vehicle routing problem1959
- military and business logistics
- production planning
- network resource allocation