Duale Ausiliario

uni
A partire da un problema in Formato Duale Standard:

$$(D)=\{\begin{array}{l}min{y}^{T}b\\ A^{T}y=c\\ y\ge 0\end{array}$$

costruisco il suo Duale Associato + tante epsilon quante sono le righe del duale moltiplicandole per l’identità $(i)$

$$(D_{aux})=\{\begin{array}{l}min{\sum }_{i=0}^n{ϵ}_i\\ y^{T}A+{ϵ}^T=c^T\\ y\ge 0\\ ϵ\ge 0\end{array}$$

Utilizzo del Duale Ausiliario

$$\begin{array}{c}(D)\{\begin{array}{l}\min b^{T}y\\ A^{T}y=c\\ y\ge 0\end{array}\to (D_{aux})\{\begin{array}{l}\min {\sum }_i{ϵ}_i\\ A^{T}y+ϵ=c\\ y\ge 0\\ ϵ\ge 0\end{array}\\ soluzionedibaseconB=\{01...2n\}:\\ \left(\begin{array}{c}y\\ ϵ\end{array}\right)=\begin{array}{c}\{\begin{array}{l}{y}_1\\ y_2\\ ...\\ y_n\end{array}\\ \{\begin{array}{l}{ϵ}_1\\ {ϵ}_2\\ ...\\ {ϵ}_n\end{array}\end{array}\left(\begin{array}{c}0\\ 0\\ ...\\ 0\\ c_1\\ c_2\\ ...\\ c_n\end{array}\right)\end{array}$$

Il duale ausiliario (D_aux) viene utilizzato per trovare una base ammissibile in un problema in forma duale std (D).
Una volta costruito il duale ausiliario, la base costituita dai primi 2n vincoli (con n dimensione del vettore y) è una base la cui soluzione di base è ammissibile (soluzione: tutte le y a 0 e tutte le epsilon uguali alle relative c). Da questa soluzione di base possiamo applicare il simplesso Duale fino all’ottimo.

• Se il valore ottimo di (D_aux) è maggiore di zero allora (D) non ha soluzioni ammissibili.
• Se il valore ottimo di (D_aux) è uguale a zero, allora (D) ha almeno una soluzione di base ammissibile, che si può costruire a partire da una base ottima per (D_aux).

ATTENZIONE: prima di costruire (D_aux) è necessario fare in modo che tutte le c in (D) siano ≥ 0, semplicemente cambiando semmai di segno alle equazioni.
Altrimenti la soluzione di base di (D_aux) indicata dai primi 2n indici non sarebbe ammissibile.