Le condizioni di ortogonalità del problema duale

Le condizioni di ortogonalità sono usate nella programmazione lineare per trovare le soluzioni ottime a un problema duale.

Date due soluzioni ammissibili x e y del problema primale e duale, sono soluzioni ottime se soddisfano la seguente condizione di ortogonalità. $$ (c^T - Ay ) x =0 $$ e simmetricamente $$ y ( A x - b ) = 0 $$

Come trovare le soluzioni ottimali del duale dal primale

Ho un problema primale di minimizzazione

$$ \begin{cases}
\min z(x) = x_2+2x_3-x_4 \\ \\
x_1-x_3-x_4 \ge 1 \\
2x_1+x_2 +x_4 \le 3 \\
x_2 +x_3-2x_4 = 4 \\ \\
x_1, x_2 \ge 0 \\
x_3 \le 0
\end{cases}
$$

Il relativo problema duale è

$$ \begin{cases}
\max w(y) = y_1+3y_2+4y_3 \\ \\
y_1+2y_2 \ge 0 \\
y_2+y_3 \ge 1 \\
-y_1+y_3 \le 2 \\
-y_1+y_2-2y_3 = -1
\\ \\
y_1 \le 0\\
y_2 \ge 0
\end{cases}
$$

Soluzione del problema primale

Calcolo una soluzione di base ammissibile per il problema primale.

Scelgo le colonne [1,2,4] della matrice A dei coefficienti.

Ottengo così una matrice quadrata di base A_B con i coefficienti delle colonne selezionate.

Poi calcolo la matrice inversa della matrice di base A_B.

$$ \begin{pmatrix} 1 & 0 & -1 \\ 2 & 1 & 1 \\ 0 & 1 & -2 \end{pmatrix}^{-1} = \begin{pmatrix} 0.6 & 0.2 & -0.2 \\ -0.8 & 0.4 & 0.6 \\ -0.4 & 0.2 & -0.2 \end{pmatrix} $$

Le soluzioni di base sono le seguenti:

$$ x = A^{-1}b = \begin{pmatrix} 1 & 0 & -1 \\ 2 & 1 & 1 \\ 0 & 1 & -2 \end{pmatrix}^{-1} = \begin{pmatrix} 0.6 & 0.2 & -0.2 \\ -0.8 & 0.4 & 0.6 \\ -0.4 & 0.2 & -0.2 \end{pmatrix} \begin{pmatrix} 1 \\ 3 \\ 4 \end{pmatrix} = \begin{pmatrix} 0.4 \\ 2.8 \\ -0.6 \end{pmatrix} $$

E' una soluzione di base ammissibile del problema primale.

Verifica. Faccio una verifica usando le soluzioni X [ 0.4 , 2.8 , 0. -0.6 ] $$ \begin{cases}
\min z(x) = x_2+2x_3-x_4 \\ \\
x_1-x_3-x_4 \ge 1 \\
2x_1+x_2 +x_4 \le 3 \\
x_2 +x_3-2x_4 = 4 \\ \\
x_1, x_2 \ge 0 \\
x_3 \le 0
\end{cases}
$$ $$ \begin{cases}
\min z(x) = 2.8+2(0)-(-0.6) \\ \\
0.4-0-(-0.6) \ge 1 \\
2(0.4)+2.8 +(-0.6) \le 3 \\
2.8 +0-2(-0.6) = 4 \\ \\
0.4, 2.8 \ge 0 \\
0 \le 0
\end{cases}
$$ $$ \begin{cases}
\min z(x) = 3.4 \\ \\
1 \ge 1 \\
3 \le 3 \\
4 = 4 \\ \\
0.4, 2.8 \ge 0 \\
0 \le 0
\end{cases}
$$Le soluzioni sono ammissibili e risolvono il problema.

Ora verifico se è anche una soluzione ottimale

$$ c^T - c^T_B A^{-1}_B A $$

