the simplex method
Imagine the set of all allowed plans for a problem forms a many-sided crystal — a polyhedron — and you want the plan that maximizes profit, a quantity that increases steadily in some direction across the crystal. A key fact makes the search tractable: the best plan always sits at a CORNER (a vertex) of the crystal. The simplex method exploits this by hopping from corner to neighbouring corner, always to one that improves the profit, until no neighbour is better — that corner is optimal.
This is the classic algorithm for LINEAR PROGRAMMING: maximize (or minimize) a linear objective c^T x subject to linear inequality and equality constraints, like A x <= b with x >= 0. The feasible region is a convex polyhedron, and because both the objective and constraints are linear, the optimum is attained at a vertex (or along an edge of equally good vertices). The simplex method, due to George Dantzig in 1947, starts at one feasible vertex and repeatedly moves along an edge to an adjacent vertex that increases the objective, using a 'pivoting' step on the constraint equations to swap which constraints are tight. When no adjacent vertex improves the objective, optimality is certified and the algorithm stops. In practice it is remarkably efficient, usually finishing in a number of pivots roughly proportional to the number of constraints.
Linear programming is one of the great success stories of computational mathematics — it powers scheduling, logistics, network flows, diet and blend problems, and is the engine inside countless planning systems — and DUALITY is its deep companion: every LP (the primal) has a paired dual LP, and their optimal values coincide (strong duality), with the dual variables acting as shadow prices on the constraints, exactly the Lagrange multipliers of the constrained problem. The honest caveats: despite its excellent everyday speed, the simplex method's WORST-CASE running time is exponential (the Klee-Minty examples force it to visit exponentially many vertices), which is why interior-point methods — provably polynomial — were a landmark. The two coexist: simplex gives exact vertex solutions and warm-starts cheaply; interior-point scales better on some large problems. And the method assumes LINEARITY throughout — for nonlinear objectives or constraints you need other tools.
Maximize 3x + 2y subject to x + y <= 4, x <= 3, x, y >= 0. The feasible region is a polygon with corners (0,0), (3,0), (3,1), (0,4). Simplex starts at (0,0), pivots along an edge to a better corner, and lands at (3,1) with value 11 — the best vertex. Checking each corner's value (0, 9, 11, 8) confirms it.
The LP optimum is always at a vertex; simplex walks corner to corner.
Simplex is fast in practice but has EXPONENTIAL worst-case complexity (Klee-Minty), unlike interior-point methods which are provably polynomial. They are complementary, not obsolete-versus-modern: simplex returns an exact vertex and warm-starts cheaply, interior-point can scale better on some large problems. And simplex assumes everything is linear.