Chapter 6.4, Problem 13P

Explanation of Solution

100% Rule for right-hand sides:

• Consider an LP that contains two constraints and right –hand sides $b_1,b_2$.
• The current basis is known to be optimal for $L_1\le b_1\le U_1$ and $L_2\le b_2\le U_2$
• Define,
  • $I_1=U_1-b_1$:
    • In here, maximum allowable increase is $b_1$ for which the current basis stays optimal.
  • $D_2=b_2-L_2$:
    • In here, maximum allowable decrease is $c_2$ for which current basis stays optimal.
  • $\Delta b_1$:
    • This stands for change in $b_1$
  • $\Delta b_2$:
    • This stands for change in $b_2$
• Thus,
  • $r_1=\frac{\Delta b_1}{U_1-b_1}$
  • $r_1=\frac{\Delta b_1}{I_1}$
• And
  • $r_2=\frac{\Delta b_2}{b_2-L_2}$
  • $r_2=\frac{\Delta b_2}{D_2}$
• Where,
  • $r_i$ measures the ratio of the actual change in $b_i$ to the maximum allowable change in $b_i$ that would keep the current basis optimal.
• As the original LP has attained the optimal basis, the current basis remains optimal as long as the right-hand side of each constraint in the optimal table is non-negative.
• It is given that $r_1+r_2\le 1$
• Hence, it is possible to write,
  • $r_1\left[U_1,b_2\right]+r_2\left[b_1,L_2\right]+\left(1-r_1-r_2\right)\left[b_1,b_2\right]$
  • $[{}_{}$