CONCEPT
Linear Programming
The mathematical technique for finding the best allocation of scarce resources under linear constraints—invented independently in the Soviet Union and the United States within a decade, and now the computational core of logistics, finance, and AI infrastructure.
Linear programming is the problem of maximizing (or minimizing) a linear objective function subject to a system of linear inequality constraints. Its feasible region is a convex polytope and its optimal solution, when one exists, lies at a vertex—a fact that grounds
the simplex method and the entire field of convex optimization.
Leonid Kantorovich discovered the technique in 1939 while solving a plywood production problem;
George Dantzig developed it independently in 1947 and invented the simplex algorithm; Tjalling Koopmans connected it to economic equilibrium theory. The field's central theorem—strong duality—states that the optimal value of the primal problem equals the optimal value of its dual, and that the dual solution yields the
shadow prices of each constraint: the rate of improvement in the objective per unit relaxation of each limit. Linear programming now governs airline scheduling, supply chain routing, financial portfolio construction, and the allocation of advertising inventory. In AI, it provides the
foundation for convex relaxations of combinatorial problems,