Chapter 6.4, Problem 10P

Explanation of Solution

Objective function coefficients:

• Case 1 result for the objective function coefficients state that “All variables whose objective function coefficients are changed have non-zero reduced costs in the optimal row 0”.
• Thus, it has two parts:
• Part 1: Maximization problem
  • Changing the objective function coefficient of a non-basic variable in maximization problem:
  • Suppose we change the objective function coefficient of a non-basic variable say x_i from c_i to $c_i+\Delta$ in a maximization problem, then $B^{-1}$ will be unchanged since the coefficients of basic variables remain the same and even $c_{BV}$ has not changed.
  • Now only variable whose row 0 coefficients will be changed by a change in c_i is x_i.
  • Therefore, BV will remain optimal if ${\overline{c}}_i\ge 0$ and BV will be suboptimal if ${\overline{c}}_i<0$ where, z can be improved by entering x_i into the basis.
  • The coefficient of the non-basic variable in row 0 of the optimal table is,
    • ${\overline{c}}_i=C_{BV}{B}^{-1}{a}_i-\left(c_i+\Delta \right)$
    • ${\overline{c}}_i=\left(C_{BV}{B}^{-1}{a}_i-c_i\right)-\Delta$
  • Thus, the current basis will remain optimal if $\left(C_{BV}{B}^{-1}{a}_i-c_i\right)\ge \Delta$ and suboptimal if $\left(C_{BV}{B}^{-1}{a}_i-c_i\right)<\Delta$.
  • As x_i is a non-basic variable, $\left(C_{BV}{B}^{-1}{a}_i-c_i\right)$ is a non-zero.
  • The reduced cost of a non-basic variable becomes the maximum amount by which the variables objective function coefficients are changed have strictly positive reduced costs in the optimal row 0