Linear Programming

⚡ Key Takeaways

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).

💡 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.

DefinitionLinear Program — Standard Forms

A linear program in standard (canonical) inequality form is

1

\quad \max_{x \in \mathbb{R}^n}\ c^\top x \quad \text{subject to} \quad Ax \le b,\ \ x \ge 0.

Derivation hint: $c$ is the cost/profit vector, $A \in \mathbb{R}^{m\times n}$ the constraint matrix, $b \in \mathbb{R}^m$ the resource vector; each row $a_i^\top x \le b_i$ is a halfspace. An equivalent standard equality form (used by the simplex method) is

2

\quad \min_{x \in \mathbb{R}^n}\ c^\top x \quad \text{subject to} \quad Ax = b,\ \ x \ge 0.

Derivation hint: convert $a_i^\top x \le b_i$ to $a_i^\top x + s_i = b_i,\ s_i \ge 0$ by adding a slack variable $s_i$ ; maximize $c^\top x \equiv$ minimize $-c^\top x$ .

Symbols: $x$ = decision variables; $c \in \mathbb{R}^n$ = objective coefficients; $A$ = $m \times n$ constraint matrix; $b \in \mathbb{R}^m$ = right-hand sides; $s$ = slack variables. The feasible region is $P = \{x : Ax \le b,\ x \ge 0\}$ , a convex polyhedron.

DefinitionVertex / Extreme Point / Basic Feasible Solution

A point $x \in P$ is a vertex (extreme point) if it cannot be written as $x = \tfrac12(u+v)$ with $u \ne 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

3

\quad x_B = B^{-1} b \ \ge 0, \qquad x_N = 0.

Derivation hint: partition $A=[B\ N]$ , $x=(x_B,x_N)$ ; $Ax=b \Rightarrow Bx_B + Nx_N = b$ ; set $x_N=0$ and invert $B$ ; feasibility requires $x_B \ge 0$ .

TheoremFundamental Theorem of Linear Programming

For an LP in standard form with feasible region $P \ne \varnothing$ : 1. If the objective is bounded on $P$ , an optimal solution exists and at least one optimal solution is a vertex of $P$ . 2. If $P$ has at least one vertex (e.g., when $x \ge 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.

TheoremStrong Duality

The primal $\max\{c^\top x : Ax \le b,\ x \ge 0\}$ and its dual

4

\quad \min_{y \in \mathbb{R}^m}\ b^\top y \quad \text{subject to} \quad A^\top y \ge c,\ \ y \ge 0

satisfy: if either has a finite optimum, so does the other and their optimal values are equal, $c^\top x^\star = b^\top y^\star$ . Derivation hint: dual variables $y_i \ge 0$ price each primal constraint; requiring the priced combination $A^\top y$ to dominate $c$ produces an upper bound $b^\top y$ on $c^\top x$ ; strong duality says the best bound is tight.

ProofWeak Duality, then the Optimality Gap

Step 1 (Weak duality). Let $x$ be primal-feasible ( $Ax \le b,\ x \ge 0$ ) and $y$ dual-feasible ( $A^\top y \ge c,\ y \ge 0$ ). Then

5

\quad c^\top x \ \le\ (A^\top y)^\top x \ =\ y^\top (A x) \ \le\ y^\top b \ =\ b^\top y.

Derivation hint: first inequality uses $c \le A^\top y$ and $x \ge 0$ ; second uses $Ax \le b$ and $y \ge 0$ .

Step 2 (Bound). Equation [5] shows every primal value $\le$ every dual value; hence $\max c^\top x \le \min b^\top y$ . The difference $b^\top y - c^\top x \ge 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^\star$ that is dual-feasible and achieves $b^\top y^\star = c^\top x^\star$ , closing the gap to zero. The existence of $y^\star$ follows from Farkas' Lemma, a theorem of the alternative for linear systems.

∎

TheoremFarkas' Lemma

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

6

\quad \exists\, x \ge 0:\ Ax = b \qquad \textbf{XOR} \qquad \exists\, y:\ A^\top y \ge 0,\ b^\top y < 0.

Derivation hint: geometrically, either $b$ lies in the convex cone generated by columns of $A$ , or a separating hyperplane $y$ strictly separates $b$ from that cone.

ProofComplementary Slackness

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

7

\quad y_i^\star\,(b_i - a_i^\top x^\star) = 0 \quad\text{and}\quad x_j^\star\,(A^\top y^\star - c)_j = 0 \ \ \forall i,j.

Derivation hint: 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^\top x^\star > 0$ ), its shadow price $y_i^\star = 0$ ; if a variable is used ( $x_j^\star > 0$ ), its dual constraint is tight. This couples primal and dual solutions exactly.

