Duality in Linear Programming
Every linear program has a hidden twin. Ask "how much product should I make to maximize profit?" and lurking behind it is a second question — "what is each of my resources really worth?" — that has exactly the same answer. This mirror problem is the dual, and the relationship between the two is one of the most elegant and useful results in all of optimization. It turns shadow prices into a rigorous theory, gives us bounds and optimality certificates for free, and often lets us solve the easier of the two problems instead.
- The idea that every LP (the primal) has an associated dual, and why they share an answer.
- The rules for constructing the dual from any primal.
- The primal–dual correspondence for constraints, variables, and signs.
- Weak duality (a universal bound) and strong duality (equal optimal values, no gap).
- Complementary slackness, which links a primal optimum to its dual.
- The economic interpretation — dual variables are shadow prices, readable from the final tableau.
The Idea of Duality
Suppose a workshop maximizes profit by choosing production quantities, limited by scarce resources. That is the primal problem. Now imagine an outsider who wants to buy all the resources: to set fair prices, they must charge at least enough that the shop would rather sell each resource than use it to make product — yet as little as possible to win the deal. That price-setting problem is the dual. Remarkably, the shop's maximum profit and the minimum total resource value coincide exactly.
Duality is not a coincidence but a structural feature of every LP. It gives bounds (any dual solution bounds the primal), certificates (matching values prove optimality), and computational shortcuts (solve whichever twin is easier). Above all it makes rigorous the shadow prices we have met informally since Chapter 5.
Constructing the Dual
For a primal in symmetric form — a maximization with all "\(\le\)" constraints and non-negative variables — the dual is written mechanically:
Every piece flips role: maximization becomes minimization; the cost vector \(\mathbf{c}\) becomes the dual's right-hand side while the primal's right-hand side \(\mathbf{b}\) becomes the dual's cost; the constraint matrix is transposed, \(A \to A^{\mathsf T}\); and each of the \(m\) primal constraints spawns one of the \(m\) dual variables, while each of the \(n\) primal variables spawns one of the \(n\) dual constraints. A pleasing consequence: the dual of the dual is the original primal.
Primal–Dual Correspondence
When the primal is not in symmetric form — mixed constraint types or free variables — the dual follows a fixed dictionary. Reading down the table converts any (maximization) primal into its dual.
| Primal (maximization) | Dual (minimization) |
|---|---|
| \(i\)-th constraint is \(\le\) | \(y_i \ge 0\) |
| \(i\)-th constraint is \(=\) | \(y_i\) free (unrestricted) |
| \(i\)-th constraint is \(\ge\) | \(y_i \le 0\) |
| variable \(x_j \ge 0\) | \(j\)-th dual constraint is \(\ge c_j\) |
| variable \(x_j\) free | \(j\)-th dual constraint is \(= c_j\) |
| \(m\) constraints | \(m\) variables |
| \(n\) variables | \(n\) constraints |
Weak Duality
The first theorem costs almost nothing to prove yet is enormously useful. For any primal-feasible \(x\) and any dual-feasible \(y\), the primal objective can never exceed the dual objective.
Proof in one line: \(\mathbf{c}^{\mathsf T}x \le (A^{\mathsf T}y)^{\mathsf T}x = y^{\mathsf T}(Ax) \le y^{\mathsf T}b = \mathbf{b}^{\mathsf T}y\), using \(A^{\mathsf T}y \ge c\), \(x \ge 0\), then \(Ax \le b\), \(y \ge 0\). Every dual-feasible value is an upper bound on the primal maximum, and every primal-feasible value is a lower bound on the dual minimum. Two immediate corollaries: if the primal is unbounded, the dual must be infeasible; and if \(\mathbf{c}^{\mathsf T}x = \mathbf{b}^{\mathsf T}y\) for some feasible pair, both are optimal.
Strong Duality
Weak duality leaves open a gap between the best primal and best dual values. The strong duality theorem closes it completely: for linear programs there is no duality gap.
The optimal profit equals the optimal imputed value of the resources, exactly. This is special to (and characteristic of) linear programming — general nonlinear problems can have a positive duality gap. It is also why the simplex method, on solving the primal, hands you the dual optimum for free.
Complementary Slackness
Strong duality says the optimal values match; complementary slackness says how the optimal solutions themselves are linked. At optimality, a primal variable and its partner dual constraint cannot both be slack, and a primal constraint and its partner dual variable cannot both be slack.
Read practically: if a resource is not fully used (primal constraint has slack), its price is zero (\(y_i = 0\)); if a product is made (\(x_j > 0\)), its dual constraint is binding (it earns exactly its worth). These conditions are strong enough to recover one optimal solution from the other — given the primal optimum, you can solve for the dual optimum, and vice versa, without re-running the simplex method.
Economic Interpretation & Reading the Dual
The dual variables \(y_i\) are precisely the shadow prices of Chapter 5: the marginal value of one more unit of resource \(i\). Their weighted sum \(w = \mathbf{b}^{\mathsf T}y\) is the total imputed value of all resources, which strong duality equates to the optimal profit. And — the practical payoff — the dual optimum is sitting in the primal's final simplex tableau all along: it is the \(z\)-row entries under the slack variables.
| Final z-row (Wyndor, Ch 8) | x₁ | x₂ | s₁ | s₂ | s₃ | RHS |
|---|---|---|---|---|---|---|
| z | 0 | 0 | 0 | 3/2 | 1 | 36 |
The \(z\)-row entries under \(s_1, s_2, s_3\) are the dual variables. Resource 1 (with slack in the primal) prices at \(0\); resources 2 and 3 (binding) carry positive shadow prices. Their total imputed value \(36\) equals the optimal profit \(36\), confirming strong duality — all read off a single tableau.
Worked Examples
Problem. Write the dual of \(\max\ z = 3x_1 + 5x_2\) s.t. \(x_1 \le 4,\ 2x_2 \le 12,\ 3x_1 + 2x_2 \le 18,\ x \ge 0\).
Solution. Three constraints give three dual variables \(y_1, y_2, y_3 \ge 0\); two primal variables give two dual constraints:
The columns of \(A\) became the dual constraints; \(b\) became the dual objective.
Problem. Dualise \(\max\ z = 2x_1 + x_2\) s.t. \(x_1 + x_2 \le 6,\ x_1 - x_2 = 2,\ x \ge 0\).
Solution. The "\(\le\)" gives \(y_1 \ge 0\); the "\(=\)" gives \(y_2\) free. The dual is \(\min\ w = 6y_1 + 2y_2\) s.t. \(y_1 + y_2 \ge 2,\ y_1 - y_2 \ge 1,\ y_1 \ge 0,\ y_2\ \text{free}\). The equality constraint is exactly what freed the sign of \(y_2\).
Problem. For the pair in Example 1, a primal-feasible point gives \(z = 30\) and a dual-feasible point gives \(w = 40\). What can you conclude about \(z^\star\)?
Solution. Weak duality says \(z \le w\) always, so \(30 \le z^\star \le 40\): the true optimum is trapped between the two. Any dual-feasible value is a certificate that the primal cannot exceed it — a cheap and rigorous bound before the problem is even solved.
Problem. The primal of Example 1 optimizes at \((2,6)\) with \(z^\star = 36\). Check the dual value at \(y = (0, \tfrac32, 1)\).
Solution. \(w = 4(0) + 12(\tfrac32) + 18(1) = 0 + 18 + 18 = 36\). Since \(z^\star = w^\star = 36\) and both points are feasible, strong duality holds and both are optimal — the values meet with no gap.
Problem. Given the primal optimum \((2,6)\) of Example 1, find the dual optimum using complementary slackness.
Solution. Primal constraint 1 has slack (\(2 < 4\)), so \(y_1 = 0\). Both primal variables are positive, so both dual constraints are binding: \(y_1 + 3y_3 = 3\) and \(2y_2 + 2y_3 = 5\). With \(y_1 = 0\), the first gives \(y_3 = 1\); the second gives \(2y_2 = 5 - 2 = 3 \Rightarrow y_2 = \tfrac32\). Thus \(y^\star = (0, \tfrac32, 1)\) — obtained without any simplex iterations.
Problem. A primal maximization has final \(z\)-row entries under its slacks \(s_1, s_2\) equal to \(2\) and \(5\), with \(b = (10, 8)\). State the dual solution and value.
Solution. The dual variables are the slack reduced costs: \(y^\star = (2, 5)\). The dual objective is \(w^\star = \mathbf{b}^{\mathsf T}y^\star = 10(2) + 8(5) = 60\), which must equal the primal optimum \(z^\star\). The final tableau delivered the entire dual solution — no separate dual solve required.
Chapter Summary
Every primal has a dual; the dual of the dual is the primal.
Swap max/min, transpose \(A\), exchange \(b \leftrightarrow c\); constraints become variables and vice versa.
\(\mathbf{c}^{\mathsf T}x \le \mathbf{b}^{\mathsf T}y\) always — every dual value bounds the primal optimum.
At optimality \(z^\star = w^\star\); LP has no duality gap.
Each primal–dual pair has at least one zero; recovers one optimum from the other.
Dual variables = marginal resource values, read from the \(z\)-row under the slacks.
Problems
For each item, apply the correspondence rules carefully and state which duality theorem you use. Difficulty rises down the list.
- Write the dual of \(\max\ z = 4x_1 + 3x_2\) s.t. \(2x_1 + x_2 \le 10,\ x_1 + 3x_2 \le 15,\ x \ge 0\).
- Write the dual of \(\min\ z = 5x_1 + 4x_2\) s.t. \(x_1 + x_2 \ge 6,\ 2x_1 + x_2 \ge 8,\ x \ge 0\).
- Dualise \(\max\ z = x_1 + 2x_2\) s.t. \(x_1 + x_2 = 4,\ x_1 - x_2 \le 1,\ x_1 \ge 0,\ x_2\ \text{free}\).
- State weak duality and use it to bound \(z^\star\) if a primal-feasible value is \(22\) and a dual-feasible value is \(31\).
- Explain why an unbounded primal forces the dual to be infeasible.
- The primal of Problem 1 optimizes at some \((x_1^\star, x_2^\star)\) with \(z^\star = 27\); what is the dual optimal value, and why?
- State the complementary slackness conditions and interpret each in resource-pricing language.
- Given a primal optimum where constraint 2 has slack and both variables are positive, deduce which dual variables are zero and which dual constraints are binding.
- A final primal tableau has \(z\)-row slack entries \(0, 4, 2\) with \(b = (6, 5, 9)\). State the dual solution and value.
- Show that the dual of the dual returns the original primal for the symmetric form.
- Use complementary slackness to find the dual optimum of \(\max\ z = 3x_1 + 5x_2\) (Example 1) if you are told only the primal optimum \((2,6)\).
- A furniture maker solves a profit-max LP and finds the shadow price of labour is ₹0 while machine-time is ₹4. Interpret both prices, explain what complementary slackness implies about labour usage at the optimum, and advise which resource to buy more of and up to what price.