Back to the on-screen lesson ·
Vertices, the fundamental theorem, and the simplex method as a walk along improving edges.
Paper packet. Every task here also exists on screen, where it is checked automatically; answers written on paper are not assessed by Nydus. When you are back at a device, enter your answers there.
By the end of this lesson you will be able to find the vertices of a two-variable feasible region and say why a crossing of constraint lines need not be one, state the fundamental theorem of linear programming, and describe the simplex method as a walk from vertex to adjacent vertex along improving edges. You will also be able to explain why stopping when no adjacent vertex is better proves global optimality — and that the bridge is convexity, not anything the method itself does.
From lesson 3: a linear optimum sits at a vertex, and for two variables you can list the vertices and compare. From lesson 9: convexity is what turns a local check into a global claim. This lesson is what to do when there are too many vertices to list — which is every real linear program.
The fundamental theorem of linear programming. If a linear program has an optimal solution, then some vertex of its feasible region is optimal.
So only vertices need examining. The difficulty is how many there are: a vertex in $n$ variables is picked out by choosing which $n$ constraints are tight, and with $m$ constraints the number of such choices grows combinatorially. A problem with 50 variables and 100 constraints has more candidate vertices than there are atoms in anything.
The simplex idea. Do not list them. Stand at one vertex; look along the edges leaving it; if one improves the objective, walk along it to the next vertex; repeat. Stop when no edge improves.
Three things make that work:
What it promises. An exact optimal vertex, in finitely many steps. In the worst case the number of steps can be exponential — there are constructed problems where simplex visits every vertex — but on problems that arise in practice it is typically a small multiple of the number of constraints. That gap between the worst case and the usual case is unusual in this subject and is worth noticing rather than glossing.
Another way: picture
A polygon with a marker at one corner. Each edge leaving the corner is an arrow; the ones that go uphill in the objective are drawn solid. Follow a solid arrow to the next corner and repeat. When every arrow from a corner is dashed, you have arrived — and no corner anywhere is better.
Another way: steps
The simplex method, as a walk:
$\max\ 5x + 4y$ over $6x + 4y \le 24$, $x + 2y \le 6$, $x, y \ge 0$.
Start at $(0,0)$. Feasible, objective $0$. Two edges leave it: along $x$, the objective rises at rate $5$; along $y$, at rate $4$. Both improve; take the steeper.
Walk along $x$. Feasibility runs out when $6x = 24$, at $x = 4$. New vertex $(4, 0)$, objective $20$.
At $(4,0)$. The edge back to the origin worsens. The other edge, along the machine constraint towards $(3, 1.5)$, changes the objective at rate... $5(-1) + 4(1.5) = 1$ per unit of the walk: an improvement. Take it.
At $(3, 1.5)$. Objective $21$. Both edges leaving it worsen. Stop.
Three vertices examined out of four, and the fourth — $(0,3)$, objective $12$ — was never visited and never needed to be. On a problem with a million vertices that saving is the whole method.
Reading a crossing as a vertex. Two lines always cross. The crossing is a vertex only if it satisfies the other constraints too.
Forgetting the first phase. When the origin is infeasible, finding a starting vertex is a problem in its own right, solved by optimising an artificial objective first. It is half the implementation and gets skipped in every summary, including this one.
Degeneracy. More than $n$ constraints tight at one vertex means several bases describe the same point, and the method can pivot without moving. Anti-cycling rules exist; without them a run can loop for ever.
Expecting the worst case. Simplex has an exponential worst case and excellent typical behaviour. Interior point methods, next lesson, have the opposite profile, which is why both are still in use.
The picture of "check all the corners and take the best" comes from lesson 3, where there were four of them, and it is the wrong picture for the method. Simplex never knows the value at a vertex it has not visited, and never needs to: it asks only whether the objective improves along each edge leaving where it stands. That is why it can solve a problem with astronomically many vertices in a few hundred steps, and it is also why the stopping argument has to invoke convexity — a method that had compared everything would need no theorem, and a method that compares only neighbours needs exactly the one lesson 9 proved.
Constraints $x + y \le 4$, $x \le 3$, $x, y \ge 0$. Cross $x + y = 4$ with $x = 3$: the point $(3, 1)$.
A crossing.
Check the rest: $x = 3 \ge 0$ and $y = 1 \ge 0$. Feasible, so $(3,1)$ is a vertex.
And a vertex.
Now cross $x + y = 4$ with $y = 0$: the point $(4, 0)$. But $x \le 3$ fails there, so it is a crossing outside the region and not a vertex at all. Every candidate needs this check, and it is the step that makes vertex enumeration expensive even when the count is small.
A crossing that is not a vertex.
$\max\ 2x + 2y$ over $x + y \le 4$, $x, y \ge 0$. From the origin, walk along $x$ to $(4,0)$, objective $8$.
A first improving edge.
The edge towards $(0,4)$ has rate of change $2(-1) + 2(1) = 0$: the objective does not change along it. Not an improvement, so the method stops at $(4,0)$.
No improving edge: stop.
And it is right — $8$ is optimal. But every point of that edge is also optimal, and a good implementation says so. That is worth reporting: the person who asked now has a free choice among equally good plans and can use some other criterion to pick.
A zero-rate edge is information, not an error.
Feasible? $4(3) = 12 \le 24$ and $2(3) = 6 \le 6$: yes, and the second constraint is tight along with $x = 0$. So it is a vertex.
Vertex first.
Objective there: $12$. Now look along the edge that keeps $x + 2y = 6$ tight and increases $x$: moving one unit in $x$ means dropping $y$ by $1/2$, so the objective changes by $5 - 4(1/2) = 3$ per unit — an improvement.
So $(0,3)$ is not optimal: an improving edge leaves it. Walking along that edge until the machine constraint becomes tight lands at $(3, 1.5)$ with objective $21$. Notice that the decision needed only the rates along the edges leaving the vertex — never the other vertices' values.
Match each linear-programming fact to the conclusion it licenses for a simplex search.
| An optimum can be sought among vertices | Those equalities determine the corner point | A pivot exchanges one active constraint for another | The current vertex is globally optimal for the linear program | |
|---|---|---|---|---|
| Fundamental theorem of linear programming | ||||
| A set of constraints is tight at a vertex | ||||
| Move along an edge to an adjacent vertex | ||||
| No adjacent edge improves the objective |
Where do $1x + 1y = 4$ and $1x + 3y = 6$ cross? Give $x$.
Answer:
How does the simplex method search for the optimum of $2x + 3y$ over a polyhedron?
| A feasible vertex | An edge to an adjacent vertex | One along which the objective improves | Stop and report an optimum | |
|---|---|---|---|---|
| Current simplex location | ||||
| Candidate move | ||||
| Acceptable candidate edge | ||||
| No improving adjacent edge |
With two variables and $5$ constraints, how many pairs of constraint lines are there to cross?
Answer:
Put one iteration of the simplex method in order.
Number the steps in order (write the number in the box):
Simplex stops when no *adjacent* vertex is better. Why does that prove no vertex anywhere is better?
| Convex | Linear | A local optimality condition | Promotes the local condition to global optimality | |
|---|---|---|---|---|
| Feasible region | ||||
| Objective | ||||
| No better adjacent move | ||||
| Convex optimization theorem |
Lesson test: one question per skill, one attempt each, no hints. Your answers are checked when you submit.
How does the simplex method search for the optimum of $4x + 3y$ over a polyhedron?
| A feasible vertex | An edge to an adjacent vertex | One along which the objective improves | Stop and report an optimum | |
|---|---|---|---|---|
| Current simplex location | ||||
| Candidate move | ||||
| Acceptable candidate edge | ||||
| No improving adjacent edge |
You can find vertices, follow a simplex walk, and say why a local stopping rule settles the problem here. Next: the method that goes through the middle instead.
9. Your turn: is $(0, 3)$ optimal for $\max\ 5x + 4y$ over $6x + 4y \le 24$, $x + 2y \le 6$, $x, y \ge 0$?, step 3