Skip to content
Tutorials Center
My learning

Topics

Lesson 16 of 38 ยท Duality and Sensitivity

The Dual Problem

Learn the dual of a linear program: the primal-dual conversion table, the economic meaning of dual variables, and a Python dual builder checked against linprog.

Every linear program has a shadow twin called its dual. The original problem (the primal) asks "how many units of each product should we make?". The dual asks "what is each resource worth?". Remarkably, solving either one solves both, and the dual gives you prices, bounds and a certificate of optimality. Duality is the most important theoretical idea in linear programming.

The bakery and its dual

Recall the bakery primal:

TEXT
maximize    40x + 30y
subject to  2x + y <= 100    (oven hours)
             x + y <=  80    (labor hours)
             x     <=  40    (flour)
            x, y >= 0

Imagine an outside buyer who wants to rent all your resources and offers prices y1, y2, y3 per unit of oven hour, labor hour and flour. You will accept only if, for each product, the money the buyer pays for the resources it uses is at least the profit you would earn from making it. And the buyer wants to pay as little as possible in total. That buyer's problem is the dual:

TEXT
minimize    100 y1 + 80 y2 + 40 y3
subject to   2 y1 +   y2 +   y3 >= 40    (product x: resources used >= its profit)
               y1 +   y2        >= 30    (product y)
            y1, y2, y3 >= 0

One dual variable per primal constraint; one dual constraint per primal variable. The right-hand side (100, 80, 40) of the primal became the dual objective, and the primal objective (40, 30) became the dual right-hand side. The coefficient matrix is transposed.

The conversion table

For a primal maximization with m constraints and n variables, the dual is a minimization with n constraints and m variables. Constraint types and variable signs map as follows:

Primal (maximize) Dual (minimize)
Constraint <= Variable >= 0
Constraint >= Variable <= 0
Constraint = Variable free
Variable >= 0 Constraint >=
Variable <= 0 Constraint <=
Variable free Constraint =
Objective coefficients c Right-hand side
Right-hand side b Objective coefficients

In matrix form for the symmetric pair:

TEXT
Primal:  max c.x   s.t. A x <= b, x >= 0
Dual:    min b.y   s.t. A^T y >= c, y >= 0

The dual of the dual is the primal, so duality is a symmetric relationship.

Python Build and solve the bakery dual

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Both optima are 2600, and the dual prices are (10, 20, 0): an oven hour is worth 10 dollars, a labor hour 20, and spare flour is worth nothing. These are precisely the shadow prices that linprog reported earlier and that appeared under the slack columns of the final simplex tableau.

Economic interpretation

The dual variable y_i is the marginal value of resource i: how much the optimal profit rises per extra unit of that resource (while the optimal basis stays the same). The dual constraint for product j says: the implicit value of the resources consumed by one unit must be at least the profit it earns. If it is strictly more, the product is not worth making (its reduced cost is positive). If it is exactly equal, the product may be made.

  • A resource with positive price is scarce (it is fully used).
  • A resource with zero price has slack (it is abundant).
  • A product that is made has resources valued at exactly its profit.

For the bakery: bread uses 2 oven hours and 1 labor hour, valued at 2*10 + 1*20 = 40 equals its profit; cakes use 1 oven and 1 labor hour, 10 + 20 = 30, also equal. Both products are made, consistent with the dual constraints being tight.

A general dual builder

The table above is easy to get wrong when written by hand. This function converts any LP of the form max/min c.x with mixed <=, >=, = rows and sign-restricted variables, then checks that primal and dual optima agree.

Python A dual builder for mixed constraints

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The two values match, and the printed dual signs follow the table: the <= row gives a >= 0 variable, the >= row a <= 0 variable, and the equality row a free variable. The free third primal variable became an equality dual constraint.

Why bother with the dual?

  • Prices. Dual values are the shadow prices used for decisions and sensitivity analysis (a later lesson).
  • Bounds. Any feasible dual solution gives an upper bound on a maximization; this is weak duality (next lesson).
  • Certificates. A primal-dual pair that match proves optimality without trusting the solver.
  • Speed. Sometimes the dual is much easier to solve (few variables, many constraints becomes many variables, few constraints). The dual simplex method works on the dual implicitly and is a default in modern solvers, especially after adding constraints.
  • Algorithms. Network flow, matching, game theory and column generation all lean on duality.
flowchart LR
  P["Primal: max c.x, Ax <= b, x >= 0"] <--> D["Dual: min b.y, A^T y >= c, y >= 0"]
  P --> V["Same optimal value"]
  D --> V

Transpose the matrix, swap objective and right-hand side, and flip the optimization direction.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. The primal is max c.x s.t. Ax <= b, x >= 0. What is the dual?

    The dual swaps b and c, transposes A, flips max to min, and the <= constraints become >= with y >= 0.
  2. 2. A primal equality constraint corresponds to which dual variable?

    Equalities carry no sign restriction on their multiplier, so the dual variable is free.
  3. 3. In the bakery, the dual price of flour is 0 because

    A resource with unused capacity has no marginal value.
  4. 4. The dual of the dual of an LP is

    Duality is symmetric: dualizing twice returns the original problem.

Summary

  • Each primal constraint has a dual variable (its price); each primal variable has a dual constraint.
  • For max c.x, Ax <= b, x >= 0 the dual is min b.y, A^T y >= c, y >= 0.
  • The conversion table maps <=, >=, = rows to >=0, <=0, free variables, and vice versa.
  • Dual variables are marginal values of resources; positive only for scarce resources.
  • A dual builder plus linprog lets you confirm primal and dual optima agree.

Next: Duality Theorems and Complementary Slackness