Problema del Flusso di Costo Minimo

uni
Questo è il modello base del Problema di Programmazione Matematica a Reti Capacitate (PLRC), ma per chiarezza e più facile consultazione, ripeterò qua considerazioni sul modello e altro.

Modello

Uguale a quello del Problema di Programmazione Matematica a Reti non Capacitate (PLRnC) solo che aggiungo la variabile $u$ che rappresenta le capacità di trasporto degli archi ovvero quanto flusso al massimo può passare sull’arco in questione.

$$\{\begin{array}{l}min{c}^T\cdot x\\ E\cdot x=b\\ 0\le x_{ij}\le u_{ij}\end{array}$$

dove $b$ sono i bilanci ai nodi
oppure

$$\{\begin{array}{l}\min {\sum }_{(i,j)\in A}{c}_{ij}\cdot x_{ij}\\ {\sum }_i{x}_{ij}-{\sum }_i{x}_{ji}=b_j\forall j(1)\\ l_{ij}\le x_{ij}\le u_{ij}\forall (i,j)\in A(2)\end{array}$$

dove $A$ è l’insieme degli archi, $l$ è la capacità minima, $u$ è la capacità massima, $(1)$ sono i vincoli di bilancio ai nodi e $(2)$ sono i vincoli di capacità.

Flusso di Base

Per definire un base nelle reti capacitate dobbiamo prima modificare leggermente il modello introducendo una variabile $w_{ij}$ che indica la portata residua di un arco:

$$\{\begin{array}{l}min{C}^T\cdot x\\ Ex=b\\ x_{ij}+w_{ij}=u_{ij}\\ x\ge 0\\ w\ge 0\end{array}$$

ovvero in forma matriciale, duale standard (Formato Duale Standard):

$$\{\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}$$

Con $M=\left(\begin{array}{cc}{E}^T& I\\ I& I\end{array}\right)$ di dimensione $2m\times (n-1+m)$ e rango $n-1+m$.