The simplex on a polytopeIl simplesso su un politopo

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.

0
The polytope with its edges, the path of the simplex in gold, the optimum (the purple diamond) with the arrow of \(c\) and the plane \(c^\top x = z^*\) that touches the polytope there. The axes are rescaled so that the polytope fills a cube, a change of units that keeps vertices, edges and path. Drag to turn, wheel or pinch to zoom.Il politopo con i suoi spigoli, il cammino del simplesso in oro, l'ottimo (il rombo viola) con la freccia di \(c\) e il piano \(c^\top x = z^*\) che lì tocca il politopo. Gli assi sono riscalati perché il politopo riempia un cubo, un cambio di unità che conserva vertici, spigoli e cammino. Trascina per ruotare, rotella o pizzico per lo zoom.

Download for 3D printingScarica per la stampa 3D

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).