Introduction to Optimization Advanced. This lesson goes beyond core Algebra I. You can skip it.

Intuition

Suppose a workshop builds chairs and tables. Each chair earns $30$ dollars in profit and each table $50$ dollars, but the shop has only $8$ hours of cutting time and $9$ hours of assembly time each day. Building only chairs is not obviously best, and neither is only tables, or some vague “mix of both.” Among all the daily plans the shop could choose, exactly one earns the most profit, and finding it precisely, not guessing, is what this lesson is for.

Every such problem pulls two things against each other: a quantity you want to push as high (or as low) as it will go, and a set of hard limits you are not allowed to break. That is an optimization problem. When the quantity and every limit are linear, the last lesson already handed you the picture you need, the feasible region. This lesson turns that picture into an answer.

Learning goals

Turn a word problem into an objective and linear constraints, with $x \ge 0$ , $y \ge 0$
Explain why a linear objective's best value sits at a vertex
Find every vertex, evaluate the objective there, and pick the extreme
Say why an unbounded region may have no maximum

Constraints, the objective, and the feasible region

An optimization problem in two variables has two parts. The first part is a list of constraints, the hard limits written as linear inequalities such as $x + y \le 4$ or $2x + y \ge 6$ . The list also carries the natural restrictions $x \ge 0$ and $y \ge 0$ whenever the variables measure amounts that cannot be negative. Those two inequalities only rule out negative values; if $x$ and $y$ must also be whole numbers, because they count separate items like chairs or trucks, that is a further restriction worth remembering, even though the examples in this lesson happen to work out whole anyway. Every constraint here is written with $\le$ or $\ge$ , never the strict $<$ or $>$ , so every boundary line belongs to the region it bounds; that inclusive boundary is what the corner-point method below relies on. You already know how to graph such a system: each inequality shades a half-plane. The points that satisfy all of the inequalities at once fill the overlap, the feasible region. Every point inside that region is an allowed choice, and there are usually infinitely many of them.

The second part is the objective function, the single linear quantity you are trying to make as large or as small as possible. Write it as

P = ax + by,

where $a$ and $b$ are fixed numbers set by the problem, such as $P = 3x + 2y$ . Maximizing profit, minimizing cost, and minimizing time are all of this form. The task is now exact: among the infinitely many points of the feasible region, find the one (or ones) where the objective $P$ is largest, for a maximum, or smallest, for a minimum. Testing points one at a time would never end, so you need a reason to look in just one place. That reason is the corner-point principle.

Why the best value sits at a corner

Fix an objective, say $P = 2x + 3y$ , over a feasible region. For any chosen number $c$ , the points where $P = c$ , that is where $2x + 3y = c$ , form a straight line called a level line of the objective. Every point on that line gives the objective the same value $c$ . Solving for $y$ gives $y = -\tfrac{2}{3}x + \tfrac{c}{3}$ , a line whose slope $-\tfrac{2}{3}$ does not depend on $c$ . So the level lines for different values of $c$ are all parallel. Changing $c$ slides the line across the plane without ever turning it. Sliding it one way makes $P$ larger, while sliding it the other way makes $P$ smaller.

Level lines of P = 2x + 3y over a feasible region with corners (0,0), (4,0), (3,1), and (0,2). The dashed lines P = 3, P = 6, P = 9 are parallel; sliding them in the direction of larger P, the last one to touch the region meets it only at the corner (3,1), so the maximum is P = 9 there.

The corners of this region are $(0, 0)$ , $(4, 0)$ , $(3, 1)$ , and $(0, 2)$ . As the three dashed level lines slide toward larger $P$ , the last one that still touches the region is $P = 9$ , and it grazes only the corner $(3, 1)$ . So the maximum of $P = 2x + 3y$ over this region is $9$ , at $(3, 1)$ .

