Constrained Optimisation Major Problem

Question

Maximize: $$f(x,y,z)=600x+480y+440z,$$ subject to these four constraints: $$x+0.75y+z\leqslant 120$$ $$x\leqslant 50$$ $$y\leqslant 40$$ $$z\leqslant 60$$ Any help or hints on how to solve this would be greatly appreciated! Thank you very much! ☆

Answer 1

Hint: Observe that the curve is increasing in all directions, so you want a value on the line $x+0.75y+z = 120$. That means that the solution is a vector $(x,y,z)$ such that $z = 120 - x - 0.75y$, so you want to maximize $f(x,y) = 600x + 480y +440(120 - x - 0.75y) = 160x + 150y + 440*120$, then you have a simpler optimization problem which is easy to solve.

Answer 2

Used the simplex algorithm to solve it. $$x=50$$ $$y=40$$ $$z=40$$

Thanks for everyone's help and input!

Answer 3

You can solve these problems with the simplex algorithm. Here, the problem has a specific structure that you can exploit to not use the simplex.

You can start by analyzing the ratios between the coefficients in the objective function and the first constraint, for each variable. Sorting these ratios by decreasing order gives you the order in which you have to process the variables to maximize the profit. In this case it is $y$ (ratio $640$), then $x$ (ratio $600$), then $z$ (ratio $440$).

1. You can give $y$ its largest value possible : $40$. The constraint has a slack capacity $120-0.75\cdot 40 = 90$.
2. You can give $x$ its largest value possible : $50$. The constraint has a remaining slack capacity $90-50=40$.
3. You can assign $z$ value $40$, and the constraint becomes active.

Answer 4

First of all, $\nabla f \ne 0, \forall x,y,z$, so you know the function has no local minima or maxima. This means the maximum must lie somewhere on the boundary.

Let's look further. The 4 boundaries are all planes, which make up a quadrilateral. The maximum cannot lie on any of the faces. Why? If you plug in any one of the constraints, let's say the first one, into the function

$$ f(x,y,120-x-0.75y) = g(x,y) = 160x + 150y + 440\cdot 120 $$

you will notice that it also results in a function whose gradient, $\nabla g \ne 0$ anywhere.

The same argument applies with the edges, which will occur when you plug in two of the constraints into the function.

This leaves the 4 vertices, so one of which must be the maximum. They are: $(50,40,60)$, $(50,40,40)$, $(50,\frac{40}{3},60)$, $(30,40,60)$

Plug in all of these points and see which one gives the highest value of $f(x,y,z)$.