$$ (0,1,2,-1) - (0, 1, -1 ) \begin{pmatrix} 0.6 & 0.2 & -0.2 \\ -0.8 & 0.4 & 0.6 \\ -0.4 & 0.2 & -0.2 \end{pmatrix} \begin{pmatrix} 1 & 0 & -1 & -1 \\ 2 & 1 & 0 & 1 \\ 0 & 1 & 1 & -2 \end{pmatrix} $$

$$ (0,1,2,-1) - (0, 1, -1 ) \begin{pmatrix} 1 & 0 & 0 & 0 \\ 0 & 1 & 1 & 0 \\ 0 & 0 & 0 & 1 \end{pmatrix} $$

$$ (0,1,2,-1) - (0, 1, 1.2, -1 ) $$

$$ (0,0,0.8,0) $$

In questo caso è una soluzione ottimale.

Essendo una soluzione ottimale, posso calcolare direttamente anche la soluzione del problema duale.

Soluzione del problema duale

Ora calcolo una soluzione di base ammissibile del problema duale.

Conosco già il risultato ottimo per il problema duale.

Secondo il teorema della dualità forte una soluzione ottimale del primale vale anche per il duale e viceversa.

$$ c^Tx = y^T b $$

Posso riscrivere la componente b in Ax

$$ c^Tx = y^T Ax $$

$$ \frac{c^Tx}{Ax} = y^T $$

$$ \frac{c^T}{A} = y^T $$

$$ c^T A^{-1} = y^T $$

In questo caso si tratta dei costi C_B e di una matrice di base A_B

$$ c^T_B A^{-1}_B = y^T $$

$$ (0,1,-1) \begin{pmatrix} 0.6 & 0.2 & -0.2 \\ -0.8 & 0.4 & 0.6 \\ -0.4 & 0.2 & -0.2 \end{pmatrix} = y^T $$

$$ \begin{pmatrix} -0.4 \\ 0.2 \\ 0.8 \end{pmatrix} = \begin{pmatrix} y_1 \\ y_2 \\ y_3 \end{pmatrix}$$

E' una soluzione ammissibile del problema duale.

Verifica. Faccio una verifica usando le soluzioni Y [ -0.4 , 0.2 , 0.8 ] $$ \begin{cases}
\max w(y) = y_1+3y_2+4y_3 \\ \\
y_1+2y_2 \ge 0 \\
y_2+y_3 \ge 1 \\
-y_1+y_3 \le 2 \\
-y_1+y_2-2y_3 = -1
\\ \\
y_1 \le 0\\
y_2 \ge 0
\end{cases}
$$ $$ \begin{cases}
\max w(y) = -0.4+3(0.2)+4(0.8) \\ \\
-0.4+2(0.2) \ge 0 \\
0.2+0.8 \ge 1 \\
-(-0.4)+0.8 \le 2 \\
-(-0.4)+0.2-2(0.8) = -1
\\ \\
-0.4 \le 0\\
0.2 \ge 0
\end{cases}
$$ $$ \begin{cases}
\max w(y) = 3.4 \\ \\
0 \ge 0 \\
1 \ge 1 \\
1.2 \le 2 \\
-1 = -1
\\ \\
-0.4 \le 0\\
0.2 \ge 0
\end{cases}
$$

Le soluzioni sono ammissibili e risolvono il problema duale.

Inolte, essendo una soluzione ottimale la soluzione del duale è uguale alla soluzione del primale.

$$ \max w(y) = \min z(x) = 3.4 $$ Se la soluzione è ottima per il primale è ottima anche per il duale.

Il risultato è lo stesso.

Nota. Il risultato vale anche all'inverso. Conoscendo la soluzione ottimale del problema duale Y [ -0.4 , 0.2 , 0.8 ] grazie all'ortogonalità potrei ottenere la soluzione ottimale del problema primale.

Come trovare le soluzioni ottimali del primale dal duale

Se conosco la soluzione ottimale del problema duale, posso calcolare anche la soluzione del problema primale.

Esempio

Nell'esempio precedente il problema duale

