Mathematics
Linear Programming and the Simplex Method
Quick fact
The simplex method, despite being developed in 1947, is still widely used today, and it often runs in polynomial time in practice, though it can be exponential in the worst case.
Why this is interesting
Imagine you're managing a factory with limited resources and try to maximize profit. How do you find the perfect production mix among infinite possibilities?
Read the full explanation
Understanding Linear Programming and the Simplex Method
Linear programming is a way to find the best outcome (like maximum profit or minimum cost) when you have a linear objective and linear constraints. Think of the constraints as walls that enclose a region called the feasible region—this is where all possible solutions live. Because the objective is linear, the best solution must occur at a corner (vertex) of this region. The simplex method exploits this by starting at one vertex and then moving along the edges to neighboring vertices that improve the objective. It does this repeatedly until no neighbor is better, ensuring optimality. Each move, called a pivot, changes one basic variable while keeping the solution feasible.
A deeper explanation
The reason the simplex method works is that it systematically explores the vertices of the feasible polytope, and the linearity of the objective guarantees that an optimal solution, if it exists, is at a vertex. In each pivot, the algorithm selects a non-basic variable with a positive reduced cost (for maximization) to enter the basis and a basic variable that will first become zero to leave, maintaining feasibility. It stops when no reduced cost is positive, indicating that the current vertex is optimal. This process is efficient in practice, typically requiring only a few pivots. However, degenerate cases can cause cycling, which is usually handled by Bland's rule. The simplex method's significance extends beyond computation; it underpins sensitivity analysis and price theory in economics.