0
$\begingroup$

Consider that I have two items. Let $P_i(x_i)$ denote the profit I get from item $i$ by taking $x_i$ units of it (assume that $x_i$ can be a real number). Let $W_i(x_i)$ denote the weight consumed by item $i$ when I take $x_i$ units of this. Assume that both profit and weight functions are monotonically increasing in the quantity of items picked. The problem I am interested in is \begin{align}\max_{x_1,x_2}&~P_1(x_1)+P_2(x_2) \\ s.t.&~~~W_1(x_1)+W_2(x_2)\leq W\end{align} where $W$ is total weight allowed. Thus I need to find $x_i$ (quantity of item $i$) such that the total profit is maximized while keeping the total weight under a given quantity. Let $x_1^*$ and $x_2^*$ be the solution to this problem. Is it true that $$\frac{P_1(x_1^*)}{W_1(x_1^*)}=\frac{P_2(x_2^*)}{W_2(x_2^*)}$$Note that ratio is essentially "Profit Per unit weight of an item". Assume that this were different at the optimum and the first item had the larger ratio. Thus I can get more profit per unit weight out of the first item. Then increasing quantity of that should increase profit. In order to balance the weights, I decrease the second items quantity decreasing its profit as well. But since the increase in profits from item $1$ is higher, this should compensate for loss from item $2$ and make the profits even more higher. What is flawed with this logic?

$\endgroup$

2 Answers 2

0
$\begingroup$

No, not true. Simply take the linear case and draw the geometry of the feasible set. The optimal solution will generically have $x_1 = 0$ or $x_2 = 0$.

Well, technically true if you rearrange it as $P_1(x_1^*)W_2(x_2^*)=P_2(x_2^*)W_1(x_1^*)$ since it then evaluates to $0=0$ as $x_1^*$ or $x_2^*$ is $0$.

$\endgroup$
0
$\begingroup$

In general, it is not true in the form that you have written it. But let's introduce a Lagrange multiplier for the constraint and see how it plays out. Assuming there are no other constraints for $x_1$ and $x_2$, then the LAgrangian function for the problem is: $\max_{x_1,x_2}~P_1(x_1) + P_2(x_2) - \lambda (W_1(x_1) + W_2(x_2)-W)$, where $\lambda$ is the non-negative Lagrange multiplier. So at the optimality, we have: \begin{align} \frac{dP_1(x^*_1)}{dx}-\lambda \frac{dW_1(x^*_1)}{dx} = 0\nonumber\\ \frac{dP_2(x^*_2)}{dx}-\lambda \frac{dW_2(x^*_2)}{dx}= 0\nonumber \end{align} Now under "mild" conditions that at optimality the gradients of $W_1$ and $W_2$ do not vanish, you can see that \begin{align} \frac{P_1'(x^*_1)}{W'_1(x^*_1)} = \frac{P_2'(x^*_2)}{W'_2(x^*_2)} = \lambda. \end{align} Note that in the linear case where all the functions are just linear, i.e. $f(x) = cx$, this relationship would imply what you have written.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .