Linear Programming: How Math Optimizes Almost Everything

Imagine you run a small bakery. You bake bread and cookies. Each bread loaf takes 1 cup of flour and 30 minutes of oven time, and you sell it for $3. Each batch of cookies takes 2 cups of flour and 10 minutes of oven time, and you sell it for$4. You have 50 cups of flour and 8 hours of oven time. How many of each should you make to maximize revenue?

This is a linear programming problem. You’re maximizing a linear function (revenue) subject to linear constraints (flour and time). The variables (number of breads, number of cookies) are continuous, and the answer turns out to be the coordinates of a corner of the feasible region in some many-dimensional space.

If your bakery had only two products, you could draw the problem on graph paper and solve it visually. With ten products, the geometry is in 10-dimensional space and you need an algorithm. With ten thousand variables — typical of real industrial problems — you need a serious computational tool.

That tool is the simplex method, invented by George Dantzig in 1947, and the broader field of linear programming (LP) is now one of the most important applied branches of mathematics. Every airline schedule, every refinery operation, every supply-chain optimization quietly runs on linear programming. This article is about what it is, how it works, and why it’s everywhere.

The standard form

A linear program (in standard form) has:

Variables: $x_1, x_2, \ldots, x_n \geq 0$ (real-valued, non-negative)

Objective: Maximize (or minimize) some linear combination

$\text{maximize } c_1 x_1 + c_2 x_2 + \cdots + c_n x_n$

Constraints: A list of linear inequalities

$a_{11} x_1 + a_{12} x_2 + \cdots + a_{1n} x_n \leq b_1$ $a_{21} x_1 + a_{22} x_2 + \cdots + a_{2n} x_n \leq b_2$ $\vdots$ $a_{m1} x_1 + a_{m2} x_2 + \cdots + a_{mn} x_n \leq b_m$

That’s it. The whole problem fits in one matrix-vector form:

$\text{maximize } \mathbf{c}^T \mathbf{x} \quad \text{subject to} \quad A\mathbf{x} \leq \mathbf{b}, \quad \mathbf{x} \geq 0.$

What makes LP useful is the rich variety of problems that fit this template. The bakery example is one. Mixing alloys to specifications is another. Routing trucks through a network. Allocating advertising budgets. Designing animal feed mixtures. Managing investment portfolios. Each translates into the same linear framework.

The geometry

Geometrically, the constraints define a polyhedron — the intersection of finitely many half-spaces in $\mathbb{R}^n$. The set of feasible solutions is everything inside this polyhedron (and on its boundary). The objective function is linear, so its level sets are parallel hyperplanes.

Maximizing the objective over a polyhedron has a key property: the optimum (if it exists) is always achieved at a vertex of the polyhedron. You don’t need to search the interior. There are only finitely many vertices, and the optimum is one of them.

For a 2D problem, the polyhedron is a polygon, and the vertices are corners. You can literally see which corner maximizes the objective. For high-dimensional problems, the polyhedron has exponentially many vertices in principle — checking them all is impractical. But the geometric insight remains: the answer is at a vertex.

This is what the simplex method exploits.

The simplex method

George Dantzig invented the simplex method in 1947 while working for the U.S. Air Force on military planning problems. The method is a vertex-walking algorithm:

1. Start at any vertex of the feasible polyhedron.
2. Look at the adjacent vertices. Is any of them better (higher objective value)?
3. If yes, move to a better adjacent vertex.
4. Repeat until no adjacent vertex is better. That vertex is optimal.

This is local search through vertex space. Each step is well-defined algebraically — the simplex method tracks which constraints are “tight” (active equalities) at the current vertex and pivots to change which constraint becomes tight.

The simplex method has a remarkable property: in practice it runs very fast. For typical problems with $m$ constraints and $n$ variables, it terminates in roughly $O(m \log m)$ or $O(mn)$ pivots. Industrial implementations solve problems with millions of variables in seconds.

