Why the LP Optimum Lives at a Vertex

The Fundamental Theorem of Linear Programming: a linear objective over a polyhedral feasible region attains its optimum at a vertex (extreme point). Students learn the endpoint lemma for line segments, the vertex theorem, and how to solve a small LP by enumerating and evaluating vertices.

Step 1 of 157%

Tutorial

A Linear Function on a Line Segment

A linear (affine) objective $f(\mathbf{x}) = \mathbf{c}^\top \mathbf{x} + d$ behaves very simply on a line segment. Take two points $\mathbf{a}$ and $\mathbf{b}$ , and consider any point on the segment between them, written as a convex combination

\mathbf{x} = (1-\lambda)\,\mathbf{a} + \lambda\,\mathbf{b}, \qquad \lambda \in [0,1].

Linearity passes straight through to $f$ :

f(\mathbf{x}) = (1-\lambda)\,f(\mathbf{a}) + \lambda\, f(\mathbf{b}).

The value of $f$ along the segment is itself a convex combination of $f(\mathbf{a})$ and $f(\mathbf{b})$ . Therefore,

\min\{f(\mathbf{a}),\,f(\mathbf{b})\} \;\leq\; f(\mathbf{x}) \;\leq\; \max\{f(\mathbf{a}),\,f(\mathbf{b})\}.

The maximum (and the minimum) of a linear function over a segment is attained at one of its endpoints, never strictly in the interior.

Illustration. Let $f(x,y) = 2x - y$ on the segment from $(0,3)$ to $(4,1)$ . We have

f(0,3) = -3, \qquad f(4,1) = 7.

So $f$ ranges over $[-3,\,7]$ on this segment, attaining its max at $(4,1)$ and its min at $(0,3)$ .