Why an optimum, if there is one, has to sit at a corner

0:00Here is a region. Every point of it satisfies every condition, so every point of it is a purchase the dealer is allowed to make. Now find the one that earns him the most. You cannot do it by checking. There are eight hundred and fifty one allowed purchases on the whole numbers. Allow halves and there are three thousand three hundred and one. Allow quarters and there are thirteen thousand and one. Halve the spacing again and it roughly quadruples again, and there is no end to that.

0:35And between any two allowed purchases there is another one. Halfway from five tables and twenty chairs to ten and fifty is seven and a half tables and thirty five chairs, and that is allowed too. So an exhaustive search is not slow. It is impossible. Something has to cut the list down from endless to finite, and that is what the next two results are for. Which is worth saying out loud, because they usually arrive with no question attached, and a result that answers a question nobody asked you is a result you will only ever memorise.

1:19The cut is going to be down to the corners, so first: what is a corner? A corner point is a point of the region where two boundary lines cross. Boundary lines. Not constraint lines. And that distinction is where people lose marks, because the two axes are boundary lines too. They have to be. The condition that the number of tables is at or above nothing is a condition like any other, and the line it is drawn from is the vertical axis. Same for chairs and the horizontal one.

1:57Watch what happens if you forget. Look only where two constraint lines cross, and on this region you find exactly one corner: ten and fifty. The origin needs both axes. Twenty and nought needs one. Nought and sixty needs the other. One corner found out of four. Three candidates thrown away before you started, and one of the three might have been the answer. So when you list corners, trace all four boundary lines in the same weight, and take every crossing that lands in the region. Here that is four, with two conditions tight at each.

2:39Now the picture that makes all of this obvious, and that nobody ever draws. I should say plainly that this argument is mine and not the standard one, because the standard treatment gives no argument at all. The profit is two hundred and fifty a table and seventy five a chair. Ask which purchases earn exactly fifteen hundred rupees, and the answer is a whole straight line of them. Ask for three thousand instead and you get another straight line, parallel to the first and further out. The value decides which line; the line never changes direction.

3:22So slide it. Push it outward and watch what the region does. At fifteen hundred the line crosses the region over five points of a half-spacing grid. At three thousand, nine points. At four thousand five hundred, thirteen. Then it starts running out of region. At six thousand, three points. At six thousand two hundred and fifty, exactly one. One point. The line is leaving, and the last thing it touches is ten tables and fifty chairs, which is a corner. Push it to six thousand five hundred and it touches nothing at all.

4:03That is the whole idea. A line leaving a region touches it last at a corner, because to leave through the middle it would have to leave through an edge first, and an edge ends at corners. Unless. Unless the line happens to finish parallel to one of the edges, in which case the last thing it touches is the whole edge at once. Hold on to that, because it comes back.

4:31So here is the first of the two results, and the thing to watch is its shape. If the objective has an optimal value on the region, then that value is attained at a corner. If. It is a conditional. It promises a place and says absolutely nothing about whether there is anything to place. Read it as a guarantee that your problem has an answer and you have read the wrong half. It tells you where to look. It does not tell you that looking will find anything.

5:05And I can measure that it is true here rather than just repeating it. I took four hundred and forty one different objectives, every pair of whole-number coefficients from minus ten to ten, and for each one compared the best value anywhere on the region against the best value at a corner. Four hundred and forty one out of four hundred and forty one for the largest. The same for the smallest.

5:35And the optimum never sits strictly inside. Of those four hundred and forty one, exactly one has an interior point among its winners, and it is the objective that is nought everywhere, where every point wins by default. The second result sits directly underneath the first and looks like its twin. It is not. If the region is bounded, then the objective has both a largest and a smallest value on it, and each is attained at a corner.

6:10Put them side by side. The first one answers where. The second answers whether. And look at what the second one had to buy that with. One word. Bounded. On a bounded region the existence is free; every one of my four hundred and forty one objectives has both a largest and a smallest value, and every one of them is at a corner. The word is doing real work, and the next thing shows you exactly how much.

6:43Take an unbounded region. This one has three corners: three and two, four and one, six and nought. Maximise the objective that subtracts the first count and adds twice the second. At the three corners it comes to one, minus two, and minus six. So the largest value at a corner is one. And one is not the answer, because there is no answer. Three and ten is in the region and returns seventeen. Three and a hundred returns a hundred and ninety seven. Three and a million returns nearly two million. Name any value you like and the region beats it.

7:27There is no largest value. Not a large one, not a hidden one. None. The set of values simply has no top. So the second result fails, exactly as advertised, because its hypothesis fails. And here is the elegant part. The first result does not fail. It said: if there is an optimal value, it is at a corner. There is no optimal value, so the condition is not met, and the result is not contradicted. It is simply silent.

8:03That is what a conditional buys you. When the region runs off the page, the guarantee of existence is withdrawn and the promise about location survives untouched — and it survives because it was conditional from the start. Which raises the obvious question. On an unbounded region, when an optimum does exist, is it still at a corner? It is, and here is one. The same shape of region, open at the top right, with corners at nought and three and at six and nought. This time we are asked for a smallest value.

