Linear programming

The formula

A linear program has three parts: a linear objective you want to push up or down, linear constraints that fence you in, and a rule that says the variables can't go negative.

maximize    z = c·x = c₁x₁ + c₂x₂ + ... + cₙxₙ
subject to  A·x ≤ b        (the constraints, one row each)
            x ≥ 0          (nothing goes negative)

Reading it in plain terms:

• z = c·x — the thing you care about (profit, weight, cost, runtime), written as a weighted sum of your decision variables. Each cᵢ is what one unit of xᵢ is worth.
• A·x ≤ b — every physical limit you have, one inequality per row: hours on a machine, pounds of raw stock, watts in a budget. A holds how much each decision consumes; b holds how much you've got.
• x ≥ 0 — you can't schedule negative shifts or buy negative aluminum.

Every LP has a mirror-image dual. Minimizing a cost under ≥ constraints is the same problem seen from the other side:

primal:  max  c·x   s.t.  A·x ≤ b,   x ≥ 0
dual:    min  b·y   s.t.  Aᵀ·y ≥ c,  y ≥ 0

Strong duality says that if both have solutions, max c·x = min b·y — the two optimal numbers are identical. The dual variables y are the shadow prices: what one more unit of each resource is worth at the optimum.

Where you meet it

• Propellant and blend problems on the test stand. You need a fuel or a coolant mix that hits a density and a heat-capacity spec at minimum cost, drawing from four stock fluids each with its own price and properties. The specs are linear in the blend fractions, the fractions sum to one, and cost is linear — that's an LP, and it's exactly the class of problem Kantorovich started with in 1938.

• Crew and bench scheduling in a review. Six technicians, nine test articles, each article needs a certain number of instrumented hours, each tech has a shift limit and a certification list. Maximize articles completed this week without blowing any labor cap. You hand the constraint matrix to a solver, not a spreadsheet you eyeball.

• Power and mass budgets on a spacecraft build. Allocate a fixed watt budget and a fixed mass budget across subsystems to maximize a weighted mission-value score. Every subsystem draws linearly on both budgets. LP tells you the allocation and, through the shadow prices, tells you which budget is actually the binding one.

• Cut-stock and allocation on the shop floor. Cutting beams, plate, or cable from standard lengths to fill an order list with minimum scrap is an allocation LP (often an integer one, which is harder — see below).

How it works

The feasible region — everything satisfying A·x ≤ b and x ≥ 0 — is a convex polytope. Picture the intersection of a stack of flat walls: a faceted, many-cornered solid. The key fact that makes LP tractable: when a linear objective is optimized over a polytope, the optimum always lands on a corner (a vertex). You never have to search the interior. If the best answer looks like it's in the middle of a face, there's a corner of that face that's just as good.

Take a concrete blend: maximize 40x₁ + 30x₂ subject to x₁ + x₂ ≤ 12, 2x₁ + x₂ ≤ 16, x ≥ 0. Walk the corners:

(0, 0)  →   0
(8, 0)  → 320
(4, 8)  → 400   ← optimum
(0, 12) → 360

The optimum is (4, 8) with z = 400, sitting where the two constraint lines cross. Both constraints are tight there — you've used every machine hour and every labor hour. That's typical: at the optimum, the binding constraints are the ones with a nonzero shadow price.

The simplex method exploits the corner fact directly. It starts at one vertex, looks at the edges leaving it, and walks to whichever neighbor improves the objective, repeating until no neighbor is better. Because the objective is linear and the region is convex, a local corner optimum is the global optimum — no local-minimum trap. In practice simplex is fast, usually finishing in a number of steps close to the number of constraints.

The gotcha that surprises people: simplex has no polynomial-time guarantee. Klee and Minty built a deformed cube in 1972 where simplex is forced to visit every one of the 2ⁿ corners before it stops. Real-world problems almost never look like that, so simplex stayed the workhorse for decades — but it means "the solver is slow" can, rarely, be the geometry and not your setup.

