Optimize a linear objective over a feasible region

These questions have two kinds of pieces, and it helps to name them.

A constraint is a limit on which pairs $(x,y)$ are allowed. The feasible region is where all the constraints overlap.

The objective is the expression you're trying to make as large or as small as possible. In a story, it's usually profit, points, area, cost or total output.

For example, the constraints might be two resource limits:

and the objective might be the profit

The objective doesn't limit anything. It gives every point in the region a score. Here's the picture to keep: the constraints draw the region, and the objective scores the points.

You'll know you need this method when a question asks for the greatest or least value of an expression like $5x+7y$. If it asks only for the greatest possible $x$-coordinate or $y$-coordinate, you want the feasible-edge method from Graph and model two-variable inequalities instead.

A corner point, also called a vertex, is a spot where the edge of the region turns. Corners usually come from one of these:

• two boundary lines crossing each other;
• a boundary line meeting the $x$-axis;
• a boundary line meeting the $y$-axis; or
• an endpoint the question gives you directly.

Here's how to collect them:

1. Turn every limit in the question into an inequality, and graph them all.
2. Trace around the outside edge of the overlap, so you don't skip a corner.
3. Let Desmos show you where boundary lines cross, and click those points when that saves you graphing work.
4. Find each corner exactly by solving its two boundary equations together, or use that algebra to confirm what Desmos shows.
5. Throw out a crossing point that breaks any of the original inequalities.
6. Write each feasible corner down once, and only then start plugging into the objective.

Let's run this on the opening example. The slanted boundaries cross where

Subtract the first equation from the second and you get $x-y=0$, so $y=x$. Put that back into $x+2y=12$ to get $3x=12$, so the crossing is exactly $(4,4)$.

The axis corners need one more check. The line $x+2y=12$ hits the $x$-axis at $(12,0)$, but $2(12)+0=24$ breaks $2x+y\le12$. So $(12,0)$ isn't a corner. On the $x$-axis, the tighter limit is $2x+y=12$, which stops at $(6,0)$. The same thing happens on the $y$-axis, where $x+2y=12$ stops you at $(0,6)$.

Use the graph to find corners, not to prove them. A decimal on the screen can hide an exact fraction, and two boundary lines can cross at a point that breaks a third constraint.

You might wonder why the corners are enough. The region has infinitely many points inside it.

Start at any point inside the region. A linear objective goes up steadily in one direction, so you can keep moving that way and the value keeps growing until you reach the edge. Now look along that edge. On a straight edge, the objective changes at a steady rate from one end to the other.

That leaves two possibilities:

• one end of the edge scores better, and that end is a corner; or
• the objective has the same value all along the edge, so the two corners at its ends share that value.

So on a bounded region like the ones here, closed in on all sides with straight edges, the maximum and the minimum each show up at a corner. Check the corners, not the inside.

The corner rule works on the full region, fractions and all. When $x$ and $y$ count things, like kits or people, the best corner might not be a real option. This is the trickiest part of these questions, so let's go slowly.

Say $x$ and $y$ must be whole numbers, and

with the objective

The two slanted boundaries cross at

where

That's the best value anywhere in the region, but you can't make $4.1$ of something. It still tells you a lot. With whole-number $x$ and $y$, $P=3x+4y$ is always a whole number too, and it can't beat $30.7$. So no allowed point can score more than $30$.

Now look for a whole-number point that actually hits $30$. Try $(2,6)$:

and

It fits both limits and reaches the ceiling, so the greatest value is exactly $\boxed{30}$.

What about just rounding the corner? $\left(\frac{41}{10},\frac{23}{5}\right)$ rounds to $(4,5)$, and

so $(4,5)$ is outside the region. Rounding each coordinate on its own can push you over a limit. Use the fractional best value as a ceiling instead. Then search the whole-number points nearby and along the edges next to that corner, and plug your final point into every original constraint.