Dualità nella programmazione lineare

Ogni problema di programmazione lineare ha un problema associato, chiamato duale, costruito a partire dagli stessi dati, ma organizzati in modo diverso e con una propria interpretazione economica.

Studiare il duale è utile per due motivi: permette di stabilire un limite al valore ottimo del problema originale e di determinare il valore marginale delle risorse, cioè quanto vale un'unità aggiuntiva di ciascuna risorsa in termini di miglioramento dell'obiettivo.

Il problema del compratore

Un'officina ha tre impianti, ciascuno con un certo numero di ore disponibili a settimana, e produce due tipi di componenti:

Il problema dell'officina è il solito: quanti lotti produrre per massimizzare il profitto.

$$\begin{aligned} \max \ \omega &= 5x_1 + 4x_2 \\ x_1 &\le 4 \\ 3x_2 &\le 15 \\ 2x_1 + 2x_2 &\le 14 \\ x_1,\ x_2 &\ge 0 \end{aligned}$$

Ora arriva un compratore che vuole affittare tutte le ore degli impianti. Deve proporre un prezzo per ogni ora di ciascun impianto: $y_1$, $y_2$, $y_3$ (k€/h), non negativi.

L'officina accetta solo se cedere le ore le rende almeno quanto usarle per produrre. Le ore che servono per un lotto di C1 (1h dell'impianto 1 e 2h dell'impianto 3) devono valere almeno i 5 k€ di profitto di quel lotto, e lo stesso per C2:

$$\begin{aligned} y_1 + 2y_3 &\ge 5 \\ 3y_2 + 2y_3 &\ge 4 \end{aligned}$$

Tra tutte le offerte che l'officina accetterebbe, il compratore vuole spendere il meno possibile:

$$\min \ \varphi_D = 4y_1 + 15y_2 + 14y_3$$

Questo è il problema duale di quello dell'officina.

Le due soluzioni. L'officina massimizza producendo $x_1 = 4$ e $x_2 = 3$ lotti, con $\omega = 32$ k€. Il compratore minimizza offrendo $y = (1;\ 0;\ 2)$, con una spesa di $\varphi_D = 32$ k€. Lo stesso numero. Il prezzo giusto delle risorse è esattamente il profitto che l'officina saprebbe ricavarne.

La definizione

In generale, a un problema di massimo con vincoli $\le$ corrisponde un problema di minimo con vincoli $\ge$:

$$\begin{aligned} P: \quad \max \ \omega &= p^\top x \\ A\,x &\le b \\ x &\ge 0 \end{aligned}$$ $$\begin{aligned} D: \quad \min \ \varphi_D &= b^\top y \\ A^\top y &\ge p \\ y &\ge 0 \end{aligned}$$

La corrispondenza è simmetrica:

• a ogni vincolo del primale corrisponde una variabile del duale, e viceversa;
• i termini noti $b$ del primale diventano i coefficienti dell'obiettivo del duale, e i profitti $p$ diventano i termini noti;
• la matrice $A$ si traspone.

Il duale del duale è di nuovo il primale. I due problemi formano una coppia primale-duale, e quale si chiama "primale" è solo una convenzione.

Il duale del problema di produzione

Il problema degli articoli precedenti, $\max\ 4x_1 + 3x_2$ con $2x_1 + x_2 \le 14$ e $x_2 \le 6$, ha come duale:

$$\begin{aligned} \min \ \varphi_D &= 14\,y_1 + 6\,y_2 \\ 2\,y_1 &\ge 4 \\ y_1 + y_2 &\ge 3 \\ y_1,\ y_2 &\ge 0 \end{aligned}$$

La soluzione è $y_1 = 2$ e $y_2 = 1$, con $\varphi_D = 34$: di nuovo uguale all'ottimo del primale. E 2 e 1 sono proprio i coefficienti che il simplesso aveva lasciato nell'ultima iterazione, $\varphi = -34 + 2s_1 + s_2$, davanti agli scarti dei due vincoli. Il simplesso, risolvendo il primale, risolve di conseguenza anche il duale.

La dualità debole: un limite all'ottimo

