Metodo del Simplesso

Il metodo del simplesso è l'algoritmo di programmazione lineare sviluppato da George B. Dantzig nel 1947 ed è fondamento della ricerca operativa. Idea centrale: la regione ammissibile di un LP in forma standard max c^T x s.t. Ax = b, x ≥ 0 è un politopo convesso e un obiettivo lineare raggiunge l'ottimo in un vertice; ogni vertice corrisponde a una soluzione basica ammissibile (BFS) in cui m variabili basiche sono positive e le n-m non basiche sono nulle. L'algoritmo procede: (1) trovare una BFS iniziale (con metodo big-M o due fasi); (2) calcolare i costi ridotti c_j - c_B^T B^(-1) A_j; se ≥ 0 per ogni variabile non basica, la BFS attuale è ottima; (3) selezionare una variabile entrante con costo ridotto negativo (regola di Dantzig: la più negativa), determinare la variabile uscente con il test del rapporto minimo, pivotare e tornare al passo (2). Geometricamente, il metodo cammina da un vertice del politopo a un vertice adiacente. Complessità: Klee e Minty (1972) mostrarono tramite il cubo di Klee-Minty che il caso peggiore può richiedere 2^n iterazioni (esponenziale); tuttavia l'analisi mediata e quella levigata (Spielman e Teng 2004) provano che il simplesso è polinomiale in media, spiegando la sua eccellente velocità pratica. Varianti: (a) simplesso rivisitato con fattorizzazione di matrici sparse per problemi di grandi dimensioni; (b) simplesso duale (Lemke 1954) procede tramite ammissibilità duale; (c) simplesso di rete risolve trasporti e assegnamenti su strutture ad albero in pochi secondi. Il cycling — ciclo infinito in un vertice degenere — è evitato dalla regola di Bland (1977) o dal pivoting lessicografico. Nei solver LP moderni il simplesso è offerto accanto ai metodi a punti interni e domina nei contesti di warm-start, in particolare all'interno di branch-and-cut per MILP.