Linear Programming
Linear programming finds the best value — most profit, least cost — of an objective like , subject to constraints that carve out a feasible region.
The key theorem: the maximum and minimum always occur at a corner (vertex) of that region. So you only have to test the corners, not the whole area.
The feasible region and its corners
The constraints are inequalities; graphing them all gives the feasible region, the set of points that satisfy every constraint. Its corners are where boundary lines meet.
Because the objective is linear, its extreme values land at these corners — never in the middle. That turns an infinite search into checking a short list of points.
The shaded quadrilateral below is a feasible region. Linear programming only tests its four corner points, marked on the figure — the best objective value is always found at one of them.
The vertex method
List every corner of the feasible region. Plug each into the objective function and compute the value.
The largest result is the maximum; the smallest is the minimum. Read the winning corner's coordinates if the problem asks where the best value occurs.
Worked examples
Example 1: maximizing profit
A feasible region has corners , , , . Maximize .
Answer: , at
Example 2: reading the minimum
For the same corners, what is the minimum of ?
Answer: , at
Try one yourself
Common questions
Why only check the corners?
For a linear objective over a polygon-shaped region, the maximum and minimum always occur at a vertex. Interior points can never beat every corner.
What is the feasible region?
The set of all points satisfying every constraint at once — the overlap of the constraint inequalities' shaded regions.
What if the region is unbounded?
Then a maximum or minimum may not exist in one direction. You can still test corners for the bounded extreme, but note when the objective can grow without limit.
Want the video version?
Allday Everyday Math has video lessons, practice, and an AI tutor for every topic, Pre-Algebra through Algebra 2.