Il legame tra i due problemi si riassume in una relazione. Scrivendo i vincoli come equazioni, con gli scarti $s$ nel primale ($A\,x + s = b$) e le eccedenze $z$ nel duale ($A^\top y - z = p$), vale sempre:

$$\omega + z^\top x + y^\top s = \varphi_D$$

La relazione, passo per passo

Si ottiene in tre passi, sostituendo in ciascun obiettivo l'equazione dei vincoli dell'altro problema.

1. L'obiettivo del primale. Dai vincoli del duale, $p = A^\top y - z$. Sostituendo in $\omega = p^\top x$:

$$\begin{aligned} \omega &= (A^\top y - z)^\top x \\ &= y^\top A\,x - z^\top x \end{aligned}$$

(si usa $(A^\top y)^\top = y^\top A$).

2. L'obiettivo del duale. Dai vincoli del primale, $b = A\,x + s$. Sostituendo in $\varphi_D = b^\top y$, che è lo stesso numero di $y^\top b$:

$$\begin{aligned} \varphi_D &= y^\top (A\,x + s) \\ &= y^\top A\,x + y^\top s \end{aligned}$$

3. Il termine comune. Entrambe le espressioni contengono $y^\top A\,x$. Dalla prima si ricava $y^\top A\,x = \omega + z^\top x$, e sostituendolo nella seconda:

$$\varphi_D = \omega + z^\top x + y^\top s$$

Le coppie $x_j, z_j$ e $s_i, y_i$ si chiamano variabili complementari.

Se le due soluzioni sono ammissibili, tutte le variabili sono $\ge 0$, quindi $z^\top x + y^\top s \ge 0$. Ne segue il teorema della dualità debole:

$$\omega \le \varphi_D$$

Qualsiasi soluzione ammissibile del problema di massimo vale al massimo quanto qualsiasi soluzione ammissibile del problema di minimo. In pratica:

• ogni soluzione ammissibile del primale dà un limite inferiore all'ottimo;
• ogni soluzione ammissibile del duale dà un limite superiore.

Basta un punto ammissibile per parte, anche scelto a caso, per sapere in che intervallo cade l'ottimo, senza risolvere niente. Nell'ottimo i due valori coincidono, come negli esempi: è la dualità forte.

Dalla relazione si vede anche perché nell'ottimo deve valere $z^\top x + y^\top s = 0$. Essendo una somma di prodotti non negativi, ogni prodotto è nullo: se una risorsa avanza ($s_i > 0$), il suo prezzo è zero ($y_i = 0$). È proprio il caso dell'impianto 2: nella produzione ottima lavora 9 ore su 15, e infatti il compratore offre $y_2 = 0$.

Costruire il duale di un problema qualsiasi

Non tutti i problemi sono nella forma (max, $\le$). Si può sempre riportarli a quella forma, oppure usare direttamente le regole di corrispondenza. Per un primale di massimo:

Un esempio:

$$\begin{aligned} \max \ \omega &= 2x_1 + 3x_2 \\ x_1 + x_2 &\le 5 \\ x_1 - x_2 &\ge -1 \\ x_1 \ge 0, &\quad x_2 \text{ libera} \end{aligned}$$

Il primo vincolo è $\le$, quindi $y_1 \ge 0$. Il secondo è $\ge$, quindi $y_2 \le 0$. $x_1 \ge 0$ dà un vincolo $\ge$, e $x_2$ libera dà un vincolo di uguaglianza:

$$\begin{aligned} \min \ \varphi_D &= 5y_1 - y_2 \\ y_1 + y_2 &\ge 2 \\ y_1 - y_2 &= 3 \\ y_1 \ge 0, &\quad y_2 \le 0 \end{aligned}$$

Riepilogo

• Ogni problema di PL ha un duale: i vincoli diventano variabili, i termini noti diventano l'obiettivo, la matrice si traspone.
• Dualità debole: il valore di una soluzione ammissibile del problema di massimo non supera mai quello di una del problema di minimo. Ogni soluzione ammissibile dà un limite all'ottimo.
• Nell'ottimo i due valori coincidono, e una risorsa che avanza ha prezzo zero.
• Il simplesso fornisce la soluzione duale nella riga dell'obiettivo, in corrispondenza degli scarti.