4.3 Condizioni di ammissibilità¶
Parte 3 · Flussi · Capitolo 4 · Capitolo 4: Modelli di flusso · Dispensa, volume 3 (PDF) · Slide · Esercizi: Modelli di flusso
Definizione 4.5: rete bilanciata
Una rete è bilanciata se \(\sum_{i \in N} b_i=0\), cioè se l'offerta totale è uguale alla domanda totale.
Proposizione 4.6: una rete ammissibile è bilanciata
Se una rete \(G=(N,A)\) ha un flusso ammissibile, allora \(\sum_{i \in N} b_i=0\).
Dimostrazione
Applichiamo il Lemma 4.3 con \(S=N\): nessun arco esce da \(N\) o vi entra, quindi \(\delta^+(N)=\delta^-(N)= \emptyset\) e \(\sum_{i \in N} b_i=0\). In forma matriciale, le righe di \(\mat{B}\) sommano al vettore nullo, e quindi anche le componenti di \(\vet{b}=\mat{B}\vet{x}\) sommano a zero. □
Proposizione 4.7: condizione di taglio
Se una rete \(G=(N,A)\) ha un flusso ammissibile, allora per ogni \(S \subseteq N\)
dove \(u(F)\) e \(l(F)\) sono le somme delle capacità e dei limiti inferiori degli archi di \(F\).
Dimostrazione
Sia \(\vet{x}\) un flusso ammissibile. Per il Lemma 4.3 e per i limiti \(x_{ij} \le u_{ij}\) su \(\delta^+(S)\) e \(x_{ij} \ge l_{ij}\) su \(\delta^-(S)\),
□
-
L'offerta dei nodi di \(S\), al netto della loro domanda, deve poter uscire da \(S\) attraverso gli archi di \(\delta^+(S)\), mentre gli archi di \(\delta^-(S)\) portano in \(S\) almeno i loro limiti inferiori.
-
Una rete bilanciata può comunque non avere flussi ammissibili: essere bilanciata è solo una condizione necessaria.
Esempio 4.3: reti bilanciate senza flussi ammissibili
Teniamo gli archi, i costi e le capacità della rete di riferimento e cambiamo i bilanci.
-
Con \(b_5=-1\), \(b_6=1\) e \(b_i=0\) per gli altri nodi, la rete è bilanciata. Ma il nodo \(6\) non ha archi uscenti: per \(S=\{6\}\) si ha \(\delta^+(S)=\emptyset\), e la condizione di taglio non vale, perché \(b_6=1>0\).
-
Con \(b_1=9\), \(b_6=-8\) e gli altri bilanci come nell'Esempio 4.1, la rete è bilanciata, perché \(9+2-3-8=0\). Per \(S=\{1\}\) si ha \(u(\delta^+(S))=u_{12}+u_{13}=8<9=b_1\): il nodo \(1\) non può inviare la sua offerta.
Per la rete di riferimento originale, tutti i \(62\) insiemi \(S\) con \(\emptyset \neq S \neq N\) soddisfano la condizione di taglio, e il flusso \(\bar{\vet{x}}\) dell'Esempio 4.1 è ammissibile.
Una rete con un flusso ammissibile è bilanciata, e ogni taglio può trasportare l'offerta netta dei nodi interni. Queste condizioni sono necessarie: una rete bilanciata può non avere flussi ammissibili.