1 Modelling context

A linear program is one way to describe a decision problem. It presents the problem from the perspective of the decision-maker: which quantities to choose, subject to which resource limits. The dual of the problem presents the same situation from the perspective of the resources: what is each resource worth, and how much would the decision-maker pay for more of it?

The two perspectives are mathematically equivalent — their optimal objective values are equal — but they answer different questions. The primal answers "what should we do?" The dual answers "what is each constraint costing us?" Both are useful. For a decision-maker, the second question is often more actionable: it identifies which constraints are worth relaxing, and by how much.

2 Learning objectives

3 Prerequisite review

Standard form LP

A maximization problem with ≤ constraints and nonnegative variables. Any LP can be converted to this form.

Matrix transposition

The n × m matrix Aᵀ obtained by interchanging rows and columns of A. The dual of a primal with constraint matrix A has constraint matrix Aᵀ.

Feasibility

A point that satisfies all constraints. Every LP has either a feasible region or no feasible solution.

Optimality

A feasible point that maximizes or minimizes the objective over the feasible region.

4 Mathematical formulation

The standard-form pair

The primal-dual pair in standard form:

Primal:  maximize    c₁ x₁ + c₂ x₂ + … + cₙ xₙ
         subject to  a₁₁ x₁ + a₁₂ x₂ + … + a₁ₙ xₙ ≤ b₁
                     a₂₁ x₁ + a₂₂ x₂ + … + a₂ₙ xₙ ≤ b₂
                     …
                     a_{m1} x₁ + … + a_{mn} xₙ ≤ b_m
                     x₁, x₂, …, xₙ ≥ 0

Dual:    minimize    b₁ y₁ + b₂ y₂ + … + b_m y_m
         subject to  a₁₁ y₁ + a₂₁ y₂ + … + a_{m1} y_m ≥ c₁
                     a₁₂ y₁ + a₂₂ y₂ + … + a_{m2} y_m ≥ c₂
                     …
                     a_{1n} y₁ + … + a_{mn} y_m ≥ cₙ
                     y₁, y₂, …, y_m ≥ 0

In matrix form:

Primal:  max  cᵀ x       Dual:  min  bᵀ y
         s.t. A x ≤ b            s.t. Aᵀ y ≥ c
              x ≥ 0                   y ≥ 0

Reading the construction

• One dual variable per primal constraint. The primal has m constraints, so the dual has m variables y₁, …, y_m.
• One dual constraint per primal variable. The primal has n variables, so the dual has n constraints.
• Coefficients transpose. The coefficient of y_i in the j-th dual constraint is a_{ij} — the same coefficient that appears in the i-th primal constraint next to x_j.
• Objective and RHS swap roles. The primal objective coefficients c_j become the dual constraint right-hand sides; the primal constraint bounds b_i become the dual objective coefficients.
• Direction reverses. Maximization becomes minimization; ≤ becomes ≥.

The fundamental duality theorem

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 optima are equal. (By the symmetric statement, if either problem has a finite optimum, so does the other.)

Complementary slackness. At optimality:

• If the i-th primal constraint is not binding (slack positive), then y_i = 0.
• If y_i > 0, then the i-th primal constraint is binding.
• If the j-th primal variable is positive (x_j > 0), then the j-th dual constraint is binding.
• If the j-th dual constraint has slack, then x_j = 0.

An economic interpretation

The dual has a natural economic interpretation. Consider the primal as a production-planning problem: maximize the value of goods produced, subject to resource constraints. The dual variable y_i is the marginal value of the i-th resource — what one additional unit of that resource would be worth.

Under this interpretation:

• The dual objective bᵀ y is the total value of the resources if they were priced at their marginal values.
• The dual constraints state that the value of the resources used in producing one unit of product j must be at least the unit profit c_j. Otherwise, the firm would be undervaluing the resources.
• Strong duality says that, at optimality, the total value of the resources equals the total value of the products — the decision-maker is indifferent between selling the resources at their marginal values and producing the goods.

5 Worked example

maximize   40 x_A + 30 x_B
subject to 2 x_A + x_B ≤ 100    (labour)
           x_A + 3 x_B ≤ 90     (material)
           x_A ≤ 40             (demand A)
           x_B ≤ 30             (demand B)
           x_A, x_B ≥ 0

minimize   100 y_L + 90 y_M + 40 y_A + 30 y_B
subject to 2 y_L + y_M + y_A       ≥ 40    (from x_A)
            y_L + 3 y_M     + y_B  ≥ 30    (from x_B)
            y_L, y_M, y_A, y_B ≥ 0

y_L = 0     (labour is not binding)
y_B = 0     (demand B is not binding)

x_A = 40 > 0  ⟹  2 y_L + y_M + y_A = 40
x_B = 16.67 > 0  ⟹  y_L + 3 y_M + y_B = 30

y_M + y_A = 40
3 y_M = 30  ⟹  y_M = 10
⟹ y_A = 30

Dual objective: 100·0 + 90·10 + 40·30 + 30·0
              = 0 + 900 + 1200 + 0
              = 2100  ✓  equals the primal optimum

6 Verification check

7 Interpretation

The dual is the same problem from a different perspective. The primal asks "what should we do?" The dual asks "what is each constraint worth?" For a decision-maker, the second question is often more directly useful, because it identifies which constraints to relax and how much to pay for relaxation.

Three interpretive points:

• The dual is not an alternative problem. It is the same problem seen from the other side. Its optimum equals the primal's, always.
• Complementary slackness ties the two together. Only binding primal constraints have positive dual variables. Only positive primal variables correspond to binding dual constraints.
• The dual variables are the shadow prices. They have a decision-relevant interpretation as marginal values of the constraints. Unit 6.2 Lesson 2 develops this interpretation in depth.

8 Uncertainty and limitations

The duality theorem is a mathematical fact. Its application to a decision problem inherits the uncertainties of the model itself.

9 Common implementation errors

10 Independent modelling task

11 Reflection prompt

12 Lesson summary

§ Self-quiz, practice, and homework