Chapter 6, Problem 29RP

Program Plan Intro

Optimal solution:

• Consider the linear programming problem given below:
• max z= $13x_1+16x_2+16x_3+14x_4+39x_5$
• Subject to constraints:
  • $11x_1+53x_2+5x_3+5x_4+29x_5\le 40$
  • $3x_1+6x_2+5x_3+x_4+34x_5\le 20$
  • $x_1,x_2,x_3,x_4,x_5\le 1$
  • $x_1,x_2,x_3,x_4,x_5\ge 0$
• Here,
• $x_i$= Fraction of investment I purchased by star oil.
• The Lindo output of the LP is given in the following figure:
• LP optimum found at step 5
• Objective function value: 57.44902.

Variable	Value	Reduced Cost
$x_1$	1.000000	0.000000
$x_2$	0.200860	0.000000
$x_3$	1.000000	0.000000
$x_4$	1.000000	0.000000
$x_5$	0.288084	0.000000

Row	Slack or Surplus	Dual prices
1	0.000000	0.190418
2	0.000000	0.984644
3	0.000000	7.951474
4	0.799140	0.000000
5	0.000000	10.124693
6	0.000000	12.063268
7	0.711916	0.000000

• Number of iterations: 5
• Ranges in which the basis is unchanged:

Obj coefficient ranges
Variable	Current coefficient	Allowable increase	Allowable Decrease
$x_1$	13.000000	Infinity	7.951474
$x_2$	16.000000	45.104527	9.117647
$x_3$	16.000000	Infinity	10.124693
$x_4$	14.000000	Infinity	12.063268
$x_5$	39.000000	51.666668	30.245285

Right-hand side ranges
Row	Current RHS	Allowable increase	Allowable Decrease
1	40.000000	38.264706	9.617647
2	20.000000	11.275863	8.849056
3	1.000000	1.139373	1.000000
4	1.000000	Infinity	0.799140
5	1.000000	1.995745	1.000000
6	1.000000	2.319149	1.000000
7	1.000000	Infinity	0.711916

Explanation of Solution

b.

• If NPV from investment 1 changes to $5 from $13 then the objective function coefficient of $x_1$ changes.
• As it can be seen from the Lindo output, the Obj coefficient ranges block determines

Explanation of Solution

c.

• Since both the objective function coefficients have a reduced cost of zero, hence 100% rule can be applied.
• A 25% decrease in the NPV from investment 2 implies
  • $\begin{array}{l}\Delta b_1=10\\ I_1=38.26\end{array}$
  • $\Delta c_2=4$
• Allowable decrease corresponding to $c_2=16$, as it can be observed from the Lindo output is $D_2=7.95$
• Now applying the formula,
  • $r_j=\frac{-\Delta c_j}{D_j}$
  • Here,
  • $r_2=\frac{4}{7.95}$
  • $r_2=0.50$
• In the same way, a 25% decrease in the NPV from investment 4 implies
  • $\Delta c_4=14\left(0.25\right)$
  • $\Delta c_4=-3$

Explanation of Solution

d.

• Since both the constraints are the binding constraints, hence 100% rule can be applied.
• Since the amount available to invest in the time 0 is increased from $40 million to $50 million,
  • $D_2=8.85$
  • $\Delta b_1=10$
• Allowable increase corresponding to $b_1=40$, as can be seen from the Lindo output is,
  • $I_1=38.26$
• Now applying the formula
  • $r_2=0.56$
  • Here,
  • $r_1=\frac{10}{38.26}$
  • $r_1=0.26$
• Similarly, since the amount available to invest in time 1 is decreased from $20 million to $15 million,
  • $\Delta b_1=15-20$
  • $\Delta b_1=-5$
• Allowable decrease corresponding to $b_2=20$, as can be seen from the Lindo output is $D_2=8$

Explanation of Solution

e.

• Define RM2 to be the pounds of raw material 2 purchased annually. The initial table is now changed by the introduction of the RM2 column. New linear program is,
  • max z=$13x_1+16x_2+16x_3+14x_4+39x_5$
• Subject to constraints:
  • $11x_1+53x_2+5x_3+5x_4+29x_5\le 40$
  • $3x_1+6x_2+5x_3+x_4+34x_5\le 20$
  • $x_1,x_2,x_3,x_4,x_5\le 1$
  • $x_1,x_2,x_3,x_4,x_5\ge 0$
• 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 formula given below:
• ${\overline{c}}_j=c_{BV}{B}^{-1}{a}_j-c_j$
• The new column for the investment 6 is
• $a_6=\left[\begin{array}{c}\begin{array}{c}5\\ 10\end{array}\\ 0\\ 0\\ \begin{array}{c}0\\ 0\\ 0\end{array}\end{array}\right]$ and $c_{BV}{B}^{-1}=[\begin{array}{c}\begin{array}{c}\begin{array}{c}0\end{array}\end{array}\end{array}$