Maximize a linear goal — profit, output — subject to linear limits — budget, capacity. The constraints carve out a polygon of allowed choices, and here’s the beautiful fact: the best answer is ALWAYS at a CORNER of that polygon, never the middle. So you just check the vertices. This runs airlines, factories, and diets; the simplex method walks corner to corner to the top. Slide to sweep the objective and watch the optimum snap to a corner.
Linear programming maximizes (or minimizes) a LINEAR objective c·x subject to LINEAR inequality constraints, whose feasible region is a convex POLYTOPE. The fundamental theorem: an optimum, if it exists, occurs at a VERTEX (corner) of that polytope — because a linear objective’s level sets are hyperplanes, sliding one until it last touches the region lands on a corner (or edge). So the [[the-gradient-descent|search]] reduces to the finite set of vertices; the SIMPLEX method walks edge-to-edge improving each step (interior-point methods cut across). It powers scheduling, logistics, diets, and network flows. A fail-loud self-check throws unless the best feasible vertex matches the known optimum. ◆ real optimization, node-verified.
The vertex-optimum theorem holds for LINEAR objectives/constraints only; nonlinear programs can optimize in the interior. Degenerate cases and huge problems need care (simplex is worst-case exponential, though fast in practice). The polytope + vertex arithmetic is exact.