Maximise the value of two items with two inputs

Question

In our game, you can make items of two types — A and B. To make an A item, you have to spend 2x+y; to make a B item, you have to spend x+2y.

Each item can be sold for exactly z. How many z can you earn if you are given a x's and b y's?

This looks to me like some kind of maximisation of 2x+y and 2y+x but I just cannot see how.

Answer 1

The problem is $$ \max_{A,B}z(A+B) $$ such that $2Ax + xB \le a$ and $Ay + 2xB \le b$. Rewrite these constraints as $2A + B \le a/x$ and $ A+2B \le b/y$.

This is a linear programming problem. Since the output price is the same for both goods, you just want to make as much as possible in total.

Look at the two cost constraints and see if there's a simple solution. Whichever input you have relatively less of, that constraint that will definitely bind, because of the symmetry in $A$ and $B$. Suppose $a/x<b/y$: then you want to make as much $B$ as possible and no $A$, because $2>1$, so making $A$ is relatively more costly. If $b/y<a/x$, the answer reverses, so you want to make as much $A$ as possible and no $B$. If $a/x=b/y$, it doesn't matter, both constraints will bind at the optimum and you can select any $A$ and $B$ for which they both bind. This works whenever $a/x < b/y$ and $2 a/x < b/y$, or $b/y < a/x$ and $2 b/y < a/x$, but otherwise maxing out one constraint will make the other bind.

To get the solutions when both constraints might bind at the optimum, write out the Lagrangian $$ \mathcal{L} = z(A+B) - \mu_1 (2A+B-a/x) - \mu_2 (A+2b-b/y) + \mu_A A + \mu_B B $$ where $\mu_A$ is the constraint on $A \ge 0$. Collect terms $$ \mathcal{L} = A(z-2\mu_1 - \mu_2+\mu_A)+B(z-\mu_1-2\mu_2+\mu_B) + \mu_1 a/x +\mu_2 b/y. $$ You'll want to increase $A$ whenever $z-2\mu_1-\mu_2+\mu_A>0$, and similarly for $B$. The complementary slackness conditions are that $$ \mu_1 (2A+B-a/x+\mu_A) = 0, \quad \mu_2 (A+2B - b/y+\mu_B) = 0, \quad \mu_A A= 0, \quad \mu_b B = 0. $$ These characterizes the corners of the constraint set, and a solution necessarily satisfies them. Since the objective is linear and the constraint set is convex, they are also sufficient.

Answer 2

Here's a hint which should help.

This is the same thing as starting at $(a,b)$, and making as many "knight's moves" as possible, i.e. adding $(-1, -2)$ or $(-2,-1)$ as many times as we can.

Since the problem is clearly symmetric, assume that $a \geq b$ without loss of generality.

If $a \geq 2b-1$, then show that the optimal path involves only $(-2, -1)$ moves (this is not too hard). So we can easily calculate how many moves we can make in this case.

If $b \leq a < 2b-1$, show that any optimal path contains moves of both types. Once you've done this, note that since the order of the moves is unimportant, we can simply take one move of each type first, and reduce it to the $(a-3, b-3)$ case, and repeat the process until we reach a state $(x,y)$ where $x \geq 2y-1$, covered in the previous part.