Chapter 6, Problem 22RP

Program Plan Intro

Optimal solution:

• Consider the linear programming problem given below:
• max z= $4x_1+x_2$
• Subject to constraints:
  • $3x_1+x_2\le 6$
  • $5x_1+3x_2\le 15$
  • $x_1,x_2\ge 0$
• The graph of the LP is given below:

Explanation of Solution

b.

• In order to find the range of values of $c_1$ for which the current basis remains optimal follow the steps stated below:
• Step 1:
  • Using the optimal table mentioned in the question, find the basic variables.
  • It is clear from the table that here $\left\{x_1,x_2\right\}$ are the basic variables.
• Step 2:
  • Find the matrix $B^{-1}$ from the optimal table.
  • These are the columns for the slack variables in the constraints of the optimal table. Thus,
  • $B^{-1}=\left[\begin{array}{cc}\frac{-1}{3}& \frac{2}{3}\\ \frac{2}{3}& \frac{-1}{3}\end{array}\right]$
• Step 3:
  • Compute $c_{BV}{B}^{-1}$, where $c_i$, the coefficients are in the objective function,
  • Thus $c_1=3+\Delta ;c_2=2$
  • $c_{BV}{B}^{-1}=\left[\begin{array}{cc}3+\Delta & 2\end{array}\right]\left[\begin{array}{cc}\frac{-1}{3}& \frac{2}{3}\\ \frac{2}{3}& \frac{-1}{3}\end{array}\right]$
  • $c_{BV}{B}^{-1}=\left[\begin{array}{cc}-\frac{\Delta }{3}+\frac{1}{3}& \frac{4}{3}+\frac{2\Delta }{3}\end{array}\right]$
• Step 4:
  • Now compute the new row 0 that corresponds to $c_1=3+\Delta$

Explanation of Solution

c.

• To find the range of values $c_2$ for which the current basis remains optimal follow the steps stated below:
• Step 1:
  • Using the optimal table given in the question, find the basic variables. It is clear from the table that here $\left\{x_1,x_2\right\}$ are the basic variables.
• Step 2:
  • Find the matrix $B^{-1}$ from the optimal table. It is simply the columns for the slack variables in the constraints of the optimal table. Thus,
  • $B^{-1}=\left[\begin{array}{cc}\frac{-1}{3}& \frac{2}{3}\\ \frac{2}{3}& \frac{-1}{3}\end{array}\right]$
• Step 3:
  • Compute $c_{BV}{B}^{-1}$ where, $c_i$ are the coefficients in the objective function, thus $c_1=3;c_2=2+\Delta$
  • $c_{BV}{B}^{-1}=\left[\begin{array}{cc}3& 2+\Delta \end{array}\right]\left[\begin{array}{cc}\frac{-1}{3}& \frac{2}{3}\\ \frac{2}{3}& \frac{-1}{3}\end{array}\right]$
  • $c_{BV}{B}^{-1}=\left[\begin{array}{cc}\frac{2\Delta }{3}+\frac{1}{3}& \frac{4}{3}-\frac{\Delta }{3}\end{array}\right]$
  • Step 4: Now compute the new row 0 corresponding to $c_2=2+\Delta$

Explanation of Solution

d.

• A change in the right hand side of a constraint will affect the right hand side of the constraints in the optimal table.
• As long as the right-hand side of each constraint in the optimal table remains non-negative, the current basis remains feasible and optimal.
• Hence, to find the range of $b_1$ for which the current basis remains optimal, first calculate the change in the right-hand side of the optimal table by computing $B^{-1}b$. Matrix $B^{-1}$ contains the columns for the slack variables in the constraints of optimal table.
  • $B^{-1}=\left[\begin{array}{cc}\frac{-1}{3}& \frac{2}{3}\\ \frac{2}{3}& \frac{-1}{3}\end{array}\right]$$b=\left[\begin{array}{c}40+\Delta \\ 50\end{array}\right]$
  • $B^{-1}b=\left[\begin{array}{cc}\frac{-1}{3}& \frac{2}{3}\\ \frac{2}{3}& \frac{-1}{3}\end{array}\right]$

Explanation of Solution

e.

• A change in the right-hand side of a constraint will affect the right-hand side of the constraints in the optimal table.
• And as long as the right-hand side of each constraint I the optimal table remains non-negative, the current basis remains feasible and optimal.
• Thus, to find the range of $b_2$ for which the current basis remains optimal, first calculate the change in the right-hand side of the optimal table by computing $B^{-1}b$. Matrix $B^{-1}$ contains the columns for the slack variables in the constraints of the optimal table.
  • $B^{-1}=\left[\begin{array}{cc}\frac{-1}{3}& \frac{2}{3}\\ \frac{2}{3}& \frac{-1}{3}\end{array}\right]$$b=\left[\begin{array}{c}40\\ 50+\Delta \end{array}\right]$
  • $B^{-1}b=\left[\begin{array}{cc}\frac{-1}{3}& \frac{2}{3}\\ \frac{2}{3}& \frac{-1}{3}\end{array}\right]$

Explanation of Solution

f.

• Assume that the labor 1 is willing  to work $40+\Delta$ hours then the LP’s optimal solution changes to $x_1=20-\frac{\Delta }{3}$ and $x_1=20-\frac{\Delta }{3}$, as calculated in part (d)

Explanation of Solution

g.

• If labor 2 is ready to work for 48 hours, this implies $\Delta =-2$. Using part (e), LP’s optimal solution can be calculated as follows:
• If $x_1=20+\frac{2\Delta }{3}$ and $x_2=10-\frac{\Delta }{3}$
• Put $\Delta =-2$
• $x_1=20+\frac{2\left(-2\right)}{3}$ and $x_2=10-\frac{\left(-2\right)}{3}$
• $x_1=$ $\frac{56}{3}$ and ${}_{}$

Explanation of Solution

h.

• Define $x_3$ to be the number of type 3 radio produced in a week. New linear program is
  • max z= $3x_1+2x_2+5x_3$
  • Subject to constraint
  • $x_1+2x_2+2x_3\le 40$
  • $2x_1+x_2+2x_3\le 50$
  • $x_1,x_2,x_3\ge 0$
• In order to determine whether a new activity causes the current basis to be optimal or not, price out the new activity. That is calculate ${\overline{c}}_j$ by applying the following formula,
• ${\overline{c}}_j=c_{BV}{B}^{-1}{a}_j-c_j$
• The new column is,
• The new column for $x_3$ is
• $a_3=\left[\begin{array}{c}2\\ 2\end{array}\right]$ $B^{-1}=\left[\begin{array}{cc}\frac{-1}{3}& \frac{2}{3}\\ \frac{2}{3}& \frac{-1}{3}\end{array}\right]$ $c_B$