The feasible region as the overlap of the half planes the constraints allow

0:00Here is an empty plane and one straight line across it. That line has just done something to every point there is. Take any point at all. It is on one side of the line, or it is on the other side, or it is on the line itself. Three possibilities, and exactly one of them is true. You can watch that happen arithmetically. Write the line as an expression set equal to a number, and for any point work out the expression and subtract the number. You get something positive, or something negative, or nought.

0:39I took every line with small whole coefficients, three hundred and thirty six of them, and every point of a small grid, eighty one of those, and asked the question twenty seven thousand two hundred and sixteen times. Every single point landed in exactly one of the three. Twelve thousand eight hundred and eighty on one side, the same number on the other, and one thousand four hundred and fifty six on the line.

1:08The two sides coming out exactly equal is not a coincidence. Negate the whole expression and you have written the same line again, with the two sides swapped. Now an inequality. At most, rather than equal to. That keeps one of the two sides and throws the other away, and it keeps the line as well, because at most a number includes that number. That is a half plane, and it is the only object in this whole business.

1:42Which side, though? You have drawn the line. Which of the two halves does the inequality actually allow? Nobody ever tells you. The method is assumed, never stated, and the words test point do not appear anywhere near this material. Here it is. Pick one convenient point that is not on the line. Substitute it. If it satisfies the inequality, then its whole side is allowed. If it does not, the other side is.

2:13That is a rule, and a rule can be wrong, so I checked it rather than assuming it. The same three hundred and thirty six lines, the same eighty one points, and the test point answer compared against plain substitution at every one of the twenty seven thousand two hundred and sixteen pairs. Twenty five thousand two hundred and seventy two agreements. Nought disagreements. And one thousand nine hundred and forty four cases where the rule declined to answer, which are the twenty four lines my test point happened to be sitting on.

2:52That is the one way it fails, and it is worth knowing, because the most convenient point of all is the origin. The origin is disqualified exactly when the line runs through it. On my grid that is forty eight lines out of three hundred and thirty six, and on the other two hundred and eighty eight the origin settles every point of the grid correctly. Twenty three thousand three hundred and twenty eight tests, nought wrong.

3:22So use the origin, and look first at whether the line goes through it. Now four inequalities at once, from a problem already set up: a dealer buying tables and chairs, with a money limit, a shelf limit, and two conditions saying neither count can go negative. x counts tables, y counts chairs. Five x plus y at most a hundred, in lots of five hundred rupees. x plus y at most sixty pieces. x at or above nothing, y at or above nothing.

4:00Four inequalities, so four half planes, and the region we want is what they all agree on. Lay them on one at a time and watch. I am counting whole purchases inside a box wide enough that nothing here is an artefact of its edges, nine thousand eight hundred and one points. x at or above nothing: eight thousand five hundred and ninety one survive. Then y at or above nothing: seven thousand eight hundred and eighty one. Then the money: one thousand and seventy one. Then the shelf: eight hundred and fifty one.

4:42Every step is a cut. No step can ever put a point back, because each new condition is asked of the survivors and of nobody else. That is what makes this an overlap and not an assembly. Eight hundred and fifty one is also exactly the number of purchases the formulation allowed, worked out with no drawing at all. The picture and the algebra are the same object. Here is the commonest drawing mistake there is, and it is invisible once the ink is dry.

5:19You shade the money condition. You shade the shelf condition. You shade the two floors. Then you look at what you have shaded. What you have shaded is not the region. It is everything that any one of them allows, and on this problem that is the entire page. Not one point of the counting box fails all four conditions. Not one. So reading what you shaded claims all nine thousand eight hundred and one against the eight hundred and fifty one that are really allowed.

5:54And that is not an accident of where I drew my box. The only place both floors fail together is the corner where both counts are negative, a hundred points of my box, and every single one of them satisfies the money condition anyway. Five times a negative number plus a negative number cannot reach a hundred. So shade lightly, and shade what survives, not what each one allows. The region is the intersection. It is the part that is under every layer at once.

6:31The picture now has names, and there are more of them than you would expect for one shape. The shape itself is the feasible region, and it has a second name as well, the solution region. Both are used and they mean the same set. Everything else on the page is the infeasible region. Not unimportant, not a mistake, just the part no purchase is allowed to come from. A point of the region is a feasible solution. A point outside it is an infeasible solution. And a point of the region at which whatever you are trying to make large or small actually reaches the value you want is an optimal solution.

