Torniamo al laboratorio che produce tavoli da cucina e tavolini con 100 ore di falegnameria e 80 di verniciatura. Abbiamo trovato che il piano ottimo rende 3.600 euro. Ora cambiamo punto di vista. Un concorrente vuole affittare tutte le ore del laboratorio e chiede: qual è il prezzo minimo per ora che dovrei offrire perché al titolare convenga accettare invece di produrre?
Questa seconda domanda è un nuovo programma lineare, il duale del primo. La teoria della dualità dice che le due domande hanno la stessa risposta, e che il legame tra i due problemi contiene informazioni economiche preziose.
Costruire il duale
Il problema di partenza, detto primale:
massimizza 60x + 40y
2x + y ≤ 100
x + y ≤ 80
x, y ≥ 0
Il concorrente offre a euro per ora di falegnameria e b euro per ora di verniciatura. Vuole spendere il meno possibile, ma ogni tavolo che il titolare rinuncia a produrre deve essere ripagato almeno quanto il suo margine:
minimizza 100a + 80b
2a + b ≥ 60 (tavolo da cucina)
a + b ≥ 40 (tavolino)
a, b ≥ 0
Lo schema generale è meccanico:
- ogni vincolo del primale diventa una variabile del duale;
- ogni variabile del primale diventa un vincolo del duale;
- i termini noti del primale diventano i coefficienti dell'obiettivo duale, e viceversa;
- la matrice dei coefficienti si traspone;
- un massimo diventa un minimo, e i «minore o uguale» diventano «maggiore o uguale».
Il duale del duale è di nuovo il primale.
Dualità debole e forte
Dualità debole: il valore di qualunque soluzione ammissibile del primale (di massimo) è minore o uguale al valore di qualunque soluzione ammissibile del duale (di minimo). Il motivo è semplice: nessun piano di produzione può rendere più del valore delle risorse che consuma, se queste sono pagate abbastanza da coprire ogni prodotto.
Questo ha un uso pratico immediato. Se un algoritmo trova un piano da 3.500 euro e una soluzione duale da 3.700, si sa che l'ottimo sta tra 3.500 e 3.700, anche senza averlo trovato. La distanza tra i due valori misura quanto si è lontani dall'ottimo.
Dualità forte: se il primale ha un ottimo finito, lo ha anche il duale, e i due valori coincidono. Nell'esempio il duale ha ottimo in a = 20, b = 20, con valore 100·20 + 80·20 = 3.600: esattamente il margine del piano ottimo.
Ne seguono anche le altre combinazioni: se il primale è illimitato il duale è inammissibile, e se il duale è illimitato il primale è inammissibile.
Prezzi ombra
Le variabili duali ottime hanno un'interpretazione diretta: sono i prezzi ombra delle risorse. Un prezzo ombra dice di quanto aumenterebbe il valore ottimo se si disponesse di un'unità in più di quella risorsa, a parità di tutto il resto.
Nell'esempio entrambe valgono 20: un'ora in più di falegnameria o di verniciatura porterebbe 20 euro di margine in più. Se lo straordinario di un falegname costa 15 euro l'ora, conviene; se costa 25, no.
Due avvertenze importanti:
- il prezzo ombra vale solo entro un certo intervallo: aggiungendo molte ore di falegnameria, prima o poi la verniciatura diventa l'unico collo di bottiglia e il valore di un'ora di falegnameria scende;
- una risorsa con prezzo ombra zero non è scarsa: aggiungerne non serve a nulla, perché ne avanza già.
Scarti complementari
Le soluzioni ottime del primale e del duale sono legate da condizioni semplici, dette scarti complementari:
- se un vincolo del primale non è attivo (avanza risorsa), la corrispondente variabile duale vale zero;
- se una variabile duale è positiva, il vincolo corrispondente è attivo;
- allo stesso modo, se un prodotto viene realizzato (variabile primale positiva), il relativo vincolo duale è soddisfatto con l'uguale: il valore delle risorse consumate è esattamente pari al margine.
| Risorsa | Ore usate | Ore disponibili | Prezzo ombra |
|---|---|---|---|
| Falegnameria | 100 | 100 | 20 |
| Verniciatura | 80 | 80 | 20 |
Queste condizioni permettono di verificare se una coppia di soluzioni è ottima senza rifare i calcoli, e sono alla base di molti algoritmi.
Costi ridotti
Per un prodotto non realizzato all'ottimo, il costo ridotto dice di quanto dovrebbe migliorare il suo margine prima che convenga produrlo. Si calcola come differenza tra il valore delle risorse che consumerebbe (ai prezzi ombra) e il suo margine. Se il laboratorio pensasse a un terzo modello che richiede 1 ora di falegnameria e 2 di verniciatura, le risorse consumate varrebbero 20 + 40 = 60 euro: il nuovo modello conviene solo se rende più di 60 euro.
Dove ritorna la dualità
La dualità non è solo teoria. Il teorema flusso massimo – taglio minimo è un caso particolare di dualità lineare. Il metodo ungherese per l'assegnamento lavora in sostanza su variabili duali. Molti algoritmi di ottimizzazione su larga scala sfruttano il duale per scomporre problemi enormi in parti più piccole, e i limiti duali sono il modo standard per certificare la qualità di una soluzione.
In sintesi
- Ogni programma lineare ha un duale: i vincoli diventano variabili e viceversa.
- Dualità debole: ogni soluzione duale fornisce un limite al valore del primale.
- Dualità forte: all'ottimo i valori di primale e duale coincidono.
- Le variabili duali ottime sono i prezzi ombra: il valore marginale di ogni risorsa.
- Scarti complementari e costi ridotti dicono quali risorse sono scarse e quali prodotti converrebbero.
