Sensitivity Range for a Right-Hand Side

The sensitivity range for the right-hand side $b_i$ of a constraint (also called the range of feasibility) is the interval of values $b_i$ can take such that the current optimal basis stays optimal. Within this range:

• the same set of constraints stays binding (and the same stays non-binding),
• the shadow price $y_i^*$ does not change,
• the optimal objective $z^*$ changes linearly with $b_i$.

We report the range as an allowable increase $\Delta^+$ and allowable decrease $\Delta^-$, so

$$b_i \in [\,b_i - \Delta^-,\; b_i + \Delta^+\,].$$

Non-binding constraint. Suppose constraint $i$ has the form $\sum_j a_{ij} x_j \le b_i$ and at the optimum $\sum_j a_{ij} x_j^* < b_i$. The slack is

$$s_i^* = b_i - \sum_j a_{ij} x_j^*.$$

Making $b_i$ larger only adds more slack — nothing in the optimum changes. Making $b_i$ smaller eats into the slack, and the basis stays optimal until the slack is fully consumed. Therefore

$$\Delta^+ = \infty, \qquad \Delta^- = s_i^*, \qquad y_i^* = 0.$$

For example, suppose a constraint reads $x_1 + 2x_2 \le 12$ and the optimum is $(x_1^*, x_2^*) = (4, 3).$ The slack is $s^* = 12 - (4 + 6) = 2,$ so $b$ can drop to $10$ or rise without bound. The sensitivity range is $[10, \infty).$