Linear programming finds optima on a polytope of constraints
Linear programming maximises or minimises a linear objective under linear equalities and inequalities. Feasible points form a convex polytope—an intersection of half-spaces—and the algorithm seeks a vertex where the objective peaks or dips. Wartime logistics made the method famous; planning still runs on it.
Fourier published a method for systems of linear inequalities in 1827, remembered in Fourier–Motzkin elimination. In the late 1930s Leonid Kantorovich studied manufacturing schedules and Wassily Leontief explored economic uses, work long overlooked. World War II logistics, scheduling, and allocation put linear models centre stage. T. C. Koopmans framed classical economic problems as linear programs; he and Kantorovich shared the 1975 economics Nobel. Frank Lauren Hitchcock cast transportation as linear programs in 1941 with a simplex-like method, but died in 1957 before any posthumous Nobel could apply.
From 1946 to 1947 George B. Dantzig formulated general linear programs for US Air Force planning and invented the simplex method that solved most instances efficiently. Meeting John von Neumann, he heard an immediate duality conjecture linking the problem to game theory; Dantzig’s unpublished proof dated 5 January 1948, with public availability in 1951. His motivating example assigned 70 people to 70 jobs: brute-force permutations outnumber particles in the observable universe, yet simplex finds an optimum in a moment by pruning the search.
Leonid Khachiyan proved polynomial-time solvability in 1979; Narendra Karmarkar’s 1984 interior-point method was a larger practical and theoretical leap. Duality, decomposition, and convexity ideas from linear programming shaped wider optimisation. Industries from transport and energy to telecom and manufacturing use it for routing, scheduling, and design; Google has used it to stabilise YouTube videos. Network-flow special cases drive their own algorithm families.
Standard form maximises cᵀx subject to Ax ≤ b and x ≥ 0. A farmer splitting L hectares between wheat and barley under fertiliser and pesticide caps is the textbook story: choose hectare variables to maximise revenue while respecting linear resource bounds. Minimisation, free-sign variables, and other constraint shapes rewrite into that mould. The geometry is simple and powerful—walk the polytope’s vertices until the linear objective can climb no further.
Source: Linear programming
