Linear programming

Linear programming is a method for achieving the best outcome in a mathematical model whose requirements are represented by linear relationships. It is the simplest and most widely applied form of optimization, used in logistics, manufacturing, scheduling, and resource allocation across virtually every industry.

The field was founded by Leonid Kantorovich in 1939 (for production planning in the Soviet Union) and independently by George Dantzig in 1947 (for the US Air Force), who developed the simplex algorithm — the first practical method for solving linear programs. The simplex algorithm walks along the edges of the feasible region's polytope, moving from vertex to vertex until an optimal solution is found. Despite its worst-case exponential complexity, the simplex method performs remarkably well in practice, a phenomenon that remains only partially understood.

The significance of linear programming extends beyond its applications. It was the first optimization problem for which a general efficient algorithm was found, and it established the template for optimization theory: formulate constraints, define an objective, and let the algorithm find the optimum. This template underlies modern machine learning, economics, and operations research. The assumption that real-world problems can be linearized is often false — but the success of linear programming suggests that many non-linear systems are well-approximated by linear models near their operating points, a principle that is itself a systems-level insight.