4.3 Feasibility conditions¶
Parte 3 · Flussi · Capitolo 4 · Capitolo 4: Modelli di flusso · Dispensa, volume 3 (PDF) · Esercizi: Modelli di flusso
Definizione 4.5: rete bilanciata
Una rete è balanced se \(\sum_{i \in N} b_i=0\), cioè se l'offerta totale è uguale alla domanda totale.
Proposizione 4.6: una rete fattibile è bilanciata
Se una rete \(G=(N,A)\) ha un flusso fattibile, allora \(\sum_{i \in N} b_i=0\).
Dimostrazione
Applicare Lemma 4.3 con \(S=N\): nessun arco esce o entra in \(N\), quindi \(\delta^+(N)=\delta^-(N)= \emptyset\) e \(\sum_{i \in N} b_i=0\). In forma di matrice, le righe di \(\mat{B}\) si sommano al vettore zero, quindi le voci di \(\vet{b}=\mat{B}\vet{x}\). □
Proposizione 4.7: cut condition
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. Da Lemma 4.3 e 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 almeno i loro limiti inferiori in \(S\).
-
Una rete equilibrata non può ancora avere un flusso fattibile: l'equilibrio è solo una condizione necessaria.
Esempio 4.3: reti bilanciate senza flusso fattibile
Manteniamo gli archi, i costi e le capacità della rete di riferimento e cambiamo gli equilibri.
-
Con \(b_5=-1\), \(b_6=1\) e \(b_i=0\) per gli altri nodi la rete è bilanciata. Ma il nodo \(6\) non ha uscita arco: per \(S=\{6\}\) otteniamo \(\delta^+(S)=\emptyset\) e la condizione di taglio fallisce, poiché \(b_6=1>0\).
-
Con \(b_1=9\), \(b_6=-8\) e gli altri equilibri come in Esempio 4.1, la rete è equilibrata, dal \(9+2-3-8=0\). Per \(S=\{1\}\) otteniamo \(u(\delta^+(S))=u_{12}+u_{13}=8<9=b_1\): il nodo \(1\) non può inviare la sua fornitura.
Per la rete di riferimento stessa, tutti i set \(62\) \(S\) con \(\emptyset \neq S \neq N\) soddisfano la condizione di taglio e il flusso \(\bar{\vet{x}}\) di Esempio 4.1 è fattibile.
Una rete con flusso ammissibile è equilibrata, e ogni taglio può portare al suo interno la fornitura netta dei nodi. Questi sono necessarie condizioni: una rete equilibrata potrebbe non avere un flusso fattibile.