Back to the on-screen lesson ·
Sliding a level line across a convex polygon, and why the last thing it touches is a corner.
Paper packet. Every task here also exists on screen, where it is checked automatically; answers written on paper are not assessed by Nydus. When you are back at a device, enter your answers there.
By the end of this lesson you will be able to evaluate a linear objective at every corner of a two-variable region and report the optimal corner together with its value, explain the optimum as the last contact of a sliding level line, find the range of an objective coefficient over which one corner stays optimal, and give the argument that testing the corners is enough.
You can find the corners of a two-variable region. This lesson adds the objective, and the surprising part is how little of the region it needs to look at.
A level line of $px + qy$ is the set of points where it takes one fixed value; the level lines are parallel, with slope $-p/q$. The improving direction is the way they must be slid for the value to rise. A feasible point where no feasible point is better is optimal.
Draw any level line of the objective and slide it, keeping it parallel, in the improving direction. The value rises as it goes. The last position at which it still touches the region is the optimum, and because the region is a convex polygon that last contact is a corner — or, when the level line is parallel to an edge, that whole edge.
That is why the graphical method is a finite procedure: evaluate the objective at each corner and take the best. The corners are few, the substitutions are one line each, and no part of the interior ever has to be looked at.
The answer to report is the corner, not only its value. A number says how good the plan is; the coordinates say what to do. And because the winner depends only on the objective's slope, it does not drift as a coefficient changes — it stays put over a whole range of coefficients and then jumps, which is the subject of unit 4.
Another way: steps
Another way: picture
Lay a ruler along a level line of the objective and slide it across the polygon without turning it. Watch where it last touches: a single corner almost always, and a whole edge in the one case where the ruler happens to lie flat along an edge.
The optimum is looked for in the middle of the region, as though the objective had a peak somewhere inside. It does not: from an interior point there is always still a direction that improves. The other error is reporting the value and stopping — the plan is the answer, and the value is only its score.
Corners $(0, 0)$, $(20, 0)$, $(0, 20)$ and $(\tfrac{100}{11}, \tfrac{180}{11})$, with profit $30x_1 + 50x_2$.
Four corners to try.
Values $0$, $600$, $1000$ and $\tfrac{12000}{11} \approx 1090.9$.
One substitution each.
The mixture wins, and both resources are used up there. It took two scarce resources to make a mixture worth making.
Report the corner.
The corners are $(0, 0)$, $(5, 0)$ and $(0, 5)$, with values $0$, $5$ and $5$.
Two of them tie.
The level lines are parallel to the edge joining them, so every point of that edge is optimal and the value is $5$.
Maximise $7x + 3y$ over $x \ge 0$, $y \ge 0$, $x \le 8$, $y \le 4$, $x + y \le 11$. Evaluate the objective at each corner.
| $x$ | $y$ | Objective | |
|---|---|---|---|
| The origin | 0 | 0 | |
| On the $x$ bound | 8 | 0 | |
| The better mixture | 8 | 3 | |
| The other mixture | 7 | 4 | |
| On the $y$ bound | 0 | 4 |
Maximise $9x + 5y$ over $x \ge 0$, $y \ge 0$, $x \le 4$, $y \le 8$, $x + y \le 10$. Give the optimal corner and its value.
A five-cornered region with two upper bounds and one shared limit.
$x$ at the optimum:
$y$ at the optimum:
The optimal value:
Maximise $8x + 7y$ over the triangle $x \ge 0$, $y \ge 0$, $x + y \le 11$. What is the optimal value?
Answer:
The level lines of $9x + 2y$ are slid across a bounded feasible region in the improving direction. What is the last part of the region a level line touches?
Over $x \ge 0$, $y \ge 0$, $x \le 5$, $y \le 4$, $x + y \le 8$ the objective is $cx + 3y$ with $c \ge 0$. For which $c$ is $(5, 3)$ optimal? Give the interval.
This task has no paper form; do it on a device.
Build the proof that over a bounded feasible region some corner is at least as good as every feasible point — so that testing $9$ corners settles an infinite region.
This task has no paper form; do it on a device.
Lesson test: one question per skill, one attempt each, no hints. Your answers are checked when you submit.
Maximise $6x + 3y$ over $x \ge 0$, $y \ge 0$, $x \le 3$, $y \le 3$, $x + y \le 5$. Evaluate the objective at each corner.
| $x$ | $y$ | Objective | |
|---|---|---|---|
| The origin | 0 | 0 | |
| On the $x$ bound | 3 | 0 | |
| The better mixture | 3 | 2 | |
| The other mixture | 2 | 3 | |
| On the $y$ bound | 0 | 3 |
You can find the optimal corner of a two-variable program and say which range of objective coefficients keeps it optimal. Say in your own words why no point strictly inside the region can be optimal.
7. Your turn: maximise $x + y$ over the triangle $x, y \ge 0$, $x + y \le 5$, step 2