That last grazing point is no accident, and the same picture works for any bounded region with an included boundary, built from $\le$ and $\ge$ constraints, and any linear objective. Push the level line in the increasing direction as far as you can while it still touches the feasible region. The very last place it touches, just before it leaves the region behind, is where $P$ is largest. For a region with straight edges, that last contact happens at a single corner, or, if the line grazes a whole edge at once, at both corners of that edge together. That is the whole idea: the search collapses from infinitely many points down to a short list of corners.

Why a linear objective is optimized at a corner#

Take a bounded feasible region with straight edges meeting at corners, its boundary included in the region (every constraint $\le$ or $\ge$ , never strict), and an objective $P = ax + by$ that is not just a constant, so $a$ and $b$ are not both zero.

No point strictly inside the region can be the best. An interior point has room to move in every direction, so a small step toward larger $P$ still lands inside the region, and that step reaches a bigger level line. There is always a nearby point that beats an interior point, so the maximum must sit on the boundary.

Now follow a single edge from one end to the other. Both $x$ and $y$ change at a constant rate along a straight edge, so $P = ax + by$ changes at a constant rate too: it climbs the whole way, falls the whole way, or (when the edge happens to run along a level line) stays exactly the same the whole way. In the first two cases the best value on that edge sits at one end. In the third case every point on the edge ties for the best value, including both ends. Either way, an endpoint is always among the best points on the edge, and the endpoints of the edges are exactly the corners of the region.

Putting the two facts together: the maximum is never interior, and along the boundary it is always matched by an endpoint. So at least one corner achieves the maximum, matching the level-line picture above. Sliding the level line the opposite way runs the identical argument for the minimum.

The corner-point method

The principle turns into a four-step recipe, for any feasible region that is bounded, has an included boundary, and has at least one point in it:

Graph the feasible region from the constraints, exactly as in the last lesson.
Find every vertex (corner) of the region. Each corner is where two boundary lines cross, so read off which two lines meet there and solve that pair as a $2 \times 2$ system, the way you solved systems in an earlier chapter. Not every such crossing is a vertex of the region: check the result against every other constraint, and discard a crossing that fails one, since it lies outside the feasible region rather than on a corner of it.
Evaluate the objective $P$ at each vertex.
Compare the values: the largest is the maximum and the smallest is the minimum, and the vertex where it happens is the point that achieves it.

Worked example 1 Maximize $P = 3x + 2y$ subject to $2x + y \le 6$ , $x + 2y \le 6$ , $x \ge 0$ , $y \ge 0$

Start with the region. The two axes give the lower and left edges, since $x \ge 0$ and $y \ge 0$ pin everything to the first quadrant. The line $2x + y = 6$ runs through $(3, 0)$ and $(0, 6)$ , and testing the origin gives $0 \le 6$ , so its half-plane is the side toward the origin. The line $x + 2y = 6$ runs through $(6, 0)$ and $(0, 3)$ , and again the origin satisfies it. Shading all four conditions leaves a four-cornered region.

Next, find the vertices. Two come from the axes meeting the slanted lines, and one comes from the two slanted lines meeting each other.

The origin $(0, 0)$ is where the axes cross. On the $x$ -axis, the constraint that actually reaches down to meet it is $2x + y = 6$ with $y = 0$ , giving $x = 3$ , so $(3, 0)$ . On the $y$ -axis, the constraint that reaches it is $x + 2y = 6$ with $x = 0$ , giving $y = 3$ , so $(0, 3)$ . The last corner is where $2x + y = 6$ and $x + 2y = 6$ cross. Subtracting the second from the first removes the constant:

(2x + y) - (x + 2y) = 0 \quad\Longrightarrow\quad x - y = 0 \quad\Longrightarrow\quad x = y.

Putting $x = y$ into $2x + y = 6$ gives $3x = 6$ , so $x = 2$ and $y = 2$ : the vertex $(2, 2)$ .

The feasible region for 2x + y ≤ 6, x + 2y ≤ 6, x ≥ 0, y ≥ 0. Its four corners are (0,0), (3,0), (2,2), and (0,3). The objective P = 3x + 2y is evaluated at each to find the maximum.

Finally, evaluate $P = 3x + 2y$ at all four corners.

