Exercise 3.21

(a) We start with the linear programming formulation from Exercise 1.16, convert it to standard form by introducing slack variables $x_4,x_5$, and switch to minimization by negating the objective function.

The initial basic feasible solution is $x=(0,0,0,8,5)$, with basis variables $x_4,x_5$. We apply the simplex method.

All reduced costs are non-negative, so the algorithm terminates. The optimal solution is $x_1=0$, $x_2=1∕2$, $x_3=3∕2$. The optimal profit is $339 million.

(b) Let the selling price of gasoline be $P_g=38+\mathrm{\Delta }$. The original profit coefficients change as follows:

The current basis $B=\{3,2\}$ remains optimal as long as the reduced costs of all nonbasic variables remain non-positive (for the maximization problem). Let $p^{\prime }=c_B^{\prime }{B}^{-1}$ be the vector of shadow prices. From the final tableau, the columns corresponding to the initial slack variables give us $B^{-1}$:

The new basic cost vector is $c_B{(\mathrm{\Delta })}^{\prime }=[c_3(\mathrm{\Delta }),c_2(\mathrm{\Delta })]=[206+3\mathrm{\Delta },60+\mathrm{\Delta }]$. The new shadow prices are:

We check the reduced costs ${\bar{c}}_j(\mathrm{\Delta })=c_j(\mathrm{\Delta })-p{(\mathrm{\Delta })}^{\prime }{A}_j$ for nonbasic variables $j=1,4,5$:

• ${\bar{c}}_1(\mathrm{\Delta })=(200+4\mathrm{\Delta })-[13,47+\mathrm{\Delta }]\left[\begin{array}{c}\hfill 3\hfill \\ \hfill 5\hfill \end{array}\right]=(200+4\mathrm{\Delta })-(39+235+5\mathrm{\Delta })=-74-\mathrm{\Delta }$. We need $-74-\mathrm{\Delta }\le 0⟹\mathrm{\Delta }\ge -74$.
• ${\bar{c}}_4(\mathrm{\Delta })=0-[13,47+\mathrm{\Delta }]\left[\begin{array}{c}\hfill 1\hfill \\ \hfill 0\hfill \end{array}\right]=-13$. This is always $\le 0$.
• ${\bar{c}}_5(\mathrm{\Delta })=0-[13,47+\mathrm{\Delta }]\left[\begin{array}{c}\hfill 0\hfill \\ \hfill 1\hfill \end{array}\right]=-47-\mathrm{\Delta }$. We need $-47-\mathrm{\Delta }\le 0⟹\mathrm{\Delta }\ge -47$.

Both conditions must hold, so we require $\mathrm{\Delta }\ge -47$. This means the price can drop by up to $47, but since the question asks how high it can go, there is no upper bound. The price of gasoline can rise indefinitely without changing the optimal basis.

(c) The shadow price corresponding to the crude oil B constraint (the second constraint) is $p_2=47$. This means that for each additional barrel of crude B, the profit increases by $47. The spot market price is $40/barrel. Since the marginal value ($47) is greater than the cost ($40), it is profitable to buy more crude B. The net gain is $7 per barrel.

We can continue buying crude B as long as the current basis remains feasible. Let $\delta$ be the millions of barrels of crude B purchased. The new RHS vector is $b^{\prime }={[8,5+\delta ]}^{\prime }$. The new basic feasible solution is:

For this solution to remain feasible, both components must be non-negative:

• $x_3(\delta )=3∕2-\delta ∕2\ge 0⟹3\ge \delta$.
• $x_2(\delta )=1∕2+5\delta ∕2\ge 0$, which is true for all $\delta \ge 0$.

The basis remains optimal for $0\le \delta \le 3$. Since the purchase is profitable throughout this range, the manager should buy the maximum possible amount. Therefore, the manager should buy 3 million barrels of crude oil B.