Teorema forte della dualità

Data una coppia di problemi primale duale P e D, se uno dei due problemi ammette una soluzione ottima finita allora anche l’altro problema ammette una soluzione ottima finita ed i valori ottimi delle funzioni obiettivo coincidono, cioè $\underline{c}^T \underline{x}^* = \underline{b}^T \underline{w}^*$

Dal teorema della dualità forte ricaviamo che, data la base ottima $B$ del primale, è possibile calcolare velocemente la soluzione ottima del duale D tramite l’equazione: $\underline{w}^{x^T} = \underline{c}_B^T A_B^{-1}$

Riassumendo

• $P$ illimitato $\Rightarrow$ $D$ non ammissibile
• P ha soluzione ottima finita $\iff$ $D$ ha soluzione ottima finita (ed i valori delle loro fo coincidono)
• $P$ è inammissibile $\Rightarrow$ $D$ illimitato o inammissibile

Complementary Slackness Theorem

Data la coppia di soluzioni $\underline{x}$ e $\underline{w}$ rispettivamente ammissibili per P e D, $\underline{x}$ e $\underline{w}$ sono ottime per P e D se e solo se

• $s_jw_j = (\underline{a}^j \underline{x}-b_j)w_j = 0$ $j = 1,..,m$
• $v_ix_i = (c_i - \underline{a}_i^T\underline{w})x_i = 0$ $i = 1,..,n$

(condizioni di ortogonalità)

dove $\underline{a}^j$ è la $j$-esima riga di $A$ e $\underline{a}_i$ è la $i$-esima colonna di $A$

Conseguenze delle condizioni di ortogonalità

• per ogni vincolo non soddisfatto all’uguaglianza dalla soluzione ottima di P, la variabile duale $w_j$ associata a questo vincolo deve essere uguale a zero nella soluzione ottima di D
• per ogni variabile $x_i$ non nulla nella soluzione ottima di P, il corrispondente vincolo in D deve essere soddisfatto all’uguaglianza dalla soluzione ottima di D

Calcolo della soluzione ottima duale

Sia P un problema di PL in forma standard e sia $x?*$ una soluzione di base ammissibile ottima (non degenere) di P

A partire da $x^*$, le condizioni degli scarti complementari individuano un’unica soluzione ottima del duale

Se P è in forma standard il sistema della prima condizione è sempre soddisfatto, infatti poichè $x^*$ è una soluzione di base ammissibile ottima (non degenere) il sistema della seconda condizione si riduce a: $(c_i-\underline{a}_j^T\underline{w}) = 0$ $i \in B$ $\Rightarrow \underline{c}_B -A_B^T \underline{w} = \underline{0} \Rightarrow A_B^T \underline{w}=\underline{c}_B$