7:18Notice what that last name needs. It needs something to optimise. The region on its own does not have optimal points, because on its own it has not been asked a question yet. Take a point and hand it to the picture, and you get one of three verdicts. Five tables and twenty chairs. Five of them cost forty five money lots against a limit of a hundred, and take twenty five shelf pieces against a limit of sixty. Both limits have room to spare. Nothing is tight. That point is strictly inside.

7:58Ten tables and fifty chairs. A hundred money lots exactly, sixty pieces exactly. Two conditions tight at once. That point is on the boundary, and it is allowed, because at most a hundred includes a hundred. Twenty five tables and forty chairs. A hundred and sixty five money lots, and sixty five pieces. Outside, and outside twice over. Of the eight hundred and fifty one purchases the region allows, seven hundred and fifty one are strictly inside, a hundred are on the boundary, and four of those hundred are corners.

8:40Four corners out of eight hundred and fifty one points. Hold on to that ratio, because the next thing is about how easy it is to forget. When this idea gets introduced, you are usually handed three sample feasible points to look at. Ten and fifty. Nought and sixty. Twenty and nought. All three are feasible. That is what they are offered for, and they do the job. But look at where they are. Ten and fifty is where the money line and the shelf line cross. Nought and sixty is the shelf line meeting the vertical wall. Twenty and nought is the money line meeting the floor.

9:26Two conditions tight at every one of them. All three are corners. Three examples of a feasible solution, and nought examples of an interior one, out of a region holding eight hundred and fifty one points. Nobody ever says feasible means corner. But if the only three you are ever shown are corners, and then the answer turns out to be a corner as well, you will believe it anyway. So lead with the interior one. Five tables and twenty chairs is feasible and is nowhere near a corner, and it is the honest first example.

10:07The infeasible sample has the same problem in reverse. Twenty five and forty breaks the money condition and breaks the shelf condition. Both of them. It is outside for two reasons at once, which makes it a weak witness, because it never shows you what one broken condition on its own looks like. And one broken condition is overwhelmingly the case you will actually meet. Over the same counting box, two thousand one hundred and forty two purchases break exactly one condition.

10:44A thousand and forty break the money alone. Two hundred and twenty break the shelf alone. Eight hundred and eighty two break a floor alone. Against six thousand eight hundred and eight that break two or more. Those first two numbers are worth a second look. A thousand and forty purchases the shelf would happily hold and the money cannot buy. Two hundred and twenty the money would buy and the shelf cannot hold. They are limits of genuinely different kinds, which is why neither one is spare, and it is the same pair of numbers the algebra gave before anything was drawn.

11:26When you test a point and it fails, name which condition it failed. A point that fails one is telling you something a point that fails everything cannot. Now the thing that is never written down anywhere, and that a description of the picture in words cannot recover. It lives entirely in the ink. Every boundary line of this region is drawn solid. Every single one. And there is a reason.

11:57Each of these conditions is written with a sign that permits equality. At most. At or above. So each condition is satisfied by the points on its own line, which means each line belongs to the region it bounds. Eleven of the region's purchases sit exactly on the money line, and all eleven are allowed. Eleven more sit exactly on the shelf line, and all eleven of those are allowed too.

12:28Make one sign strict. Less than a hundred, rather than at most a hundred. The same eleven are thrown straight out. All of them. Ten tables and fifty chairs is the point that settles it. It sits on both lines at once. It satisfies both conditions as written, and it satisfies neither the moment either sign is made strict. A solid line and a dashed line are drawn differently to record exactly that difference, and that is the only place the difference is recorded at all.

13:06Run the whole region with every sign made strict and you can measure what the boundary is worth. Eight hundred and fifty one becomes seven hundred and fifty one. A hundred purchases go, and the hundred that go are precisely the hundred boundary points, with nought disagreements. So a solid line says these points count. A dashed line says they do not. In everything you will meet here, every constraint is non strict, so every constraint line is solid. Somewhere in the working you will see one line drawn dashed, and it is worth knowing in advance what that means, because it will not be explained.

13:52It means that line did not come from a constraint. It came from a strictly greater or a strictly smaller, asked as a test rather than imposed as a limit, and its own points do not satisfy it. Draw that one solid and you have claimed that points on it satisfy a condition they do not satisfy. It is a real error and nothing on the page will catch it.

14:20Two words get used about these regions, bounded and unbounded, and there is a test. Can you draw a circle big enough to hold the whole region? If you can, it is bounded. If no circle is big enough, it is unbounded. For the dealer's region, the point furthest from the origin is nought tables and sixty chairs, at a distance of exactly sixty. So a circle of radius sixty round the origin holds it. Every one of the eight hundred and fifty one points is inside that circle, and the region is bounded.

