Problema del flusso di costo minimo

Prima di affrontare il problema MCF, fissiamo delle nozioni preliminari.

Pseudoflusso

Uno pseudoflusso è un vettore $x$ (quindi nella pratica lo usiamo come un flusso) che rispetta i vincoli di capacità ma non deve necessariamente soddisfare quelli di bilanciamento (e per questo NON è un flusso):

• Vincoli di capacità:

  $$ 0\leq x_{ij}\leq u_{ij}\quad(i,j)\in A $$

• Definiamo lo sbilanciamento $e_x(i)$ di un nodo $i$ in $x$ come:

  $$ e_x(i) =\sum_{(i,j)\in BS(i)}x_{ij}-\sum_{(i,j)\in FS(i)}x_{ij}-b_i $$

  E possiamo vedere $e_x$ come il vettore degli sbilanciamenti.

• Dato uno pseudoflusso $x$, i nodi sbilanciati rispetto a $x$ fanno parte di uno dei due insiemi:

  • $O_x=\{i\in N|e_x(i)>0\}$;
  • $D_x=\{i\in N|e_x(i)<0\}$.

  I nodi di $O_x$ sono quelli con eccesso di flusso (cioè che ricevono più flusso di quanto ne esce), mentre i nodi in $D_x$ sono quelli con difetto di flusso (ne esce più di quanto ne entra). Se entrambi gli insiemi sono vuoti (e quindi tutti gli $e_x(i)$ valgono 0) allora $x$ è un flusso.

• Lo sbilanciamento complessivo di $x$ è definito come:

  $$ g(x)=\sum_{i\in O_x}e_x(i)=-\sum_{j\in D_x}e_x(j) $$

Cammini aumentanti (pt. 2 - la vendetta)

Lavorando con gli pseudoflussi, la nozione di cammino aumentante si fa più generale.

Il grafo residuo che abbiamo costruito precedentemente si generalizza facilmente al problema MCF:

• Costruiamo il grafo residuo allo stesso modo;
• Ogni arco però avrà un costo;
  • In un arco concorde $(i,j)$ di $G_x$ il costo è $c_{ij}$;
  • In un arco discorde $(j,i)$ di $G_x$ il costo è invece $-c_{ij}$.

Un cammino $P$ tra $i$ e $j$ in $G_x$ verrà detto cammino aumentante e avrà le proprietà:

• I suoi archi possono essere partizionati in $P^+$ e $P^-$;
• La sua capacità $\theta(P,x)$ è definita come al solito;
• Un cammino aumentante tra $i$ e $j$ viene anche detto ciclo aumentante.

Dato uno pseudoflusso $x$ e un cammino aumentante $P$, possiamo inviare un certo numero di unità di flusso $\theta$ (con $0\leq\theta\leq\theta(P,x)$) lungo $P$ tramite l'operazione già vista $x(P,\theta)$.

<aside> 🚧 Da ora in poi $x(P,\theta)$ verrà indicato anche come $x\oplus P\theta$.

</aside>