4.1 Reti e flussi¶
Parte 3 · Flussi · Capitolo 4 · Capitolo 4: Modelli di flusso · Dispensa, volume 3 (PDF) · Esercizi: Modelli di flusso
Definizione 4.1: rete
Una rete è un grafo diretto \(G=(N,A)\), con nodi \(n=|N|\) e archi \(m=|A|\), insieme ai seguenti dati.
-
Ogni nodo \(i \in N\) ha un balance \(b_i \in \R\). Il nodo è un nodo di fornitura se \(b_i>0\), un nodo di richiesta se \(b_i<0\) e nodo di traslato se \(b_i=0\).
-
Ogni arco \((i,j) \in A\) ha un limite inferiore \(l_{ij}\) e un capacità \(u_{ij}\), con \(0 \le l_{ij} \le u_{ij} \le +\infty\), and a cost \(c_{ij} \in \R\) per unità di portata.
Quando non vengono forniti i limiti inferiori, \(l_{ij}=0\) per ogni arco.
Definizione 4.2: flusso
Sia \(G=(N,A)\) una rete. Un flusso è un vettore \(\vet{x} \in \R^m\) con una componente \(x_{ij}\) per ogni \((i,j) \in A\), pari alla quantità inviata lungo l'arco.
-
Il flusso soddisfa il vincolo conservazione del flusso del nodo \(i\) se ciò che esce da \(i\) meno ciò che entra \(i\) equivale al saldo:
\[ \sum_{(i,j) \in \delta^+(i)} x_{ij} \;-\; \sum_{(j,i) \in \delta^-(i)} x_{ji} = b_i . \] -
Il flusso è ammissibile se soddisfa la conservazione del flusso in ogni nodo e \(l_{ij} \le x_{ij} \le u_{ij}\) per ogni arco. Il suo costo è \(\sum_{(i,j) \in A} c_{ij}\, x_{ij}\).
-
Un nodo di offerta invia \(b_i\) unità in più di quante ne riceve; un nodo di domanda riceve \(-b_i\) unità in più di quante ne invia. Un nodo di transito trasmette tutto il flusso che riceve.
-
Con la matrice di incidenza nodo-arco \(\mat{B}\) del Capitolo 1 «Grafi», la conservazione del flusso in tutti i nodi si scrive \(\mat{B}\vet{x}=\vet{b}\): la riga \(i\) di \(\mat{B}\vet{x}\) è il deflusso meno l'afflusso di \(i\).
Esempio 4.1: la rete di riferimento
Aggiungiamo i dati al grafo di riferimento di Capitolo 1 «Grafi», con gli archi numerati \(a_1,a_2,\dots,a_9\) in ordine lessicografo. I saldi sono
quindi i nodi \(1\) e \(2\) forniscono unità \(7\), i nodi \(4\) e \(6\) le richiedono e i nodi \(3\) e \(5\) sono nodi di traslato. I limiti inferiori sono zero e i costi e le capacità sono:
| arco | \((1,2)\) | \((1,3)\) | \((2,4)\) | \((3,2)\) | \((3,5)\) | \((4,3)\) | \((4,6)\) | \((5,4)\) | \((5,6)\) |
|---|---|---|---|---|---|---|---|---|---|
| \(c_{ij}\) | \(2\) | \(2\) | \(5\) | \(2\) | \(3\) | \(3\) | \(5\) | \(5\) | \(3\) |
| \(u_{ij}\) | \(4\) | \(4\) | \(4\) | \(2\) | \(4\) | \(3\) | \(5\) | \(3\) | \(2\) |
Nella figura ogni arco porta la coppia \(c_{ij},u_{ij}\), e ogni nodo il suo equilibrio \(b_i\) (in blu).
Il flusso \(\bar{\vet{x}}\) con
è fattibile. Ad esempio, nel nodo \(4\) il deflusso è \(\bar{x}_{43}+\bar{x}_{46}=2\), l'afflusso è \(\bar{x}_{24}+\bar{x}_{54}=5\) e \(2-5=-3=b_4\). Gli archi \((1,3)\), \((3,5)\) e \((5,6)\) sono al completo e il costo di \(\bar{\vet{x}}\) è \(63\).
4.1.1 Flusso attraverso un taglio¶
- Per un insieme di nodi \(S \subseteq N\), denotiamo con \(\delta^+(S)\) gli archi con la coda in \(S\) e la testa all'esterno di \(S\), da \(\delta^-(S)\) gli archi con la testa in \(S\) e la coda all'esterno di \(S\) e \(x(F)=\sum_{(i,j) \in F} x_{ij}\) for a set of arcs \(F\).
Lemma 4.3: flusso attraverso un taglio
Lascia che \(\vet{x}\) soddisfi la conservazione del flusso in ogni nodo di una rete \(G=(N,A)\). Quindi, per ogni \(S \subseteq N\),
Dimostrazione
Sommare i vincoli di conservazione dei nodi di \(S\); il lato destro è \(\sum_{i \in S} b_i\).
-
Un arco con entrambi i punti finali in \(S\) appare due volte, con \(+x_{ij}\) nella riga della coda e \(-x_{ij}\) nella riga fila della sua testa: annulla.
-
Un arco di \(\delta^+(S)\) appare solo nella riga della sua coda, con \(+x_{ij}\); un arco di \(\delta^-(S)\) solo in la fila della sua testa, con \(-x_{ij}\); gli altri archi non compaiono.
□
- In Esempio 4.1, l'insieme \(S=\{1,2,3\}\) ha \(\delta^+(S)=\{(2,4),(3,5)\}\) e \(\delta^-(S)=\{(4,3)\}\). Il flusso \(\bar{\vet{x}}\) dà \(3+4-0=7=b_1+b_2+b_3\).
Una rete ha equilibri sui nodi e limiti inferiori, capacità e costi sugli archi. Un flusso ammissibile soddisfa \(\mat{B}\vet{x}=\vet{b}\) e i limiti; attraverso ogni taglio, il deflusso netto equivale al saldo totale dei nodi dentro.