Every corner of a feasible region is named by a set of columns called a basis. Two corners are joined by an edge exactly when their bases differ in one column, and one step of the simplex method is one such exchange. So the method never enters the interior and never tries every corner: it walks a path along the boundary, uphill, and stops at the first corner with no improving edge leaving it.
Core ideas
“Standard Form, Slack and Surplus” wrote the programme as equations and “Basic Solutions and Corners” paired a choice of columns with a point. One idea is new here, and it is what makes a step mean something.
Choose m of the columns of the m-row system and set every other variable to zero; solving the m remaining equations gives one point. The chosen columns are the basis, their variables are basic, and when all of them come out at or above zero the point is a corner of the feasible region. The region of maximise 3x₁ + 5x₂ under x₁ ≤ 4, 2x₂ ≤ 12, 3x₁ + 2x₂ ≤ 18 has five corners, and five bases to match.
A basis is a set, so the distance between two of them is the size of their difference. {s₁, s₂, s₃} and {s₁, x₂, s₃} differ in one member: x₂ in, s₂ out. That is one edge of the region and one pivot of the method. {s₁, s₂, s₃} and {x₁, s₂, x₂} differ in two, and no single pivot goes there however short the line looks on the picture.
On the five-corner region above, the method starting from the origin reaches the optimum after two pivots, standing at three corners and never looking at the other two. Corner-counting and work are different quantities, which is why a region with a thousand corners is not a thousand times the work of one with ten.
The material
Which point a basis names, when two of them are one edge apart, and what licences the method to stop walking.
For a standard-form system with m equations and n ≥ m columns, a basis is a choice of m columns whose matrix is invertible. Setting the other n - m variables to zero and solving for the basic ones gives the basic solution belonging to that basis. If every basic variable comes out at or above zero it is a basic feasible solution, and it is a corner of the feasible region.
Nothing in that definition mentions the objective. A basis is a choice of columns, the point follows from the choice, and the objective only decides which of these points you want. Two different bases can even name the same point — which is degeneracy, and “Degeneracy, Cycling and Bland’s Rule” is where it matters.
Take maximise 3x₁ + 5x₂ subject to x₁ ≤ 4 (plant A hours), 2x₂ ≤ 12 (plant B hours) and 3x₁ + 2x₂ ≤ 18 (plant C hours), with one slack per row. Every column is one of x₁, x₂, s₁, s₂, s₃, three of them are basic, and the region has five corners.
(0, 0) stands on {s₁, s₂, s₃} at z = 0; (0, 6) on {s₁, x₂, s₃} at 30; (2, 6) on {s₁, x₂, x₁} at 36; (4, 0) on {x₁, s₂, s₃} at 12; (4, 3) on {x₁, s₂, x₂} at 27. The basis at the origin is the three slacks, which is what makes the origin the free starting corner of a programme with only ≤ rows.
Two bases are adjacent when they differ in exactly one column. The corners they name are then the two ends of one edge of the feasible region, and one pivot of the simplex method moves between them: one column enters the basis and one leaves.
Read the two verdicts off the sets rather than off the drawing. From {s₁, s₂, s₃} at the origin, {s₁, x₂, s₃} is one exchange away and so is {x₁, s₂, s₃} — the two edges of the region that leave the origin. {x₁, s₂, x₂} at (4, 3) needs s₁ and s₃ out and x₁ and x₂ in: two changes at once, so no pivot goes there. The lab refuses that move and prints the two columns that would have had to change together.
From the origin the method takes the edge to (0, 6), raising z from 0 to 30, then the edge to (2, 6), raising it to 36. At (2, 6) every edge leaving the corner lowers z, so it stops. Two pivots, three corners visited, two corners never examined.
A linear objective on a convex feasible region has no local maximum that is not a global maximum. Convexity, and Why a Local Optimum Is Global proves this, and it is the whole licence for stopping: the method checks the edges at one corner and concludes something about every point of the region.
That licence is what separates this from hill climbing. A method that walks uphill on an arbitrary surface can only report a local summit; here the surface is a plane and the region has no dents in it, so a corner that beats its neighbours beats everything. Without that theorem the method would be a heuristic.
It also explains why the number of corners is not the amount of work. A programme with n columns and m rows has at most n choose m bases, which grows ferociously, and the region above has ten possible choices of three columns from five, of which five are corners. The method visited three. Termination and the Klee–Minty Cube is where the honest count lives, and the news there is mixed.
One warning about reading a basis off a picture: the basis is not “the variables that are not zero”. At a corner where three boundary lines meet, one basic variable is zero as well, and two different bases name that single point. That is the subject of “Degeneracy, Cycling and Bland’s Rule” and it is worth knowing now, because it is the one case where corner and basis stop being the same thing.
Interactive
Two bases are adjacent when they differ in exactly one column; anything else is not an edge
Method
Bases first, objective last. A move that is not an exchange of one column is not a step, whatever it does to the objective.
Write the programme in standard form and name every column, slacks included. On a three-row problem a basis is three of those names, and you cannot say which corners exist until you know what there is to choose from.
Set the nonbasic variables to zero and solve for the rest. Check the signs: a negative basic variable means the choice of columns was not a corner of the feasible region at all, only a solution of the equations.
Compare the sets. One member different is an edge and a candidate for the next pivot; two or more is not reachable in one step, and that is true no matter how close the two corners look.
Move along an edge that raises the objective, then repeat from the new corner. When every edge leaving the corner lowers it, stop and say why: a linear objective on a convex region has no local optimum that is not global.
Five corners, five bases, and a path that visits three of them. The objective is 3x₁ + 5x₂ and the three rows are the plant hours.
The refusal is the part worth dwelling on. (0, 0) and (4, 3) are not far apart on the drawing, and a reader who thinks of the method as “try corners, keep the best” sees no reason not to go there. But {s₁, s₂, s₃} and {x₁, s₂, x₂} differ in two columns, and one pivot exchanges one column. There is no edge between those two corners, and the method walks the boundary rather than crossing the middle.
For a faded rehearsal, change the objective to 2x₁ + 3x₂ in the lab and predict the walk before running it. The supplied first move is that the corner list and the five bases do not change — they are a property of the constraints. Say which corner is optimal now, how many pivots reach it from the origin, and which corners are skipped, then check all three against the panel.
Then push the objective coefficient on x₁ up to 9. The walk goes the other way round the region, the corner list is still the same five points, and the number of pivots changes. That separation — the region fixes the corners, the objective fixes the path — is what the rest of this course is built on.
You should be able to write a small programme in standard form, list the basis at each corner, decide adjacency by comparing sets of columns, and state the theorem that lets a check at one corner settle the whole region.
Something to change about this lesson? Write it down, tick it off when it is handled, and export the list when you want to act on it. Kept in this browser only: nothing is sent anywhere, and nobody is notified.
No recommendations yet for this lesson.