But in worst case, the simplex method is exponential. The Klee-Minty cube (1972) is an adversarial polyhedron where the simplex method must visit all $2^n$ vertices. So worst-case complexity is bad — but worst case essentially never appears on real problems. This is one of the more striking gaps between theoretical worst-case analysis and practical algorithm behavior.

Better algorithms?

The exponential worst case bothered theorists for decades. In 1979, Leonid Khachiyan published the ellipsoid method — a polynomial-time algorithm for linear programming. This was a major theoretical breakthrough, but the algorithm is slow in practice and was almost immediately replaced for practical use.

In 1984, Narendra Karmarkar at Bell Labs published an interior-point method that was both theoretically polynomial and practically fast. Karmarkar’s announcement made front-page news in The New York Times — unusual for an algorithm. Modern LP solvers use a mix of simplex and interior-point methods, with the interior-point methods often winning for very large problems.

So linear programming has three families of algorithms:

• Simplex (Dantzig 1947) — fast in practice, exponential worst case.
• Ellipsoid (Khachiyan 1979) — polynomial worst case, slow in practice.
• Interior-point (Karmarkar 1984) — polynomial worst case, fast in practice.

For most real problems, modern solvers like Gurobi, CPLEX, and the open-source HiGHS use both simplex and interior-point, choosing whichever runs faster on the specific problem. The combined practical state of LP-solving is mature and astonishingly capable.

Duality

A deep mathematical feature of linear programming is duality. Every LP has a dual LP, formed by transposing the matrix and swapping rows with columns. The original (primal) is “maximize subject to constraints.” The dual is “minimize subject to constraints” with the matrix transposed.

The strong duality theorem states: if either the primal or the dual has an optimal solution, then both do, and their optimal objective values are equal.

This isn’t just a curiosity. Duality has practical and conceptual importance:

• Sensitivity analysis. The optimal dual variables represent “shadow prices” — how much the optimal objective would change if a constraint were slightly relaxed. This is used everywhere in economics and engineering for what-if analysis.
• Algorithm design. The simplex method can pivot on the primal or the dual; interior-point methods solve both simultaneously. Which is faster depends on the problem.
• Verification. A claimed optimal solution can be verified by exhibiting a feasible dual solution with the same objective value.

LP duality is also a special case of more general duality theories in convex optimization, semidefinite programming, and conic optimization. It’s one of the unifying mathematical concepts in modern optimization theory.

Where LP is actually used

The applications of linear programming are enormous. A small sample:

Airlines. Airlines run massive LPs to schedule flights, assign aircraft types to routes, schedule crews, and price tickets. American Airlines famously credits revenue management LP with saving them billions annually. The “yield management” pricing you see on airline websites is the visible output of this background optimization.

Petroleum refining. A refinery takes crude oil and produces gasoline, diesel, jet fuel, and dozens of byproducts. The mix is governed by an LP that accounts for prices, demand, refinery capacity, and chemical constraints. ExxonMobil and Shell have run LP-based optimizers for half a century.

Manufacturing. Production planning across multiple factories with multiple products and material constraints is an LP. Companies like Ford, GM, and most large manufacturers run such optimizers continuously.

Logistics. Routing trucks, scheduling deliveries, assigning warehouses to retail outlets — all variants of LP. UPS, FedEx, and Amazon have entire teams whose job is to formulate and solve these problems.

Telecommunications. Routing internet packets, allocating bandwidth, designing network topologies — many of these reduce to LPs or close relatives.

Diet and feed mixing. Animal feed manufacturers solve LPs daily to find the cheapest mixture of ingredients meeting nutritional requirements. The “Stigler diet problem” — what’s the cheapest diet meeting human nutritional needs? — was one of the early test problems for LP and is still used as a benchmark.

Sports scheduling. Major League Baseball, the NFL, and the NBA all use LPs to construct their season schedules, balancing travel costs, broadcast requirements, and competitive fairness.

Financial portfolios. Markowitz’s portfolio optimization is a quadratic program, but its linear approximations are widely used. So is LP-based asset-liability matching for insurance companies and pension funds.

The total economic impact of linear programming is in the trillions of dollars annually. It’s not glamorous, but it’s everywhere.