P(0, 0) = 0, \qquad P(3, 0) = 9, \qquad P(2, 2) = 6 + 4 = 10, \qquad P(0, 3) = 6.

The largest value is $10$ , reached at $(2, 2)$ . So the maximum of $P = 3x + 2y$ over this region is $\mathbf{10}$ , achieved at $x = 2$ , $y = 2$ . Notice the winner is the inside corner where the two slanted limits meet, not one of the axis corners, which is why checking every vertex matters.

Check your understanding

A feasible region has corners $(0, 0)$ , $(5, 0)$ , $(4, 3)$ , and $(0, 6)$ . Which corner maximizes $P = 2x + 5y$ ?

(4, 3)

(0, 6)

(5, 0)

(0, 0)

Check your understanding

A feasible region is bounded by $x \ge 0$ , $y \ge 0$ , $x + y \le 5$ , and $2x + y \le 8$ . What is the vertex where the lines $x + y = 5$ and $2x + y = 8$ cross?

(3, 2)

(2, 3)

(4, 0)

(0, 5)

When the region is unbounded

The corner-point principle promises a maximum and a minimum whenever the feasible region is bounded, meaning it fits inside some large box, and has an included boundary, meaning every constraint is $\le$ or $\ge$ rather than strict, exactly as in every constraint you have written so far. Many cost problems instead have an unbounded region that stretches out forever in some direction, because the constraints only set lower limits. There you have to be a little careful. Being unbounded does not by itself remove the maximum or the minimum; what matters is which direction the region stretches, compared to the direction that grows the objective. If the region keeps going exactly where $P$ keeps growing, there is no maximum, because you can travel outward without limit and drive $P$ as high as you like. Whenever the region does have at least one vertex, an extreme that exists is still found among the vertices, exactly as before; every region you build in this lesson, from $x \ge 0$ , $y \ge 0$ , and at least one more constraint, always has one. You just have to notice, and say plainly, when the extreme in the runaway direction does not exist.

Worked example 2 Minimize $C = 3x + 2y$ subject to $2x + y \ge 4$ , $2x + 3y \ge 8$ , $x \ge 0$ , $y \ge 0$

Because both slanted constraints are “greater than or equal to,” each half-plane is the side away from the origin. So the feasible region sits above and to the right of the two lines, and it runs off to infinity in that direction. The region is unbounded, which is fine for a minimum. Push the level line of $C = 3x + 2y$ in the decreasing direction, toward the origin, and it last touches the region at a corner.

Find the corners. On the $y$ -axis ( $x = 0$ ), the constraint that reaches it is $2x + y = 4$ , giving $y = 4$ , so $(0, 4)$ . On the $x$ -axis ( $y = 0$ ), the constraint that reaches it is $2x + 3y = 8$ , giving $x = 4$ , so $(4, 0)$ . The middle corner is where $2x + y = 4$ and $2x + 3y = 8$ meet. Subtracting the first from the second removes $2x$ :

(2x + 3y) - (2x + y) = 8 - 4 \quad\Longrightarrow\quad 2y = 4 \quad\Longrightarrow\quad y = 2,

and then $2x + 2 = 4$ gives $x = 1$ : the vertex $(1, 2)$ .

The unbounded feasible region for 2x + y ≥ 4, 2x + 3y ≥ 8, x ≥ 0, y ≥ 0. The shaded area opens up and to the right without end. Its corners are (0,4), (1,2), and (4,0), and C = 3x + 2y is smallest at (1,2).

Evaluate $C = 3x + 2y$ at the three corners.

C(0, 4) = 8, \qquad C(1, 2) = 3 + 4 = 7, \qquad C(4, 0) = 12.

The smallest value is $7$ , at $(1, 2)$ , so the minimum cost is $\mathbf{7}$ . There is no maximum here: starting from any feasible point and moving up and to the right keeps every constraint satisfied while sending $C = 3x + 2y$ upward without bound. Reporting “no maximum” is the honest and correct answer when the region is unbounded in the increasing direction.

