Feasible regions, the simplex method, and LP duality
A linear program looks for the best corner of a many-sided shape. Rotate, pivot, and pair problems up to see why the answer always sits at a vertex.
Pick a set of constraints and rotate the objective direction. Watch the optimal point jump from vertex to vertex, never stopping in the middle.
Drag the objective direction to see how the optimal vertex changes. The yellow arrow shows the direction that maximizes the objective function.
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.
Key insight: The fundamental theorem of LP: if a finite optimum exists, it is attained at a vertex of the feasible polytope.
Choose an objective and press Next Pivot or Auto-Play. Each pivot moves to a neighboring vertex with a better value until no neighbor improves.
Starting at vertex O, the simplex method pivots to adjacent vertices with higher objective values until no improvement is possible.
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.
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.
Switch between the examples and compare the primal minimum with the dual maximum. They always match.
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); every positive dual variable corresponds to one of them.
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.
Key insight: Duality provides a certificate of optimality: if you find primal and dual solutions with equal objectives, both must be optimal.
Spot a mistake or have an idea?