Il metodo del simplesso risolve problemi di programmazione lineare camminando tra vertici adiacenti del poliedro ammissibile. Ogni vertice corrisponde a una soluzione di base ammissibile: un insieme di variabili di base determina il punto corrente, mentre le variabili non di base sono poste a zero.
L’idea geometrica è semplice: in una PL con ottimo finito, almeno un vertice del poliedro ammissibile è ottimo. Il simplesso parte da un vertice ammissibile, controlla se esiste una direzione che migliora l’obiettivo e, se esiste, si sposta lungo uno spigolo fino al vertice adiacente successivo. La parte delicata è scegliere la variabile entrante, la variabile uscente e riconoscere i casi di ottimo, illimitatezza o degenerazione.
Forma standard
Il punto di partenza operativo è la forma standard:
dove A è la matrice dei vincoli, b il vettore delle risorse e x il vettore delle variabili non negative. Scelta una base B, le colonne di A_B devono essere linearmente indipendenti. Le variabili di base si esprimono in funzione delle variabili non di base:
Se x_N=0 e x_B=A_B^{-1}b\ge0, la base è ammissibile. L’obiettivo diventa:
Questa formula separa il valore corrente dell’obiettivo dal contributo potenziale delle variabili fuori base.
Costi ridotti e criterio di ottimalità
I costi ridotti sono:
In massimizzazione, se tutti i costi ridotti sono non positivi, la base è ottima. Se una variabile ha costo ridotto positivo, può entrare in base perché aumentarla migliora l’obiettivo almeno localmente. In minimizzazione il verso del criterio si inverte.
I costi ridotti hanno anche una lettura duale: misurano quanto una variabile violerebbe o rispetterebbe il sistema dei prezzi impliciti. Per questo il simplesso è strettamente collegato alla dualità lineare e ai prezzi ombra. Quando tutti i costi ridotti hanno il segno corretto, la base corrente fornisce insieme una soluzione primale ammissibile e un certificato duale di ottimalità.
Pivot e test del rapporto
Il test del rapporto determina quale variabile esce:
Il vettore d descrive come cambiano le variabili di base quando la variabile entrante x_j aumenta. Il rapporto seleziona il primo vincolo che diventa attivo: quella variabile di base lascia la base, evitando di uscire dalla regione ammissibile. Il passaggio si chiama pivot perché sostituisce una colonna della base con una nuova colonna.
Se non esiste d_i\gt0, il problema è illimitato nella direzione scelta: la variabile entrante può crescere indefinitamente senza violare i vincoli e l’obiettivo continua a migliorare. Se invece il minimo del rapporto è zero, il pivot è degenere: si cambia base senza aumentare il valore dell’obiettivo. La degenerazione può causare stalli e, in casi patologici, cicli; per evitarli si usano regole di pivot come la regola di Bland.
Avvio e uso pratico
Il simplesso richiede una base iniziale ammissibile. Nei problemi già in forma standard con variabili di scarto positive, la base iniziale è spesso immediata. Quando compaiono vincoli \geq, uguaglianze o termini noti negativi, servono procedure di fase I, metodo delle due fasi o metodo del grande M per costruire una base ammissibile artificiale.
Nelle applicazioni di ricerca operativa il metodo non serve soltanto a ottenere numeri ottimi. Il tableau finale indica vincoli attivi, risorse residue, costi ridotti, sensibilità dei coefficienti e valore marginale delle risorse. Per questo il simplesso resta importante anche quando i software moderni risolvono automaticamente modelli molto grandi: la sua struttura spiega perché una soluzione è ottima e quali risorse stanno davvero limitando il sistema.
Limiti
Nel caso peggiore teorico il simplesso può richiedere un numero esponenziale di pivot, anche se in moltissimi problemi pratici è molto efficiente. Per problemi enormi o strutturati si usano anche metodi interior point, decomposizioni o algoritmi specializzati, per esempio nei trasporti e nei flussi su rete. Il simplesso resta comunque il riferimento classico per capire la geometria della programmazione lineare e l’analisi post-ottimale.
Vedi anche: programmazione lineare, dualità lineare, prezzo ombra, formulario di ricerca operativa ed esercizi su simplesso e dualità.