Chapter 6, Problem 33RP

Explanation of Solution

Optimal solution:

• Consider the linear programming problem given below:
• max z= $c_1{x}_1+c_2{x}_2$
• Subject to constraints:
  • $3x_1+4x_2\le 6$
  • $2x_1+3x_2\le 6$
  • $x_1,x_2\ge 0$
• The optimal table for this LP is,
  • $z+s_1+2s_2=14$
  • $x_1+3s_1-4s_2=2$
  • $x_2-2s_1+3s_2=2$
• ${\overline{c}}_j$ is the coefficient of $x_j$ in the optimal table’s row 0. Hence, ${\overline{c}}_j$ can be calculated by using the following formula:
  • ${\overline{c}}_j=c_{BV}{B}^{-1}{a}_j-c_j$
• In this case, the matrix $B^{-1}$ is derived from optimal table. It contains the columns of the slack variables in the constraints of the optimal table. Thus,
• $B^{-1}=\left[\begin{array}{cc}3& -4\\ -2& 3\end{array}\right]$
• Compute $c_{BV}{B}^{-1}$, where $c_i$ the coefficient is in the objective function,
  • $c_{BV}{B}^{-1}=\left[\begin{array}{cc}{c}_1& c_2\end{array}\right]\left[\begin{array}{cc}3& -4\\ -2& 3\end{array}\right]$
  • $c_{BV}{B}^{-1}=\left[\begin{array}{cc}3c_1-2c_2& -4c_1+3c_2\end{array}\right]$
• The coefficient of $s_1$ and $s_2$ is known in the objective function as well as in the optimal table. Using this fact, compute the values of $x_1$ and $x_2$