Linear Programming: Formulation, Geometry, and Duality
This domain tests formulation of linear programs, their geometric structure, and duality relationships. Expect extreme points, basic feasible solutions, binding constraints, shadow prices, reduced costs, complementary slackness, and infeasibility or unboundedness.
Core rules
- Convert to standard form carefully; slack, surplus, and artificial variables have different meanings.
- An optimal extreme point occurs where enough independent constraints bind, but not every binding set is optimal.
- Strong duality says primal and dual optimal objectives match when both are feasible and bounded.
- A dual variable is a shadow price only within the range where the basis stays optimal.
- Complementary slackness links a positive primal variable to a zero reduced cost and a positive dual variable to a binding primal constraint.
Worked example
Maximize 3x+2y subject to x+y≤4, x≤2, y≤3, x,y≥0. Vertices include (0,0), (2,0), (2,2), (1,3), and (0,3). At (2,2), objective is 10; at (1,3), it is 9; at (2,0), it is 6. The optimum is (2,2). Constraints x≤2 and x+y≤4 bind, while y≤3 is slack, so its dual variable is zero by complementary slackness. Increasing the x+y right-hand side may raise the objective, but only until another basis becomes optimal.
Traps
Confusing a shadow price with an objective coefficient, assuming every binding constraint has a nonzero price, calling an unbounded model infeasible, and ignoring degeneracy when interpreting duals.
Key points
- Standard form changes variable meanings.
- Optima occur at extreme points.
- Strong duality links primal and dual values.
- Shadow prices have validity ranges.
- Slack constraints have zero duals.