MISSION · Algebra
Linear Programming
The continuous optimum is at a corner; whole-item plans need an integer check
LEVEL 1 · EXPLORE
Make the idea move
Change the controls and watch what happens. Follow your curiosity and see what you notice.
Loading the activity…
LEVEL 2 · LEARN
Unlock the explanation
Open the chapters in any order. Try the examples as you go.
The idea in one sentence
Draw every constraint as an inequality, shade what survives, and the best continuous solution is guaranteed to sit at a corner of the region that’s left. If the variables count whole products, check the feasible integer points as well.
The setup
Three pieces, always:
- Variables — what you get to choose. How many of each product to make.
- Constraints — inequalities limiting the choice. Machine hours, materials, staff, and the fact that you can’t make a negative number of anything.
- Objective function — what you’re maximising or minimising. Usually profit or cost.
A workshop makes tables and chairs. Each table takes 4 hours of labour and 1 roll of fabric; each chair takes 2 hours and 2 rolls. There are 80 hours and 50 rolls available. Tables make £70 profit, chairs £40.
\(4t + 2c \le 80 \qquad t + 2c \le 50 \qquad t, c \ge 0\) \(\text{maximise } P = 70t + 40c\)
The feasible region
Each inequality cuts the plane in half. Shade the overlap of all of them and you have the feasible region — every combination that satisfies every constraint at once.
Because all the constraints are straight lines, the region is a polygon. That fact is what makes the whole method work.
Why the continuous answer is at a corner
The objective function \(P = 70t + 40c\) describes a family of parallel lines, one for each profit level. Raising the profit slides the line outwards without turning it.
So push that line as far as it goes while still touching the feasible region. The last point of contact, before it leaves entirely, is where the maximum lives — and sliding a straight line out of a polygon, you leave through a corner. (If the line happens to be parallel to an edge, you leave through the whole edge, and every point on it is equally optimal — corners included.)
That reduces an infinite search to a finite one: evaluate the objective at each vertex and compare. No calculus, no guessing. This corner theorem is about the continuous region; requiring whole products turns the problem into an integer program, where the best integer point may sit just inside an edge rather than at a continuous vertex.
For the workshop, the corners are \((0,0)\), \((0, 25)\), \((20, 0)\), and where the two constraint lines cross, at \((10, 20)\). The profits there are £0, £1,000, £1,400, and £1,500. The best plan is 10 tables and 20 chairs — and note that it isn’t either of the “make only one thing” corners, which is the usual reason this is worth doing at all.
What it’s used for
This is one of the most commercially applied pieces of mathematics there is. Airline crew rostering, refinery blending, delivery routing, portfolio allocation, hospital shift planning — all are linear programs, usually with thousands of variables rather than two, solved by the simplex algorithm rather than by drawing.
The two-variable graphical version is the same idea small enough to see.
Common mix-ups
- Forgetting \(x, y \ge 0\). Negative production is not a plan, and leaving it out opens the region to nonsense.
- Shading the wrong side. Test a point — the origin is usually easiest — and see whether it satisfies the inequality.
- Checking only some corners. Evaluate every vertex.
- Reading a non-integer answer as final. If you cannot make half a table, the nearest whole-number point inside the region needs checking separately.
Check yourself
Why is it enough to test the corners rather than every point in the region?
For continuous variables, the objective is a straight line sliding across a polygon. Its last contact as it moves outwards is at a vertex, so no interior point can beat every corner; whole-item plans require a separate feasible-integer check.
LEVEL 3 · REFLECT
Add this quest to your trail
When you feel ready, mark this idea as explored. You can always come back and try it again.
EXPLORER STRATEGIES