Linear Programming

Linear Programming (LP) is the optimization of a linear objective function subject to linear equality and inequality constraints. Key result: an LP either is infeasible, is unbounded, or attains its optimum at a vertex (extreme point) of its feasible polyhedron — and this optimum is found efficiently by the simplex method or interior-point methods. Applies to: resource allocation, scheduling, transportation, network flows, game theory, and as a relaxation for integer problems. Who/when: formalized by George Dantzig (simplex method, 1947); foundations by Kantorovich (1939) and von Neumann (duality, 1947).

A linear program seeks to maximize or minimize a linear function $c^{⊤} x$ over a set of decision variables $x \in R^{n}$ constrained by finitely many linear inequalities and equalities, which together carve out a convex polyhedron. LP matters because it is the simplest nontrivial class of constrained optimization that is both expressive enough to model thousands of real decisions and tractable enough to solve at enormous scale (millions of variables). The surprising fact is duality: every LP has a "shadow" partner LP whose optimal value exactly equals the original's, turning prices and constraints into a perfectly symmetric pair. This makes LP the cornerstone of operations research, the basis for integer-programming relaxations, and a recurring tool across economics, engineering, and machine learning.

The Core Insight

The feasible region of an LP is a convex polyhedron, and a linear objective is constant along directions and increases linearly across the region. Therefore, if an optimum exists, you can always slide to a corner (vertex) without decreasing the objective. The whole theory reduces to: (1) the geometry of polyhedra, and (2) strong duality, which says the best you can achieve equals the tightest bound the constraints can certify against you.

Formal Statement

Linear Program — Standard Forms

A linear program in standard (canonical) inequality form is

x \in R^{n} max c^{⊤} x subject to A x \leq b, x \geq 0.

⟳

c

is the cost/profit vector,

A \in R^{m \times n}

the constraint matrix,

b \in R^{m}

the resource vector; each row

a_{i}^{⊤} x \leq b_{i}

is a halfspace.

An equivalent standard equality form (used by the simplex method) is

x \in R^{n} min c^{⊤} x subject to A x = b, x \geq 0.

⟳convert

a_{i}^{⊤} x \leq b_{i}

a_{i}^{⊤} x + s_{i} = b_{i}, s_{i} \geq 0

by adding a slack variable

s_{i}

; maximize

c^{⊤} x \equiv

minimize

- c^{⊤} x

Symbols:

x

= decision variables;

c \in R^{n}

= objective coefficients;

A

m \times n

constraint matrix;

b \in R^{m}

= right-hand sides;

s

= slack variables. The feasible region is

P = {x : A x \leq b, x \geq 0}

, a convex polyhedron.

Vertex / Extreme Point / Basic Feasible Solution

A point $x \in P$ is a vertex (extreme point) if it cannot be written as $x = \frac{1}{2} (u + v)$ with $u \neq = v$ both in $P$ . Equivalently, in equality form with $A$ of rank $m$ , a basic feasible solution (BFS) chooses $m$ linearly independent columns of $A$ (the basis $B$ ), sets the other (nonbasic) variables to $0$ , and solves

x_{B} = B^{- 1} b \geq 0, x_{N} = 0.

⟳partition

A = [B N]

x = (x_{B}, x_{N})

;

A x = b \Rightarrow B x_{B} + N x_{N} = b

; set

x_{N} = 0

and invert

B

; feasibility requires

x_{B} \geq 0

Fundamental Theorem of Linear Programming

For an LP in standard form with feasible region $P \neq = \emptyset$ :

If the objective is bounded on $P$ , an optimal solution exists and at least one optimal solution is a vertex of $P$ .
If $P$ has at least one vertex (e.g., when $x \geq 0$ ), then the optimum (if finite) is attained at a vertex.

Consequently, optimization over an infinite set $P$ reduces to searching the finite set of vertices.

Strong Duality

The primal $max {c^{⊤} x : A x \leq b, x \geq 0}$ and its dual

y \in R^{m} min b^{⊤} y subject to A^{⊤} y \geq c, y \geq 0

satisfy: if either has a finite optimum, so does the other and their optimal values are equal,

c^{⊤} x^{⋆} = b^{⊤} y^{⋆}

⟳dual variables

y_{i} \geq 0

price each primal constraint; requiring the priced combination

A^{⊤} y

to dominate

c

produces an upper bound

b^{⊤} y

c^{⊤} x

; strong duality says the best bound is tight.

Why It Holds / Derivation

Weak Duality, then the Optimality Gap

Step 1 (Weak duality). Let

x