The other family — interior point methods — ignores the corners and drives a path straight through the middle of the polytope toward the optimum, bending away from the walls. These carry a proven polynomial-time bound and tend to win on very large, sparse problems (tens of thousands of variables). Modern solvers ship both and pick automatically.

Two limits worth stating plainly:

• Everything must be linear. The moment a constraint or the objective goes nonlinear — a squared term, a product of two variables, an on/off logic — it is no longer an LP. Force it into LP form and you'll get a confidently wrong answer.
• "Whole units" is a different, harder problem. If your variables must be integers (you can't build 4.7 satellites), you have an integer program. Dropping the integer requirement, solving the LP, and rounding often gives an infeasible or badly suboptimal answer. Integer programming is its own tool and is genuinely harder than LP.

The mistake people make is treating a solver's optimum as the whole story and ignoring the shadow prices. In the blend above, the shadow prices are 20 and 10: one more machine hour is worth 20 units of profit, one more labor hour is worth 10. That tells you where to spend the next dollar of capacity — often more useful than the optimum itself. But shadow prices are marginal: they hold only until the binding constraint set changes, and then they change too (usually dropping). Buying 50 more machine hours is not worth 50 × 20 — re-solve with the new capacity, or read the allowable range every solver reports alongside the duals.

History

The idea showed up on both sides of the Iron Curtain, years apart, mostly out of contact.

In 1938 the Soviet mathematician Leonid Kantorovich was handed a plywood-trust production problem: distribute raw materials across machines to maximize output. He recognized the general structure and, in 1939, published a monograph laying out what we now call linear programming — objective, linear constraints, and a method ^[1][2]. The work sat largely unnoticed for years, partly because it brushed against Soviet economic orthodoxy about prices.

The Western branch grew out of World War II logistics. George Dantzig, working Air Force planning problems, formulated the general linear program and in 1947 invented the simplex method — the corner-walking algorithm that made LP practical to actually solve ^[1][3]. Dantzig later credited the economist Tjalling Koopmans, who had been formulating transportation and allocation problems the same way, with pushing the field into economics.

Kantorovich and Koopmans shared the 1975 Nobel Memorial Prize in Economic Sciences for the theory of optimal allocation of resources — the economic face of linear programming ^[2][4]. (Dantzig, whose algorithm made the whole thing computable, was not included, a snub still argued over.)

Two later milestones settled the theory question. In 1979 Leonid Khachiyan proved with the ellipsoid method that LP is solvable in polynomial time — a landmark result, though the method was too slow to use in practice ^[6]. Then in 1984 Narendra Karmarkar at Bell Labs published an interior point method that was both polynomial-time and genuinely fast, with a complexity around O(n³·⁵L). That kicked off the modern interior-point era and, within a decade, hundreds of papers ^[5][7].

Related tools

• /tools/mixing-dilution — the two-component version of a blending problem; LP is what you reach for once there are more than two ingredients and a real cost to minimize.
• /tools/link-budget — allocating gain and loss across an RF chain is a budget-allocation cousin of LP's resource constraints.

Sources

1. https://en.wikipedia.org/wiki/Linear_programming
2. https://www.nobelprize.org/prizes/economic-sciences/1975/summary/
3. https://www.engineering.iastate.edu/~jdm/ee458/DantzigHistoryLP.pdf
4. https://www.nobelprize.org/prizes/economic-sciences/1975/press-release/
5. https://mathworld.wolfram.com/InteriorPointMethod.html
6. https://en.wikipedia.org/wiki/Ellipsoid_method — Khachiyan, L.G. (1979), "A polynomial algorithm in linear programming," Soviet Mathematics Doklady 20:191–194
7. https://en.wikipedia.org/wiki/Karmarkar%27s_algorithm — Karmarkar, N. (1984), "A new polynomial-time algorithm for linear programming," Combinatorica 4(4):373–395, doi:10.1007/BF02579150