The feasible region

One inequality, 1.1 S + 1.5 D <= 131, describes a line and everything on one side of it. That is a half-plane: the boundary is the plans that use the milling capacity exactly, and the interior is the plans that use less. The inequality is not a line, it is a line and a side, and the side is the half that matters.

Three inequalities plus the two non-negativity conditions give five half-planes, and the plans that satisfy all of them at once are the overlap. That overlap is the feasible region. It is flat-sided by construction, because every wall came from a linear inequality, and its sharp points, where two or more walls meet, are its corners.

• Half-plane. One linear inequality: a boundary line and the side of it that satisfies the inequality.
• Feasible region. The intersection of all the half-planes. Every plan in it is legal, and almost all of them are poor.
• Corner, or vertex. A point where enough walls meet to pin it down. In two variables that means two walls.
• Extreme point. The same idea said precisely: a feasible point that is not the midpoint of any two other feasible points.
• Binding constraint. A wall the chosen plan is touching. Its inequality holds with equality there.
• Slack. How far a plan is from a wall, in that wall's own unit. Blending finishes with 0.2414 hours unused.
• Objective contour. The set of plans earning the same margin. A straight line here, and every contour is parallel to every other.
• A tie. When a contour lies flat along an edge, every point on that edge is optimal and a corner is still among them. The solver ships one on purpose: max x + y subject to x + y <= 10, optimum 10.

Put the objective on the picture as a family of parallel lines. Every plan earning 3,000 lies on one line; every plan earning 3,500 lies on another, parallel to it and further out. Maximising the margin means pushing that line as far out as it will go while still touching the region.

Now the argument, in one breath. Stand anywhere inside the region and start walking in the direction that increases margin. Nothing stops you improving until you hit a wall. Once you are on a wall, walk along it in whichever direction still improves, and again nothing stops you until you hit another wall. Where two walls meet you can no longer move in any improving direction at all, and that is a corner. So the search never needs to look at the interior.

Said precisely, the claim is that at least one corner is optimal, which is slightly weaker than "the optimum is a corner" and is the version that is always true. If a contour happens to lie flat along an edge, then every plan on that edge earns the same and all of them are optimal, corners included. The solver in this page ships exactly that case in its own tests: maximise x + y subject to x + y at most 10, where the optimum is 10 and an entire edge achieves it. Ravensworth is not such a case, and it was checked: exactly one integer plan reaches 4,656.00.

Before the corner result, the search space is every point in a continuous region, which is not a list and cannot be enumerated. After it, the search space is the corners, which is a finite list. That single step is what makes linear programming a solvable thing rather than an aspiration, and every method in the rest of the practitioner track depends on it.

It also tells you what a solver is allowed to skip. Nothing in the interior ever has to be evaluated, no matter how promising it looks, because any interior point can be improved by walking. That is a strong claim and it is easy to test rather than believe: the box below throws thousands of random legal plans at the mill and reports the best of them against the corner.

A corner in two variables is where two walls meet, and "meet" means both inequalities hold as equalities at once. So finding a corner is solving two linear equations in two unknowns, which is arithmetic anyone can do. The two walls can be two constraints, or one constraint and an axis, or the two axes at the origin.

Not every pair gives a corner of the region. Two walls may cross at a point that breaks a third constraint, in which case the crossing is real but it is outside the region and not a candidate. That is the check the box above performs: solve each pair, then test the crossing point against every constraint and discard it if it fails one. The test uses the same feasibility function the rest of the course uses.

This is also where the geometric view starts to cost something. With three variables a corner needs three walls meeting, so the pairs become triples. With ten variables it is ten walls at a time, and the number of combinations to test grows far faster than the number of variables does. Enumerating corners is correct and it is not a method anyone can use at scale, which is precisely the gap the simplex method fills.

Look at the corner in the second diagram and notice that the blending line passes above it without touching. That gap is 0.2414 hours of blending capacity that the best plan never uses. Now ask what would happen if the blending ceiling were raised: the wall moves further away from a corner it was not touching, the corner does not move, the plan does not change, and the margin does not change.

That is the entire argument for a shadow price of zero, and it was made with no arithmetic at all. The same picture makes the opposite case just as plainly: the milling wall is touching, so moving it outward moves the corner, which moves the plan and changes the margin. Session 4 puts a figure on how much, and finds that the figure has a much shorter shelf life than anyone quoting it expects.

A plan on its own is unarguable and unexplainable. Add the geometry and it becomes a sentence somebody can push back on: this plan is where the milling wall meets the protein wall, and it is there because every direction that would earn more runs into one of those two. Somebody who disagrees now has something to disagree with. They can challenge a ceiling, or a rate, or the objective, and each challenge points at a specific number.

This matters more than it sounds, because an optimum that cannot be explained tends not to be run. The binding set is the shortest honest explanation of any linear plan, it is two or three items long even on large models, and it comes free with the answer in r.binding.

Whether to teach the geometry first, or at all, is a live argument among people who teach this for a living, and it is not about taste.

One camp says the picture is the subject and everything else is bookkeeping. Without it, the simplex method is a ritual of row operations that students execute and do not understand, and binding, slack and the dual are memorised words rather than things you can see. On this view the drawing is what makes the algebra meaningful, and a practitioner who cannot sketch a two-variable region cannot debug a two-hundred-variable model either.

The other camp says the picture builds an intuition that then has to be unlearned. Real problems have thousands of variables, the number of corners grows far faster than anyone's mental image can accommodate, and there are perfectly good methods that never visit a corner at all: interior point methods cut straight through the middle of the region and converge on the optimum from inside. A student who has been taught that optimisation means walking corners will find that whole family of methods surprising, and will carry a picture that quietly misleads about what is expensive in a large model.

Both camps are describing something true. The corner result is correct in any number of dimensions and the picture is the fastest way to believe it. The picture is also the reason people are surprised that a method could work from the inside. There is no resolution on offer here, only the recommendation to notice which one you are relying on when you next explain a model to somebody.