Lesson 7: Duality and Sensitivity Analysis¶
7.1 Learning Outcomes¶
By the end of this hour a student will be able to:
- Construct the dual of any LP.
- State and apply weak duality, strong duality and complementary slackness.
- Interpret dual variables as shadow prices and use them for economic decisions.
- Compute ranging on objective coefficients and right-hand sides.
- Apply the 100 % rule for simultaneous changes.
7.2 The Dual Problem¶
Every LP (the primal) has a companion LP (the dual). They describe the same situation from opposite viewpoints: the primal allocates resources to activities; the dual prices those resources.
The construction¶
Primal (canonical maximisation):
Dual:
In words. Transpose everything.
| Primal | Dual |
|---|---|
| \(\max\) | \(\min\) |
| \(m\) constraints | \(m\) variables |
| \(n\) variables | \(n\) constraints |
| objective coefficients \(\vec c\) | right-hand sides \(\vec c\) |
| right-hand sides \(\vec b\) | objective coefficients \(\vec b\) |
| constraint matrix \(A\) | \(A^{T}\) |
| \(\le\) constraints | \(\ge\) constraints |
The full correspondence rules¶
| Primal (max) | Dual (min) |
|---|---|
| constraint \(\le\) | variable \(\ge 0\) |
| constraint \(\ge\) | variable \(\le 0\) |
| constraint \(=\) | variable unrestricted |
| variable \(\ge 0\) | constraint \(\ge\) |
| variable \(\le 0\) | constraint \(\le\) |
| variable unrestricted | constraint \(=\) |
Theorem. The dual of the dual is the primal.
7.3 The Three Duality Theorems¶
Weak duality¶
Theorem. If \(\vec x\) is feasible for the primal (max) and \(\vec y\) is feasible for the dual (min), then
Proof.
The first inequality uses the dual constraints \(A^{T}\vec y \ge \vec c\) with \(\vec x\ge0\); the second uses the primal constraints \(A\vec x\le\vec b\) with \(\vec y\ge0\). \(\blacksquare\)
Corollaries.
- Any dual-feasible \(\vec y\) gives an upper bound on the primal optimum — useful for certifying near-optimality.
- If the primal is unbounded, the dual is infeasible (and vice versa).
Strong duality¶
Theorem. If either problem has a finite optimum, so does the other, and
The four possible outcome pairs.
| Primal | Dual | Possible? |
|---|---|---|
| finite optimum | finite optimum | ✓ (the usual case) |
| unbounded | infeasible | ✓ |
| infeasible | unbounded | ✓ |
| infeasible | infeasible | ✓ (rare but possible) |
| finite | infeasible/unbounded | ✗ impossible |
Complementary slackness¶
Theorem. \(\vec x^{*}\) and \(\vec y^{*}\) are optimal for their respective problems iff
In words — the two rules that matter.
The economic reading. A resource that is not fully used has zero marginal value. If you have idle machine hours, an extra machine hour is worth nothing.
Symmetrically: an activity that is used (\(x_j > 0\)) must exactly break even at the shadow prices — its dual constraint holds with equality.
7.4 Shadow Prices¶
The marginal value of one extra unit of resource \(i\).
Where to read them. In the final simplex tableau, \(y_i = (z_j - c_j)\) in the column of slack \(s_i\).
Four practical uses.
- Purchasing. Buy an extra unit if its price is below \(y_i\).
- Pricing. \(y_i\) is the internal transfer price of the resource.
- Priorities. The largest \(y_i\) identifies the tightest bottleneck.
- Product costing. A new product is worth introducing only if its revenue exceeds \(\sum_i a_{i,\text{new}}y_i\) — its imputed resource cost.
7.5 Sensitivity Analysis (Ranging)¶
Ranging an objective coefficient c_j¶
For a NON-BASIC variable \(x_j\). It stays non-basic (so the plan is unchanged) while
For a BASIC variable \(x_j\). Changing \(c_j\) alters the whole \(z_k - c_k\) row. The basis stays optimal while, for every non-basic \(k\),
where \(\alpha_{jk}\) is the entry in row \(x_j\), column \(k\) of the final tableau. Solving gives
Ranging a right-hand side b_i¶
Changing \(b_i\) by \(\Delta\) changes the basic variables to
where \((B^{-1})_{\cdot i}\) is the \(s_i\) column of the final tableau. Feasibility requires \(\vec x_B^{\text{new}} \ge 0\):
Within this range the shadow price \(y_i\) is constant; outside it, the basis changes and a new shadow price applies.
The 100 % rule¶
For simultaneous changes, compute each change as a fraction of its allowable range in the direction of change. If
then the basis (and therefore all shadow prices) remain valid. If the sum exceeds 1, re-solve — the rule gives no conclusion either way.
7.6 Solved Problems¶
Problem 1 — Constructing and verifying a dual¶
Form the dual of the following, solve both, and verify strong duality.
Solution.
The dual. Three constraints ⟹ three dual variables \(y_1,y_2,y_3 \ge 0\); two primal variables ⟹ two dual constraints.
Solving the primal by simplex. The final tableau is
| Basis | \(c_B\) | \(x_1\) | \(x_2\) | \(s_1\) | \(s_2\) | \(s_3\) | RHS |
|---|---|---|---|---|---|---|---|
| \(s_1\) | 0 | 0 | 0 | 1 | \(1/3\) | \(-1/3\) | 2 |
| \(x_2\) | 5 | 0 | 1 | 0 | \(1/2\) | 0 | 6 |
| \(x_1\) | 3 | 1 | 0 | 0 | \(-1/3\) | \(1/3\) | 2 |
| \(z_j-c_j\) | 0 | 0 | 0 | 3/2 | 1 | 36 |
Reading the dual solution off the slack columns.
Verifying dual feasibility.
Verifying strong duality.
Verifying complementary slackness.
| \(i\) | Constraint | LHS at optimum | Slack | \(y_i\) | \(y_i\times\text{slack}\) |
|---|---|---|---|---|---|
| 1 | \(x_1\le4\) | \(2\) | \(\mathbf{2}\) | \(\mathbf{0}\) | 0 ✓ |
| 2 | \(2x_2\le12\) | \(12\) | 0 | \(3/2\) | 0 ✓ |
| 3 | \(3x_1+2x_2\le18\) | \(18\) | 0 | \(1\) | 0 ✓ |
Constraint 1 has slack 2, and its shadow price is exactly 0 — Rule 1 confirmed. Resource 1 is not scarce, so an extra unit of it is worthless.
Problem 2 — Economic decisions from shadow prices¶
Using Problem 1's shadow prices \((0,\ 1.5,\ 1)\): (a) Should the firm buy 3 more units of resource 2 at ₹1.20 each? (b) At ₹2.00 each? (c) A new product needs 1 unit of resource 1, 2 of resource 2 and 2 of resource 3, and sells for ₹6. Should it be introduced?
Solution.
(a) 3 units of resource 2 at ₹1.20.
Range check. The \(s_2\) column of the final tableau is \(\left(\frac13,\ \frac12,\ -\frac13\right)^T\) against basic values \((2,\ 6,\ 2)\). Increasing \(b_2\) by \(\Delta\):
\(\Delta = 3 \le 6\) ✓ — the ₹1.50 rate applies fully.
(b) At ₹2.00.
The general rule: buy resource \(i\) if and only if its market price is below \(y_i\).
(c) The new product.
Its imputed resource cost at the shadow prices is
Its revenue is ₹6.
This is exactly the simplex entering-variable test, applied to a column that was not in the original problem. It is called column generation and is the engine behind large-scale LP (airline crew scheduling, cutting-stock problems), where columns are generated on demand rather than enumerated in advance.
(If instead the product sold for ₹4, the reduced cost would be \(4-5 = -1 < 0\) and it should not be produced — it would destroy ₹1 of value per unit by consuming resources worth more than it earns.)
Problem 3 — Ranging a right-hand side¶
For Problem 1, find the range over which \(b_3 = 18\) may vary with the shadow price \(y_3 = 1\) still valid, and compute \(Z^{*}\) at the endpoints.
Solution.
The \(s_3\) column of the final tableau is \(\left(-\frac13,\ 0,\ \frac13\right)^{T}\) against basic values \((s_1, x_2, x_1) = (2,\ 6,\ 2)\).
Changing \(b_3\) by \(\Delta\):
Feasibility conditions.
Objective at the endpoints.
At \(b_3 = 24\) (\(\Delta = +6\)): \(x_1 = 4\), \(x_2 = 6\), \(s_1 = 0\).
At \(b_3 = 12\) (\(\Delta = -6\)): \(x_1 = 0\), \(x_2 = 6\), \(s_1 = 4\).
Both confirm \(y_3 = 1\) exactly.
What happens beyond the range? At \(b_3 = 24\), \(s_1\) hits zero — constraint 1 (\(x_1\le4\)) becomes binding. Push further and the basis must change: \(x_1\) can no longer grow, so the extra resource 3 becomes useless.
The management lesson. "Resource 3 is worth ₹1 per unit" is true only up to 24 units. Beyond that, buying more is pointless. Never quote a shadow price without its range — this is the single most common error in applying LP results.
Problem 4 — Ranging an objective coefficient¶
For Problem 1, find the range of \(c_2 = 5\) (the profit on \(x_2\)) keeping the current basis optimal.
Solution.
\(x_2\) is basic, in row 2 of the final tableau. Its row is
The non-basic variables are \(s_1, s_2, s_3\) with \(z_j-c_j = (0,\ \frac32,\ 1)\).
Changing \(c_2\) by \(\Delta\) changes each \(z_k - c_k\) by \(\Delta\alpha_{2k}\), where \(\alpha_{2k}\) is the entry in \(x_2\)'s row:
| Non-basic \(k\) | \(z_k-c_k\) | \(\alpha_{2k}\) | New value |
|---|---|---|---|
| \(s_1\) | 0 | 0 | \(0\) (unaffected) |
| \(s_2\) | \(3/2\) | \(1/2\) | \(\tfrac32 + \tfrac{\Delta}{2}\) |
| \(s_3\) | 1 | 0 | \(1\) (unaffected) |
Optimality requires all \(\ge 0\):
No upper restriction (no non-basic column has a negative entry in \(x_2\)'s row).
Interpretation. The plan \((2, 6)\) stays optimal as long as product 2's profit is at least ₹2 — and however high it goes. Only \(Z\) changes.
Verification at \(c_2 = 2\).
Compare the neighbouring corner \((4, 3)\): \(Z = 3(4)+2(3) = 12+6 = 18\) — a tie, confirming that \(c_2 = 2\) is exactly the boundary where alternate optima appear ✓.
Verification at \(c_2 = 1.9\) (just below).
\((4,3)\) now wins — the basis has changed, as predicted ✓.
Problem 5 — The 100 % rule for simultaneous changes¶
For Problem 1, suppose \(b_2\) increases by 2 and \(b_3\) increases by 3 simultaneously. Are the shadow prices still valid? Compute the new \(Z^{*}\).
Solution.
Step 1 — the individual allowable ranges.
For \(b_2\) (column \(\left(\frac13,\ \frac12,\ -\frac13\right)^T\), basics \((2,6,2)\)):
Allowable increase in \(b_2\): 6.
For \(b_3\) (from Problem 3): allowable increase: 6.
Step 2 — the fractions.
Step 3 — the new objective value.
Step 4 — direct verification. With \(b_2 = 14\) and \(b_3 = 21\), the new basic values are
All non-negative ✓ — the basis is indeed still feasible.
Check the original constraints.
A cautionary counter-example. Had the changes been \(\Delta_2 = 5\) and \(\Delta_3 = 5\):
The rule gives no guarantee — you must re-solve. (Note the rule is only sufficient: exceeding 100 % does not prove the basis changed, it merely means you cannot conclude it did not.)
Checking directly: \(x_1 = 2 - \frac53 + \frac53 = 2 \ge 0\) ✓ and \(s_1 = 2+\frac53-\frac53 = 2 \ge 0\) ✓ — the basis actually does survive here. The 100 % rule is conservative, which is exactly what you want from a safety check.
7.7 Practice Problems¶
- Write the dual of \(\min\ 4y_1+6y_2\) s.t. \(y_1+2y_2\ge3\), \(3y_1+y_2\ge5\), \(y\ge0\).
- If a primal is unbounded, what can you say about its dual? [Ans: infeasible]
- Given slack \(= 5\) on constraint 2, what is \(y_2\)? [Ans: 0, by complementary slackness]
- A resource costs ₹8/unit in the market and has shadow price ₹6. Buy or not? [Ans: do not buy]
- Verify \(\vec b^{T}\vec y^{*} = Z^{*}\) for the furniture problem of L05.
- Changes use 40 %, 30 % and 20 % of their ranges. Is the basis still optimal? [Ans: 90 % ≤ 100 %, yes]
- A new product's imputed cost is ₹12 and it sells for ₹10. Introduce it? [Ans: no — reduced cost \(-2\)]
7.8 Summary¶
- The dual transposes the primal: \(m\) constraints ↔ \(m\) variables, \(\vec b\) ↔ \(\vec c\), \(A\) ↔ \(A^{T}\), \(\le\) ↔ \(\ge\). The dual of the dual is the primal.
- Weak duality: any dual-feasible solution bounds the primal optimum. Strong duality: \(Z^{*} = W^{*}\). Complementary slackness: slack > 0 ⟹ shadow price 0, and shadow price > 0 ⟹ constraint binding.
- Shadow prices \(y_i = \partial Z^{*}/\partial b_i\) are read from the slack columns' \(z_j-c_j\) entries. Use them for buying decisions, bottleneck priorities and product costing (reduced cost \(= c_{\text{new}} - \sum_i a_iy_i\) — the basis of column generation).
- Ranging: an RHS range comes from keeping \(\vec x_B + \Delta(B^{-1})_{\cdot i} \ge 0\); an objective-coefficient range comes from keeping all \(z_k-c_k \ge 0\).
- Never quote a shadow price without its range — beyond the range the price changes, often to zero.
- The 100 % rule validates simultaneous changes: if the fractions of the allowable ranges sum to at most 1, the basis survives. It is sufficient but not necessary — conservative by design.
Next lesson: L08 — The transportation problem: formulation and initial basic feasible solutions.
Practise now: unit1-lp-lab.html → Duality & Sensitivity: solve any LP and see the dual,
shadow prices, ranging tables and a live 100 %-rule calculator.