Home » Intelligenza Artificiale » 📋 URL
L’insieme delle soluzioni di un problema lineare è rappresentato da un poliedro, ovvero dall’intersezione di un numero finito di semispazi affini e iperpiani.
Tramite l’interpretazione geometrica del poliedro possiamo anche analizzare ciò che significa trovare una soluzione a un problema di ottimizzazione. Dal punto di vista geometrico infatti, la funzione che stiamo cercando di massimizzare/minimizzare cx è dal punto di vista geometrico, una retta, e nella ricerca della soluzione ottima per un problema stiamo cercando il vertice del poliedro che soddisfa tutti i vincoli posti.
Dualità
Ad ogni problema di ottimizzazione è associato un altro problema di ottimizzazione: il cosiddetto problema duale.
Quando trasformiamo un problema nella sua forma duale stiamo, di fatto, cercando un lower bound al problema di partenza (primale).
Per passare da un problema di programmazione primale al suo duale si utilizzano delle trasformazioni, riportate in tabella seguente:
Esercizio: dato il seguente problema primale, lo si scriva nella sua forma duale.
\begin{cases}\min{(2x_2+x_3-3x_4)}\\x_1-x_2+2x_4\geq2& (u_1)\\2x_2+x_3=4&(u_2)\\2x_1-x_3+x_4\leq1& (u_3)\\x_1\geq0\\x_2\geq0\\x_3,\,x_4&\text{libere}\end{cases}Soluzione
Come primo passaggio sappiamo, dalle regole di trasformazione di Farkas, che poiché il problema è posto col minimo deve essere trasformato in massimo. Si avrà dunque che la funzione obiettivo, da \min(2x_2+x_3-3x_4) diventa \max(2u_1+4u_2+u_3), dove come coefficienti di u_1,\,u_2,\,u_3 sono stati utilizzati i termini noti delle equazioni/disequazioni corrispondenti.
Bisogna poi scrivere le variabili del problema. Dovremo scrivere una variabile per il problema duale per ogni vincolo presente nel problema primale. Si utilizzano sempre le regole di Farkas per trasformare le disuguaglianze/uguaglianze nelle loro controparti. Si ottengono le seguenti trasformazioni:
u_1\geq0\\u_2\,\text{libera}\\u_3\leq0Per finire è necessario scrivere i vincoli del problema, e per ottenerli si possono sfruttare u_1,\,u_2,\,u_3 scritti in forma matriciale, posizionandoli sopra ai coefficienti della funzione obiettivo originale:
\begin{matrix}
u_1 \\
u_2 \\
u_3
\end{matrix}\begin{bmatrix}
1 & -1 & 0 & 2 \\
0 & 2 & 1 & 0 \\
2 & 0 & -1 & 1
\end{bmatrix}\\\,\,\,\,\,\,\,\,\,0 \,\,\,\,\,\,\,\,\, 2 \,\,\,\,\,\,\,\,\, 1 \,\,\,\,-3Ogni colonna della matrice è ora sufficiente scrivere le seguenti relazioni:
\begin{cases}u_1+2u_3\leq0\\-u_1+2u_2\leq2\\u_2-u_3=1\\u_1+u_3=-3\end{cases}Abbiamo così ottenuto i nuovi vincoli, dove le varie uguaglianze/disuguaglianze sono state sostituite nel precedente sistema tenendo conto delle regole di Farkas, in particolare, poiché lo 0 è ad esempio coefficiente di x_1 e x_2 nel problema primale è \geq0, allora tramite i lemmi di Farkas so che nel duale dovrà essere \leq del numero che è scritto sotto la matrice—0 in questo caso. Per il secondo coefficiente 2 si fa la stessa cosa: poiché x_2 nel problema primale è anch’esso \geq0 si avrà lo stesso risultato di x_1. Per x_3 e x_4 però che sono libere nel primale, nel duale dovranno essere messe con l’=.
Il problema duale finale sarà dunque il seguente:
\begin{cases}\max(2u_1+4u_2+u_3)\\u_1+2u_3\leq0\\-u_1+2u_2\leq2\\u_2-u_3=1\\2u_1+u_3=-3\\u_1\geq0\\u_2\,\text{libera}\\u_3\leq0\end{cases}Esercizio: dato il seguente problema primale, lo si scriva nella sua forma duale.
\begin{cases}
\min(x_2+3x_3+7x_4)\\
x_1-x_2+2x_4\leq2 & (u_1)\\
5x_2+x_3=4 &(u_2)\\
x_1-x_3+2x_4\geq1 &(u_3)\\
x_1,\,x_2>0\\
x_3,\,x_4 &\text{libere}
\end{cases}Soluzione
Per le variabili del problema di ha, tramite Farkas
u_1\leq0\\u_2\text{ libera}\\u_2\geq0La matrice per la traduzione è la seguente
\begin{matrix}
u_1 \\
u_2 \\
u_3
\end{matrix}\begin{bmatrix}
1 & -1 & 0 & 2 \\
0 & 5 & 1 & 0 \\
1 & 0 & -1 & 2
\end{bmatrix}\\\,\,\,\,\,\,\,0 \,\,\,\,\,\,\,\,\, 1 \,\,\,\,\,\,\,\,\,\,\, 3 \,\,\,\,\,\,\,\,7Da cui si ottiene poi l’espressione finale del problema duale utilizzando le trasformazioni di Farkas
\begin{cases}
\max(2u_1+4u_2+u_3)\\
u_1+u_3<0\\
-u_1+5u_2<1\\
u_2-u_3=3\\
2u_1+u_3=7\\
u_1\leq0\\
u_2\text{ libera}
\\u_2\geq0
\end{cases}