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 max x 1 , x 2 P 1 ( x 1 ) + P 2 ( x 2 ) s . t . W 1 ( x 1 ) + W 2 ( x 2 ) ≤ W 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 P 1 ( x 1 ∗ ) W 1 ( x 1 ∗ ) = 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?

Question

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                              max                                    x              1                        ,                          x              2                                                                     P          1                (                  x          1                )        +                  P          2                (                  x          2                )                            s        .        t        .                                                         W          1                (                  x          1                )        +                  W          2                (                  x          2                )        ≤        W            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                    P        1            (              x        1        ∗            )                      W        1            (              x        1        ∗            )        =                    P        2            (              x        2        ∗            )                      W        2            (              x        2        ∗            )      Note that ratio is essentially &quot;Profit Per unit weight of an item&quot;. 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?

Cecelia Mullins · Accepted Answer

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.

Jordon Haley · Accepted Answer

In general, it is not true in the form that you have written it. But let&#039;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    )  −  λ  (      W    1    (      x    1    )  +      W    2    (      x    2    )  −  W  ), where   λ is the non-negative Lagrange multiplier. So at the optimality, we have:                                          d                          P              1                        (                          x              1              ∗                        )                                d            x                          −        λ                              d                          W              1                        (                          x              1              ∗                        )                                d            x                          =        0                                                  d                          P              2                        (                          x              2              ∗                        )                                d            x                          −        λ                              d                          W              2                        (                          x              2              ∗                        )                                d            x                          =        0            Now under &quot;mild&quot; conditions that at optimality the gradients of       W    1   and       W    2   do not vanish, you can see that                                                        P              1              ′                        (                          x              1              ∗                        )                                              W              1              ′                        (                          x              1              ∗                        )                          =                                            P              2              ′                        (                          x              2              ∗                        )                                              W              2              ′                        (                          x              2              ∗                        )                          =        λ        .            Note that in the linear case where all the functions are just linear, i.e.   f  (  x  )  =  c  x, this relationship would imply what you have written.

Consider that I have two items. Let P i </msub> ( x i </msub>

Answered question

Answer & Explanation

New Questions in High school geometry