be primal-feasible (

A x \leq b, x \geq 0

) and

y

dual-feasible (

A^{⊤} y \geq c, y \geq 0

). Then

c^{⊤} x \leq (A^{⊤} y)^{⊤} x = y^{⊤} (A x) \leq y^{⊤} b = b^{⊤} y .

⟳first inequality uses

c \leq A^{⊤} y

and

x \geq 0

; second uses

A x \leq b

and

y \geq 0

Step 2 (Bound). Equation [5] shows every primal value

\leq

every dual value; hence

max c^{⊤} x \leq min b^{⊤} y

. The difference

b^{⊤} y - c^{⊤} x \geq 0

is the duality gap. Step 3 (Strong duality via Farkas / separation). If the primal optimum is finite, the supporting hyperplane at the optimal vertex furnishes a

y^{⋆}

that is dual-feasible and achieves

b^{⊤} y^{⋆} = c^{⊤} x^{⋆}

, closing the gap to zero. The existence of

y^{⋆}

follows from Farkas' Lemma, a theorem of the alternative for linear systems.

Farkas' Lemma

Exactly one of the following holds for $A \in R^{m \times n}$ , $b \in R^{m}$ :

\exists x \geq 0 : A x = b XOR \exists y : A^{⊤} y \geq 0, b^{⊤} y < 0.

⟳geometrically, either

b

lies in the convex cone generated by columns of

A

, or a separating hyperplane

y

strictly separates

b

from that cone.

Complementary Slackness

At optimality, $x^{⋆}$ and $y^{⋆}$ satisfy: from Step 1 the two inequalities in [5] must be equalities. Equality of the second forces

y_{i}^{⋆} (b_{i} - a_{i}^{⊤} x^{⋆}) = 0 and x_{j}^{⋆} (A^{⊤} y^{⋆} - c)_{j} = 0 \forall i, j .

⟳a sum of nonnegative terms equals zero iff each term is zero; each product pairs a primal slack with its dual variable (and vice versa).

Interpretation: if a constraint is slack (

b_{i} - a_{i}^{⊤} x^{⋆} > 0

), its shadow price

y_{i}^{⋆} = 0

; if a variable is used (

x_{j}^{⋆} > 0

), its dual constraint is tight. This couples primal and dual solutions exactly.

George B. Dantzig | 1914–2005

Dantzig invented the simplex method in 1947 while working for the U.S. Air Force on planning ("programming") logistics — the word "programming" here means scheduling, not coding. He famously, as a graduate student, mistook two open problems written on a blackboard for homework and solved them. Dantzig formalized LP as a discipline, recognized the role of duality (in dialogue with von Neumann), and made large-scale planning computationally feasible. His simplex method remains, decades later, one of the most-used algorithms in the world.

Building Intuition

Picture the feasible region as a cut diamond floating in space, and the objective $c^{⊤} x$ as a flat sheet you push in the direction $c$ . You slide the sheet as far as it can go while still touching the diamond — it will rest against a face, and the last point of contact is a corner. That is why optima live at vertices. The dual is the same picture viewed from outside: each constraint is a wall, and the dual asks for the cheapest combination of wall-pressures that pins down the objective from above. Strong duality says "the corner you reach from inside" and "the cheapest certificate from outside" meet at exactly the same number.

Feasible polyhedron with objective contours; optimum at a vertex

<svg viewBox="0 0 460 340" xmlns="http://www.w3.org/2000/svg">
<rect width="460" height="340" fill="#0a0e17"/>
<!-- axes -->
<line x1="50" y1="300" x2="430" y2="300" stroke="#94a3b8" stroke-width="1.5"/>
<line x1="50" y1="300" x2="50" y2="30" stroke="#94a3b8" stroke-width="1.5"/>
<text x="420" y="318" fill="#e2e8f0" font-size="13">x₁</text>
<text x="28" y="40" fill="#e2e8f0" font-size="13">x₂</text>
<!-- feasible polygon -->
<polygon points="50,300 50,150 130,90 280,140 320,300" fill="#1e293b" stroke="#94a3b8" stroke-width="1.5" opacity="0.85"/>
<text x="150" y="230" fill="#e2e8f0" font-size="13">feasible P</text>
<!-- constraint labels -->
<text x="60" y="120" fill="#94a3b8" font-size="11">a₁·x ≤ b₁</text>
<text x="290" y="200" fill="#94a3b8" font-size="11">a₂·x ≤ b₂</text>
<!-- objective contours (key curve color) -->
<line x1="60" y1="300" x2="200" y2="40" stroke="#d4a853" stroke-width="1.3" stroke-dasharray="5,4"/>
<line x1="130" y1="300" x2="270" y2="40" stroke="#d4a853" stroke-width="1.3" stroke-dasharray="5,4"/>
<line x1="200" y1="300" x2="340" y2="40" stroke="#d4a853" stroke-width="2"/>
<text x="345" y="55" fill="#d4a853" font-size="12">c·x increases →</text>
<!-- optimal vertex -->
<circle cx="280" cy="140" r="6" fill="#d4a853" stroke="#e2e8f0" stroke-width="1.5"/>
<text x="288" y="135" fill="#e2e8f0" font-size="12">optimum x*</text>
</svg>

