Skip to content

Lesson 7: Duality and Sensitivity Analysis

7.1 Learning Outcomes

By the end of this hour a student will be able to:

  1. Construct the dual of any LP.
  2. State and apply weak duality, strong duality and complementary slackness.
  3. Interpret dual variables as shadow prices and use them for economic decisions.
  4. Compute ranging on objective coefficients and right-hand sides.
  5. 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):

\[ \max\ Z = \sum_{j=1}^{n} c_jx_j \quad\text{s.t.}\quad \sum_{j=1}^{n}a_{ij}x_j \le b_i\ (i=1..m), \quad x_j\ge0 \]

Dual:

\[ \min\ W = \sum_{i=1}^{m} b_iy_i \quad\text{s.t.}\quad \sum_{i=1}^{m}a_{ij}y_i \ge c_j\ (j=1..n), \quad y_i\ge0 \]

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

\[ \boxed{\ \vec c^{T}\vec x \ \le\ \vec b^{T}\vec y\ } \]

Proof.

\[ \vec c^{T}\vec x \ \le\ (A^{T}\vec y)^{T}\vec x = \vec y^{T}A\vec x \ \le\ \vec y^{T}\vec b \]

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

\[ \boxed{\ Z^{*}_{\text{primal}} \ =\ W^{*}_{\text{dual}}\ } \]

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

\[ \boxed{\ y_i^{*}\left(b_i - \sum_j a_{ij}x_j^{*}\right) = 0 \quad\text{for all } i\ } \]
\[ \boxed{\ x_j^{*}\left(\sum_i a_{ij}y_i^{*} - c_j\right) = 0 \quad\text{for all } j\ } \]

In words — the two rules that matter.

\[ \textbf{Rule 1: } \ \text{slack}_i > 0 \ \Longrightarrow\ y_i^{*} = 0 \]
\[ \textbf{Rule 2: } \ y_i^{*} > 0 \ \Longrightarrow\ \text{constraint } i \text{ is binding} \]

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

\[ \boxed{\ y_i^{*} = \frac{\partial Z^{*}}{\partial b_i}\ } \]

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.

  1. Purchasing. Buy an extra unit if its price is below \(y_i\).
  2. Pricing. \(y_i\) is the internal transfer price of the resource.
  3. Priorities. The largest \(y_i\) identifies the tightest bottleneck.
  4. 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

\[ c_j \ \le\ z_j \qquad\Longleftrightarrow\qquad c_j \le c_j^{\text{current}} + (z_j - c_j) \]

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\),

\[ z_k - c_k + \Delta c_j\,\alpha_{jk} \ \ge\ 0 \]

where \(\alpha_{jk}\) is the entry in row \(x_j\), column \(k\) of the final tableau. Solving gives

\[ \max_{k:\ \alpha_{jk}<0}\left\{\frac{-(z_k-c_k)}{\alpha_{jk}}\right\} \ \le\ \Delta c_j \ \le\ \min_{k:\ \alpha_{jk}>0}\left\{\frac{-(z_k-c_k)}{\alpha_{jk}}\right\} \]

Ranging a right-hand side b_i

Changing \(b_i\) by \(\Delta\) changes the basic variables to

\[ \vec x_B^{\text{new}} = \vec x_B + \Delta\,\big(B^{-1}\big)_{\cdot i} \]

where \((B^{-1})_{\cdot i}\) is the \(s_i\) column of the final tableau. Feasibility requires \(\vec x_B^{\text{new}} \ge 0\):

\[ \boxed{\ \max_{k:\ \beta_{ki}>0}\left\{\frac{-x_{B_k}}{\beta_{ki}}\right\} \ \le\ \Delta \ \le\ \min_{k:\ \beta_{ki}<0}\left\{\frac{-x_{B_k}}{\beta_{ki}}\right\}\ } \]

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

\[ \sum_i \frac{|\Delta_i|}{\text{allowable range}_i} \ \le\ 1 \]

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.

\[ \max\ Z = 3x_1+5x_2 \quad \text{s.t.}\quad x_1\le4,\ \ 2x_2\le12,\ \ 3x_1+2x_2\le18,\ \ x_1,x_2\ge0 \]

