Maximum of linear combination

Question

I have an range like this: $$x + 2y \leq 40$$ $$4x + 3y \leq 120$$ $$x \geq 0, y \geq 0 $$ I made an plot using wolfram alpha. Now I have a linear combination $$4x+5y$$ and I want to find the maximum of this linear combination, but with restriction to the range which I described. But I want to do this using geometric interpretation. How can I do that?

Answer 1

This falls in the domain of Linear Programming which essentially deals with optimizing linear functions subject to linear constraints. In your case, the restrictions you wrote are linear equations and the objective function is also.

Since you wanted a geometric interpretation, here you go:

The first thing you need to know is that for Linear Programs, the optimum solution always lies at one of the vertices (or end points if you will) of the restriction set. So, if we plot the equations you describe as restrictions, we get something called the feasible region. In our case, it looks like this:

---

Now, you want to maximize the function $4x+5y$ over this feasible region. So, now, you can compute the value of $4x+5y$ at each vertex point and the one with the highest value wins. Turns out, this point is the point $(24,8)$ giving us an optimal value of $136$.

One way to interpret this process of optimization is the following: Imagine that you have a stick. Place the stick at the origin such that it aligns with the equation of the line $4x+5y=0$. Now, move the stick in a way that at least some part of the stick stays in the feasible region, your objective value is increasing and you don't change its angle. At one point, (assuming the polygon is bounded), the stick will exit the region. The point at which it exits the region is our optimum point.

Here is a picture of what's happening:

---

I used MATLAB to generate the plots. If you'd like to know how I generated it, I have uploaded it here.

Answer 2

Let the maximum be $M$. Then we have $4x + 5y = M$. In other words, $y = -\frac{4}{5}x + \frac{M}{5}$. Thus, we want to find the line $l$ with slope $\frac{-4}{5}$ with the largest y-intercept such that there exists a point in $l$ that intersects with the range.

(The actual values in the plot are wrong, not sure why)

Note that in the inequality, the slopes of the lines are $-\frac{1}{2}$ and $-\frac{4}{3}$, respectively. Note that $- \frac{4}{5}$ is between those two, so from the diagram we have good reason to believe that the maximal line $l$ will be the one which intersects at the point that the "slope" of the inequality graph changes.

We can calculate that by finding the intersections of the range inequalities as if they were equations. This yields $(24, 8)$ as the point of intersection.

Thus, the maximum is achieved at $(4)(24) + (5)(8) = 136$