Linear Programming — Mathematics Knowledge System

Overview

Linear programming (LP) is the problem of optimizing a linear objective function subject to linear equality and inequality constraints. It is one of the most widely applied mathematical techniques, with applications in operations research, economics, logistics, telecommunications, and manufacturing. The feasible region of an LP is a convex polytope, and the optimal value — if finite — is always achieved at a vertex (extreme point) of that polytope.

Intuition

Linear programming is about finding the corner of a polygon (or polytope in higher dimensions) that maximises a linear 'score'. The feasible region is a convex polytope, and the linear objective tilts a hyperplane until it just touches the polytope — the touching point is optimal.

Formal Definition

Definition

The standard form of a linear program is:

\begin{aligned} \min_{x \in \mathbb{R}^n} \quad & c^T x \\ \text{s.t.} \quad & Ax = b \\ & x \ge 0 \end{aligned}

Standard form LP

\begin{aligned} \min_{x} \quad & c^T x \\ \text{s.t.} \quad & Ax \le b \end{aligned}

Inequality form LP

\text{Feasible region: } \mathcal{P} = \{x \ge 0 : Ax = b\} \text{ (a convex polytope)}

Feasible polytope

Notation

Notation	Meaning
$c \in \mathbb{R}^n$	Cost (objective) vector
$A \in \mathbb{R}^{m \times n}$	Constraint matrix
$b \in \mathbb{R}^m$	Right-hand side vector
$x \in \mathbb{R}^n$	Decision variable vector
$x_B = B^{-1}b,\; x_N = 0$	Basic feasible solution

Properties

Fundamental theorem of LP

\text{If an LP has an optimal solution, it has an optimal basic feasible solution (a vertex of } \mathcal{P}\text{)}

Optimality via reduced costs

\text{A BFS } x_B = B^{-1}b \text{ is optimal} \iff \bar{c}_N = c_N - c_B^T B^{-1} N \ge 0

Strong LP duality

\min c^T x = \max y^T b \text{ (when both are feasible and bounded)}

Worked Examples

1
Enumerate vertices of the feasible polygon: (0,0),(3,0),(3,1),(1,3),(0,3).
$\text{Vertices: } (0,0),(3,0),(3,1),(1,3),(0,3)$
2
Evaluate 2x+3y at each vertex.
$0,\; 6,\; 9,\; 11,\; 9$
3
Maximum is 11 at (1,3).
$\text{Optimal: } (x^*,y^*) = (1,3),\quad p^* = 11$

✓ Answer

Maximum value is 11, achieved at (1,3).

Practice Problems

Mediumfree response

Write the dual of the LP: min cᵀx s.t. Ax ≥ b, x ≥ 0.

Common Mistakes

Common Mistake

Thinking LP always has a unique optimal solution

If the objective is parallel to a constraint face, there can be infinitely many optimal solutions (an entire edge or face of the polytope).

Quiz

The optimal solution to a linear program (if it exists) always occurs at:

The centroid of the feasible regionA vertex (extreme point) of the feasible polytopeThe originThe midpoint of the longest edge

Historical Background

George Dantzig formulated the general linear program and invented the simplex method in 1947 while working for the US Air Force. Independently, Leonid Kantorovich had developed LP methods for resource allocation in the Soviet Union in 1939. John von Neumann recognised the duality connection to game theory. Khachian (1979) proved polynomial-time solvability via the ellipsoid method; Karmarkar's interior-point method (1984) became practically competitive.

1939
Kantorovich develops LP for optimal resource allocation
Leonid Kantorovich
1947
Dantzig formulates LP and invents the simplex method
George Dantzig
1979
Khachian proves polynomial-time solvability via ellipsoid method
Leonid Khachian
1984
Karmarkar's interior-point algorithm for LP
Narendra Karmarkar

Summary

A linear program minimises a linear objective over a convex polytope defined by linear constraints.
The optimal value is attained at a vertex (basic feasible solution) of the feasible polytope.
Every LP has a dual LP; strong duality holds when both are feasible and bounded.
The simplex method traverses vertices; interior-point methods move through the interior.

References

BookDantzig, G.B. — Linear Programming and Extensions (1963), Princeton University Press
WebsiteWikipedia — Linear programming
WebsiteMathWorld — Linear Programming