Dualità lineare — ingegnerismo.it

La dualità lineare associa a un problema di programmazione lineare un secondo problema, detto duale. I due modelli descrivono lo stesso fenomeno da due punti di vista complementari: il primale sceglie le quantità decisionali, il duale assegna valori marginali alle risorse e ai vincoli. Per il primale in forma canonica di massimizzazione:

\begin{aligned} \max\quad & c^Tx\\ \text{soggetto a}\quad & Ax\le b,\\ &x\ge0, \end{aligned}

il duale è il problema di minimizzazione:

\begin{aligned} \min\quad & b^Ty\\ \text{soggetto a}\quad & A^Ty\ge c,\\ &y\ge0. \end{aligned}

Ogni vincolo primale genera una variabile duale; ogni variabile primale genera un vincolo duale. La matrice dei coefficienti viene trasposta, i termini noti $b$ diventano i coefficienti dell’obiettivo duale e i coefficienti $c$ diventano termini noti dei vincoli duali. Le variabili duali sono interpretabili come prezzi ombra delle risorse: misurano quanto vale, localmente, un’unità aggiuntiva di capacità.

Interpretazione

Nel primale si domanda: quanto produrre, spedire, assegnare o attivare per massimizzare un beneficio? Nel duale si domanda: quali prezzi attribuire alle risorse in modo che nessuna attività risulti sottoprezzata? Se un’attività primale ha profitto $c_j$ , il vincolo duale impone che il costo implicito delle risorse usate da quell’attività sia almeno $c_j$ :

(A^Ty)_j\ge c_j.

Questa condizione impedisce arbitraggi: se un’attività producesse più valore del costo duale delle risorse che consuma, il sistema dei prezzi non sarebbe coerente con l’ottimo. Per questo la dualità è centrale nella ricerca operativa: non dà soltanto una tecnica di calcolo, ma anche una spiegazione economica dell’ottimo.

Teoremi fondamentali

Dualità debole:

c^Tx\le b^Ty

per ogni coppia primale-duale ammissibile.

La dualità debole dice che ogni soluzione duale ammissibile fornisce un limite superiore al valore di qualunque soluzione primale ammissibile. Infatti, usando $A^Ty\ge c$ , $x\ge0$ e $Ax\le b$ , si ottiene:

c^Tx\le y^TAx\le y^Tb=b^Ty.

Questa catena di disuguaglianze è un certificato: se si trova una soluzione primale e una soluzione duale con lo stesso valore obiettivo, nessuna delle due può essere migliorata.

Dualità forte:

c^Tx^\ast=b^Ty^\ast

quando primale e duale hanno soluzioni ottime finite.

La dualità forte afferma che, sotto le ipotesi usuali della programmazione lineare, il miglior valore primale e il miglior valore duale coincidono. Il gap duale

g=b^Ty-c^Tx

è sempre non negativo per coppie ammissibili; all’ottimo vale zero. In pratica, il gap misura quanto manca a una soluzione per essere certificata ottima.

Scarti complementari:

y_i^\ast(b_i-a_i^Tx^\ast)=0, \qquad x_j^\ast((A^Ty^\ast)_j-c_j)=0

Queste relazioni certificano l’ottimalità e spiegano quando una risorsa o una variabile ha valore marginale positivo. Il primo prodotto dice che un vincolo primale non saturo, cioè con risorsa inutilizzata, deve avere prezzo ombra nullo. Il secondo dice che una variabile primale positiva può comparire in soluzione solo se il vincolo duale corrispondente è attivo.

Uso operativo

Nel metodo del simplesso la dualità compare nei costi ridotti, nei tableau e nell’analisi di sensibilità. Una base ammissibile è ottima quando non esistono direzioni che migliorano l’obiettivo; in termini duali, questo equivale alla fattibilità del sistema dei prezzi impliciti. Per questo, dopo aver risolto una PL, non basta riportare il vettore $x^\ast$ : conviene leggere anche variabili duali, vincoli attivi e scarti.

La dualità è particolarmente utile nei problemi di produzione, miscelazione, portafoglio, pianificazione e logistica. Nel problema dei trasporti, per esempio, i potenziali duali associati a origini e destinazioni permettono di controllare se una soluzione è migliorabile. Nei modelli di capacità, invece, i prezzi ombra indicano quali risorse conviene aumentare per ottenere il massimo beneficio marginale.

Casi limite

Se il primale è ammissibile e illimitato superiormente, il duale non può essere ammissibile: altrimenti la dualità debole fornirebbe un limite superiore finito. Se il duale è ammissibile e illimitato inferiormente, il primale non può essere ammissibile. Quando uno dei due problemi è non ammissibile, l’altro può essere non ammissibile oppure illimitato: la sola infeasibilità non basta, da sola, a dedurre un ottimo.

La dualità lineare è quindi un linguaggio di controllo: consente di costruire limiti, certificare ottimi, interpretare vincoli attivi e capire quali risorse guidano davvero la soluzione.

Vedi anche: programmazione lineare, metodo del simplesso, prezzo ombra, formulario di ricerca operativa ed esercizi su simplesso e dualità.