Il metodo del simplesso risolve la programmazione lineare muovendosi tra i vertici della regione ammissibile, migliorando l’obiettivo a ogni passo finché non si raggiunge l’ottimo. La dualità associa a ogni problema (primale) un problema gemello (duale) il cui ottimo coincide, fornendo i prezzi ombra delle risorse. Questa scheda allena i meccanismi del simplesso e la lettura del duale.
1. Tableau iniziale
Esercizio. Per \max Z=3x_1+2x_2 con x_1+x_2\le4, x_1+3x_2\le6, scrivere la forma standard e individuare la base iniziale.
Aggiungendo le variabili di scarto s_1,s_2\ge0:
x_1+x_2+s_1=4,\qquad x_1+3x_2+s_2=6.
La base iniziale è \{s_1,s_2\}, corrispondente al vertice (x_1,x_2)=(0,0) con Z=0. Le variabili di scarto offrono una base di partenza immediata e ammissibile.
2. Scelta della variabile entrante
Esercizio. Nel tableau iniziale del punto 1, quale variabile conviene far entrare in base?
Si massimizza: entra la variabile con coefficiente più alto nell’obiettivo (riduzione di costo più favorevole):
\text{coeff. } x_1=3,\ x_2=2\ \Rightarrow\ \text{entra }x_1.
Far crescere x_1 aumenta Z di 3 per unità, più che x_2. La variabile entrante è quella che promette il miglioramento maggiore.
3. Criterio del rapporto minimo (variabile uscente)
Esercizio. Entrando x_1, determinare quale variabile esce dalla base (test del rapporto minimo).
Si calcola, per ogni riga con coefficiente positivo di x_1, il rapporto termine noto / coefficiente:
\dfrac{4}{1}=4\ (s_1),\qquad \dfrac{6}{1}=6\ (s_2).
Il minimo è 4, sulla riga di s_1: esce s_1. Il rapporto minimo garantisce di restare nella regione ammissibile (non violare gli altri vincoli).
4. Criterio di ottimalità
Esercizio. Come si riconosce l’ottimo nel simplesso (massimizzazione)?
L’ottimo è raggiunto quando nessuna variabile fuori base può migliorare l’obiettivo, cioè quando tutti i costi ridotti sono \le0 (per la massimizzazione):
c_j-z_j\le0\ \text{per ogni }j\ \Rightarrow\ \text{ottimo}.
Finché esiste un coefficiente positivo nella riga obiettivo, si itera. Quando spariscono, il vertice corrente è ottimo.
5. Costruzione del problema duale
Esercizio. Scrivere il duale di \max Z=3x_1+2x_2 con x_1+x_2\le4, x_1+3x_2\le6, x\ge0.
Il duale ha una variabile per ogni vincolo primale (y_1,y_2\ge0) e inverte max↔min:
\min W=4y_1+6y_2\quad\text{s.v.}\quad\begin{cases}y_1+y_2\ge3\\ y_1+3y_2\ge2\end{cases},\ y\ge0.
I coefficienti dell’obiettivo primale diventano i termini noti dei vincoli duali e viceversa; la matrice si traspone. Ogni vincolo primale “genera” una variabile duale.
6. Dualità forte e prezzi ombra
Esercizio. Spiegare il teorema della dualità forte e il significato delle variabili duali.
Il teorema della dualità forte afferma che se primale e duale hanno soluzione ottima, i due valori ottimi coincidono:
Z^*=W^*.
Le variabili duali ottime y_i^* sono i prezzi ombra: indicano di quanto aumenterebbe Z^* se la risorsa i (termine noto del vincolo) crescesse di un’unità. Un prezzo ombra nullo segnala una risorsa non satura (vincolo non attivo); uno positivo, una risorsa “preziosa” che conviene aumentare.
7. Primo pivot del simplesso
Esercizio. Eseguire il primo pivot del problema:
con:
e base iniziale \{s_1,s_2\}.
Dai punti 2 e 3 entra x_1 ed esce s_1. La prima equazione diventa:
Sostituiamo nella seconda:
Quindi:
e:
Sostituiamo nell’obiettivo:
Quindi:
La nuova soluzione di base si ottiene ponendo le fuori base x_2=0, s_1=0:
Risultato:
Poiché nella forma Z=12-x_2-3s_1 non compaiono coefficienti migliorativi positivi, la soluzione è già ottima.
8. Lettura dei vincoli attivi dalla soluzione
Esercizio. Per la soluzione ottima x_1=4, x_2=0 del punto 7, individuare vincoli attivi e scarti.
I vincoli originali sono:
Nel punto (4,0):
quindi il primo vincolo è attivo e:
Per il secondo:
quindi:
Il secondo vincolo non è saturo: restano 2 unità di risorsa inutilizzata.
9. Soluzione duale tramite complementarità
Esercizio. Trovare la soluzione duale ottima del problema:
con:
Il duale, già scritto al punto 5, è:
con:
Dalla soluzione primale ottima:
Per scarti complementari, il vincolo duale associato a x_1 è attivo:
Inoltre il secondo vincolo primale ha scarto positivo s_2=2, quindi la variabile duale corrispondente è:
Allora:
La soluzione duale è:
Il valore duale è:
uguale a Z^*=12, come previsto dalla dualità forte.
10. Scarti complementari
Esercizio. Interpretare economicamente gli scarti complementari del punto 9.
Gli scarti complementari dicono:
per ogni risorsa. Quindi:
- se una risorsa è inutilizzata (s_i>0), il suo prezzo ombra deve essere nullo (y_i=0);
- se una risorsa ha prezzo ombra positivo (y_i>0), allora è completamente usata (s_i=0).
Nel nostro caso:
la prima risorsa è scarsa e vale 3 unità di obiettivo per unità aggiuntiva.
Invece:
la seconda risorsa è abbondante: aumentarne la disponibilità non migliora l’obiettivo.
11. Riconoscere illimitatezza nel tableau
Esercizio. Come si riconosce un problema illimitato durante il simplesso?
In una massimizzazione, se una variabile fuori base ha costo ridotto positivo, vorremmo farla entrare. Ma se nella sua colonna tutti i coefficienti dei vincoli sono \leq0, aumentarla non viola nessun vincolo di disponibilità.
In quel caso il test del rapporto minimo non produce alcuna variabile uscente: l’obiettivo può crescere senza limite.
Sintesi operativa:
Questo è quasi sempre un segnale modellistico: manca un vincolo che limiti quella direzione.
Errori comuni
- Scegliere male la variabile entrante. In massimizzazione entra quella col coefficiente obiettivo più positivo; in minimizzazione il più negativo.
- Dimenticare il test del rapporto minimo. La variabile uscente è data dal rapporto minimo positivo: sbagliarlo porta fuori dalla regione ammissibile.
- Trasporre male il duale. Numero di variabili duali = numero di vincoli primali; i versi delle disuguaglianze si invertono con max↔min.
- Ignorare i prezzi ombra. Le variabili duali dicono quali risorse aumentare: trascurarle vanifica l’analisi di sensibilità.
- Confondere scarto positivo e prezzo positivo. Per complementarità non possono essere entrambi positivi sulla stessa risorsa.