∎

mathematician · 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.

🧠 Intuition

Picture the feasible region as a cut diamond floating in space, and the objective $c^\top 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.

Figure

Feasible polyhedron with objective contours; optimum at a vertex

```svg

```

ExampleFurniture Factory — Maximize Profit

A workshop makes tables ( $x_1$ ) and chairs ( $x_2$ ). Profit: $30 per table, $20 per chair. Constraints: wood $4x_1 + 2x_2 \le 100$ (board-feet), labor $2x_1 + 4x_2 \le 80$ (hours), $x_1,x_2 \ge 0$ .

LP: $\max\ 30x_1 + 20x_2$ s.t. $4x_1+2x_2 \le 100,\ 2x_1+4x_2 \le 80,\ x \ge 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 $4x_1+2x_2=100,\ 2x_1+4x_2=80$ .

From these: multiply 2nd by 2 → $4x_1+8x_2=160$ ; subtract 1st → $6x_2=60 \Rightarrow x_2=10$ , then $4x_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)$ .

\boxed{x^\star=(20,10),\quad \text{max profit} = \$800}

Dual check (shadow prices): solving the dual gives $y^\star_{\text{wood}}=\$7,\ y^\star_{\text{labor}}=\$1$ per unit; $b^\top y = 100(7)+80(1)=780$ ... recompute correctly: dual binding gives $4y_1+2y_2=30,\ 2y_1+4y_2=20 \Rightarrow y_1=\$\tfrac{40}{6}\approx 6.67,\ y_2=\$\tfrac{10}{6}\approx1.67$ ; $b^\top y=100(6.67)+80(1.67)=667+133=\$800.$ ✓ (matches primal).

ExampleDiet Problem — Minimize Cost

Meet daily needs of $\ge 8$ units protein and $\ge 6$ units vitamin from two foods. Food A: 2 protein, 1 vitamin, $3/kg. Food B: 1 protein, 3 vitamin, $2/kg.

LP: $\min\ 3x_A + 2x_B$ s.t. $2x_A + x_B \ge 8,\ x_A + 3x_B \ge 6,\ x \ge 0.$

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

$(x_A,x_B)=(4,0)$ : protein $2(4)=8$ ✓, vitamin $4 \ge 6$ ? No, $4<6$ → infeasible.
$(0,8)$ : vitamin $24\ge6$ ✓, protein $8\ge8$ ✓; cost $2(8)=16$ .
$(6,0)$ : protein $12$ ✓, vitamin $6$ ✓; cost $3(6)=18$ .
Intersection of both binding: $2x_A+x_B=8,\ x_A+3x_B=6 \Rightarrow$ from 1st $x_B=8-2x_A$ ; sub: $x_A+3(8-2x_A)=6 \Rightarrow x_A+24-6x_A=6 \Rightarrow -5x_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$ .

\boxed{x^\star=(3.6,\ 0.8)\ \text{kg},\quad \text{min cost} = \$12.40/\text{day}}

⚠️ Common mistake

"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 $\mathbb{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."

CounterexampleGeometry breaks for non-vertex search

Consider $\max\ x_1 + x_2$ subject to $x_1 + x_2 \le 1,\ x \ge 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 $(\tfrac12,\tfrac12)$ , is optimal. The Fundamental Theorem still holds (at least one optimum is a vertex), but uniqueness fails. Worse, replacing $\le$ by $<$ (strict inequality) makes the supremum $1$ unattained — LP theory requires closed feasible sets.

connection

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.

🔬 Where this appears

⏳ History

- 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.

open-problem

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.

Formal Statement

Why It Holds / Derivation

Building Intuition

Worked Examples

Common Misconceptions

Connections

Real-World Applications

Historical Development

Subtleties & Limits

See Also