Corner Point Optimality¶

Proposition¶

For the LPs in the course with a nonempty feasible region in nonnegative variables, if a finite optimum exists, at least one feasible corner point attains it. Consequently, a unique optimal solution must be a feasible corner point. If a bounded feasible region has multiple optimal solutions, at least two of its corner points are optimal.

Interpretation¶

This result reduces the search for the optimum of an LP from infinitely many feasible points to finitely many corners: if the best value is attained at all, it is attained at some feasible corner point.

The feasible pentagon with the objective value at each corner and an objective line touching the region at the corner (20, 60), where the maximum 180 is reached.

The figure lists the value of $z=3x_s+2x_t$ at each of the five feasible corners. The largest, $180$ , belongs to $(20,60)$ , and the objective line $3x_s+2x_t=180$ touches the region only there.

The reason is linearity. Along a straight edge between two corners the objective changes at a constant rate, so on that edge it is largest at one of the endpoints, or equal along the whole edge. The hypotheses matter. Without a finite optimum there is nothing to attain: maximizing cost over the unbounded region of the diet problem has no optimum. Without the sign restrictions the region may have no corner at all: maximizing $x_1+x_2$ subject only to $x_1+x_2\le1$ has optimal value $1$ , attained along a whole line, but no two boundary lines meet.

The proposition says that some optimal solution is a corner, not that every one is: when an objective line lies along an edge, all points of that edge are optimal. The graphical method uses the result directly, and the simplex method later turns it into an algebraic search from corner to corner.

Key Results¶

The existence of a finite optimum is essential.
The bounded-region qualification in the multiple-corner statement matters when the feasible region has rays.
Every convex combination of optimal corners is optimal.

Examples¶

The figure evaluates $z=3x_s+2x_t$ at its five feasible corners: the values are $0,120,160,180,160$ . The largest is 180 at $(20,60)$ , and the orange line is the objective line through that point.

The manufacturing optimum $(2,5)$ is a feasible corner.
For the course LP with objective $4x_1+2x_2$ and boundary $2x_1+x_2\le11$ $11$ , an entire feasible boundary segment attains 22.

Prerequisites¶

Sources¶

OR Modelling · Week 1

Aliases: extreme point theorem Keywords: fundamental theorem of linear programming

Last updated: 20 October 2026 03:02