Linear Programming - Maximization Question

I'm working on this problem right now:

You are a jeweler who sells necklaces and rings. Each necklace takes 4 ounces of gold and 2 diamonds to produce, each ring takes 1 ounce of gold and 3 diamonds to produce. You have 80 ounces of gold and 90 diamonds. You make a profit of 60 dollars per necklace you sell and 30 dollars per ring you sell, and want to figure out how many necklaces and rings to produce to maximize your profits.

Clearly this is a maximization problem, and this is how I formulated it.

Let $$n$$, $$r$$, $$g$$, and $$d$$ represent units of necklaces, rings, gold, and diamonds, respectively.

Then, $$n = 4g + 2d$$, and $$r = g + 3d$$.

Our profit can be defined by $$p = 60n + 30r$$.

Our constraints are $$g \le 80$$, and $$d \le 90$$.

I tried to approach solving this by substituting $$n$$ and $$r$$ for their production functions in the profit function. But, on second thought, I'm not sure if plugging them in maintains an equivalent profit function, because the gold/diamond amounts are tied together for each necklace/ring made.

So, I'm not sure if $$p = 60n + 30r$$ and $$p = 60(4g + 2d) + 30(g + 3d)$$ are equivalent statements.

Am I approaching this problem correctly? If not, how should I think about the problem? Thank you.

• One of your constraints is $4n+r \leq 80$. The others are... – Fabio Somenzi Oct 19 '18 at 20:10

$$d = 3r + 2n \le 90\\ g = 1r + 4n \le 80$$

$$P = 30r + 60 n$$

This then gives 3 allocations that maximize the use of resources.

All rings, All necklaces, and whatever combination is the solution to.

$$3r + 2n = 90\\ 1r + 4n = 80$$

one of the 3 will be most profitable.

• How did you derive the constraints? I thought it was simply $g \le 80$, since we can't have more than 80 oz. of gold, but I guess I was thinking about it the wrong way. – LeetCoder Oct 19 '18 at 20:28
• Each ring uses 3 diamonds, each necklace uses 2. The first inequality shows how you are using your diamonds, the second, how you use your gold. – Doug M Oct 19 '18 at 22:05

Your statements $$n=4g+2d$$ and $$r=g+3d$$ look wrong

If $$g$$ is the amount of gold used then $$g=4n+r$$; similarly if $$d$$ shows the diamonds used then $$d=2n+3r$$ and solving these for $$n$$ and $$r$$ would give $$n=\dfrac{3g-d}{10}$$ and $$r=\dfrac{2d-g}{5}$$

so you would have $$p=60n+30r=60\dfrac{3g-d}{10}+30\dfrac{2d-g}{5} = 12g +6d$$

This approach suggests that if you simply required $$g \le 80$$ and $$d \le 90$$ then this might suggest the maximum possible $$p$$ would be $$12 \times 80+6 \times 90 = 1500$$ and this would require you to make $$n=\dfrac{3\times 80-90}{10}=15$$ necklaces and $$r=\dfrac{2\times 90-80}{5}=10$$ rings

That turns out correct for these particular numbers, but ignores some other constraints which should also be considered, since all the values must be non-negative and some of them have to be integers; for example, if you started with $$g\le 80$$ and $$d \le 10$$ or with $$g\le 81$$ and $$d \le 93$$ it would give wrong answers

In fact you are trying to maximise $$p=60n+30r$$ subject to:

• $$n \ge 0$$ and $$r\ge 0$$, and presumably integers
• $$g=4n+r$$ and $$d=2n+3r$$
• $$0 \le g \le 80$$ and $$0 \le d \le 90$$ and $$d$$ presumably an integer