$$ \begin{cases}
\max w(y) = y_1+3y_2+4y_3 \\ \\
y_1+2y_2 \ge 0 \\
y_2+y_3 \ge 1 \\
-y_1+y_3 \le 2 \\
-y_1+y_2-2y_3 = -1
\\ \\
y_1 \le 0\\
y_2 \ge 0
\end{cases}
$$

Ha la seguente soluzione ottimale Y [ -0.4 , 0.2 , 0.8 ].

$$ \begin{cases}
\max w(y) = 3.4 \\ \\
0 \ge 0 \\
1 \ge 1 \\
1.2 \le 2 \\
-1 = -1
\\ \\
-0.4 \le 0\\
0.2 \ge 0
\end{cases}
$$

Seleziono le equazioni dei vincoli del problema duale che sono soddisfatti con un'uguaglianza dalle soluzioni Y.

In questo caso, la prima, la seconda e la quarta equazione.

La terza equazione 1.2 ≤ 2 la escludo perché è soddisfatta soltanto tramite la diseguaglianza.

$$ \begin{cases}
y_1+2y_2 \ge 0 \\
y_2+y_3 \ge 1 \\
-y_1+y_2-2y_3 = -1
\end{cases}
$$

Ottengo così una matrice quadrata dei coefficienti.

$$ D_B = \begin{pmatrix}
1 & 2 & 0 \\
0 & 1 & 1 \\
-1 & 1 & -2
\end{pmatrix}
$$

So già che per calcolare le soluzioni del duale dal primale posso applicare la stessa formula

$$ c^T_B A^{-1}_B = y^T $$

In questo caso, però, devo calcolare le soluzioni del primale dal duale.

Ora i costi e la matrice dei coefficienti da considerare sono quelli del problema duale

Pertanto, adeguo la formula.

$$ c^T_B D^{-1}_B = x^T $$

Quindi sostituisco i valori e calcolo la soluzione.

$$ (1,3,4) D^{-1}_B = x^T $$

$$ (1,3,4) \begin{pmatrix}
1 & 2 & 0 \\
0 & 1 & 1 \\
-1 & 1 & -2
\end{pmatrix}^{-1} = x^T $$

$$ (1,3,4) \begin{pmatrix}
0.6 & -0.8 & -0.4 \\
0.2 & 0.4 & 0.2 \\
-0.2 & 0.6 & -0.2
\end{pmatrix} = \begin{pmatrix}
x_1 \\
x_2 \\
x_3
\end{pmatrix} $$

$$ \begin{pmatrix}
0.4 \\ 2.8 \\ -0.6
\end{pmatrix} = \begin{pmatrix}
x_1 \\
x_2 \\
x_3
\end{pmatrix} $$

Ho così trovato anche le soluzioni ottimali del problema primale a partire dalle soluzioni del primale.

Verifica. Faccio una rapida verifica. Uso le soluzioni X [ 0.4 , 2.8 , 0. -0.6 ] nel problema primale $$ \begin{cases}
\min z(x) = x_2+2x_3-x_4 \\ \\
x_1-x_3-x_4 \ge 1 \\
2x_1+x_2 +x_4 \le 3 \\
x_2 +x_3-2x_4 = 4 \\ \\
x_1, x_2 \ge 0 \\
x_3 \le 0
\end{cases}
$$ $$ \begin{cases}
\min z(x) = 2.8+2(0)-(-0.6) \\ \\
0.4-0-(-0.6) \ge 1 \\
2(0.4)+2.8 +(-0.6) \le 3 \\
2.8 +0-2(-0.6) = 4 \\ \\
0.4, 2.8 \ge 0 \\
0 \le 0
\end{cases}
$$ $$ \begin{cases}
\min z(x) = 3.4 \\ \\
1 \ge 1 \\
3 \le 3 \\
4 = 4 \\ \\
0.4, 2.8 \ge 0 \\
0 \le 0
\end{cases}
$$Le soluzioni sono ammissibili e risolvono il problema. Inoltre, è una soluzione ottimale del problema primale perché derivano dalle soluzioni ottimali del problema duale.