Worked Examples

Furniture Factory — Maximize Profit

A workshop makes tables ( $x_{1}$ ) and chairs ( $x_{2}$ ). Profit: \ $30 p er t ab l e,$ 20 per chair. Constraints: wood $4 x_{1} + 2 x_{2} \leq 100$ (board-feet), labor $2 x_{1} + 4 x_{2} \leq 80$ (hours), $x_{1}, x_{2} \geq 0$ .

LP:

max 30 x_{1} + 20 x_{2}

s.t.

4 x_{1} + 2 x_{2} \leq 100, 2 x_{1} + 4 x_{2} \leq 80, x \geq 0.

Step 1 — find vertices (intersections of binding constraints):

$(0, 0)$ : profit $0$ .
$(25, 0)$ (wood binds, $x_{2} = 0$ ): $30 (25) = 750$ .
$(0, 20)$ (labor binds, $x_{1} = 0$ ): $20 (20) = 400$ .
Intersection of both: solve $4 x_{1} + 2 x_{2} = 100, 2 x_{1} + 4 x_{2} = 80$ .

From these: multiply 2nd by 2 →

4 x_{1} + 8 x_{2} = 160

; subtract 1st →

6 x_{2} = 60 \Rightarrow x_{2} = 10

, then

4 x_{1} + 20 = 100 \Rightarrow x_{1} = 20

. Profit

= 30 (20) + 20 (10) = 600 + 200 = 800

. Step 2 — compare:

{0, 750, 400, 800}

; the maximum is at

(20, 10)

x^{⋆} = (20, 10), max profit = $800

Dual check (shadow prices): solving the dual gives

y_{wood}^{⋆} =

7,\ y^\star_{\text{labor}}=\

1

per unit;

b^{⊤} y = 100 (7) + 80 (1) = 780

... recompute correctly: dual binding gives

4 y_{1} + 2 y_{2} = 30, 2 y_{1} + 4 y_{2} = 20 \Rightarrow y_{1} =

\tfrac{40}{6}\approx 6.67,\ y_2=\

\frac{10}{6} \approx 1.67

;

b^{⊤} y = 100 (6.67) + 80 (1.67) = 667 + 133 =

800.$ ✓ (matches primal).

Diet Problem — Minimize Cost

Meet daily needs of $\geq 8$ units protein and $\geq 6$ units vitamin from two foods. Food A: 2 protein, 1 vitamin, \ $3/ k g . F oo d B : 1 p r o t e in, 3 v i t amin,$ 2/kg.

LP:

min 3 x_{A} + 2 x_{B}

s.t.

2 x_{A} + x_{B} \geq 8, x_{A} + 3 x_{B} \geq 6, x \geq 0.

Step 1 — candidate vertices of the feasible (upper) region:

$(x_{A}, x_{B}) = (4, 0)$ : protein $2 (4) = 8$ ✓, vitamin $4 \geq 6$ ? No, $4 < 6$ → infeasible.
$(0, 8)$ : vitamin $24 \geq 6$ ✓, protein $8 \geq 8$ ✓; cost $2 (8) = 16$ .
$(6, 0)$ : protein $12$ ✓, vitamin $6$ ✓; cost $3 (6) = 18$ .
Intersection of both binding: $2 x_{A} + x_{B} = 8, x_{A} + 3 x_{B} = 6 \Rightarrow$ from 1st $x_{B} = 8 - 2 x_{A}$ ; sub: $x_{A} + 3 (8 - 2 x_{A}) = 6 \Rightarrow x_{A} + 24 - 6 x_{A} = 6 \Rightarrow - 5 x_{A} = - 18 \Rightarrow x_{A} = 3.6, x_{B} = 0.8$ ; cost $3 (3.6) + 2 (0.8) = 10.8 + 1.6 = 12.4$ .

Step 2 — compare feasible vertices

{16, 18, 12.4}

: minimum is

12.4

