Duality and sensitivity analysis

Why it matters

An LP answer is only the start of the manager's questions: what is one more machine-hour worth, how far can a price fall before the plan changes, should a new product be introduced? Duality and sensitivity analysis answer these from the final simplex tableau without re-solving. Shadow prices are how production engineers justify overtime, outsourcing and capacity purchases.

Key ideas

The dual problem. Every LP (the primal) has a partner LP (the dual) built from the same data. For a primal in canonical maximisation form (all constraints ≤, variables ≥ 0):

• each primal constraint i gets a dual variable yᵢ ≥ 0;
• primal Max becomes dual Min; primal RHS bᵢ become dual objective coefficients; primal objective coefficients cⱼ become dual RHS;
• the coefficient matrix is transposed; ≤ constraints become ≥. Variations: a primal = constraint gives an unrestricted (free) dual variable; a primal ≥ constraint in a Max problem gives yᵢ ≤ 0 (or multiply it by −1 first). The dual of the dual is the primal.

Economic meaning. If the primal maximises profit from scarce resources, yᵢ is the shadow price (imputed value) of one more unit of resource i. The dual asks: what is the least total value I can put on my resources so that every product is "paid for" (Σ aᵢⱼ yᵢ ≥ cⱼ)?

Duality theorems.

• Weak duality: for any feasible primal x (Max) and feasible dual y (Min), Z(x) ≤ W(y). Any feasible dual value is an upper bound on the primal optimum.
• Strong duality: if either problem has a finite optimum, so does the other and Z* = W*.
• If the primal is unbounded, the dual is infeasible (and vice versa). Both can also be infeasible.
• Complementary slackness: at optimality, (slack of primal constraint i) × yᵢ = 0 and (surplus of dual constraint j) × xⱼ = 0. A resource that is not fully used has zero shadow price; a product that is made has zero reduced cost.

Reading duals from the final tableau. In a Max problem with ≤ constraints, the optimal yᵢ is the |Cj − Zj| (equivalently Zj) entry under slack sᵢ.

Sensitivity (post-optimality) analysis. The current optimal basis stays optimal while:

• RHS change — the basic variables stay non-negative (feasibility). Within that range Z changes at the rate of the shadow price, but the values of the basic variables change.
• Objective-coefficient change — all reduced costs keep their optimal sign (optimality). Within that range the solution x* is unchanged; only Z changes.
• New variable — price it out: worth adding only if cⱼ − Σ aᵢⱼ yᵢ > 0 (Max). Outside a range the basis changes and the shadow price is no longer valid.

Formulas

• Primal: Max Z = cᵀx, A x ≤ b, x ≥ 0
• Dual: Min W = bᵀy, Aᵀ y ≥ c, y ≥ 0
• Weak duality: cᵀx ≤ bᵀy for any feasible pair
• Strong duality: Z* = W*
• Complementary slackness: yᵢ · sᵢ = 0, xⱼ · tⱼ = 0
• Marginal effect of RHS: ΔZ = yᵢ · Δbᵢ (valid inside the RHS range)
• Reduced cost of activity j: c̄ⱼ = cⱼ − Σ aᵢⱼ yᵢ

Symbols: x = primal decision variables (units); c = profit coefficients (₹/unit); A = technology matrix (resource per unit); b = resources available (h, kg…); y = dual variables or shadow prices (₹ per unit of resource); sᵢ = primal slack; tⱼ = dual surplus.

Worked examples

Example 1 (dual and shadow prices). Primal: Max Z = 3x₁ + 5x₂ subject to x₁ ≤ 4, 2x₂ ≤ 12, 3x₁ + 2x₂ ≤ 18, x ≥ 0 (Z in ₹ thousand, resources in hours). Its optimum is x₁ = 2, x₂ = 6, Z = 36.

1. Dual: Min W = 4y₁ + 12y₂ + 18y₃ subject to y₁ + 3y₃ ≥ 3, 2y₂ + 2y₃ ≥ 5, y ≥ 0.
2. Complementary slackness: constraint 1 has slack 4 − 2 = 2 > 0, so y₁ = 0. Both x₁, x₂ > 0, so both dual constraints are equalities.
3. From 3y₃ = 3 → y₃ = 1; from 2y₂ + 2(1) = 5 → y₂ = 1.5.
4. W = 4(0) + 12(1.5) + 18(1) = 18 + 18 = 36 = Z ✓ (strong duality).
5. Shadow prices: Plant 1 ₹0, Plant 2 ₹1.5 thousand/h, Plant 3 ₹1 thousand/h.

Example 2 (GATE-type ranging). For the same problem, find (a) the range of b₃ (Plant 3 hours) over which y₃ = 1 stays valid and Z at b₃ = 20 h; (b) the range of c₁ over which (2, 6) stays optimal.

1. The optimal basis is (x₁, x₂, s₁). With constraints 2 and 3 binding: x₂ = 12/2 = 6, x₁ = (b₃ − 2·6)/3 = (b₃ − 12)/3, s₁ = 4 − x₁.
2. Feasibility: x₁ ≥ 0 → b₃ ≥ 12; s₁ ≥ 0 → (b₃ − 12)/3 ≤ 4 → b₃ ≤ 24. So 12 h ≤ b₃ ≤ 24 h.
3. At b₃ = 20: ΔZ = y₃ · Δb₃ = 1 × (20 − 18) = 2, so Z = 38 (₹ thousand) with x₁ = 8/3, x₂ = 6. Check: 3(8/3) + 5(6) = 8 + 30 = 38 ✓.
4. Objective ranging: the corner (2, 6) is where x₂ = 6 (slope 0) meets 3x₁ + 2x₂ = 18 (slope −3/2). It stays optimal while the iso-profit slope −c₁/5 lies between −3/2 and 0, i.e. 0 ≤ c₁ ≤ 7.5 (₹ thousand per door). At c₁ = 7.6 the corner (4, 3) becomes better (Z = 45.4 > 45.2).

Common mistakes

• Forgetting to put the primal in canonical form before writing the dual (a ≥ row in a Max problem gives a non-positive dual variable).
• Using a shadow price outside its RHS range, where the basis has changed.
• Thinking an RHS change inside the range leaves the solution unchanged — the basic variable values do change; only the basis stays.
• Reading the shadow price with the wrong sign from a Zj − Cj versus Cj − Zj tableau.
• Assigning a positive shadow price to a resource that has slack (violates complementary slackness).
• Believing "primal infeasible ⇒ dual unbounded" always; both can be infeasible.

For GATE PI

• Write the dual of a 2–3 variable LP and identify its number of variables and constraints.
• Use complementary slackness to get the dual optimum from a known primal optimum.
• Interpret shadow prices from a final tableau and compute ΔZ for a small RHS change.
• Conceptual MCQs on weak and strong duality and primal–dual status combinations.

Quick check

1. A Max primal has 3 constraints and 2 variables. How many variables does its dual have?
2. A resource has 5 units of slack at the optimum. What is its shadow price?
3. Primal Max is unbounded. What can you say about the dual?
4. In Example 1, Plant 2 hours rise from 12 to 13 (within range). What is the new Z?

Answers: 1. Three. 2. Zero. 3. It is infeasible. 4. 36 + 1.5 = 37.5 (₹ thousand).