Simplex in space
About this app
The simplex algorithm on a glass body: from the starting vertex it climbs edge by edge, with pivot column, ratio test as a ray and an objective plane that moves along. Five examples (including Klee–Minty, degenerate, ambiguous), rolling new bodies, four pivot rules compared, tableau in lockstep.
With explain mode: an AI tutor walks you through the app, points out what matters in the scene and answers your questions.
Simplex as a walk over vertices
With three variables, the feasible region of a linear program is a convex polyhedron. Each vertex corresponds to a basic solution: the faces meeting there belong to the non-basic variables, which are zero. A pivot step is a walk along an edge to a neighbouring vertex. The pivot column picks the edge, and the ratio test determines how far you may go before hitting a new face. The objective c·x = z is a plane; at the optimum it touches the polytope only at a vertex, or rests on an edge or face.
What the app shows
The polytope is drawn as glass, and the path of the algorithm runs uphill edge by edge from the starting vertex at the origin. The ratio test appears as a ray and the objective plane moves along. Five examples are available: gem, workshop, the Klee–Minty cube, a degenerate house with a pyramid roof and a case with multiple optima. “Roll a new polytope” creates a random problem. Four pivot rules can be chosen: Dantzig, steepest edge, greatest increase and Bland. The tableau runs in step, in fractions or decimals.
Try it yourself
Load the Klee–Minty cube and compare the step counts of the pivot rules: with Dantzig’s rule the method visits all 8 vertices. In the degenerate example the basis changes while the point stays put, because four faces meet at one vertex. In the multiple-optima case the objective plane rests on a whole face. Clicking another vertex restarts the method there, and the objective plane can be pushed through the polytope.
Frequently asked questions
- What does the simplex algorithm do geometrically?
- It walks along the edges of the feasible polytope from vertex to vertex, with the objective rising or staying equal at every step. It stops at a vertex from which no edge leads uphill. That vertex is optimal.
- What is the Klee–Minty cube?
- A deformed cube on which the simplex algorithm with Dantzig’s pivot rule visits every vertex. In n dimensions that is 2ⁿ vertices. It shows that this variant needs exponentially many steps in the worst case.
- What is degeneracy in the simplex method?
- A vertex is degenerate if more faces meet there than the dimension requires. A pivot can then change the basis without moving the point or increasing the objective. In unlucky cases the method can cycle; Bland’s rule prevents this.
- Which pivot rules can I compare in the app?
- Dantzig (most negative objective-row entry), steepest edge in the picture, greatest total increase to the next vertex, and Bland (smallest index). The number on each button shows how many pivot steps the rule needs.
Subject: Operations research
More from Operations research
- Big M: Nebenbedingungen an- und ausschalten
- Dijkstra's algorithm
- Ganzzahlig ist anders: LP gegen IP
- Konvexe Mengen, Hülle und Ecken
- Linear problems made visual
- Nebenbedingungen verschärfen (Tightening)
- Simplex algorithm
- Tabu search on a small TSP
A VisuApp by heyprof: interactive, free in your browser, no sign-up. What is a VisuApp? · All apps