Testing every corner, and the extra check an unbounded region forces

0:00Here is the whole procedure for solving one of these problems on a graph. It is short, it is finite, and it is the reason the corner results were worth proving. Find the region and find its corners. Evaluate the objective at every corner. Read off the largest and the smallest of the values you get. If the region is bounded, those two are the answer and you stop. Three steps, and a branch hanging off the third for when the region is not bounded. That branch is the whole of the hard part and we will spend half this video on it.

0:40You will also meet this written as four steps rather than three, and the fourth is worth a word. The step that announces the unbounded case ends at a colon and carries nothing underneath it. Its content turns up as a separate step below. And later, when the rule is called on by number, the number given is the empty one. So the cross reference points at a step with nothing in it. That is not a deep problem, but someone chasing that reference and finding an empty line concludes they have misread something. They have not. Three steps with a branch is the honest shape, and that is what is on screen from here on.

1:27Step one. Find the region, then find its corners. Two routes are offered for the corners, and they are presented as equals. Read the corner straight off the drawing. Or solve together the equations of the two lines that meet there. They are not equals. Reading off the drawing works when the crossing lands on the ruling, and only then. Here is a corner from the exercise set. The two lines are three x plus five y equals fifteen, and five x plus two y equals ten. Solve them together and the crossing is at twenty nineteenths and forty five nineteenths.

2:09Nineteenths. That lands on no ruling any drawing carries. Not halves, not fifths, not tenths, not hundredths. I checked all four. And it is the corner that wins. The objective there is two hundred and thirty five nineteenths, which is larger than at any other corner of that region. So reading off the picture does not cost you accuracy there. It costs you the answer. On the two worked drills the crossings do land on whole numbers, every one of them, which is exactly why reading them off looks safe. Solve when the crossing is not on the ruling, and you will never be caught out.

2:55Step two. Put every corner into the objective and write down what you get. Then give the two extremes names. The largest of those values, and the smallest. That is all step two is. It is arithmetic, one substitution per corner, and for a region with four corners it is four substitutions. The only thing worth saying is that you must do every corner. Not the ones that look promising. The corner that wins is very often not the one you expect, and the next case is exactly that.

3:34Step three, first half. If the region is bounded, those two numbers are the answer. The largest value you found is the largest value there is, the smallest is the smallest, and you are finished. That is not obvious and it is not free. It is bought by the second corner result, the one whose hypothesis is the word bounded. Existence of both extremes, and both attained at corners. Bounded means some circle can be drawn round the region. Practically it means the region does not run off the page in any direction, and you can check it from the drawing in a second.

4:18When it is bounded, the procedure really is finite and really does finish. That is worth pausing on, because the search it replaces was over infinitely many points. A bounded maximum, worked start to finish. Maximise four x plus y, subject to x plus y at most fifty, three x plus y at most ninety, and both counts at least nought. Step one. The corners are the origin, nought and fifty, twenty and thirty, and thirty and nought. Four of them, and the two axes supply two.

4:59Step two. The objective takes nought, fifty, a hundred and ten, and a hundred and twenty. Step three. The region is bounded, so the largest is a hundred and twenty, at thirty and nought. Done. Now look at where the winner is. It is on the horizontal axis. The corner where the two real constraints cross, twenty and thirty, gives a hundred and ten, ten short. That corner is the one everybody expects to win, because it is the one that feels like a compromise between the two limits. It comes second. Which is the whole argument for evaluating every corner rather than the interesting one.

5:45A bounded minimum next, and nothing about the method changes. Minimise two hundred x plus five hundred y, subject to x plus two y at least ten, three x plus four y at most twenty four, and both counts at least nought. Three corners this time. Nought and five, nought and six, and four and three. The values are two thousand five hundred, three thousand, and two thousand three hundred, so the smallest is two thousand three hundred at four and three. Bounded, so that is the answer.

