A linear inequality in two variables is satisfied by a half-plane, and a system of them by the region where the half-planes overlap. On a nonempty closed, bounded feasible polygon, a linear objective reaches its largest and smallest values at corners, reducing infinitely many candidates to a finite list.
Core ideas
The whole subject rests on one theorem. Without it there would be infinitely many points to check and no method at all.
The line ax + by = c splits the plane in two. On one side ax + by > c, on the other ax + by < c, and on the line itself they are equal. So a single test point decides the entire side, and the boundary belongs to the solution for ≤ and ≥ and not for < and >.
A point is feasible only if it satisfies every constraint. Two boundary lines crossing somewhere is not enough to make that crossing a corner of the region; it has to survive all the other constraints as well.
A linear objective on a feasible polygon that is nonempty, closed and bounded attains its largest and smallest values at corners. That is why the method is "list the corners and evaluate" rather than a search. An unbounded region needs a separate check of the directions in which it continues.
The material
Shading by test point, finding corners by elimination, and the theorem that says corners are enough.
Lines, Functions and Graphs ended with a single linear inequality in two variables: draw the boundary line, decide which side, shade it. Everything here is that, done several times on one set of axes, and then asked a question.
The set of points (x, y) making the statement true. For a linear inequality it is a half-plane: everything on one side of the line ax + by = c, with the line included when the inequality is ≤ or ≥ and excluded when it is < or >.
One test point settles the shading. Pick any point not on the boundary — the origin, unless the line passes through it — and substitute. If the statement is true, shade that side; if false, shade the other. This works because ax + by - c keeps one sign throughout each side and only changes sign by passing through the line.
Given a system of linear inequalities, the feasible region is the set of points satisfying all of them at once: the intersection of the half-planes. It may be empty, it may be a bounded polygon, and it may run off to infinity.
x ≥ 0, y ≥ 0, x + y ≤ 8, 2x + y ≤ 10. The first two confine everything to the first quadrant; the last two cut it with two lines. What survives is a four-sided region with corners at (0, 0), (5, 0), (2, 6) and (0, 8), and the worked example below finds those corners rather than reading them off a picture.
A linear objective function P = ax + by, together with a system of linear inequalities called the constraints. The problem is to find the point of the feasible region at which P is largest, or smallest. Such a point is called optimal.
If the feasible region is not empty, closed and bounded, then a linear objective function attains both a maximum and a minimum on it, and each occurs at a corner. If the same optimal value occurs at two corners, then every point of the edge joining them is optimal as well.
This statement does not classify an unbounded feasible region. There the objective must also be tested along the directions in which the region continues; a maximum, a minimum, both or neither may exist.
The reason is worth seeing even though the proof is not given here. The points where ax + by takes some fixed value k form a line, and different values of k give parallel lines. Increasing k slides that line across the plane in one direction. The largest k for which the line still touches the region is the one where it is just about to leave — and a straight line leaving a polygon leaves through a corner, or along a whole edge if it happens to be parallel to one.
That is the entire method. Infinitely many feasible points, and the theorem says four of them need checking. Nothing about it survives if the objective is not linear: P = xy on the region above is largest at (2.5, 5), which is not a corner of anything.
Take x ≥ 0, y ≥ 0, x + y ≥ 4. The region is everything in the first quadrant on or above the line x + y = 4, and it runs off to infinity. C = 2x + 3y has a minimum of 8 at (4, 0): C = 2(x + y) + y ≥ 8. It has no maximum, because the feasible points (4 + t, 0) make C = 8 + 2t grow without bound. The corner values suggest the minimum, but these two inequalities prove the global claims.
Two practical cautions. A strict inequality removes its boundary line from the region, so an optimum sitting on that line is approached but never reached; applied problems are stated with ≤ and ≥ for exactly this reason. And if the quantities are things like whole machines or whole people, the corner may be fractional, and rounding it is not guaranteed to give the best whole-number answer — that is a different subject.
Interactive
The objective at every corner, and the corner that wins
Method
Four steps. The third is where the answers are lost.
Replace each inequality sign by = and draw the line, solid for ≤ and ≥, dashed for < and >. Do not skip x ≥ 0 and y ≥ 0; they are constraints like any other and they contribute corners.
One point per inequality, the origin where possible. The feasible region is what all the shadings have in common, and it is worth outlining once it is clear.
Every corner is the intersection of two boundary lines, so solve those two equations together — elimination, from “Solving by Elimination”. Then test the point against every other constraint and discard it if it fails one.
For a nonempty closed, bounded region, tabulate the values and pick the largest or the smallest, as asked; the corner theorem makes that comparison conclusive. For an unbounded region, also test the feasible directions in which the region continues.
Four constraints give four boundary lines, and four lines cross in six places. Two of those six crossings are not corners of the region, and both of them would give a larger P than the true answer.
The last line is why step 3 ends with a test rather than a corner. Both rejected crossings give P = 40, comfortably larger than the true maximum of 34. An unchecked crossing does not add a harmless extra candidate to the list; it wins, and the answer is then a point at which one of the constraints is false.
The maximum is 34, attained at x = 2, y = 6. Report the point as well as the value: "34" alone does not say what to do.
Faded rehearsal: keep the same four constraints but minimise C = 2x + 7y. The feasible corners have already been established, so build a fresh objective table without reusing the old P values. Name both the winning point and value, then explain why the bounded closed, bounded region makes the corner comparison conclusive.
Given four or five constraints you should be able to produce the corner list without a graph, discard the crossings that fail a constraint, and on a nonempty closed, bounded region name the optimal point and its value. For an unbounded region, exhibit a feasible ray or a global bound instead of citing the bounded theorem. Saying "the maximum is 34" without saying where is half an answer.
Something to change about this lesson? Write it down, tick it off when it is handled, and export the list when you want to act on it. Kept in this browser only: nothing is sent anywhere, and nobody is notified.
No recommendations yet for this lesson.