§ Overview

A linear program is a problem of the form "maximize the objective subject to the constraints." Every such problem has a companion problem — its dual — of the form "minimize a weighted cost of the constraints." The two problems are intimately connected, and the connection is one of the most useful results in optimization: the fundamental duality theorem.

The dual is not just a mathematical curiosity. Its variables have a direct interpretation as marginal values: the change in the optimal objective that would result from relaxing a constraint by one unit. These are the shadow prices that decision-makers need in order to know what a constraint is costing them. The reduced costs of the primal variables have a parallel interpretation as opportunity costs.

The final piece is sensitivity: the ranges within which the coefficients and right-hand sides can change without altering the optimal basis. Within those ranges, the shadow prices and reduced costs are valid. Outside them, they change, and the decision-maker's interpretation must change too.

§ Learning outcomes

§ Lessons

§ The duality theorem

The fundamental duality theorem relates a primal LP and its dual. For the standard-form pair:

Primal:  maximize    cᵀ x
         subject to  A x ≤ b
                     x ≥ 0

Dual:    minimize    bᵀ y
         subject to  Aᵀ y ≥ c
                     y ≥ 0

The theorem states three things:

• Weak duality. For any feasible x of the primal and any feasible y of the dual, cᵀ x ≤ bᵀ y. The primal objective is always bounded above by the dual objective.
• Strong duality. If the primal has an optimal solution x*, then the dual has an optimal solution y*, and cᵀ x* = bᵀ y*. The two optimal objective values are equal.
• Complementary slackness. At optimality, for each constraint, either the primal constraint is binding or the corresponding dual variable is zero (or both). Equivalently, for each decision variable, either the variable is zero or its reduced cost is zero (or both).

§ Self-check