Check your understanding

A feasible region satisfies $x \ge 0$ , $y \ge 0$ , and $x + y \ge 3$ , and it stretches upward and to the right without end. For the objective $P = x + y$ , which is true?

P

has both a maximum and a minimum B

P

has a minimum but no maximum C

P

has a maximum but no minimum D

P

has neither a maximum nor a minimum

Optimization in word problems

Most optimization problems arrive as a story, not as ready-made inequalities. Your job is to name the variables, translate each limited resource into one inequality, add the non-negativity constraints, and write the objective. After that, the corner-point method finishes the work, provided the variables can take any value in the region; if they must be whole numbers because they count separate items, that adds one more thing to check, covered below.

Worked example 3 A workshop's best daily plan

A workshop builds chairs and tables. Each chair needs $2$ hours of cutting and $1$ hour of assembly. Each table needs $1$ hour of cutting and $3$ hours of assembly. In a day the shop has at most $8$ hours of cutting and $9$ hours of assembly available. Each chair brings a profit of $30$ dollars and each table $50$ dollars. How many of each should the shop build to maximize profit?

Every number in the story becomes one coefficient. Laying them out in a table makes the translation easy to check:

	Cutting (hr)	Assembly (hr)	Profit (dollars)
Chair ( $x$ )	$2$	$1$	$30$
Table ( $y$ )	$1$	$3$	$50$
Daily limit	$8$	$9$	maximize

Let $x$ be the number of chairs and $y$ the number of tables. Reading down the Cutting column, cutting time used is $2x + y$ hours and cannot exceed $8$ ; reading down the Assembly column, assembly time used is $x + 3y$ hours and cannot exceed $9$ . The Profit column gives the objective, $P = 30x + 50y$ dollars. Since $x$ and $y$ count separate items, they must also be whole numbers, and of course neither can be negative. The full model is

\begin{aligned} \text{maximize } P = 30x + 50y \quad\text{subject to}\quad &2x + y \le 8, \;\; x + 3y \le 9, \\ &x \ge 0, \;\; y \ge 0, \;\; x, y \text{ whole numbers}. \end{aligned}

The corner-point method finds the best point while treating $x$ and $y$ as any real numbers, whole or not. Whenever that point turns out to have whole-number coordinates, as it will here, it is also the best whole-number plan, so the method still gives the answer directly.

Graph the region and find its corners. The origin $(0, 0)$ is one. On the $x$ -axis the constraint that reaches it is $2x + y = 8$ , giving $(4, 0)$ . On the $y$ -axis the constraint that reaches it is $x + 3y = 9$ , giving $(0, 3)$ . The inside corner is where $2x + y = 8$ and $x + 3y = 9$ meet. From the first, $y = 8 - 2x$ ; substituting into the second,

x + 3(8 - 2x) = 9 \quad\Longrightarrow\quad x + 24 - 6x = 9 \quad\Longrightarrow\quad -5x = -15,

so $x = 3$ and $y = 8 - 2(3) = 2$ : the vertex $(3, 2)$ .

The workshop's feasible production plans: 2x + y ≤ 8 (cutting) and x + 3y ≤ 9 (assembly), with x, y ≥ 0. The corners are (0,0), (4,0), (3,2), and (0,3), where x counts chairs and y counts tables.

Evaluate the profit $P = 30x + 50y$ at every corner.

\begin{aligned} P(0, 0) &= 0, &\qquad P(4, 0) &= 120, \\ P(3, 2) &= 90 + 100 = 190, &\qquad P(0, 3) &= 150. \end{aligned}

The best profit is $190$ dollars, at $(3, 2)$ , both whole numbers, so the shop should build $3$ chairs and $2$ tables each day. That plan uses $2(3) + 2 = 8$ cutting hours and $3 + 3(2) = 9$ assembly hours, so it spends both resources completely, which confirms $(3, 2)$ is where the two slanted limits cross. It is comparing all four corners, not merely using up every resource, that proves this plan earns the most profit.

