Sensitivity and Post-Optimality Analysis
An LP solution is only as trustworthy as the numbers fed into it — and those numbers are usually estimates. Will next quarter's prices shift? Might a supplier deliver more? The most valuable output of an LP is often not the optimal plan itself but the answer to "what if?" Sensitivity analysis tells you exactly how far each coefficient can move before the solution changes, how much a scarce resource is worth and over what range, and whether a new product is worth launching — all read from the final tableau, without ever re-solving.
- Why sensitivity analysis matters and what "what-if" questions it answers without re-solving.
- How reduced costs certify optimality and price non-basic variables.
- The range of optimality for objective coefficients — how far \(c_j\) can move.
- The range of feasibility for right-hand sides — how far \(b_i\) can move.
- The range over which a shadow price stays valid, and how \(z^\star\) changes.
- Handling added variables/constraints and simultaneous changes via the 100% rule.
Why Sensitivity Analysis?
Real LP data are forecasts: profit margins, resource availabilities, and usage rates are all estimated and all liable to change. Sensitivity analysis (also called post-optimality or "what-if" analysis) studies how the optimal solution and its value respond to such changes — and, crucially, does so by exploiting the structure already computed in the final tableau, so no fresh optimization is needed.
We will lean on the running Wyndor example. Its final tableau (Chapter 8) was:
| Basis | x₁ | x₂ | s₁ | s₂ | s₃ | RHS |
|---|---|---|---|---|---|---|
| s₁ | 0 | 0 | 1 | 1/3 | −1/3 | 2 |
| x₂ | 0 | 1 | 0 | 1/2 | 0 | 6 |
| x₁ | 1 | 0 | 0 | −1/3 | 1/3 | 2 |
| z | 0 | 0 | 0 | 3/2 | 1 | 36 |
with \(c = (3, 5)\), \(b = (4, 12, 18)\), optimum \((x_1, x_2) = (2, 6)\), \(z^\star = 36\), and dual (shadow) prices \(y = (0, \tfrac32, 1)\). Every range below comes straight out of this table.
Reduced Costs and Optimality
The \(z\)-row entries are the reduced costs. A basic variable always has reduced cost zero. A non-basic variable's reduced cost is how much its objective coefficient would have to improve before it becomes worth bringing into the basis — the built-in "price" of forcing it in. At optimality (maximization) all reduced costs are \(\ge 0\).
If a non-basic variable's coefficient \(c_j\) rises by more than its reduced cost, its reduced cost turns negative and it enters the basis — the plan changes. So the reduced cost is precisely the allowable increase in \(c_j\) for a non-basic variable before the current solution stops being optimal.
Ranging Objective Coefficients
The range of optimality of a coefficient \(c_j\) is the interval over which it can vary while the current optimal solution (the same vertex, the same basis) stays optimal — though \(z^\star\) itself changes. Geometrically, changing \(c_j\) rotates the objective line; the vertex stays optimal as long as the line's slope remains within the "cone" formed by its two binding edges.
Algebraically, for a basic variable, changing \(c_j\) by \(\Delta\) shifts every non-basic reduced cost by \(\Delta\) times that variable's row entry; the range is the set of \(\Delta\) keeping all reduced costs \(\ge 0\). For \(x_1\) in Wyndor (\(c_1 = 3\)), the \(x_1\)-row entries under \(s_2, s_3\) are \(-1/3\) and \(1/3\), and the current reduced costs are \(3/2\) and \(1\):
Ranging the Right-Hand Side
The range of feasibility of a right-hand side \(b_i\) is the interval over which the current basis stays feasible (all basic variables remain \(\ge 0\)). Changing \(b_i\) by \(\Delta\) shifts every basic variable by \(\Delta\) times the corresponding entry of that constraint's slack column (which encodes \(B^{-1}\)). For Wyndor's \(b_2 = 12\), the \(s_2\) column is \((1/3, 1/2, -1/3)\) and the basic values are \((s_1, x_2, x_1) = (2, 6, 2)\):
Over this range the set of binding constraints — the basis — is unchanged, so the shadow price stays constant and the optimal value moves linearly with \(b_2\). Outside it, a different constraint becomes binding and a new shadow price takes over.
Shadow Prices and Their Range
The shadow price \(y_i\) is the rate at which the optimal value improves per unit increase in \(b_i\) — but only while the basis holds. Plotting \(z^\star\) against \(b_i\) gives a piecewise-linear curve whose slope is the shadow price on each segment; the slope steps down (for a maximization) at each breakpoint where the basis changes.
For Wyndor, raising \(b_2\) from \(12\) to \(15\) (\(\Delta = 3\), inside \([6,18]\)) gives \(\Delta z^\star = \tfrac32 \times 3 = 4.5\), so \(z^\star\) rises from \(36\) to \(40.5\). Beyond \(b_2 = 18\) the shadow price drops and this rate no longer applies — the single most common mistake in sensitivity analysis is applying a shadow price outside its valid range.
Adding a Variable or a Constraint
Post-optimality questions often introduce something new. To evaluate a new variable (say a proposed product), compute its reduced cost using the existing dual prices: \(\bar{c}_{\text{new}} = c_{\text{new}} - \mathbf{y}^{\mathsf T}\mathbf{a}_{\text{new}}\). For a maximization, if \(\bar{c}_{\text{new}} > 0\) the product improves the objective and should enter; if \(\le 0\), the current plan remains optimal and the product is not worth making at that margin.
To evaluate a new constraint, simply test whether the current optimum satisfies it. If it does, the optimum is unchanged — the constraint was redundant at this solution. If it does not, the old optimum is now infeasible and the problem must be re-optimized (efficiently, via the dual simplex method, starting from the old tableau).
Simultaneous Changes: The 100% Rule
The ranges above each assume one coefficient changes at a time. When several change together, the 100% rule gives a sufficient condition for the current solution to remain optimal (for objective changes) or the basis to remain feasible (for right-hand-side changes).
Add up each change as a fraction of its own allowable range (in the direction it moves). If the total is at most \(100\%\), optimality is guaranteed. If it exceeds \(100\%\), the rule is silent — the solution might still be optimal, but you must re-solve to be sure. The same rule, applied to right-hand sides and their feasibility ranges, protects the basis.
Worked Examples
Problem. A non-basic product has reduced cost \(\bar{c} = 4\) (₹/unit) in a maximization. What does it mean, and by how much must its profit rise to make it worth producing?
Solution. A positive reduced cost of \(4\) means introducing one unit of this product would reduce the objective by \(4\) at current prices — so it stays out. Its profit coefficient must increase by more than \(4\) before its reduced cost turns negative and it enters the optimal plan. Below that, the current solution is unchanged.
Problem. Find the range of optimality of \(c_1 = 3\) in Wyndor.
Solution. With \(x_1\)-row entries \(-1/3\) (under \(s_2\)) and \(1/3\) (under \(s_3\)) and reduced costs \(3/2\) and \(1\): keeping both \(\ge 0\) requires \(\Delta \le 9/2\) and \(\Delta \ge -3\). So \(c_1 \in [0, 7.5]\). Within this range the optimum stays at \((2,6)\); only \(z^\star\) changes. (This matches the graphical cone: the objective slope \(-c_1/5\) must lie between the two binding edges' slopes, \(0\) and \(-3/2\).)
Problem. Over what range of \(b_2 = 12\) does the shadow price \(y_2 = 3/2\) remain valid?
Solution. Using the \(s_2\) column \((1/3, 1/2, -1/3)\) against basic values \((2, 6, 2)\): \(2 + \Delta/3 \ge 0\), \(6 + \Delta/2 \ge 0\), \(2 - \Delta/3 \ge 0\) give \(-6 \le \Delta \le 6\), so \(b_2 \in [6, 18]\). The shadow price \(3/2\) holds throughout this interval.
Problem. If \(b_2\) rises from \(12\) to \(16\), find the new \(z^\star\).
Solution. \(\Delta = 4\) is within \([6, 18]\), so the shadow price applies: \(\Delta z^\star = y_2 \Delta b_2 = \tfrac32 (4) = 6\). Thus \(z^\star\) rises from \(36\) to \(42\). Had \(\Delta\) exceeded \(6\) (taking \(b_2\) past \(18\)), we could not use \(3/2\) for the whole increase.
Problem. A new product would use \((0, 2, 2)\) of the three resources and earn ₹6. Should Wyndor make it? (Shadow prices \(y = (0, \tfrac32, 1)\).)
Solution. Reduced cost \(= c_{\text{new}} - \mathbf{y}^{\mathsf T}\mathbf{a}_{\text{new}} = 6 - (0\cdot0 + \tfrac32\cdot2 + 1\cdot2) = 6 - 5 = 1 > 0\). Positive, so introducing it would raise profit — it is worth making. If its profit were only ₹4, the reduced cost would be \(-1 < 0\) and the current plan would stay optimal.
Problem. Wyndor's allowable changes are: \(c_1\) up to \(+4.5\), \(c_2\) down to \(-3\). Suppose \(c_1\) rises by \(1.5\) and \(c_2\) falls by \(1.5\). Is the current solution still optimal?
Solution. Fractions: \(\dfrac{1.5}{4.5} = \dfrac13\) and \(\dfrac{1.5}{3} = \dfrac12\). Their sum is \(\dfrac13 + \dfrac12 = \dfrac56 \le 1\), so by the 100% rule the optimum \((2,6)\) remains optimal. Had the changes summed above \(100\%\) (e.g. \(+3\) and \(-2\), giving \(\tfrac23 + \tfrac23 > 1\)), the rule could not confirm it and a re-solve would be required.
Chapter Summary
Answer "what-if" questions about changing data straight from the final tableau — no re-solve.
How much a non-basic coefficient must improve before that variable enters the basis.
Interval of \(c_j\) keeping the same optimal solution (vertex).
Interval of \(b_i\) keeping the same basis; shadow price valid there.
\(\Delta z^\star = y_i \Delta b_i\) within the feasibility range; never apply a price outside it.
New variable via reduced cost; new constraint by feasibility test; 100% rule for simultaneous changes.
Problems
Use the given final tableau or shadow prices; state which range or rule you apply. Difficulty rises down the list.
- Explain in one sentence each the difference between "range of optimality" and "range of feasibility."
- A non-basic variable has reduced cost \(0\) at optimality. What does this signal about the solution?
- For Wyndor, find the range of optimality of \(c_2 = 5\) (use the \(x_2\)-row entries).
- For Wyndor, find the range of feasibility of \(b_3 = 18\) (use the \(s_3\) column).
- If Wyndor's \(b_3\) increases from \(18\) to \(20\) (within range), find the new \(z^\star\) given \(y_3 = 1\).
- A resource has shadow price \(0\). What does this imply about its usage at the optimum, and about buying more of it?
- A proposed product uses \((1, 0, 3)\) of the resources and earns ₹4. Using \(y = (0, \tfrac32, 1)\), decide whether to make it.
- A new constraint \(x_1 + x_2 \le 10\) is added; the current optimum is \((2,6)\). Is the optimum still valid? Why?
- Two objective coefficients change: one by \(40\%\) of its allowable range, another by \(50\%\). Can you conclude the solution stays optimal?
- Explain why applying a shadow price beyond its range of feasibility gives a wrong answer, using the piecewise-linear \(z^\star(b_i)\) picture.
- A manager wants to increase profit by expanding one resource. Given shadow prices \((0, 3, 5)\), which resource should be expanded first, and what is the value of the first extra unit?
- A factory's LP optimum uses machine-time fully (shadow price ₹4, valid for \(+30\) hours) and has spare labour (shadow price ₹0). Management can buy 20 extra machine-hours at ₹3 each or 40 extra labour-hours at ₹1 each. Advise which purchase to make, compute the net gain, and explain what the labour shadow price implies about that option.