The feasible region of a linear program in three variables, \(\max\ c^\top x\) subject to \(Ax \le b\), \(x \ge 0\), is a polytope, and the simplex method walks along its edges: from the origin (the basis of the slack variables) it moves at each pivot to an adjacent vertex where \(c^\top x\) is larger, until no edge goes up, and that vertex is optimal. On the Klee-Minty cube (1972), a cube squeezed so that every vertex is higher than the one before it along a Hamiltonian path, the rule of Dantzig (the largest reduced cost) visits all \(2^3 = 8\) vertices; in \(n\) variables it takes \(2^n - 1\) pivots, the first proof that the method is not polynomial. The path is printed as a tube on the edges, the optimum as a ball.
La regione ammissibile di un programma lineare in tre variabili, \(\max\ c^\top x\) con \(Ax \le b\), \(x \ge 0\), è un politopo, e il metodo del simplesso cammina sui suoi spigoli: dall'origine (la base delle variabili di slack) a ogni pivot passa a un vertice adiacente in cui \(c^\top x\) è maggiore, finché nessuno spigolo sale, e quel vertice è ottimo. Sul cubo di Klee-Minty (1972), un cubo schiacciato in modo che lungo un cammino hamiltoniano ogni vertice sia più alto del precedente, la regola di Dantzig (il costo ridotto maggiore) visita tutti i \(2^3 = 8\) vertici; in \(n\) variabili servono \(2^n - 1\) pivot, la prima prova che il metodo non è polinomiale. Il cammino si stampa come un tubo sugli spigoli, l'ottimo come una sfera.
The polytope as printed in the view chosen above: a solid lying on its face \(x_3 = 0\), with the edges off the path engraved as grooves and the path raised as a tube, or a frame of struts with the path thicker; the start is a small ball, the optimum a large one, and the arrow of \(c\) may stand on it (it needs supports).
Il politopo stampato nel modo scelto sopra: un solido appoggiato sulla faccia \(x_3 = 0\), con gli spigoli fuori dal cammino incisi come solchi e il cammino in rilievo come un tubo, oppure un telaio di aste con il cammino più spesso; l'inizio è una sfera piccola, l'ottimo una grande, e la freccia di \(c\) può stare su di esso (richiede supporti).