Overview

Linear programming (also called linear optimisation) is the branch of mathematical optimization concerned with selecting the best outcome from a set of alternatives modeled by linear relationships. A linear program typically specifies a linear objective function to be maximized or minimized and a collection of linear equality or inequality constraints that define a feasible region. The subject provides a formal framework for decision-making where objectives and restrictions can be described by linear expressions, and it forms a cornerstone of operations research.

Mathematical formulation and geometry

In standard form a linear program seeks to maximize c·x subject to Ax ≤ b and x ≥ 0, where x is a vector of variables, c is the objective coefficient vector, A is a matrix of constraint coefficients, and b is a vector of bounds. Geometrically, the set of feasible solutions of a linear program is a convex polyhedron (or polytope when bounded) in Euclidean space. Optimal solutions, when they exist, occur at extreme points (vertices) of this region; this connection allows geometric intuition and visual methods when dimensions are small. For more on polyhedral concepts see polyhedra and modeling approaches in geometric optimization.

Algorithms and computational aspects

Two families of algorithms dominate practical linear programming. The simplex method, developed by George Dantzig, traverses vertices of the feasible polyhedron to improve the objective and is often extremely fast in practice despite having exponential worst-case time complexity. Interior-point methods approach an optimum via a path through the interior of the feasible region and are known for polynomial-time worst-case bounds and good performance on large sparse problems. Problem instances can also be attacked with revised simplex, barrier methods, and specialized decomposition techniques for very large or structured models. The theoretical complexity of different formulations and algorithms is discussed within computational complexity and algorithmic research literature.

Duality, sensitivity and extensions

Every linear program has an associated dual problem whose optimal value bounds the original (primal) objective; under mild conditions the two values coincide. Duality theory provides economic interpretations (shadow prices), certificates of optimality, and tools for sensitivity analysis that show how solutions change when data are perturbed. Linear programming is a special case of convex optimization and serves as the foundation for integer programming and mixed-integer programming when integrality constraints are added. Connections to other fields and methods appear in texts and surveys covering linear inequalities and convex analysis.

History and development

The modern subject took shape in the mid-20th century. Early theoretical work by Leonid Kantorovich predated wider adoption, and George Dantzig popularized the term "linear programming" and developed the simplex algorithm while working on resource allocation problems. The name "programming" reflected planning and allocation rather than computer code; the rise of electronic computers after World War II made it possible to solve large-scale instances numerically. Historical surveys and biographies give context to these developments Kantorovich and Dantzig.

Applications, tools and notable facts

Linear programming is applied in transportation and logistics, production planning, workforce scheduling, portfolio optimization, network flows, and many other domains where linear models are appropriate. Practical implementations rely on dedicated solvers that implement simplex and interior-point techniques; modern packages handle large sparse systems and exploit structure for speed. For accessible introductions and software references see educational resources and solver documentation simplex, operations research guides, and algorithmic surveys interior point. Additional reading on modeling practice and polyhedral theory can be found in computational optimization collections geometry and applied optimization texts complexity.

  • Key strengths: clear theoretical foundation, wide applicability, strong solver ecosystem.
  • Limitations: only linear relationships; many practical problems require integer or nonlinear extensions.
  • Related topics: integer programming, convex optimization, network optimization; see introductory references linear inequalities and historical accounts term origin.