1

Consider, $$\max 1.000.000x_1 + 2.500.000x_2 $$ \begin{align} s.t. x_1 + 2x_2 \le 7 \\ x_1 + 3x_2 \le 10 \\ -3x_1 + x_2 \le 0 \\ x_1, x_2 \ge 0\end{align}

which is an LP-problem on a company's wishes to maximise profit given certain constraints on the production of product 1 ($x_1$) and product 2 ($x_2$).

The company has 7 liters of oil, product 1 requires 1 liter per production, and product 2 requires 2. This is the first equation.

Now, here are the questions I have a problem with:

  1. Can the company increase its profits if more oil can be bought?. If yes, what should the price be for that to happen (i.e. increased profits)?
  2. Can the company increase its profits by selling oil? If yes, what should the selling price be for more profit?

I suspect by 'more profit', they are comparing to the current optimal solution, which I found to be $x_1 = 1, x_2 = 3$.

I haven't done an exercise like this before, (have only theoretical experience, so these types of exercises geared towards econ-students always cause me trouble) so would like some help. Any ideas?

Michael Grant
  • 19,450
Standard
  • 19
  • Have you learned about shadow prices yet? To answer these questions that's what you have to do compute. – Michael Grant Apr 10 '15 at 11:36
  • That's my main problem here. I know about dual variables, but I gather from reading online that they have a lot to do with 'shadow prices' and 'shadow costs'. I have zero intuition on that, as all my knowledge comes from a purely theoretical book with no 'real life examples' included. – Standard Apr 10 '15 at 11:44
  • The values of dual variables are precisely what the shadow prices are. Do you know (or can you find) the value of the dual variable associated with the constraint $x_1+2x_2\leq 7$? That will represent the value of increasing the right-hand side of that constraint. – Michael Grant Apr 10 '15 at 11:45
  • Yes, that should be straight forward (although it'll take some calculations and use of complementary slackness) ..... I drew the feasible set, and it seems INCREASING the amount of oil makes the first equation redundant.... does this not imply that more oil makes no difference at all, as it doesn't affect the feasible set? And when it comes to decreasing, then I'd take $y_1$ and multiply by $\Delta b_1$ (increase in oil), and get my increase in $\zeta$? But now my problem is, is the current basis still optimal when changing $b_1 to b + \Delta b_1$, because if not, surely $y_1$ is useless? – Standard Apr 10 '15 at 11:51
  • Yeah, it looks like increasing the oil quantity will not help, because production is constrained by the next two constraints. Reducing consumption will free up oil for sale, though. So the profit will be the price of oil minus the reduction in profit from production. The shadow price should give you the price of oil required to make this a positive number. – Michael Grant Apr 10 '15 at 12:26
  • You may not need to compute the dual variable to get this. You can probably intuit what it will be by determining how $x_1$ and $x_2$ will change if you reduce the oil quantity slightly. I am guessing $x_1$ must decrease alone but you should confirm this. – Michael Grant Apr 10 '15 at 12:28

1 Answers1

0

As we discussed in the comments this brings in the concept of the "shadow price" or the dual variable associated with the constraint $x_1+2x_2\leq 7$. But I think we can get the answers without appealing to the dual.

For each question we are asking what happens if we perturb the first constraint to $x_1+2x_2\leq 7+\epsilon$, where $\epsilon$ is small.

In the first case, $\epsilon>0$. The optimal solution satisfies $x_1+2x_2=7$, so initially we might think that a positive $\epsilon$ would relax this constraint and allow the objective to increase. But in fact, both the second and third inequalities are active as well, and there is no way to increase $x_1$ or $x_2$ without violating one or both of these constraints. Therefore, purchasing more oil will simply make the first inequality inactive: $x_1+2x_2<7+\epsilon$. It will not increase production, and so no price is worth paying.

In the second case, $\epsilon<0$. We must reduce $x_1$ and/or $x_2$ to compensate. Reducing either will make the second constraint inactive. But the third constraint will remain active, so the complete basis is given by the first and third constraints. This leads to $$\begin{aligned} x_1 + 2 x_2 &= 7+\epsilon \\ -3 x_1 + x_2 &= 0\end{aligned} \quad\Longrightarrow\quad \begin{bmatrix} x_1 \\ x_2 \end{bmatrix} = \begin{bmatrix} 1 \\ 3 \end{bmatrix} + \epsilon \begin{bmatrix} 1 & 2 \\ -3 & 1 \end{bmatrix}^{-1} \begin{bmatrix} 1 \\ 0 \end{bmatrix}.$$ The objective value will be (in millions) $$8.5 + \epsilon \begin{bmatrix} 1 & 2.5 \end{bmatrix} \begin{bmatrix} 1 & 2 \\ -3 & 1 \end{bmatrix}^{-1} \begin{bmatrix} 1 \\ 0 \end{bmatrix} = 8.5 + (17/14)\epsilon \approx 8.5 + 1.214\epsilon.$$ Therefore, the reduction in sales is approximately $\$1.214M$ per liter of oil. If you can sell oil for more than that amount, it is profitable to do so.

This is an interesting problem because it shows the potentially asymmetric nature of shadow prices. If you had computed the shadow price associated with $x_1+2x_2\leq 7$, you would have arrived at the $\$1.214M$ figure. However, because there were more than 2 active constraints at the optimal solution, this shadow price applied only to a decrease and not an increase.

Michael Grant
  • 19,450