Con due variabili un problema di programmazione lineare si risolve disegnando la regione ammissibile e valutando l'obiettivo nei vertici. Con cinquanta variabili e trenta vincoli non si può disegnare nulla, e i vertici possono essere un numero astronomico. Serve un metodo che visiti solo i vertici utili.
Il metodo del simplesso, sviluppato da George Dantzig alla fine degli anni Quaranta, fa proprio questo: parte da un vertice della regione ammissibile e si sposta lungo gli spigoli verso vertici adiacenti sempre migliori, finché non ne trova uno da cui nessuno spostamento migliora l'obiettivo. Poiché la regione è convessa, quel vertice è l'ottimo globale.
Primo passo: la forma standard
Il simplesso lavora su uguaglianze. Ogni vincolo «minore o uguale» si trasforma aggiungendo una variabile di scarto, che misura quanta risorsa resta inutilizzata. Riprendiamo il problema dei tavoli:
massimizza 60x + 40y
2x + y + s1 = 100
x + y + s2 = 80
x, y, s1, s2 ≥ 0
s1 sono le ore di falegnameria non usate, s2 quelle di verniciatura. Con x = y = 0 si ha s1 = 100 e s2 = 80: è il vertice di partenza, cioè «non produrre nulla».
Variabili di base e non di base
In ogni vertice alcune variabili valgono zero (le non di base) e le altre si ricavano dalle equazioni (le di base). Il numero di variabili di base è uguale al numero di vincoli. All'inizio le variabili di base sono s1 e s2; x e y sono a zero.
Spostarsi su un vertice adiacente significa far entrare in base una variabile non di base e farne uscire una di base. Questa operazione si chiama pivot.
Il tableau e le regole del pivot
I dati si organizzano in una tabella, il tableau. L'ultima riga contiene i coefficienti dell'obiettivo con segno cambiato, che indicano quanto migliorerebbe il guadagno aumentando ciascuna variabile.
| Base | x | y | s1 | s2 | Valore |
|---|---|---|---|---|---|
| s1 | 2 | 1 | 1 | 0 | 100 |
| s2 | 1 | 1 | 0 | 1 | 80 |
| Obiettivo | −60 | −40 | 0 | 0 | 0 |
Chi entra? Si sceglie una variabile con coefficiente negativo nella riga dell'obiettivo; la regola classica prende il più negativo. Qui entra x: ogni tavolo da cucina vale 60.
Chi esce? Si aumenta x finché un vincolo non lo blocca. Per ogni riga con coefficiente positivo nella colonna di x si calcola il rapporto valore / coefficiente: 100/2 = 50 e 80/1 = 80. Il minimo è 50, nella riga di s1: è la falegnameria a finire per prima. Esce s1. Questo test del rapporto minimo garantisce di restare nella regione ammissibile.
Dopo il pivot, con le normali operazioni tra righe, si ottiene x = 50, y = 0, guadagno 3.000. Nella riga dell'obiettivo il coefficiente di y è ancora negativo (−10): conviene far entrare y. Il test del rapporto fa uscire s2. Il nuovo vertice è x = 20, y = 60, con guadagno 3.600. Ora tutti i coefficienti della riga obiettivo sono non negativi: nessuna variabile migliorerebbe il risultato, e l'algoritmo si ferma.
Nella riga obiettivo finale i coefficienti di s1 e s2 valgono entrambi 20: sono i prezzi ombra delle due risorse, letti direttamente dal tableau.
Trovare un vertice di partenza
Nell'esempio il vertice iniziale era ovvio. Con vincoli del tipo «maggiore o uguale» o uguaglianze, l'origine può non essere ammissibile. Si usa allora il metodo delle due fasi: nella prima fase si aggiungono variabili artificiali e si risolve un problema ausiliario che le spinge a zero. Se ci si riesce, si ha un vertice ammissibile da cui partire con il problema vero; se non ci si riesce, il problema originale è inammissibile.
Casi particolari
- Problema illimitato: la variabile che entra non ha coefficienti positivi nella sua colonna, quindi nessun vincolo la blocca. L'obiettivo può crescere senza limite.
- Soluzioni multiple: all'ottimo una variabile non di base ha coefficiente zero nella riga obiettivo. Farla entrare porta a un altro vertice con lo stesso valore.
- Degenerazione: una variabile di base vale zero. Un pivot può non migliorare l'obiettivo e, in casi rari, l'algoritmo può girare in tondo tra le stesse basi. La regola di Bland, che sceglie sempre la variabile con l'indice più basso tra quelle ammesse, evita questi cicli.
Quanto è veloce
Esistono esempi costruiti apposta in cui il simplesso visita un numero di vertici che cresce in modo esponenziale con la dimensione del problema. Nella pratica, però, il numero di pivot cresce in genere in modo moderato con il numero di vincoli, e il simplesso resta uno degli algoritmi più usati per la PL. Esistono anche i metodi a punto interno, che attraversano l'interno della regione invece di camminare sugli spigoli e hanno garanzie di tempo polinomiale; i risolutori moderni offrono entrambi gli approcci.
Una ragione pratica per cui il simplesso resta centrale è il riavvio a caldo: se si aggiunge un vincolo o si cambia un coefficiente, si può ripartire dall'ultima base invece che da zero. È fondamentale negli algoritmi di programmazione intera, che risolvono migliaia di programmi lineari quasi identici.
In sintesi
- Il simplesso cammina tra vertici adiacenti della regione ammissibile, migliorando l'obiettivo a ogni passo.
- Le variabili di scarto trasformano i vincoli in uguaglianze e forniscono il vertice iniziale.
- A ogni pivot entra una variabile che migliora l'obiettivo ed esce quella indicata dal test del rapporto minimo.
- Il metodo delle due fasi trova un punto di partenza o dimostra l'inammissibilità.
- Illimitatezza, soluzioni multiple e degenerazione si riconoscono direttamente dal tableau.
