- \(c \cdot x\)
- \(b \cdot y\)
- \(b \cdot y - c \cdot x\)
The same linear program as in the plane, \(\max\, c \cdot x,\ A x \le b,\ x \ge 0\), now with three variables, and therefore with a polytope as feasible region. The simplex walks along its edges from vertex to vertex, each pivot raising the level plane \(c \cdot x = z\), until no reduced cost is positive; on the Klee-Minty cube Dantzig's rule visits all 8 vertices. The barrier method goes through the inside instead, along the central path, from the analytic center to the optimum as \(\mu\) shrinks.
Lo stesso programma lineare del piano, \(\max\, c \cdot x,\ A x \le b,\ x \ge 0\), ora con tre variabili, e quindi con un politopo come regione ammissibile. Il simplesso ne percorre gli spigoli da vertice a vertice, e ogni pivot alza il piano di livello \(c \cdot x = z\), finché nessun costo ridotto è positivo; sul cubo di Klee-Minty la regola di Dantzig visita tutti gli 8 vertici. Il metodo barriera passa invece per l'interno, lungo il cammino centrale, dal centro analitico all'ottimo mentre \(\mu\) decresce.