Lesson 171
Linear Programming & Duality
Polytopes · Simplex · Shadow Prices
1:00How to optimize a linear objective subject to linear constraints — the geometry of corners, the simplex walk, and the mirror relationship between a problem and its dual.
By the end, you can
- Identify whether an objective and a set of constraints form a valid linear program.
- Describe the feasible region as a convex polytope and explain why the optimum sits at a vertex.
- Evaluate the objective at given corner points and identify the optimal one.
- Trace the simplex walk through the lesson's worked example from (0,0) to (2,6).
- Explain the worst-case vs. practical complexity of simplex, and state that LP is in P.
- Construct the dual of a primal LP and state what each dual variable represents.
- Distinguish weak duality from strong duality, and verify the zero duality gap numerically.
- Interpret shadow prices as marginal values of resources and apply complementary slackness.
- Compute the minimum cut for a small flow network and connect it to LP duality.
- Explain the integrality gap and how LP relaxation enables approximation algorithms for ILP.
Up next in Algorithms & Graph Algorithms