14:59That is the whole test, and it is worth stopping there, because the sentence usually added after it will mislead you. The sentence usually added says that an unbounded region carries on without limit in any direction, and if you read any as every, it is false. Here is an unbounded region. Three conditions and the two floors. Its corners are nought and five, nought and three, one and nought, and six and nought.

15:32No circle holds it. Name a radius and I can hand you a point of the region further out than that. Ten and ten is in it. A hundred and a hundred is in it. A thousand and a thousand, and a million and a million, both in it. So it is unbounded. And yet it is walled on the left, walled below, and capped above. I stood at a point inside it and walked out along fourteen thousand six hundred and forty different directions. One thousand five hundred and fifty of them carry on for ever. Thirteen thousand and ninety hit a wall.

16:11Every escaping direction points up and to the right, in a narrow wedge between a slope of two thirds and a slope of two. Straight up is stopped. Straight left is stopped. Straight down is stopped. And straight right is stopped as well. Unbounded means no circle holds it. It does not mean the region goes everywhere, and the picture settles that faster than any sentence about it. Sometimes the overlap is empty, and the right response is not to redraw it.

16:47Two conditions. Three x plus five y at most fifteen, which with the two floors gives a small triangle at the origin. And x plus y at or above eight, which is a band a long way off. Two shaded pieces, and nothing in common. And you can prove that before you draw either one. On the triangle the first condition allows, how large can the plain sum of the two counts get? I checked every fifth of that triangle, two hundred and eleven points, and the largest sum is five, reached at one point only, five and nought.

17:28The other condition demands at least eight. Five is less than eight. Nothing can satisfy both, and over the whole grid the overlap holds nought points while the two conditions separately hold two hundred and eleven and two thousand nine hundred and one. It is the gap doing that, not the shapes. Raise the first limit from fifteen to forty and the same two conditions overlap at five hundred and fifty nine points.

17:59An empty region is an answer. It says these demands cannot be met at once. Prove it with arithmetic and say so, rather than assuming your drawing hand slipped. There is a word attached to these regions that gets used and never explained. Convex. Here is what it means. Take any two points of the region and join them with a straight segment. If every point of that segment is also in the region, for every pair you could pick, the region is convex. No dents. No gaps. No pieces that are not joined to each other.

18:41I took ten points from the dealer's region, made all forty five pairs, and walked each joining segment in sixths. Nought pairs left the region. That test has to be able to fail, or it is not a test. So run it on the two pieces from a moment ago, the triangle and the distant band, treated as one set. Twenty one pairs, and twelve of them leave. Convexity is not decoration. It is what guarantees the region has corners at all, and no dents to hide an answer in. Everything that comes next depends on searching a finite list of corners instead of a whole region, and this is the property that makes that legal.

19:29It is usually asserted in about six words and never proved. Now you know what is being asserted. One more piece of small print, because it is the kind of thing that is easy to read past. A corner point gets defined as a point of the region where two boundary lines cross. Read that literally and it is looser than it looks. It admits any crossing of two boundary lines that happens to lie in the region, whether or not that crossing is actually a corner of the shape.

20:05So I enumerated every crossing of every pair of boundary lines in all three figures here. The dealer's region has six pairs of lines and four crossings that land inside it, and all four are its corners. The unbounded one has ten pairs and four in region crossings, and all four are its corners. The triangle has three pairs, three crossings, three corners. So the loose reading never once picks up a point that is not a corner. The definition does not misfire here, even though it could.

20:42I am telling you because it was checked and not because it bites. If you ever meet a system where two boundary lines cross somewhere in the middle of the region, that crossing is not a corner, whatever the words seem to allow. So you have a region. What have you actually got? You have every purchase that is allowed, and there are infinitely many of them, because between any two allowed points there is another one. The eight hundred and fifty one is only the whole numbers.

21:17And every single one of them is equally allowed. The region does not rank them. It has not been asked to. That is the whole point of the next step. The region says what is possible. It takes an objective, and a reason to prefer one point to another, before any of those points becomes the answer. Two things to carry forward. First, sometimes there is no region at all, and you should be able to see it coming: one of the standard practice systems asks for the second count strictly above the first and at or below it in the same breath, and nothing can be both. Nought points survive, while the two conditions separately admit five thousand three hundred and twenty five and two thousand five hundred and fifty six.

22:08Second, and this one is a warning. The one page summary you would revise from at the end covers the definition of the problem and says nothing whatever about the region, the boundary, boundedness, or convexity. Every single thing in this video is outside it. Revise from the working, not from the summary.