La dualità nella programmazione lineare
Nella programmazione lineare ogni problema di ottimizzazione, detto primale, può essere associato a un problema duale.
A cosa serve il problema duale?
Il problema duale (D) mi permette di ottenere una stima per difetto del problema (P).
$$ P = \begin{cases} z(x)=\min c^Tx \\ Ax = b \\ x \ge 0 \end{cases} $$
$$ D = \begin{cases} w(y)= \max b^Ty \\ A^Tb \le c \\\end{cases} $$
Una qualsiasi soluzione di base ammissibile del problema duale D è una stima per difetto della soluzione nel problema primale P.
Una volta ottenuto la stima per difetto e una per eccesso, posso circoscrivere le soluzioni del problema primale P senza dover calcolare la soluzione ottimale.
$$ w(y) \le z(x*) \le z(x) $$
Nota. La stima per eccesso del problema primale z(x) è una qualsiasi soluzione di base (SBA) del problema primale P.
Come trovare il problema duale
Per trovare un problema duale seguo queste regole
- I coefficienti della matrice duale sono la trasposta (AT) della matrice primale dei coefficienti (A).
- La funzione obiettivo duale è l'opposto della primale. Ad esempio, se min() è primale allora max() è duale, e viceversa.
- Se una variabile primale è libera, il corrispettivo vincolo duale è un'uguaglianza (=).
- Se una variabile primale è vincolata, il corrispettivo vincolo duale è una disuguaglianza (≤ o ≥).
- Se un vincolo primale è un'uguaglianza, la corrispettiva variabile duale è libera.
- Se un vincolo primale è una disuguaglianza (≤ o ≥), la corrispettiva variabile duale è vincolata.
Nota. Nelle diseguaglianze nei vincoli e nelle variabili vincolate devo ribaltare la relazione in almeno uno dei due casi. Ad esempio, se il vincolo di disuguaglianza primale è ≥ allora la corrispettiva variabile vincolata duale è ≤. In questo caso però i vincoli delle variabili vincolate primali mantengono la stessa relazione anche nei vincoli di disuaglianza duali. E viceversa.
Un esempio pratico
Ecco qualche esempio pratico di costruzione del problema duale
Esempio 1
Questo è il problema primale
$$ \begin{cases} \min z= 4x_1+2x_2 \\ x_1+x_2 \ge 2 \\ x_1-x_2 \ge 1 \\ x_1,x_2 \ge 0 \end{cases} $$
La matrice dei coefficienti è
$$ A = \begin{pmatrix} 1 & 1 \\ 1 & -1 \end{pmatrix} $$
Il vettore dei termini noti è
$$ b = \begin{pmatrix} 2 \\ 1 \end{pmatrix} $$
Il vettore dei costi è
$$ c = \begin{pmatrix} 4 \\ 2 \end{pmatrix} $$
La funzione obiettivo primale è di minimizzazione.
Pertanto la funzione obiettivo duale è di massimizzazione.
$$ \begin{cases} \max z= b^Ty \end{cases} $$
$$ \begin{cases} \max z= \begin{pmatrix} 2 \\ 1 \end{pmatrix}^T \begin{pmatrix} y_1 \\ y_2 \end{pmatrix} \end{cases} $$
$$ \begin{cases} \max z= \begin{pmatrix} 2 , 1 \end{pmatrix} \begin{pmatrix} y_1 \\ y_2 \end{pmatrix} \end{cases} $$
$$ \begin{cases} \max z= 2y_1+y_2 \end{cases} $$
Ora calcolo i vincoli del problema duale
$$ \begin{cases} \max z= 2y_1+y_2 \\ A^T y \le c \end{cases} $$
$$ \begin{cases} \max z= 2y_1+y_2 \\ \begin{pmatrix} 1 & 1 \\ 1 & -1 \end{pmatrix}^T \begin{pmatrix} y_1 \\ y_2 \end{pmatrix} \le \begin{pmatrix} 4 \\ 2 \end{pmatrix} \end{cases} $$
$$ \begin{cases} \max z= 2y_1+y_2 \\ \begin{pmatrix} 1 & 1 \\ 1 & -1 \end{pmatrix} \begin{pmatrix} y_1 \\ y_2 \end{pmatrix} \le \begin{pmatrix} 4 \\ 2 \end{pmatrix} \end{cases} $$
$$ \begin{cases} \max z= 2y_1+y_2 \\ y_1+y_2 \le 4 \\ y_1-y_2 \le 2 \end{cases} $$
A questo punto devo aggiungere solo i vincoli delle variabili y.
La relazione è opposta a quella nei vincoli del problema duale.
In questo caso i vincoli primali sono due diseguaglianze ≥ , quindi le variabili y sono entrambe ≤.
$$ \begin{cases} \max z= 2y_1+y_2 \\ \\ y_1+y_2 \le 4 \\ y_1-y_2 \le 2 \\ \\ y_1 \le 0 \\ y_2 \le 0 \end{cases} $$
Nota. Ecco la relazione tra il problema primale e duale. Una delle due è opposta.
E' uno degli esempi più semplici.
E così via.