6:23I have drawn that region larger than it really is, and I want to say so. The real region is a sliver. It covers an area of two. The previous region covers nine hundred and fifty, which is four hundred and seventy five times as much. This one holds five whole number points; the previous one holds a thousand and six. At that scale you cannot see that it has three distinct corners at all. It is a wedge against the vertical axis between the heights five and six, four wide and three tall, and the two heights it sits between are exactly the two numerals the vertical scale usually leaves out.

7:08So it is redrawn here, opened up, with those numerals restored. The mathematics is untouched. If a figure is too small to read, the honest thing is to redraw it and say you did. Now the branch. What happens when the region is not bounded. Minimise minus fifty x plus twenty y, subject to two x minus y at least minus five, three x plus y at least three, two x minus three y at most twelve, and both counts at least nought.

7:45A negative coefficient in the objective is not a mistake and not a special case. What it changes is which corner wins, and nothing else. The corners are nought and three, nought and five, one and nought, and six and nought. The objective takes sixty, a hundred, minus fifty, and minus three hundred. So the smallest value found is minus three hundred, at six and nought. On a bounded region we would be finished.

8:17This region is not bounded. And on an unbounded region, minus three hundred is a candidate. It is the smallest value at any corner, which is a different sentence from the smallest value anywhere. Unbounded is a statement about directions, not about the drawing. Within a reach of twelve there are seventy whole directions you can walk in from inside this region and never leave. Take three across and two up from the winning corner: you are still inside after one step, still inside after ten, still inside after a million.

8:58So one more step is needed, and here it is. Ask whether any point of the region does strictly better than the candidate. Not as well. Strictly better. For a smallest value that means graphing the objective strictly less than the candidate. Minus fifty x plus twenty y strictly below minus three hundred. Divide through by ten if you like: minus five x plus two y below minus thirty. That is an open half plane. Open, because the inequality is strict, so the points on its own boundary line do not belong to it.

9:39Which is why that line is drawn dashed, and why every constraint boundary you will ever see is drawn solid. A constraint permits equality, so it keeps its own boundary. This test does not, so it does not keep its line. That distinction is carried entirely by the ink, and it is almost never said out loud. If you are reading the words and not looking at the picture, it is invisible.

10:08And the direction matters. Strictly greater when you are testing a largest value, strictly smaller when you are testing a smallest one. Get that backwards and you will reverse the conclusion. Drop the test line in, shade the open side, and look at whether anything of the region is in there. It is. Take the point ten across and eight thirds up. It satisfies every one of the five conditions, and the objective there is minus one thousand three hundred and forty thirds, which is about minus four hundred and forty seven.

10:49That is a hundred and forty seven below the candidate, and it is an ordinary point of the region. And it is not one lucky point. Of the seven thousand five hundred and ninety two half grid points of this region out to sixty, six thousand two hundred and fifty two beat the candidate. Most of the region beats it. So the conclusion is not that minus three hundred was slightly wrong. The conclusion is that there is no smallest value at all.

11:23Here is why, in one line. Every single direction this region runs off along drives the objective down. Of those seventy directions the gentlest costs minus ten per step and the steepest minus four hundred and forty, and not one of them is positive. Walk three across and two up from the winning corner and the value goes to minus four hundred and ten. Ten steps and it is minus one thousand four hundred. A million steps and it is minus a hundred and ten million three hundred. You can make it as small as you please, so no smallest exists.

12:07There is a trap in that picture and it catches a lot of people. The test line passes through the corner you are testing. It has to. It is the line where the objective equals the candidate exactly, and the candidate is the value at that corner. So the line always touches the region. Always. Seeing them touch tells you nothing at all. The corner sits on the line, and the half plane is open, so the corner is not in it. Twenty five half grid points of this region sit exactly on the test line, and every one of them is excluded from the test.

12:48The question is only ever about the open side. Six thousand two hundred and fifty two points sit strictly beyond the line, and that is the number that decides the case. It is worth saying the two halves apart. The corner satisfies all five conditions with two of them tight, which is what makes it a corner. And it fails the strict test, which is what makes the line dashed.

