Feasible regions, the simplex method, and LP duality
A linear program optimizes a linear objective function subject to linear inequality constraints. The feasible set is a convex polytope, and the optimum always occurs at a vertex. The simplex method exploits this by walking along edges of the polytope, improving the objective at each step.
Linear constraints define half-planes. Their intersection is the feasible polytope. Rotate the objective direction to see the optimum slide between vertices.
Drag the objective direction to see how the optimal vertex changes. The yellow arrow shows the direction that maximizes the objective function.
Key insight: The fundamental theorem of LP: if a finite optimum exists, it is attained at a vertex of the feasible polytope.
The simplex method starts at a vertex and pivots to adjacent vertices along edges, always improving the objective. Watch it trace a path along the polytope boundary to the optimum.
Starting at vertex O, the simplex method pivots to adjacent vertices with higher objective values until no improvement is possible.
Key insight: Despite worst-case exponential time, the simplex method is remarkably efficient in practice. It typically finds the optimum in O(m) pivots for m constraints.
Every LP has a dual problem. The primal minimizes, the dual maximizes. Strong duality says their optimal values are equal. Complementary slackness links the solutions.
Primal constraint matrix A:
Dual constraint matrix AT:
Strong duality: at optimality, primal and dual objectives are equal. Highlighted rows indicate tight constraints (zero slack), which correspond to positive dual variables.
Key insight: Duality provides a certificate of optimality: if you find primal and dual solutions with equal objectives, both must be optimal.