6.6 Practice Problems

Problem 6.6.1. In the running example, find the range of \(b_1\) by hand from \(B^{-1}\), and the optimal solution when \(b_1 = 30\).

Show solution

Solution. \(B^{-1}e_1 = (1, \frac 23, -\frac 13)\), so the conditions are \(3 + \delta \geq 0\), \(8 + \frac 23\delta \geq 0\), \(10 - \frac 13\delta \geq 0\): \(-3 \leq \delta \leq 30\), that is \(23 \leq b_1 \leq 56\). At \(b_1 = 30\), \(\delta = 4\): \(s_3 = 7\), \(x_1 = 8 + \frac 83 = \frac {32}3\), \(x_2 = 10 - \frac 43 = \frac {26}3\), and \(Z = 230 + 4 \cdot \frac 53 = 236.7\).

Problem 6.6.2. Derive the range \(7.5 \leq c_1 \leq 30\) from the reduced costs.

Show solution

Solution. With \(c_B = (0, c_1, 15)\) for \((s_3, x_1, x_2)\), the multipliers are \(y = c_B^{\mathsf T}B^{-1} = (\frac 23c_1 - 5, -\frac 16c_1 + 5, 0)\), and the reduced profits of \(s_1\) and \(s_2\) are \(-y_1\) and \(-y_2\). Optimality requires \(y_1 \geq 0\) and \(y_2 \geq 0\): \(c_1 \geq 7.5\) and \(c_1 \leq 30\). At \(c_1 = 10\) these give \(y = (\frac 53, \frac {10}3, 0)\).

Problem 6.6.3. A new product needs \(3\), \(1\) and \(0\) units of the three resources. What profit per unit must it earn to be worth making?

Show solution

Solution. It is worth making if its profit exceeds \(y^{\mathsf T}a = 3\cdot \frac 53 + 1\cdot \frac {10}3 + 0 = \frac {25}3 = 8.33\).

Problem 6.6.4. Using the 100% rule, decide whether the basis stays optimal if \(b_1\) rises by \(10\) and \(b_2\) falls by \(15\) at the same time.

Show solution

Solution. The allowed increase of \(b_1\) is \(30\) and the allowed decrease of \(b_2\) is \(30\). The fractions are \(\frac {10}{30} + \frac {15}{30} = \frac 56 \leq 1\), so the basis remains optimal. Check: \[ x_B = (3, 8, 10) + 10\bigl (1, \tfrac 23, -\tfrac 13\bigr ) - 15\bigl (-\tfrac 12, -\tfrac 16, \tfrac 13\bigr ) = (20.5, 17.17, 1.67) \geq 0 . \]

Problem 6.6.5. Explain why the optimal value is a convex function of the cost vector \(c\), for a fixed feasible region.

Show solution

Solution. For a bounded feasible region with vertices \(v^1, \ldots , v^K\), the optimal value of the maximisation is \(\max _kc^{\mathsf T}v^k\), a maximum of linear functions of \(c\), which is convex. Economically, if prices can vary, being able to re-optimise is worth more the more they vary.

Problem 6.6.6. In the running example the third resource has slack \(3\) and price \(0\). A consultant proposes buying \(10\) more units of it at Rs. 1 each. Should the firm accept?

Show solution

Solution. No. Its shadow price is \(0\) for all \(b_3 \geq 2\), so extra units add no profit: the firm would pay Rs. 10 for nothing. The third resource is not a bottleneck; the first two are, worth \(\frac 53\) and \(\frac {10}3\) per unit within their ranges.

Questions on this section

Stuck on something here? Ask below and it stays attached to this topic.