Mathematics
Duality in Linear Programming: Primal and Dual Relationships
Quick fact
For any linear program, there exists a paired 'dual' problem, and the famous Strong Duality Theorem guarantees that if both problems have feasible solutions, their optimal objective values are equal—even when the problems have completely different numbers of variables and constraints.
Why this is interesting
Every linear programming problem has a hidden twin that, when solved, can give you the answer to the original problem—and even more valuable information. What is this mysterious relationship?
Read the full explanation
Understanding Duality in Linear Programming: Primal and Dual Relationships
Think of a company that manufactures two products, using limited resources like labor and materials. The 'primal' problem asks: how many of each product to make to maximize profit? Now imagine a competitor who wants to buy all the company's resources. The 'dual' problem asks: what prices should the competitor offer per unit resource, so that the total buying cost is minimized while still being at least as profitable as making the products?\n\nThe primal and dual are constructed from the same data: the objective coefficients, the constraint coefficients, and the right-hand-side values. To build the dual, you swap the roles: the primal's objective coefficients become the dual's right-hand sides, the primal's constraints become the dual's variables, and the direction of inequalities flips (max becomes min, <= becomes =, etc.). This creates a mirror-image problem that encodes the same information from a different perspective.
A deeper explanation
The magic of duality lies in the theorems that connect the primal and dual. The Weak Duality Theorem states that any feasible solution to the dual gives a bound on the optimal value of the primal (for a maximization primal, the dual's objective value is always at least the primal's). This is intuitively because the dual's constraints are constructed so that no feasible dual solution can be less than the primal objective at any feasible primal point.\n\nThe Strong Duality Theorem goes further: if the primal has an optimal solution, then the dual also has an optimal solution, and their optimal values are equal. This is not just a theoretical nicety—it is the foundation of the simplex method's stopping criterion and of sensitivity analysis. The values of the dual variables at optimality are called 'shadow prices' and tell you the marginal worth of each resource. Moreover, complementary slackness conditions provide a way to check optimality and to derive dual solutions from primal solutions, linking the two problems in a delicate balance.