Linear programming

Linear programmes model allocation problems (production, transport, diets). Their feasible sets are polyhedra and optima sit at corners, which the simplex method walks between.

1. Standard form (Def. 1.1), basic feasible solutions = vertices (Prop. 1.2), and the fundamental theorem (Thm 1.3).
2. The simplex method (Def. 1.4) with its optimality test (Prop. 1.5) and a worked example (Example 1.6).
3. Duality (Def. 1.7): weak (Thm 1.8) and strong (Thm 1.9) duality, and complementary slackness (Cor. 1.10).

A linear programme in standard form is: minimise $c^{\mathsf T}x$ subject to $Ax = b$, $x\ge0$. Every LP can be put in this form: a constraint $a^{\mathsf T}x\le\beta$ becomes $a^{\mathsf T}x + s = \beta$ with a slack $s\ge0$; a free variable $x_j$ becomes $x_j^+ - x_j^-$; maximising $c^{\mathsf T}x$ is minimising $-c^{\mathsf T}x$. $x$ is feasible if it satisfies the constraints; the LP is infeasible if none is, and unbounded if the objective is unbounded below on the feasible set.

Choose $m$ linearly independent columns $A_B$ of $A$. The basic solution sets $x_B = A_B^{-1}b$ and $x_j = 0$ for $j\notin B$; it is a basic feasible solution (BFS) if $x_B\ge0$. The BFSs are exactly the vertices (extreme points) of the feasible set $\{x: Ax = b, x\ge0\}$; there are at most $\binom nm$ of them.

For an LP in standard form: if it is feasible, it has a BFS; and if it has an optimal solution, it has an optimal BFS. So an optimum, when it exists, is attained at a vertex.

Start at a BFS with basis $B$. Compute the reduced costs $\bar c_j = c_j - c_B^{\mathsf T}A_B^{-1}A_j$ for $j\notin B$.

1. If all $\bar c_j\ge0$, stop: the BFS is optimal (see Prop. 1.5).
2. Otherwise choose $j$ with $\bar c_j < 0$ to enter; let $d = A_B^{-1}A_j$. If $d\le0$ the LP is unbounded.
3. Ratio test: the leaving variable is the basic $x_i$ minimising $\frac{(x_B)_i}{d_i}$ over $d_i > 0$. Pivot and repeat. With an anti-cycling rule (e.g. Bland's: smallest index), the method terminates.

If a BFS $x$ with basis $B$ has all reduced costs $\bar c_j\ge0$, then $x$ is optimal.

Maximise $3x + 5y$ subject to $x\le4$, $2y\le12$, $3x + 2y\le18$, $x, y\ge0$.

• Start at the origin (basis $s_1, s_2, s_3$). $y$ has the most negative reduced cost ($-5$): it enters. Ratios $\frac{12}2 = 6$, $\frac{18}2 = 9$: $s_2$ leaves. New vertex $(0, 6)$, value $30$.
• Now $x$ has reduced cost $-3$ and enters. Ratios: $\frac41 = 4$ (row 1) and $\frac{18 - 12}3 = 2$ (row 3): $s_3$ leaves. New vertex $(2, 6)$, value $36$.
• Reduced costs of $s_2, s_3$ are $\frac32$ and $1$, both $\ge0$: optimal, $(x, y) = (2, 6)$ with value $36$.

The dual of the primal (P) $\min c^{\mathsf T}x$, $Ax = b$, $x\ge0$ is (D) $\max b^{\mathsf T}y$ subject to $A^{\mathsf T}y\le c$ ($y$ free). For the inequality form (P) $\max c^{\mathsf T}x$, $Ax\le b$, $x\ge0$, the dual is (D) $\min b^{\mathsf T}y$, $A^{\mathsf T}y\ge c$, $y\ge0$. The dual of the dual is the primal.

If $x$ is feasible for (P) $\min c^{\mathsf T}x$, $Ax = b$, $x\ge0$ and $y$ is feasible for (D), then $b^{\mathsf T}y\le c^{\mathsf T}x$. Consequently, if the values are equal, both are optimal; if (P) is unbounded, (D) is infeasible.

If (P) has an optimal solution, so does (D), and the optimal values are equal. (So exactly one of: both have optima with equal values; one is unbounded and the other infeasible; both are infeasible.)

Feasible $x$ for (P) and $y$ for (D) are both optimal if and only if $x_j(c_j - A_j^{\mathsf T}y) = 0$ for every $j$: whenever a primal variable is positive, the corresponding dual constraint is tight. (For inequality forms, also: a dual variable is positive only if its primal constraint is tight.)

• Convert to standard form; find a starting BFS (slacks, or a phase-one problem).
• Pivot: enter negative reduced cost, leave by ratio test.
• Certify: exhibit a dual feasible $y$ with the same value, or check complementary slackness.
• Two variables: draw the region and check vertices.