College Algebra's linear programming chapter is where "optimal solution" first meant something concrete: shade every constraint, find the region every one of them agrees on, and slide a line across it until it's about to leave for good. That two-variable picture is the entire simplex method in miniature, and it never stops being true once this course's later chapters push into dozens or thousands of variables -- there just stops being a picture to draw. Getting the graphical version rock solid now is what makes the algebraic version in chapter 7 feel like the same idea wearing bookkeeping instead of ink.
Theorem
Corner-Point Theorem
also known as: the fundamental theorem of linear programming
Recalled from College Algebra · Linear programming — first taught there.
If a linear objective function z=ax+by has a maximum or minimum value over a feasible region defined by linear constraints, that optimal value occurs at one of the region's vertices. It never occurs at an interior point.
Assume (a,b)\neq(0,0) (otherwise z is the same constant everywhere and every point, vertices included, is trivially optimal). Suppose z attains its maximum at some feasible point P.
P can't be an interior point. If P is interior, every point close enough to P in every direction is still feasible. Moving a tiny step from P in the direction (a,b) changes z by a positive amount (that's what (a,b)\neq(0,0) buys), producing a nearby feasible point with a strictly larger z — contradicting that P was already maximal.
So P sits on the boundary — either at a vertex (done), or in the interior of an edge joining two vertices V_1 and V_2. Along that edge, every point is (1-t)V_1+tV_2 for some t\in[0,1], and because z is linear, z\big((1-t)V_1+tV_2\big) = (1-t)\,z(V_1) + t\,z(V_2), an affine function of t alone. An affine function on [0,1] reaches its largest value at t=0 or t=1 — the two endpoints — unless it's constant on the whole interval, in which case z(V_1)=z(V_2)=z(P) too. Either way, some vertex achieves a value at least as large as z(P)'s, and since P was already maximal, that vertex ties or matches it.
The minimum case is identical with every inequality reversed.
Picture the feasible region as the floor of a room built entirely from straight walls, one wall per constraint, with only the space every wall agrees is "inside" left over. Now picture the objective as a giant flat ruler you can slide across that floor without tilting it, always parallel to itself, with every point along one position of the ruler worth the same score. As you slide the ruler in the direction that increases the score, it keeps touching the floor right up until the very last instant it's still inside the room -- and because straight walls only meet at sharp corners, that last instant almost always happens exactly at one corner, never in the middle of a flat wall or in some open patch of floor. That is the entire reason optimizing a straight-line objective only ever needs checking the corners: nowhere else on a polygon's floor can be the very last point a straight ruler touches while sliding through.
A linear program in two variables shades each constraint as a half-plane, and the feasible region is the intersection of all of them -- a polygon (or an unbounded region) whenever the constraints are consistent. The corner-point theorem guarantees that if an optimal solution to a linear objective exists on a bounded feasible region, it exists at one of the region's corners (vertices), never strictly inside an edge and never in the interior. That is not a coincidence of easy examples: because the objective c_1x+c_2y is linear, its level curves are parallel lines, and sliding a family of parallel lines across a polygon always leaves it last through a single vertex (or, in a tie, an entire edge connecting two vertices) -- never through an interior point, since a line through the interior could always slide a little further in the improving direction before leaving the region.
Where two boundaries cross
This crossing point is a candidate vertex of the feasible region -- but it only counts if it also satisfies every OTHER constraint the region has, not just the two lines that happen to meet here.
Loading interactive…
Slide the ruler, watch which corner survives
Toggle each constraint on and drag the objective's sliding ruler across the shaded region -- find the vertex it leaves last as you push the ruler's value higher, and drop it there.
Loading interactive…
Right on try — credit. Right — the answer had already been shown, so no credit this time. Next try is worth Answer shown after three tries — this one no longer earns credit. You chose to see the answer — this one earns no credit.
What this task checks
Structure checked automatically. Whether your ideas are convincing isn't graded, so reread with the checklist.
The compiler says
A model answer
Correct answer
Also accepted:
Why
Why
A second feasible region, worked from scratch
Drag the sliding ruler (the level line P=30x+40y) across this region -- find the vertex it leaves last, and drop it there.
Loading interactive…
Right on try — credit. Right — the answer had already been shown, so no credit this time. Next try is worth Answer shown after three tries — this one no longer earns credit. You chose to see the answer — this one earns no credit.
What this task checks
Structure checked automatically. Whether your ideas are convincing isn't graded, so reread with the checklist.
The compiler says
A model answer
Correct answer
Also accepted:
Why
Why
Worked example
Maximizing P=5x+4y subject to x+2y\le14, 3x+y\le15, x,y\ge0
-
1
A small shop makes two products, x units of the first and y of the second, earning profit P=5x+4y subject to x+2y\le14 and 3x+y\le15 (both resource limits), with x,y\ge0.
-
2solve the two binding constraints as a system to find their crossing
Find every vertex. The two resource lines cross where x+2y=14 and 3x+y=15: solving, y=15-3x, so x+2(15-3x)=14 \implies -5x=-16 \implies x=3.2,\ y=5.4.
solve the two binding constraints as a system to find their crossing
-
3
List all vertices of the feasible region: (0,0), (5,0) (where 3x+y=15 meets y=0), (3.2,5.4) (the two resource lines' crossing), and (0,7) (where x+2y=14 meets x=0).
-
4
Evaluate P=5x+4y at each: P(0,0)=0, P(5,0)=25, P(3.2,5.4)=16+21.6= 37.6, P(0,7)=28.
-
5
\boxed{\text{Maximum }P=37.6\text{ at }(x,y)=(3.2,5.4).} Every candidate was a corner -- exactly as the corner-point theorem promised, no interior point of the region was ever a contender.
Where this shows up
Resource allocation and production planning
This exact shape -- a linear profit or cost subject to linear resource limits -- is how a factory decides a production mix, how a diet plan meets nutrient minimums at least cost, and how a shipping company allocates trucks across routes, all before this course adds a single new idea. The graphical method tops out at two decision variables because a person can only draw two axes, but the corner-point logic behind it is exactly what chapter 7's simplex method automates once a real problem has fifty variables and no picture to draw.
Check your understanding (counts toward your progress)
An LP's objective is P=3x+2y. Two adjacent vertices, (5,1) and (1,5), both give P=17. What does this tie mean for the optimal solution?
Right on try — credit. Right — the answer had already been shown, so no credit this time. Next try is worth Answer shown after three tries — this one no longer earns credit. You chose to see the answer — this one earns no credit.
A tie between two vertices doesn't mean no solution exists -- it means there's more than one.
Both can be correct at once -- a linear objective can tie along an entire edge when its level line happens to run parallel to that edge.
A tie between two adjacent vertices says nothing about whether the region is bounded or not.
Why
When the objective's level line is parallel to an edge, every point along that edge -- not just its two endpoints -- shares the same optimal value. This is the tie case the corner-point theorem's own statement allows for.
Two boundary lines, x+y=8 and 2x+y=10, cross at (2,6). What must be checked before calling (2,6) a vertex of the feasible region?
Right on try — credit. Right — the answer had already been shown, so no credit this time. Next try is worth Answer shown after three tries — this one no longer earns credit. You chose to see the answer — this one earns no credit.
Positive coordinates matter only if x\\ge0,y\\ge0 happen to be constraints in this particular problem -- and even then, that's just one more constraint to check, not a general rule.
The objective's value doesn't determine feasibility -- a point can be feasible with a low objective value, or infeasible with a high one.
A crossing of two lines is only a CANDIDATE -- it counts as a vertex only if it also satisfies every other constraint.
Why
A crossing point of two constraint boundaries is a candidate vertex, but only becomes an actual vertex of the feasible region once it's confirmed to satisfy every remaining constraint too.
A candidate point satisfies x+y\le10 and x\ge0, but fails y\ge0. Can this point still be a vertex of the feasible region?
Right on try — credit. Right — the answer had already been shown, so no credit this time. Next try is worth Answer shown after three tries — this one no longer earns credit. You chose to see the answer — this one earns no credit.
There's no "majority rule" for feasibility -- every single constraint must hold at once, with no exceptions.
Two lines crossing is only a CANDIDATE vertex; it only counts if that crossing point also satisfies every other constraint.
Evaluating the objective at an infeasible point produces a number, but that number is never a valid candidate for the optimum.
Why
The feasible region is the intersection of every constraint's half-plane. Failing even one constraint removes a point from consideration entirely, regardless of how many others it satisfies.
A feasible region has vertices (0,0), (6,0), (4,3), and (0,5). For the objective P=2x+3y, what is P at the vertex (4,3)?
Right on try — credit. Right — the answer had already been shown, so no credit this time. Next try is worth Answer shown after three tries — this one no longer earns credit. You chose to see the answer — this one earns no credit.
Why
P(4,3)=2(4)+3(3)=8+9=17.
Correct answer
Also accepted:
Why
Check your understanding (counts toward your progress)
A club sells T-shirts (x) and mugs (y) to raise money, with a \$500 material budget and 40 hours of volunteer time available. Describe, in words, the two steps needed to turn this scenario into a graphical linear program (without solving it).
AI grading isn't configured on this deployment.
Right on try — credit. Right — the answer had already been shown, so no credit this time. Next try is worth Answer shown after three tries — this one no longer earns credit. You chose to see the answer — this one earns no credit.
First mistake
Correct answer
Also accepted:
Why
Think about what becomes the objective, and what becomes the constraints.
A farmer plants wheat (x acres) and corn (y acres), constrained by total acreage x+y\le100 and a labor limit 3x+2y\le240, wanting to maximize revenue R=200x+300y. Which constraint is more restrictive at the vertex where both are tight at once?
Right on try — credit. Right — the answer had already been shown, so no credit this time. Next try is worth Answer shown after three tries — this one no longer earns credit. You chose to see the answer — this one earns no credit.
A single constraint only fixes a whole boundary LINE, not a single point -- the vertex needs a second tight constraint to pin down.
Same issue -- one tight constraint alone leaves an entire line of possibilities, not one specific vertex.
The objective decides WHICH vertex wins, but the constraints are still what define where every candidate vertex sits.
Why
A vertex is where two boundary lines cross, so by definition it's exactly where two constraints (here, acreage and labor) are simultaneously tight.
A bakery makes cakes (x) and pies (y), earning profit P=6x+9y, limited by oven-time 2x+3y\le18 and decorating-time x+y\le7, with x,y\ge0. Which pair of constraints, if any, is missing from this model?
Right on try — credit. Right — the answer had already been shown, so no credit this time. Next try is worth Answer shown after three tries — this one no longer earns credit. You chose to see the answer — this one earns no credit.
The objective IS the profit -- capping it as a separate constraint would just contradict what the problem is maximizing.
Nothing in the scenario says cakes and pies must be made in equal amounts.
An inequality is the right model here -- oven time can be used UP TO its limit, not necessarily exactly used up.
Why
The two resource limits plus nonnegativity are exactly what the scenario describes; no hidden constraint is missing.
A shipping company wants to MINIMIZE cost subject to linear constraints on a bounded feasible region. Does the corner-point theorem still apply?
Right on try — credit. Right — the answer had already been shown, so no credit this time. Next try is worth Answer shown after three tries — this one no longer earns credit. You chose to see the answer — this one earns no credit.
Minimizing c_1x+c_2y is the same as maximizing -c_1x-c_2y -- still a linear objective over the same region, so the same vertex argument applies.
The sliding-line argument never assumed a direction -- sliding "downhill" to the last touching point works exactly the same way.
The sign of the coefficients changes WHICH vertex wins, never WHETHER the optimum is at a vertex.
Why
Minimizing is just maximizing the negative of the same linear objective, so the corner-point theorem transfers over unchanged.
Practice: Vertices, objective values, and the corner-point shortcut (3 problems · doesn’t affect your progress)
A feasible region has vertices (0,0), (4,0), (2,3), and (0,5). For P=3x+2y, evaluate P at (2,3).
Right on try — credit. Right — the answer had already been shown, so no credit this time. Next try is worth Answer shown after three tries — this one no longer earns credit. You chose to see the answer — this one earns no credit.
Why
P(2,3)=3(2)+2(3)=6+6=12.
Correct answer
Also accepted:
Why
Using the same region ((0,0), (4,0), (2,3), (0,5)) and P=3x+2y, what is the maximum value of P?
Right on try — credit. Right — the answer had already been shown, so no credit this time. Next try is worth Answer shown after three tries — this one no longer earns credit. You chose to see the answer — this one earns no credit.
Why
P(0,0)=0, P(4,0)=12, P(2,3)=12, P(0,5)=10 -- the maximum is 12, tied between two adjacent vertices.
Correct answer
Also accepted:
Why
In the previous problem, (4,0) and (2,3) tie for the maximum. What does the corner-point theorem say happens between them?
Right on try — credit. Right — the answer had already been shown, so no credit this time. Next try is worth Answer shown after three tries — this one no longer earns credit. You chose to see the answer — this one earns no credit.
A tie between vertices doesn't break the problem -- it just means there's more than one optimal point.
Both tied vertices are equally valid optima -- neither is preferred by coordinate size alone.
A bounded region can produce a tie too, exactly as it does here -- unboundedness isn't required.
Why
When the objective's level line runs parallel to an edge, that entire edge -- both endpoints and everything between -- shares the same optimal value.
Every point on the edge connecting (4,0) and (2,3) is also optimal