Solution.

The dual. Three constraints ⟹ three dual variables \(y_1,y_2,y_3 \ge 0\); two primal variables ⟹ two dual constraints.

\[ \begin{aligned} \min\ & W = 4y_1 + 12y_2 + 18y_3\\ \text{s.t. } & y_1 + 3y_3 \ge 3 && \text{(from the } x_1 \text{ column)}\\ & 2y_2 + 2y_3 \ge 5 && \text{(from the } x_2 \text{ column)}\\ & y_1,y_2,y_3 \ge 0 \end{aligned} \]

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
\[ \boxed{\ x_1^{*} = 2,\ x_2^{*} = 6,\ Z^{*} = 3(2)+5(6) = 36\ } \]

Reading the dual solution off the slack columns.

\[ y_1^{*} = 0, \qquad y_2^{*} = \tfrac32 = 1.5, \qquad y_3^{*} = 1 \]

Verifying dual feasibility.

\[ y_1 + 3y_3 = 0 + 3 = 3 \ge 3 \ \checkmark \ \text{(equality)} \]
\[ 2y_2 + 2y_3 = 3 + 2 = 5 \ge 5 \ \checkmark \ \text{(equality)} \]

Verifying strong duality.

\[ W = 4(0) + 12(1.5) + 18(1) = 0 + 18 + 18 = \mathbf{36} = Z^{*} \ \checkmark \]
\[ \boxed{\ Z^{*} = W^{*} = 36\ } \]

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.

\[ \text{marginal value} = ₹1.50 > ₹1.20 = \text{price} \]
\[ \text{net gain} = 3\times(1.50-1.20) = \mathbf{₹0.90} \]
\[ \boxed{\textbf{BUY}} \]

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\):

\[ s_1 = 2 + \tfrac{\Delta}{3} \ge 0 \ \ \text{always}; \quad x_2 = 6+\tfrac{\Delta}{2}\ge0 \ \ \text{always}; \quad x_1 = 2 - \tfrac{\Delta}{3}\ge0 \ \Longrightarrow\ \Delta \le 6 \]

\(\Delta = 3 \le 6\) ✓ — the ₹1.50 rate applies fully.

(b) At ₹2.00.

\[ ₹2.00 > ₹1.50 \ \Longrightarrow\ \text{net loss of } 3\times0.50 = ₹1.50 \]
\[ \boxed{\textbf{DO NOT BUY}} \]

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

\[ \sum_i a_{i,\text{new}}\,y_i = 1(0) + 2(1.5) + 2(1) = 0 + 3 + 2 = ₹5 \]

Its revenue is ₹6.

\[ \text{reduced cost} = c_{\text{new}} - z_{\text{new}} = 6 - 5 = \mathbf{+₹1} > 0 \]
\[ \boxed{\textbf{INTRODUCE IT — it earns ₹1 more than the resources it consumes are worth.}} \]

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\):

\[ s_1 = 2 - \tfrac{\Delta}{3}, \qquad x_2 = 6 + 0 = 6, \qquad x_1 = 2 + \tfrac{\Delta}{3} \]

Feasibility conditions.

\[ s_1 \ge 0: \quad 2 - \tfrac{\Delta}{3} \ge 0 \ \Longrightarrow\ \Delta \le 6 \]
\[ x_1 \ge 0: \quad 2 + \tfrac{\Delta}{3} \ge 0 \ \Longrightarrow\ \Delta \ge -6 \]
\[ \boxed{\ -6 \le \Delta \le 6 \qquad\Longleftrightarrow\qquad 12 \le b_3 \le 24\ } \]

Objective at the endpoints.

At \(b_3 = 24\) (\(\Delta = +6\)): \(x_1 = 4\), \(x_2 = 6\), \(s_1 = 0\).

\[ Z = 3(4)+5(6) = 12+30 = 42 = 36 + 6(1) \ \checkmark \]

At \(b_3 = 12\) (\(\Delta = -6\)): \(x_1 = 0\), \(x_2 = 6\), \(s_1 = 4\).

