Linear programming (LP) is the foundational tool of operations research. It addresses the problem of optimizing (maximizing or minimizing) a linear function of several variables subject to linear equality and inequality constraints. The technique is both mathematically elegant and practically powerful — it underlies supply chain optimization, airline scheduling, portfolio management, and hundreds of other applications.
A linear program has three components:
A canonical LP in standard form:
Maximize: c₁x₁ + c₂x₂ + ... + cₙxₙ
Subject to: a₁₁x₁ + a₁₂x₂ + ... + a₁ₙxₙ ≤ b₁
a₂₁x₁ + a₂₂x₂ + ... + a₂ₙxₙ ≤ b₂
...
aₘ₁x₁ + aₘ₂x₂ + ... + aₘₙxₙ ≤ bₘ
x₁, x₂, ..., xₙ ≥ 0
In matrix notation: maximize cᵀx subject to Ax ≤ b, x ≥ 0, where c and x are n-vectors, A is an m×n matrix, and b is an m-vector.
A factory makes two products, A and B. Each unit of A earns $5 profit; each unit of B earns $4. Production requires machine time (8 hours available) and labor (6 hours available). Product A needs 2 machine hours and 1 labor hour per unit; Product B needs 1 machine hour and 2 labor hours.
Maximize: 5xₐ + 4x_b
Subject to: 2xₐ + x_b ≤ 8 (machine hours)
xₐ + 2x_b ≤ 6 (labor hours)
xₐ, x_b ≥ 0
The optimal solution is xₐ = 10/3, x_b = 4/3, giving profit = 50/3 + 16/3 = 22. (In practice we might require integer solutions — see Integer and Combinatorial Optimization.)
The constraints define a feasible region — the set of all points satisfying all constraints simultaneously. For a problem with n variables, this region is a convex polytope (or polyhedron) in n-dimensional space. Convexity is crucial: a convex set has no "holes" or "dents," which means any local optimum is a global optimum.
The objective function defines a family of parallel hyperplanes. We seek the hyperplane with the best objective value that still intersects the feasible region. This optimal hyperplane will touch the feasible region at a vertex (corner point) of the polytope — unless the problem is unbounded or infeasible.
Key theorem: If an LP has an optimal solution, there exists an optimal vertex. This is the geometric foundation of the simplex method.
Developed by George Dantzig in 1947, the simplex method is an iterative algorithm that moves along the edges of the feasible polytope from vertex to vertex, improving the objective at each step. It terminates when no neighboring vertex yields improvement.
The simplex method is not polynomial in the worst case — Klee and Minty (1972) constructed an LP where it examines exponentially many vertices. However, in practice, it is remarkably efficient, typically taking O(m) to O(3m) pivots for an LP with m constraints.
This apparent paradox — exponential worst case, polynomial average case — is still not fully explained theoretically. The smoothed analysis framework (Spielman and Teng, 2004) gave partial answers, showing that small random perturbations make the worst case vanish.
Karmarkar's 1984 algorithm, and the class of interior-point (barrier) methods that followed, are polynomial in the worst case. Interior-point methods traverse the interior of the feasible region rather than its boundary, following a curved path to the optimum.
For very large LPs (millions of variables and constraints), interior-point methods are often competitive with or faster than simplex. Modern commercial solvers (CPLEX, Gurobi) implement both and choose heuristically.
Every LP (the primal) has an associated dual LP. For the standard primal:
Primal: max cᵀx s.t. Ax ≤ b, x ≥ 0
Dual: min bᵀy s.t. Aᵀy ≥ c, y ≥ 0
Duality is not a technical curiosity — it is conceptually central to LP.
For any primal feasible x and dual feasible y: cᵀx ≤ bᵀy. The dual provides an upper bound on the primal objective (for maximization). This means any feasible dual solution certifies that the primal cannot do better.
If both the primal and dual have feasible solutions, they have equal optimal values: max cᵀx = min bᵀy. The duality gap is zero at optimality.
A primal solution x* and dual solution y* are both optimal if and only if:
The dual variables have a natural interpretation as shadow prices or marginal values. In the factory example, the dual variable for the machine-hours constraint tells you how much the optimal profit would increase if you had one more machine hour. This interpretation makes LP duality an essential tool for sensitivity analysis — understanding how much the optimal solution changes when parameters shift.
Real-world LP models contain uncertain parameters: costs, resource capacities, demand forecasts. Sensitivity analysis answers questions like:
Commercial solvers report sensitivity ranges automatically. This capability transforms LP from a one-time calculation into a continuous planning tool.
Many practical LPs have a special structure — the constraint matrix is a network incidence matrix, with one +1 and one -1 per column. These network flow problems can be solved much faster than general LP using specialized network simplex or shortest-path algorithms.
The transportation problem is an archetypal network LP:
This structure appears in shipping, telecommunications routing, assignment problems, and production planning.
| Industry | Application | Scale |
|---|---|---|
| Airlines | Crew scheduling, fleet assignment | Millions of variables |
| Oil refining | Refinery planning, blending | Hundreds of constraints |
| Agriculture | USDA crop allocation planning | National scale |
| Finance | Portfolio optimization, risk management | Thousands of assets |
| Telecommunications | Network capacity planning | Large networks |
| Military | Logistics, airlift planning | Theater-scale |
| Retail | Inventory allocation, shelf placement | Chain-wide |
Modern LP is solved using commercial or open-source solvers:
Modeling languages like AMPL, GAMS, and the Julia package JuMP allow formulating models independently of the solver.