Check your understanding

A garden shop plants rose bushes ( $x$ ) and shrubs ( $y$ ). Each rose bush needs $3$ square feet and each shrub needs $2$ square feet, in a bed with at most $18$ square feet. Which inequality models the space limit?

3x + 2y \le 18

2x + 3y \le 18

3x + 2y \ge 18

x + y \le 18

Check your understanding

A caterer makes wraps ( $x$ ) and salads ( $y$ ). Each wrap needs $4$ minutes of prep and each salad needs $6$ minutes, with at most $120$ minutes of prep time available. Each wrap earns $5$ dollars profit and each salad $7$ dollars. Which is the complete correct model for maximizing profit?

A maximize

P = 5x + 7y

subject to

4x + 6y \le 120

x \ge 0

y \ge 0

x, y

whole numbers B maximize

P = 5x + 7y

subject to

4x + 6y \le 120

C maximize

P = 4x + 6y

subject to

5x + 7y \le 120

x \ge 0

y \ge 0

D minimize

P = 5x + 7y

subject to

4x + 6y \le 120

x \ge 0

y \ge 0

Check your understanding

Why is it enough to check only the corners of the feasible region when maximizing a linear objective?

A Because the interior points are not part of the feasible region B Because the corners are always the points farthest from the origin C Because the level lines of the objective are parallel, so the last one to touch the region meets it at a corner D Because a linear objective is zero everywhere except at the corners

Common mistakes

Testing random interior points. The feasible region has infinitely many points, and picking a few from the middle never proves you found the best one. The corner-point principle is what lets you stop: whenever an optimum is attained, it is attained at a vertex, so checking the corners is enough, provided the region has one to check.
Missing a vertex. Every corner must go on the list. Skipping the inside corner where two slanted constraints cross is the most common slip, and that corner is often the one that wins, as in the worked examples.
Guessing a corner instead of solving for it. A vertex is the exact intersection of two boundary lines. Read off which two lines meet there and solve that $2 \times 2$ system. Do not eyeball the coordinates off the grid, since a near-miss like $(2, 3)$ instead of $(2, 2)$ changes the objective value.
Optimizing the wrong direction. Maximizing takes the largest objective value and minimizing takes the smallest. Compute the value at every corner first, then pick the end you actually want.
Expecting a maximum on an unbounded region. If the region runs off to infinity in the direction that increases the objective, there is no maximum. Only report the extreme that exists, and say so when the other one does not.
Forgetting the non-negativity limits. When the variables count real things, $x \ge 0$ and $y \ge 0$ are real constraints. Leaving them out can invent corners in a quadrant the problem never allows.

Key takeaways

An optimization problem pairs an objective function $P = ax + by$ to maximize or minimize with a system of linear constraints whose overlap is the feasible region.
Corner-point principle: a linear objective attains its maximum and its minimum on a bounded feasible region with an included boundary (every constraint $\le$ or $\ge$ ) at a vertex (corner), and here is why. The parallel level lines $ax + by = c$ last touch the region at a corner or all along an edge, and the objective is never best strictly inside.
The method: graph the region, find every vertex by solving the pair of boundary lines that cross there as a $2 \times 2$ system. Then evaluate the objective at each vertex, and take the largest (maximum) or smallest (minimum).
On a bounded region with an included boundary, both the maximum and minimum exist. On an unbounded region one of them may not exist, because the objective can run off without limit; report only the extreme that does.
For a word problem, name the variables, turn each resource limit into an inequality, add $x \ge 0$ and $y \ge 0$ , write the objective, and then run the corner-point method. If the variables count separate items, add that they must be whole numbers; the continuous optimum solves that version directly only when its coordinates already come out whole.

Introduction to Optimization Advanced. This lesson goes beyond core Algebra I. You can skip it.

Learning goals

Constraints, the objective, and the feasible region

Why the best value sits at a corner

The corner-point method

When the region is unbounded

Optimization in word problems

Common mistakes

Practice

Multiple Choice Questions (MCQ)

Core practice