Linear Programming

Maximize c^ x over a polytope; a finite optimum sits at a vertex.

The idea

A linear program asks for the best value of a linear objective over the points that satisfy a list of linear inequalities. In standard form it is written

$\begin{aligned} \max\quad & c^{\top} x \\ \text{s.t.}\quad & A x \le b \\ & x \ge 0, \end{aligned}$

where each row of $A x \le b$ is one inequality and $c^{\top} x$ is the quantity being maximized. The points satisfying every constraint at once form the feasible region; with two variables it is a polygon in the plane, cut out by the constraint lines.

A vertex of the feasible region is a corner: a feasible point at which $n$ linearly independent constraints hold with equality, $n$ being the number of variables. In the plane, that is a point where two independent constraint lines cross.

Theorem (Fundamental theorem of linear programming).

If the objective of a linear program has a finite maximum over the feasible region, that maximum is attained at a vertex of the region.

Here is where the theorem comes from. The points scoring a given value $k$ form the line $c^{\top} x = k$, and raising $k$ slides that line across the plane without turning it. The maximum is the last value of $k$ whose line still touches the feasible region, and a sliding line leaves a polygon at a corner. So a finite optimum never lies strictly inside the region, and checking the corners is enough.

Ways to work on it

• Walkthrough. Solve a 2-variable LP in standard form by checking the vertices of the feasible polygon.
• Practice. Given a feasible region's vertices, find the optimal value and corner.
• Hardest. Spot an unbounded LP and name the two ways an LP can lack an optimal vertex.

Not sure where to start? Take the ten-question placement test.