Why this is the right framework

Why does a 1940s mathematical technique remain so useful?

The answer is that linearity is a remarkably good approximation for many real problems, and the corresponding mathematics is unusually clean.

For real-world problems, doubling the inputs often doubles the outputs (linearity). Constraints often combine additively (also linear). Objective functions are often well-approximated as linear over the feasible range. So real problems often fit the LP template natively.

When they don’t — when costs are nonlinear, when variables must be integers, when constraints have logical structure — practitioners use modifications: integer programming, mixed-integer programming, quadratic programming, nonlinear programming. Each is harder than LP. But often, the right approach is to start with an LP relaxation, get a good answer fast, then refine with the harder methods.

The deeper lesson

Linear programming illustrates several lessons that recur in applied mathematics:

Geometry illuminates algebra. The simplex method’s correctness depends on the geometric fact that LP optima lie at polyhedral vertices. Without this geometric insight, the algorithm would be much harder to understand or analyze.

Worst-case theory and practical performance can diverge. Simplex is exponential in the worst case but runs fast on real problems. This pattern repeats throughout algorithmic theory and is a persistent reminder that “the worst case” isn’t always what matters.

Duality is everywhere. The primal-dual relationship in LP is a special case of a general phenomenon in optimization, mathematical physics, and economics. Wherever you find an optimization problem, look for the dual — it usually exists and reveals structure.

Linearity is a powerful approximation. Real problems are rarely truly linear, but linear models often capture enough of the structure to be useful. This is one of the recurring miracles of applied mathematics, related to the Central Limit Theorem (which is why averages often look Gaussian) and the broader phenomenon of “near-linearity” in physical systems.

George Dantzig once said that he was given a problem in 1947 that someone told him couldn’t be solved efficiently — and he didn’t know enough to be intimidated, so he solved it. The simplex method came out of that work. Almost 80 years later, his algorithm is still running on more computers, optimizing more economic activity, than any other algorithm in mathematics.

When you fly somewhere, eat manufactured food, drive a car, use the internet, or buy almost anything from a global supply chain, linear programming is somewhere in the background, deciding how that activity should be efficiently routed. It’s one of the great quiet successes of 20th-century applied mathematics — and one most people use every day without ever knowing it exists.

Frequently asked

Is linear programming really used everywhere?

Yes. Airlines schedule flights and crews using linear programming. Oil refineries decide what to produce. Hospitals schedule doctors. Manufacturers plan production. Internet routers route packets. Stock portfolios are sometimes optimized by linear programming. Trillions of dollars of economic activity is governed daily by these algorithms running quietly in the background.

Why is the simplex method 'fast' if it's exponential in the worst case?

Worst-case theory and average-case practice diverge here. In theory, the simplex method can take exponential time on adversarially constructed examples. In practice, on real-world problems, it almost always runs in polynomial time — typically linear or quadratic in the size of the problem. This is one of the most striking gaps between worst-case complexity and observed behavior in any algorithm.

Are there problems linear programming can't solve?

Yes. Linear programming requires the objective function and constraints to be linear. Many real problems involve nonlinear costs, integer-valued variables, combinatorial constraints, or stochastic uncertainty. These extensions (integer programming, nonlinear programming, stochastic programming) are dramatically harder — integer programming is NP-hard. Practical optimizers use a mix of techniques.

Continue reading

Blog

Dynamic Programming: Solving Hard Problems by Remembering Easy Ones

Many problems repeat the same subproblems over and over. Storing each answer the first time you compute it can turn an exponential algorithm into a polynomial one — sometimes a stunning speedup.

Read →Blog

Chaos Theory and the Butterfly Effect

A weather model from 1963 produced wildly different forecasts from nearly identical inputs. The phenomenon Lorenz discovered changed how scientists think about prediction itself.

Read →Blog

Markov Chains: Probability With No Memory

Card shuffling, weather patterns, web surfing, and language models all follow the same mathematical structure: random sequences where the next state depends only on the current one.

Read →