Mathematics
Linear Programming and the Simplex Method for Optimization
Quick fact
The simplex method, invented by George Dantzig in 1947, can find the optimal solution of a linear program by walking through the vertices of the feasible region, and it almost always requires far fewer steps than the number of vertices—sometimes fewer than 100 for problems with millions of constraints.
Why this is interesting
Have you ever wondered how airlines decide which flights to cancel, or how factories decide what to make when resources are tight? Hidden inside these decisions is a mathematical formula that can be optimized—but how do you find the very best answer without checking every possibility?
Read the full explanation
Understanding Linear Programming and the Simplex Method for Optimization
Imagine you have a company that makes two products, each requiring certain amounts of machine time and labor. Your profit depends linearly on how many of each you produce, and your resources set limits. This is a linear program: maximize profit = c1x1 + c2x2 subject to constraints like a11x1 + a12x2 ≤ b1 (and x1, x2 ≥ 0). The set of all possible production plans that satisfy the constraints is called the feasible region. Because the constraints are linear, this region is a convex polygon (in 2D) or a polytope (in higher dimensions). The key insight is that the optimal maximum (or minimum) occurs at a vertex (corner) of this region. So the problem reduces to evaluating the objective function at the vertices.
A deeper explanation
The simplex method capitalizes on the vertex property. It starts at a feasible vertex (often the origin, if it's feasible). It then checks whether moving along an edge to an adjacent vertex would increase (or decrease, depending on the objective) the value of the objective function. If such a move improves the objective, it performs a mathematical operation called a pivot, which efficiently recomputes the new vertex. This process repeats until no adjacent vertex yields a better objective—that vertex is the optimal solution. The reason this works is that the objective function is linear, and the feasible region is convex: a locally optimal vertex is also globally optimal. The simplex method is incredibly practical; it has been the workhorse of operations research for decades, used in industries from logistics to finance. However, it is not polynomial-time in the worst case; there exist pathological examples where the number of steps grows exponentially. Nevertheless, in practice, it is remarkably efficient, and its extensions (like the revised simplex method) handle huge problems with ease.