John will spend £5 of his Christmas money on plain and milk chocolates.

He can buy boxes at £2 each. These contain 25 plain and 25 milk chocolates.

He can buy single plain chocolates at 6p each and loose milk chocolates at 7p each.

John wants to have at least twice as many milk as plain chocolates.

John wishes to maximize the number of chocolates he can buy subject to the constraints.

From that problem, I decided on the three variables:

  • $x$ for the number of loose plain chocolates
  • $y$ for the number of loose milk chocolates
  • $z$ for the number of boxes

And the following constraints:

$$2z + 0.06x + 0.07y \le 5 $$

$$y \ge 2x + 25z $$

To maximize:

$$50z + x + y$$

The question asks for a graph to be drawn to show that if $z = 2$ there is no feasible solution to the problem.

Whilst being able to solve two-variable LPs, how would I go about solving this three-variable LP graphically?


You forgot the natural constraints $x\geq 0, y \geq 0, z \geq 0$ since supposedly you cannot sell them short.

You only have to solve it for $z=2$. Setting this, reduces LP to maximizing $x+y$ subject to $0.06x + 0.07y \leq 1$ (equivalently, $6x+7y \leq 100$ and $y \geq 2x+50$. There are in 2 variables, so can be drawn without a problem in the regular 2D graph.

EDIT To add intuition, with pure algebra, Note the constraints imply $$ 14x + 350 \leq 7y \leq 100 - 6x, $$ which of course implies $14x+350 \leq 100-6x$, so $20x \leq -250$ or $x \leq -12.5$, which cannot be since $x \geq 0$...


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.