5.1 Il problema del flusso massimo

Parte 3 · Flussi · Capitolo 5 · Capitolo 5: Flusso massimo · Dispensa, volume 3 (PDF) · Esercizi: Flusso massimo · App: Flusso massimo: Ford–Fulkerson ed Edmonds–Karp

Definizione 5.1: problema di flusso massimo

Sia \(G=(N,A)\) un grafo diretto con nodi \(n=|N|\) e archi \(m=|A|\), due nodi distinti \(s\), il source e \(t\), sink e capacity \(u_{ij} \ge 0\) per ogni arco \((i,j) \in A\).

• Un flusso ammissibile è un vettore \(\vet{x} \in \R^m\) con \(0 \le x_{ij} \le u_{ij}\) per ogni arco \((i,j) \in A\) e conservazione del flusso in ogni nodo diverso da \(s\) e \(t\):

  \[ \sum_{(i,j) \in \delta^+(i)} x_{ij} \;-\; \sum_{(j,i) \in \delta^-(i)} x_{ji}=0, \quad \forall i \in N \setminus \{s,t\}. \]

• Il valore del flusso è il deflusso netto della sorgente:

  \[ v=\sum_{(s,j) \in \delta^+(s)} x_{sj} \;-\; \sum_{(j,s) \in \delta^-(s)} x_{js} . \]

• Il problema di flusso massimo richiede un flusso ammissibile di valore massimo, un flusso massimo. Suo il valore è indicato con \(\tilde{v}\).

• Le capacità sono finite e il flusso \(\vet{x}=\vet{0}\), di valore \(0\), è sempre fattibile.

• I nodi diversi da \(s\) e \(t\) trasmettono tutto ciò che ricevono: il flusso lascia \(s\) e viaggia attraverso rete verso \(t\).

• Come in Capitolo 4 «Modelli di flusso di rete», \(\delta^+(i)\) e \(\delta^-(i)\) sono gli archi che escono ed entrano nel nodo \(i\), e gli archi sono numerato \(a_1,a_2,\dots,a_m\) in ordine lessicografo.

Esempio 5.1: la rete di riferimento

Diamo capacità al grafo di riferimento di Capitolo 1 «Grafi», con sorgente \(s=1\) e lavello \(t=6\):

arco	\((1,2)\)	\((1,3)\)	\((2,4)\)	\((3,2)\)	\((3,5)\)	\((4,3)\)	\((4,6)\)	\((5,4)\)	\((5,6)\)
\(u_{ij}\)	\(5\)	\(4\)	\(3\)	\(2\)	\(4\)	\(2\)	\(4\)	\(2\)	\(3\)
\(\bar{x}_{ij}\)	\(3\)	\(0\)	\(3\)	\(0\)	\(2\)	\(2\)	\(1\)	\(0\)	\(2\)

Nella figura ogni arco porta la sua capacità \(u_{ij}\).

Il flusso \(\bar{\vet{x}}\) della tabella è fattibile. Ad esempio, nel nodo \(4\) l'afflusso è \(\bar{x}_{24}+\bar{x}_{54}=3+0=3\) e il deflusso è \(\bar{x}_{43}+\bar{x}_{46}=2+1=3\). Il suo valore è

\[ v=\bar{x}_{12}+\bar{x}_{13}=3+0=3 , \]

e il nodo \(6\) riceve unità \(\bar{x}_{46}+\bar{x}_{56}=1+2=3\). Nella figura ogni arco porta \(\bar{x}_{ij}/u_{ij}\): gli archi con \(0<\bar{x}_{ij}<u_{ij}\) sono blu, gli archi saturati (\(\bar{x}_{ij}=u_{ij}\)) rosso e gli archi vuoti grigi e tratteggiati.

5.1.1 Il modello LP

• Usiamo una variabile continua \(x_{ij}\) per ogni arco \((i,j) \in A\), il flusso sull'arco, e una variabile \(v\), il valore del flusso.

Utilizzando queste variabili, un modello LP per il problema del flusso massimo si legge come segue:

\[\begin{align*} && \max \;\; v \label{mf:obj} \tag{5.1a}\\[1ex] && \text{subject to} \quad \sum_{(s,j) \in \delta^+(s)} x_{sj} - \sum_{(j,s) \in \delta^-(s)} x_{js} &= v, & \label{mf:cons-s} \tag{5.1b}\\[1ex] && \sum_{(i,j) \in \delta^+(i)} x_{ij} - \sum_{(j,i) \in \delta^-(i)} x_{ji} &= 0, & \forall i \in N \setminus \{s,t\}, \label{mf:cons} \tag{5.1c}\\[1ex] && \sum_{(t,j) \in \delta^+(t)} x_{tj} - \sum_{(j,t) \in \delta^-(t)} x_{jt} &= -v, & \label{mf:cons-t} \tag{5.1d}\\[1ex] && x_{ij} &\le u_{ij}, & \forall (i,j) \in A, \label{mf:cap} \tag{5.1e}\\[1ex] && x_{ij} &\ge 0, & \forall (i,j) \in A, \label{mf:dom} \tag{5.1f}\\[1ex] && v &\in \R. & \label{mf:domv} \tag{5.1g} \end{align*}\]

Questo modello LP è denominato modello \(\mathrm{MF}\).

• Descrizione della funzione obiettivo e dei vincoli del modello \(\mathrm{MF}\):

  • la funzione obiettivo \(\eqref{mf:obj}\) massimizza il valore del flusso;

  • Il vincolo  \(\eqref{mf:cons-s}\) afferma che il deflusso netto di \(s\) è \(v\) e il vincolo \(\eqref{mf:cons-t}\) che l'afflusso netto di \(t\) è \(v\);

  • Vincoli  \(\eqref{mf:cons}\) sono i vincoli di conservazione del flusso degli altri nodi;

  • I vincoli  \(\eqref{mf:cap}\) impongono le capacità, mentre i vincoli \(\eqref{mf:dom}\) e \(\eqref{mf:domv}\) definiscono le variabili del modello LP.

• Ogni arco contribuisce con \(+x_{ij}\) alla fila della coda e \(-x_{ij}\) alla fila della testa, quindi la mano sinistra i lati di \(\eqref{mf:cons-s}\)–\(\eqref{mf:cons-t}\) si sommano a zero: il vincolo \(\eqref{mf:cons-t}\) segue dagli altri.

• In Capitolo 4, Sezione «Casi particolari» il problema del flusso massimo è un modello di flusso a costo minimo: zero saldi e zero costi, più il arco \((t,s)\) con portata \(+\infty\) e costo \(-1\). Chiamando \(v\) il flusso \(x_{ts}\) su questo arco, \(\eqref{mf:cons-s}\)–\(\eqref{mf:cons-t}\) sono i suoi vincoli di conservazione e \(\min\,(-x_{ts})\) è \(\max\, v\).

Un flusso ammissibile rispetta le capacità e si conserva in ogni nodo diverso da \(s\) e \(t\); il suo valore \(v\) è il deflusso netto di \(s\). Il problema del flusso massimo è il LP \(\mathrm{MF}\): massimizza \(v\) in condizioni di conservazione e capacità.

---

Avanti: 5.2 Tagli