Chapter 6.4, Problem 11P

Explanation of Solution

Objective function coefficients:

• Consider an LP that contains four decision variables $x_1,x_2,x_3,x_4$ and two constraints in which $x_1,x_2$ are basic variables in the optimal basis.
• The current basis is known to be optimal for $L_1\le c_1\le U_1$ and $L_2\le c_2\le U_2$
• Define,
  • $I_1=U_1-c_1$:
    • In here, maximum allowable increase is $c_1$ for which the current basis stays optimal.
  • $D_2=c_2-L_2$:
    • In here, maximum allowable decrease is $c_2$ for which current basis stays optimal.
  • $\Delta c_1$:
    • This stands for change in $c_1$
  • $\Delta c_2$:
    • This stands for change in $c_2$
• Thus,
  • $r_1=\frac{\Delta c_1}{U_1-c_1}$
  • $r_1=\frac{\Delta c_1}{I_1}$
• And
  • $r_2=\frac{\Delta c_2}{c_2-L_2}$
  • $r_2=\frac{\Delta c_2}{D_2}$
• Where,
  • $r_i$ measures the ratio of the actual change in $c_i$ to the maximum allowable change in $c_i$ that would keep the current basis optimal.
• Now, a variable $x_i$ will price out to $c_{BV}{B}^{-1}{a}_i-c_i$. It is given that $r_1+r_2\le 1$
• Hence, it is possible to write,
  • $r_1\left[U_1,c_2\right]+r_2\left[c_1,L_2\right]+\left(1-r_1-r_2\right)\left[c_1,c_2\right]$
  • $[r_1$