The Geometry of Linear Programming

A linear program has an algebra of variables and inequalities, but its soul is geometric. Draw the feasible region and the objective, and the answer almost leaps off the page — and, better, you see why the answer is where it is. That geometric picture is not a teaching aid you outgrow; it is the exact reason the simplex method works the way it does. Understand the shape, and you understand the algorithm.

We continue with the tables-and-chairs workshop: \max\, 40x_1 + 30x_2 subject to x_1 + x_2 \le 30, 2x_1 + x_2 \le 40, and x_1, x_2 \ge 0.

The feasible region is a convex polytope

Each constraint is a half-plane; their intersection is the feasible region. Because every constraint is a straight cut, the region is flat-sided — a polygon in two dimensions, a polytope in general. Crucially it is convex: the segment joining any two feasible points lies entirely inside the region. This is automatic, because a half-space is convex and an intersection of convex sets is convex.

Convexity means the region has no dents — you can never leave it by walking straight between two points that are in it.
A convex feasible region plus a linear objective means every local optimum is a global optimum — there are no misleading "false peaks" to get stuck on.
So we may search locally (walk to a better neighbour, repeat) and still be sure of the global answer when we stop.

The objective is a sliding family of parallel lines

Fix a profit level k and the equation 40x_1 + 30x_2 = k is a straight line — every production plan on it earns exactly k. Change k and the line slides, keeping the same slope: the objective is a whole family of parallel lines, one per profit level, marching across the plane in the direction of increasing profit.

Maximising profit is therefore a single physical picture: push the line as far as it will go in the profit-increasing direction while it still touches the feasible region. Drag the slider and watch the objective line sweep upward. The last point it touches before leaving the region for good is the optimum — and notice where it lands.

The line leaves the region for the last time exactly at the corner (10, 20) — 10 tables and 20 chairs — where the profit is 40(10) + 30(20) = 1000. Not the interior, not the middle of an edge: a corner.

The corner-point (fundamental) theorem

That was no accident. It is the central fact of linear programming, and it is worth stating precisely.

If a linear program has an optimal solution, then an optimum is attained at a vertex (extreme point / corner) of the feasible polytope.

A linear objective has no interior peak — its gradient is constant and nonzero, so it always improves in some direction. The optimum is therefore pushed to the boundary.
On the boundary, sliding along a flat edge keeps improving until you hit the end of that edge — a corner. So an optimum sits at a vertex.
Consequently you never need to search the infinitely many interior points: it suffices to check the finitely many vertices.

With only four corners we can simply enumerate them and read off the winner:

Vertex (x_1, x_2)	Meaning	Profit 40x_1 + 30x_2
(0, 0)	make nothing	£0
(20, 0)	all tables	£800
(0, 30)	all chairs	£900
(10, 20)	both binding	£1000 ⟵ best

Why this is exactly why the simplex method walks corners

The theorem hands us a strategy and an algorithm in one breath. If an optimum always lives at a vertex, we need only ever look at vertices — never the interior. Enumerating all of them is hopeless in high dimensions (their number explodes), but we do not have to. Because the region is convex, any vertex that beats all its neighbouring vertices beats every vertex, and is the global optimum.

That is precisely what the simplex method does: start at a corner, hop along an edge to an adjacent corner with higher profit, and repeat until no neighbouring corner is better. Convexity guarantees that this local "always climb to a better neighbour" rule delivers the true global optimum. The geometry is not a metaphor for the algorithm — it is the algorithm.

Usually the sliding line's last contact is a single sharp corner. But if the objective happens to be exactly parallel to one of the binding edges, the line makes contact with that whole edge at once as it leaves — and every point along that edge is optimal, an infinity of production plans all earning the same top profit. This is alternative optima, and it does not break the theorem: at least one vertex is still optimal (in fact both ends of the edge are), so "check the corners" still finds the best value. Far from a nuisance, alternative optima are a gift to a manager — you get to pick, among equally profitable plans, the one that is easiest to run.

The fundamental theorem opens with an "if": if the LP has an optimal solution. Two things can spoil that. If the feasible region stretches to infinity in a profit-increasing direction, the sliding line never leaves it — the LP is unbounded and there is no maximum to sit at a corner. If the constraints contradict each other, the region is empty — the LP is infeasible and there are no corners at all. A well-posed model boxes the region in on the profitable side and leaves it non-empty; only then is "the answer is at a vertex" a promise you can collect on.