8:45Sweep sixty by sixty of that region and the smallest value found is six. The smallest value at a corner is six. And it is genuinely unbounded — sixty and sixty is in it, and so is a million and a million. So unbounded does not mean broken. It means one guarantee is missing and you have to establish existence some other way. What it never means is that the corners stop mattering.

9:17One sentence you should not skip past, and it usually sits just before the first result. The proofs are outside the scope. Both of them. That is not a gap. It is honesty, and it is unusual enough to be worth pointing at. Nothing in this material is proved — the word prove does not appear at all. Which tells you exactly where my sliding line stands. It is not a proof either. It is a reason to believe, and a picture you can reconstruct when you have forgotten the words.

9:53Both of these results are true and both have real proofs. You are simply not being shown them, and you should know that you are not being shown them rather than assuming you missed something. So the method, finally, and it is four lines long. Find the corners. Evaluate the objective at each. Read off the best. Stop. The furniture problem. Corners at the origin, at twenty and nought, at ten and fifty, and at nought and sixty.

10:26Nought. Five thousand. Six thousand two hundred and fifty. Four thousand five hundred. Six thousand two hundred and fifty, at ten and fifty. Ten tables and fifty chairs. That is the answer, and it took four substitutions. One small thing that wastes people's time. The order the corners are listed in carries no meaning whatever. You will see the same four listed in one order in a sentence and in a different order in the table beneath it. Both are right. Sort them however you like — the winner and the value come out the same.

11:08Now the case the sliding line warned you about. A different region, with four corners: nought and ten, nought and twenty, five and five, fifteen and fifteen. The objective takes ninety, a hundred and eighty, sixty, and a hundred and eighty. The smallest is sixty, at one corner. The largest is a hundred and eighty, at two. Which is what a line finishing parallel to an edge looks like in a table.

11:38And now the part that is asserted and never explained: every single point between those two corners is also optimal. Here is why, and it is one line. The objective is a linear expression, so as you walk steadily along a straight segment its value moves steadily from the value at one end to the value at the other. If the two ends agree, it has nowhere to move to.

12:07I checked that as an identity rather than as a fact about this pair: three thousand six hundred and forty five combinations of objective, endpoints and position along the segment, and it holds at every one. So walk the segment between the two winners in twelfths. Thirteen points, all thirteen in the region, all thirteen returning exactly a hundred and eighty. If a question asks for the optimal solution and there is a tie, the question is badly worded. The honest answer names the whole segment.

12:47Ties get presented as curiosities. They are not. You can see one coming from the algebra, before you draw anything at all, and this rule is mine rather than the standard one. A tie happens when the objective is a positive multiple of one of the constraint expressions. Because then the objective is constant along that constraint's own boundary line, which is an edge of the region — and a line of constant value that is parallel to an edge leaves along the whole edge.

13:23And the tied value is that multiple times the constraint's own limit. The region we just did. The objective was three x plus nine y. The first condition was x plus three y at most sixty. Three times that expression is the objective exactly. Three sixties is a hundred and eighty, which is the tied value. Three more. One problem has the objective x plus two y and a condition x plus two y at least six. One multiple, limit six, tied value six. Another has five x plus ten y against x plus two y at most a hundred and twenty. Five times, limit one hundred and twenty, tied value six hundred. And another has x plus two y against x plus two y at least a hundred. Tied value a hundred.

14:19Four cases, four matches. There is a sense to attach. An at-most condition holds the region back, so an objective pointing the same way ties at the largest value. An at-least condition pushes the region out, so the same proportionality ties at the smallest. And this is a rule, not four coincidences. I ran all four hundred and forty non-trivial objectives against the furniture region. For the largest value the rule predicts thirty two ties, there are thirty two, and the prediction and the reality agree at every single one of the four hundred and forty. For the smallest, the same three numbers.

15:06The furniture problem's own objective is not a multiple of either limit expression, and it has one winner, not two. Which is why that one had a clean single answer. Four things these results do not say. They do not say your problem has an answer. Only the second one does, and only when the region is bounded. They do not say the optimum is at exactly one corner. It can be at two, and then it is at every point between them.

15:40They do not say the largest and the smallest are at different corners. Nothing forbids the same corner, and nothing forbids either from being shared. And they do not require the region to be a closed shape with finitely many sides. You will see the phrase convex polygon in brackets beside the first result, and four lines later that same result gets applied to an unbounded region, which is not a polygon. Both readings cannot stand.

16:14The later use is the one that matters, because a whole worked example depends on it. Read the bracket as a remark about the commonest picture, not as something the result requires. The unbounded region here has three corners and contains points as far out as you please — corners without being a polygon. What to keep. Find every corner, axes included. Evaluate. If the region is bounded you are finished. If it is not, you have found a candidate and you still owe yourself an argument that an optimum exists at all. And if the objective is a multiple of a constraint, expect a tie and name the segment.