George Weasley, the owner of Weasleys' Wizard Wheezes, recently found that his Skiving Snackboxes have become extremely popular amongst the students at Hogwarts School of Witchcraft and Wizardry, and he wants your help to work out how many of each type he should stock in order to maximize his prot. There are three types of Skiving Snackboxes: Fainting Fancies, Nosebleed Nougats and Puking Pastilles. Fainting Fancies and Puking Pastilles both cost 5 dollars to produce, and Nosebleed Nougats cost 7 dollars to produce. He sells Fainting Fancies to the students for 15 dollars each, Nosebleed Nougats for 23 dollars each, and Puking Pastilles for 7 dollars each. (We are working in dollars to make the mathematics easier.) George knows that he can only order up to 200 Skiving Snackboxes in total, and he must order at least 14 of each type. He also knows that Puking Pastilles has unpleasant side-effects which means it is not as popular amongst the students, so the number of Puking Pastilles ordered must be less than or equal to half the number of Fainting Fancies and Nosebleed Nougats combined. You may assume that all products are sold.

(a) Identify the decision variables for this problem and their units.

(b) Formulate the problem of maximizing the store's prot as a linear program.


Well, obviously, the point is to decide how many of which type of product he has to order. There are three types of products, so our variables will be also three, each denoting the ordered amount of the corresponding product: let us denote these variables by $x_1,x_2,x_3$ (corresponding to the types in the order you have listed them).

Now, we have to formulate the LP problem. We want to maximize the store's profit. Since we assume that all products are sold, the numbers of products of each type sold are clearly $x_1,x_2,x_3$ as well. The profit from the first type is then $(15-5)x_1 = 10 x_1$, since he produces them for 5 and sells them for 15. The profit from the second type is $(23-7)x_2 = 16x_2$ and from the third type $(7-5)x_3 = 2x_3$ (by the same logic). Thus, our objective function clearly is $$10 x_1 + 16x_2 + 2x_3.$$ Now, let us examine the restrictions imposed. First, he can order at most 200 items in total, thus $$x_1 + x_2 + x_3 \leq 200.$$ Second, he must order at least 14 of each type, thus $x_1 \geq 14$, $x_2 \geq 14$ and $x_3 \geq 14$. The last restriction says $x_3 \leq \frac{1}{2}(x_1 + x_2)$. Finally, the numbers of ordered products must clearly be integer, so this is going to be an ILP.

Our resulting integer linear program is thus as follows:

Maximize $$10 x_1 + 16x_2 + 2x_3$$ subject to $$x_1 + x_2 + x_3 \leq 200$$ $$x_1 \geq 14$$ $$x_2 \geq 14$$ $$x_3 \geq 14$$ $$x_3 \leq \frac{1}{2}(x_1 + x_2)$$ $$x_1,x_2,x_3 \in \mathbb{Z}$$

I might have made a mistake somewhere, but the main principle should be clear.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.