\[ Z = 0 + 30 = 30 = 36 - 6(1) \ \checkmark \]

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.

\[ \text{At } b_3 = 30: \ x_1 = 4, x_2 = 6 \ \text{still, so } Z = 42 \ \text{— unchanged.} \]
\[ \boxed{\ \text{For } b_3 > 24 \text{ the shadow price DROPS TO ZERO.}\ } \]

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

\[ (x_1,\ x_2,\ s_1,\ s_2,\ s_3) = \left(0,\ 1,\ 0,\ \tfrac12,\ 0\right) \]

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\):

\[ \tfrac32 + \tfrac{\Delta}{2} \ge 0 \ \Longrightarrow\ \Delta \ge -3 \]

No upper restriction (no non-basic column has a negative entry in \(x_2\)'s row).

\[ \boxed{\ \Delta \ge -3 \qquad\Longleftrightarrow\qquad c_2 \ge 2, \ \text{ with no upper limit}\ } \]

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\).

\[ Z(2,6) = 3(2)+2(6) = 6+12 = 18 \]

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).

\[ Z(2,6) = 6 + 11.4 = 17.4, \qquad Z(4,3) = 12 + 5.7 = 17.7 \]

\((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)\)):

\[ x_1 = 2 - \tfrac{\Delta_2}{3} \ge 0 \ \Longrightarrow\ \Delta_2 \le 6 \]

Allowable increase in \(b_2\): 6.

For \(b_3\) (from Problem 3): allowable increase: 6.

Step 2 — the fractions.

\[ \frac{\Delta_2}{6} + \frac{\Delta_3}{6} = \frac{2}{6} + \frac{3}{6} = 0.333 + 0.500 = \mathbf{0.833} \]
\[ 0.833 \ \le\ 1 \]
\[ \boxed{\ \textbf{The 100 \% rule holds — the basis and both shadow prices remain valid.}\ } \]

Step 3 — the new objective value.

\[ Z^{*}_{\text{new}} = 36 + 2(1.5) + 3(1) = 36 + 3 + 3 = \mathbf{42} \]

Step 4 — direct verification. With \(b_2 = 14\) and \(b_3 = 21\), the new basic values are

\[ s_1 = 2 + \tfrac{2}{3} - \tfrac{3}{3} = 2 + 0.667 - 1 = 1.667 \]
\[ x_2 = 6 + \tfrac{2}{2} + 0 = 7 \]
\[ x_1 = 2 - \tfrac{2}{3} + \tfrac{3}{3} = 2 - 0.667 + 1 = 2.333 \]

All non-negative ✓ — the basis is indeed still feasible.

\[ Z = 3(2.333) + 5(7) = 7.00 + 35 = \mathbf{42} \ \checkmark \]

Check the original constraints.

\[ x_1 = 2.333 \le 4 \ \checkmark \ (s_1 = 1.667) \]
\[ 2x_2 = 14 \le 14 \ \checkmark \ \text{(binding)} \]
\[ 3(2.333)+2(7) = 7+14 = 21 \le 21 \ \checkmark \ \text{(binding)} \]

A cautionary counter-example. Had the changes been \(\Delta_2 = 5\) and \(\Delta_3 = 5\):

\[ \frac{5}{6}+\frac{5}{6} = 1.667 > 1 \]

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

  1. Write the dual of \(\min\ 4y_1+6y_2\) s.t. \(y_1+2y_2\ge3\), \(3y_1+y_2\ge5\), \(y\ge0\).
  2. If a primal is unbounded, what can you say about its dual? [Ans: infeasible]
  3. Given slack \(= 5\) on constraint 2, what is \(y_2\)? [Ans: 0, by complementary slackness]
  4. A resource costs ₹8/unit in the market and has shadow price ₹6. Buy or not? [Ans: do not buy]
  5. Verify \(\vec b^{T}\vec y^{*} = Z^{*}\) for the furniture problem of L05.
  6. Changes use 40 %, 30 % and 20 % of their ranges. Is the basis still optimal? [Ans: 90 % ≤ 100 %, yes]
  7. 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.