Problema dei Potenziali su Reti

uni
Il problema dei potenziali su rete è il Duale della forma matriciale duale standard del Problema del Flusso di Costo Minimo:

$$(flussominimo)\{\begin{array}{l}\min {\left(\begin{array}{c}c\\ 0\end{array}\right)}^T\left(\begin{array}{c}x\\ w\end{array}\right)\\ {\left(\begin{array}{cc}{E}^T& I\\ 0& I\end{array}\right)}^T\left(\begin{array}{c}x\\ w\end{array}\right)=\left(\begin{array}{c}b\\ u\end{array}\right)\\ (x,w)\ge 0\end{array}$$

Modello

$$\{\begin{array}{l}\max (bu{)}^T\left(\begin{array}{c}\pi \\ \mu \end{array}\right)\\ \left(\begin{array}{cc}{E}^T& I\\ 0& I\end{array}\right)\left(\begin{array}{c}\pi \\ \mu \end{array}\right)\le \left(\begin{array}{c}c\\ 0\end{array}\right)\end{array}$$

che equivale a:

$$\{\begin{array}{l}\max {\pi }^{T}b+{\mu }^{T}u\\ {\pi }^{T}E+{\mu }^T\le c^T\\ \mu \le 0\end{array}$$

Ammissibilità e Degenere

Il potenziale di base $\overline{\pi }$ è ammissibile se e solo se i costi ridotti ($c_{ij}^{\pi }={\pi }_i+c_{ij}-{\pi }_j$)degli archi in $L$ sono non negativi ed i costi ridotti degli archi in $U$ sono non positivi.