Local vs. Global Sensitivity in LP

How shadow prices give a local rate of change of the optimal LP objective with respect to a right-hand side, why this rate is only valid within an allowable range, and how to compute the optimal value globally using the piecewise linear value function that emerges across basis changes.

Step 1 of 157%

Tutorial

Local Sensitivity and the Allowable Range

After solving an LP, every constraint has a shadow price $y_i$ that measures the marginal change in the optimal objective per unit change in the right-hand side $b_i{:}$

y_i \;=\; \dfrac{\partial z^*}{\partial b_i}.

This rate is local. It applies only as long as the current optimal basis remains optimal. The set of values $b_i+\Delta$ for which this happens is called the allowable range (or range of feasibility) for $b_i,$ written

b_i^{\text{lo}} \;\le\; b_i + \Delta \;\le\; b_i^{\text{up}}.

For any $\Delta$ inside this range, the change in optimal value is exactly

\Delta z \;=\; y_i \cdot \Delta.

For example, suppose a current LP has optimal profit $z^* = \$ 1000, $shadow price$ y_1 = $5 $/unit on resource$ 1, $current RHS$ b_1 = 50, $and allowable range$ [30,,80]. $If$ b_1 $rises to$ 65, $then$ \Delta = 15 $lies inside$ [30,,80],$ so

z^*_{\text{new}} \;=\; 1000 + 5\cdot 15 \;=\; \$1075.

Sensitivity analysis carried out entirely inside the allowable range is called local sensitivity.