Duality Theory: Explained with Examples, Notes and FAQs

Duality theory says that every linear programming problem (the primal) has a mirror-image problem (the dual) whose optimal value equals the primal's optimal value. Solving one gives deep information about the other.

It matters for two reasons: economically, dual variables have meaning as "shadow prices" — how much the optimum would improve if a resource increased slightly; and computationally, when the primal has many constraints but few variables, solving the dual can be much easier.

Key Concepts

• Primal problem: the original LP, e.g. maximise cTx subject to Ax ≤ b, x ≥ 0.
• Dual problem: minimise bTy subject to ATy ≥ c, y ≥ 0.
• Weak duality: any feasible dual value ≥ any feasible primal value (for maximisation primal).
• Strong duality: if one problem has an optimal solution, so does the other, with equal objective values.
• Complementary slackness: at optimality, each primal slack pairs with a zero dual variable and vice versa.
• Shadow price: the dual variable's value — worth of one extra unit of a resource.

How It Works

1. Write the primal in canonical form: maximise Z = cTx, Ax ≤ b, x ≥ 0.
2. For each primal constraint, create one dual variable yᵢ ≥ 0.
3. For each primal variable, create one dual constraint: a₁ᵢy₁ + … + aₘᵢyₘ ≥ cᵢ.
4. The dual objective is minimise b₁y₁ + … + bₘyₘ.
5. Solve either problem; the other one's optimum follows by strong duality, and optimal dual values appear in the primal's final tableau (the Zⱼ − Cⱼ row under the slack variables).

Worked Example

Primal: maximise Z = 3x + 5y subject to x + 2y ≤ 10, x + y ≤ 6, x, y ≥ 0.

1. Dual variables: u for the first constraint, v for the second.
2. Dual: minimise W = 10u + 6v subject to u + v ≥ 3, 2u + v ≥ 5, u, v ≥ 0.
3. From the earlier simplex solution, optimum primal is Z = 26 at (2, 4).
4. Solve the dual: try the corner where both constraints bind: u + v = 3 and 2u + v = 5 → u = 2, v = 1. Then W = 10·2 + 6·1 = 26.
5. W = 26 = Z — strong duality confirmed.

The shadow prices are u = 2 (one more unit of the first resource raises profit by 2) and v = 1.

Common Misconceptions

• "The dual is just the same problem rewritten." It is a genuinely different problem whose optimum coincides with the primal's.
• "Dual variables are artificial." They are shadow prices with direct economic meaning.
• "Feasibility transfers too." If the primal is unbounded, the dual is infeasible — the two track each other only in this paired way.

Real-World Applications

• Managers use shadow prices to decide whether buying more of a scarce resource is worthwhile.
• Auction designers rely on duality results to understand optimal bidding.
• Network-flow and shortest-path algorithms are duals of each other in practice.

Duality reveals that every optimisation problem carries a hidden twin: one about choosing activities, the other about pricing resources. Their optimal values always agree, and the dual's prices tell you exactly what each constraint is worth.