Vai al contenuto

4.3 Condizioni di ammissibilità

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\)

\[ \sum_{i \in S} b_i \;\le\; u(\delta^+(S)) - l(\delta^-(S)), \]

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)\),

\[ \sum_{i \in S} b_i = x(\delta^+(S))-x(\delta^-(S)) \le u(\delta^+(S))-l(\delta^-(S)). \qedhere \]

□

  • 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.

  1. 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\).

  2. 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.


Avanti: 4.4 Rimozione dei limiti inferiori