100% Rule for Simultaneous Changes

The 100% Rule provides a sufficient condition for determining whether the current optimal solution (for objective coefficient changes) or current basis (for right-hand side changes) remains optimal when several parameters change simultaneously. For each changed parameter, the percent of its allowable change is computed; if the sum is at most 100%, the current solution or basis is guaranteed to remain optimal.

Step 1 of 157%

Tutorial

100% Rule for Objective Coefficients

From the sensitivity report of a linear program, each objective coefficient $c_j$ comes with an allowable increase $I_j$ and an allowable decrease $D_j$ . These tell us how much $c_j$ can change individually while the current optimal solution remains optimal.

When several objective coefficients change simultaneously, the individual ranges no longer apply directly. Instead, we use the 100% Rule.

For each coefficient that changes by $\Delta c_j$ , define its percent of allowable change:

r_j = \begin{cases} \dfrac{\Delta c_j}{I_j} \cdot 100\% & \text{if } \Delta c_j > 0, \\[6pt] \dfrac{|\Delta c_j|}{D_j} \cdot 100\% & \text{if } \Delta c_j < 0, \\[6pt] 0 & \text{if } \Delta c_j = 0. \end{cases}

The 100% Rule states:

\text{If } \sum_j r_j \;\le\; 100\%, \text{ then the current optimal solution remains optimal.}

For example, suppose $c_1$ has $I_1 = 5,\,D_1 = 2$ and $c_2$ has $I_2 = 2,\,D_2 = 4$ . If $c_1$ increases by $2$ and $c_2$ decreases by $1$ , then

r_1 = \dfrac{2}{5} \cdot 100\% = 40\%, \qquad r_2 = \dfrac{1}{4} \cdot 100\% = 25\%.

The sum is $65\% \le 100\%$ , so the current optimal solution remains optimal.