Teoria della Dualità

uni
Dato un Problema di Programmazione Lineare (PL) in Formato Primale Standard ne individuiamo il suo complementare duale:

$$(P)\{\begin{array}{l}max{c}^T\cdot x\\ Ax\le b\end{array}\to (D)\{\begin{array}{l}min{b}^T\cdot y\\ A^{T}y=c\\ y\ge 0\end{array}$$

Questa è una operazione di dualità, trovare il duale di un primale; Inoltre il duale di un duale è il suo primale!!

Teorema della Dualità Forte / degli Scarti Complementari

Sia $(P)$ un problema PL con Duale (D), se $x,y$ sono soluzioni ammissibili di $(P),(D)$ e inoltre:

1. ogni volta che $x_j\ne 0$, $y$ soddisfa il $j$-esimo vincolo con uguaglianza
2. ogni volta che $y_i\ne 0$, $x$ soddisfa il $i$-esimo vincolo con uguaglianza
   Allora $x$ e $y$ sono entrambe Ottime.
   Sappiamo che una base del primale è anche una base del duale.
   QUINDI:
3. Dato un vertice del problema primale, se nella sua duale la soluzione generata dalla stessa base è ammissibile, Allora la soluzione di base di quella stessa base è Ottimo in entrambi i problemi.
4. Se uno degli elementi di $x_B$ è $0$, la soluzione di base è Degenere.
5. Se tutti gli elementi di $y_B$ sono $\ge 0$ allora la soluzione di base è ammissibile (vertice).

Test dell’Ottimalità

Per sapere se un dato vertice di un $(P)$ in forma primale è ottimo:

1. trovo la base che lo genera
2. trovo la duale di $(P)$
3. dal sistema $A^{T}y=c$ pongo a $0$ le componenti Non Di Base e risolvo
4. se risolvendo le componenti Di Base tornano tutte positive, scopriamo che (la soluzione di base è ammissibile poiché rispetta tutti i vincoli $y\ge 0$ e di conseguenza) la nostra base genera un ottimo in entrambi i problemi.