13:18Now the same test run the other way, because the demonstration you just saw was the test failing, and a student who only ever sees it fail has not seen how it works. Same region, same objective, but ask for the largest value instead. The largest at any corner is a hundred, at nought and five, and no other corner reaches it. The test is now: is there a point of the region where the objective is strictly above a hundred. Divide by ten again and that asks for y above five plus two and a half x.

13:58But look at the first condition. Two x minus y at least minus five says y is at most five plus two x. So we need y above five plus two and a half x and at the same time no more than five plus two x. Two and a half x has to be less than two x, and that needs x below nought. Which is not allowed. The two demands cannot hold together anywhere in the region. I checked every whole x out to a thousand and every half x out to a hundred, and there is not one.

14:35So the open half plane meets the region nowhere, and this time the candidate stands. A hundred is the maximum, attained at nought and five. The sweep agrees with the algebra. Out to a hundred and twenty on half steps, not a single point of the region has the objective above a hundred. And it agrees with the directions too: not one of the seventy directions the region runs off along increases the objective. All seventy decrease it.

15:10That is the same fact read three ways. And it is the direction that usually gets left as an exercise with a bare why after it and no answer given anywhere. The answer is a hundred. Step back. An answer to a problem of this kind can take exactly five shapes, and it is worth knowing all five before you start, because you will meet all five. One. Bounded region, one winning corner. One point, one value, and this is most problems.

15:46Two. Bounded region, two winning corners, and then the whole segment between them. A tie, and the honest answer names the segment. Three. Unbounded region, and the extreme value you found is not attained. There is no answer, and the test is how you find that out. Four. Unbounded region, and the extreme value you found is attained. There is an answer, and the test is how you earn the right to say so.

16:17Five. No region at all. The conditions contradict each other, nothing satisfies them, and the method never starts. Three and four are the same picture until you run the test. That is the entire reason the test exists. The practice set for all of this is one exercise of ten items, so here is every one of them sorted by the shape its answer takes. Two of the ten ask for a largest and a smallest, so ten items ask twelve questions.

16:53Six of those twelve land in the first shape. Bounded, one winning corner. Sixteen at nought and four. Minus twelve at four and nought, the only one with a negative coefficient in its objective. Two hundred and thirty five nineteenths, the awkward one. Eighteen at four and three. Three hundred at sixty and nought. And four hundred at nought and two hundred. Two land in the second shape, a tie along a segment. Six hundred at two corners in one, a hundred at two corners in another.

17:30One lands in the third shape: the item with no maximum at all. Its best corner value is one, and three and ten is a point of the region returning seventeen. One lands in the fourth: unbounded, smallest seven at three halves and a half, and attained, because every direction that region runs off along increases the objective. One lands in the fifth: no region at all. One condition asks the second count to be at least one more than the first, the other asks it to be no more than the first, and both at once would need one to be no more than nought.

18:14And one item lands in two shapes at once. Its region is unbounded, its smallest value is attained, and it is attained at two corners and therefore along the whole segment between them. The fourth shape and the second at the same time. The five shapes are a checklist, not a set of boxes that exclude each other. Three of the ten regions are unbounded, and two of those three have perfectly good answers. Unbounded means test. It does not mean give up.

18:50What to keep from all of this. Find the region. Find every corner, and solve for the ones that do not land on the ruling. Evaluate at all of them. Name the largest and the smallest. If the region is bounded, stop. You are done, and the result that lets you stop is the one whose hypothesis is the word bounded. If the region is not bounded, what you have is a candidate. Draw the open half plane strictly beyond it, in the improving direction, and look at whether any of the region is in there.

19:28If something is, there is no extreme value in that direction at all. Not a corrected number. No number. If nothing is, the candidate stands and you can say so. And do not be fooled by the line touching the region, because it always does. It runs through the very corner you are testing. The test is about the open side and nothing else.