x^{⋆} = (3.6, 0.8) kg, min cost = $12.40/ day

Common Misconceptions

"The optimum is always unique." False. If the objective vector

c

is parallel to a face of the polyhedron, an entire edge or face of optimal points exists (infinitely many optima). Also, degenerate vertices (more than

n

binding constraints in

R^{n}

) can stall the simplex method and require anti-cycling rules (e.g., Bland's rule). Finally, LP can be unbounded (objective

\to \pm \infty

) or infeasible (empty

P

); always check these before claiming "no solution at the corners."

Geometry breaks for non-vertex search

Consider $max x_{1} + x_{2}$ subject to $x_{1} + x_{2} \leq 1, x \geq 0$ . The objective is constant ( $= 1$ ) along the entire top edge from $(1, 0)$ to $(0, 1)$ . Searching only interior points or expecting a single corner answer is wrong — every point on that segment, including the midpoint $(\frac{1}{2}, \frac{1}{2})$ , is optimal. The Fundamental Theorem still holds (at least one optimum is a vertex), but uniqueness fails. Worse, replacing $\leq$ by $<$ (strict inequality) makes the supremum $1$ unattained — LP theory requires closed feasible sets.

Connections

LP sits at the crossroads of several fields. It is the foundational case of Convex Optimization — every LP is convex, so local optima are global. Its duality generalizes to Lagrangian Duality and is mirrored in the minimax theorem of Game Theory (von Neumann's zero-sum games reduce to a pair of dual LPs). Restricting variables to integers yields Integer Programming, where the LP relaxation provides crucial bounds for branch-and-bound. Network problems — shortest paths, max-flow/min-cut, assignment — are special LPs with totally unimodular matrices guaranteeing integer vertices, linking LP to Combinatorial Optimization and the Max-Flow Min-Cut Theorem. The geometry rests on Convex Polyhedra and separating-hyperplane theorems.

Real-World Applications

Airline crew & fleet scheduling — assigning crews and aircraft to flights minimizing cost while honoring rest rules (American Airlines' decision-support systems save hundreds of millions annually).
Petroleum refining & blending — choosing crude mixes and product yields to maximize margin under capacity and quality specs (the original 1950s industrial driver of LP).
Transportation & logistics — the transportation problem routes goods from warehouses to stores at minimum cost; underlies supply-chain planning at Amazon, UPS, FedEx.
Diet & agriculture — Stigler's diet problem and modern feed-formulation for livestock minimize cost subject to nutritional requirements.
Portfolio & finance — linear risk-budget and cash-flow matching models; LP relaxations in index tracking.
Telecom & power-grid routing — bandwidth allocation, optimal power flow approximations, and capacity planning.
Machine learning — support-vector-machine variants ( $ℓ_{1}$ SVM), LP-based robust regression, and optimal transport (a giant LP) for distribution comparison.

Historical Development

1827 — Fourier studies systems of linear inequalities (Fourier–Motzkin elimination), an early ancestor of LP feasibility.
1939 — Leonid Kantorovich formulates production-planning as linear optimization in the USSR; later shares the 1975 Nobel Prize in Economics.
1941 — Frank Hitchcock states the transportation problem in modern form.
1947 — George Dantzig invents the simplex method; John von Neumann articulates LP duality and links it to game theory.
1947–49 — Tjalling Koopmans develops activity-analysis economics on LP foundations (Nobel 1975 with Kantorovich).
1958 — Gomory introduces cutting planes, bridging LP to integer programming.
1972 — Klee and Minty construct a polytope on which simplex takes exponential time in the worst case.
1979 — Leonid Khachiyan's ellipsoid method proves LP is solvable in polynomial time (first such result).
1984 — Narendra Karmarkar's interior-point method delivers polynomial time and practical speed, revolutionizing large-scale LP.

Subtleties & Limits

Is there a strongly polynomial algorithm for LP? Current polynomial methods (ellipsoid, interior-point) run in time depending on the bit-length of the data, not purely on the dimensions

m, n

. Whether an algorithm exists whose arithmetic-operation count is bounded by a polynomial in

m

and

n

alone — independent of the size of the numbers — is a famous open question (related to Smale's 9th problem). Connected to this is the diameter of polytopes: the Hirsch conjecture (that the graph diameter of a

d

-dimensional polytope with

n

facets is at most

n - d

) was disproved by Santos in 2012, yet the true polynomial-diameter question (the polynomial Hirsch conjecture) remains open — and a positive answer could yield a polynomial-pivot simplex variant. Whether simplex with some pivot rule runs in polynomial time is likewise unresolved.