Introduction to Optimization

Learning goals

Pair an objective $P = ax + by$ with linear constraints
Explain why a linear objective peaks at a vertex
Find each vertex by solving the two boundary lines that cross
Evaluate the objective at every corner and take the extreme
Say why an unbounded region may have no maximum
Add $x \ge 0$ and $y \ge 0$ when modeling a word problem

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 count real things that cannot go negative. 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 whole task is now sharp. 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.

Maximizing $P$ over the region is now a physical picture. 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 whose edges are all straight lines, that last contact happens at a corner.

Why a linear objective is optimized at a corner#

Take a bounded feasible region whose boundary is made of straight edges meeting at corners. Take also an objective $P = ax + by$ that genuinely depends on the variables, so $a$ and $b$ are not both zero.

First, the maximum cannot happen strictly inside the region. From any interior point, take a small step in the direction that increases $P$ , the direction pointing across the level lines toward larger values. Because the point started strictly inside, a short enough step stays inside the region, and it lands on a level line with a larger value of $P$ . So no interior point can be the best: there is always a nearby feasible point that beats it. The maximum must therefore lie on the boundary.

Now look along a single edge. As you slide from one endpoint of the edge to the other, both $x$ and $y$ change at steady rates, so $P = ax + by$ changes at a steady rate too. A quantity that changes at a constant rate along a segment is largest at one of the two ends, never strictly in the middle. The ends of the edges are exactly the corners of the region. Since the maximum lives on the boundary, and on each edge it is pushed to an endpoint, the maximum over the whole region is reached at a corner.

The parallel level lines say the same thing in a picture. The last line to touch the region as you slide outward meets it either at a single corner or all along an edge parallel to it. In that second case, the two corners at the ends of that edge tie for the best value. Either way at least one corner achieves the maximum. Sliding the line the opposite way runs the identical argument for the minimum. So both the maximum and the minimum of a linear objective over such a region occur at a corner.

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)$ . The level line $P = 9$ is the last one that still grazes the region, touching it only at $(3, 1)$ . That is the whole idea: the search collapses from infinitely many points down to a short list of corners.

The corner-point method

The principle turns into a four-step recipe that works every time.

First, graph the feasible region from the constraints, exactly as in the last lesson. Second, 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. Third, evaluate the objective $P$ at each vertex. Fourth, 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 binding limit is $2x + y = 6$ with $y = 0$ , giving $x = 3$ , so $(3, 0)$ . On the $y$ -axis, the binding limit 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)

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. 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: the objective can still have a minimum at a corner, but it may have no maximum at all. That is because you can travel outward without limit and drive the objective as high as you like. The method is the same; you just report only the extreme that actually exists.

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 binding constraint is $2x + y = 4$ , giving $y = 4$ , so $(0, 4)$ . On the $x$ -axis ( $y = 0$ ), the binding constraint 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.

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.

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?

Let $x$ be the number of chairs and $y$ the number of tables. Both are counts, so $x \ge 0$ and $y \ge 0$ . Cutting time used is $2x + y$ hours and cannot exceed $8$ , and assembly time used is $x + 3y$ hours and cannot exceed $9$ . The profit to maximize is $P = 30x + 50y$ dollars. 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. \end{aligned}

Graph the region and find its corners. The origin $(0, 0)$ is one. On the $x$ -axis the binding limit is $2x + y = 8$ , giving $(4, 0)$ . On the $y$ -axis the binding limit 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)$ . 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. That is exactly why the plan lands on the corner where the two limits meet.

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: the optimum is always at a vertex, so only the corners need checking.
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 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 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.

Introduction to Optimization

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)

Free Response Questions (FRQ)