Why the best plan sits at a corner
The graphical method solves a linear program with two variables by drawing its limits and looking at the corners of the shape they make. It works because the best plan is always at a corner.
That means a computer, or you, only has to check a few points instead of every possible plan.
By the end of this lesson
Note
I can solve a two-variable problem by looking at its corners.
Key words
| Word | What it means |
|---|---|
| Boundary line | the line where a constraint is used up exactly |
| Feasible region | the set of all feasible plans |
| Corner point | a point where two boundary lines cross |
| Optimal plan | the feasible plan with the best objective value |
The cells students fill in are left blank in this preview.
The limits leave a feasible region
Draw the oven limit as a line on a graph with loaf batches across and cake batches up. Every plan on the correct side of the line obeys it. Do the same for the flour limit and for x >= 0 and y >= 0.
The plans that obey every line at once form a shape with straight sides. This is the feasible region.
Worked example: the four boundary lines
| Line | Where it cuts the axes | Keep the side |
|---|---|---|
| x + 2y = 8 (oven) | x = 8 when y = 0; y = 4 when x = 0 | Towards the origin |
| 3x + 2y = 18 (flour) | x = 6 when y = 0; y = 9 when x = 0 | Towards the origin |
| x = 0 | The upward axis | Right of it |
| y = 0 | The sideways axis | Above it |
The cells students fill in are left blank in this preview.
A corner is where two boundary lines meet
The shape has four corners. Two are on the axes: the origin (0, 0) and the flour line at (6, 0). A third is the oven line at (0, 4).
The fourth is where the oven and flour lines cross. Take the oven line away from the flour line and you get 2x = 10, so x = 5 and y = 1.5.
Check where the lines cross
docker exec jupyter python3 -c "print(5 + 2 * 1.5, 3 * 5 + 2 * 1.5)"Shown here, not run. Create a free account to press Run and type it into your own lab’s terminal.
The fourth corner uses both limits
The command printed 8.0 18.0. At 5 loaf batches and 1.5 cake batches the oven works for exactly 8 hours and the flour is exactly used up.
Both limits are met with nothing to spare, which is why this point is a corner.
The best plan is always at a corner
Picture the profit as a line that moves across the region. Each position of the line is one profit level. The best plan is the last point the line touches as it leaves the shape.
A straight line leaves a straight-sided shape at a corner, or along a whole edge. So you only have to find the profit at each corner and take the largest.
The profit at each corner
docker exec jupyter python3 -c "print([20 * x + 30 * y for x, y in [(0, 0), (6, 0), (0, 4), (5, 1.5)]])"Shown here, not run. Create a free account to press Run and type it into your own lab’s terminal.
Worked example: the profit at each corner
| Corner | Loaf batches | Cake batches | Profit in pounds |
|---|---|---|---|
| A | 0 | 0 | 0 |
| B | 6 | 0 | 120 |
| C | 0 | 4 | 120 |
| D | 5 | 1.5 | 145 |
The cells students fill in are left blank in this preview.
A common mistake
Warning
Many people think the best plan is somewhere in the middle of the region, where nothing is wasted. The profit always improves in one direction, so the best point is at the edge. Check the corners, not the centre.
Two corners can tie for the best profit
Suppose a loaf batch earned 10 pounds and a cake batch 20. The profit 10x + 20y is exactly half of the oven line x + 2y.
Corners C and D then both earn 80 pounds, and so does every plan on the oven line between them. The method still works: take any corner with the largest profit.
Going further
Change the profits to 30 pounds a loaf batch and 10 pounds a cake batch and work out which corner wins. Then try 10 and 40.
Explain why the winning corner moves as the profits change, while the shape of the region stays the same.