Vai al contenuto

8.9 L'albero iniziale: la Fase 0

Definizione 8.20: rete ausiliaria

Sia \(G=(N,A)\) una rete con \(\sum_{i \in N}b_i=0\). La rete ausiliaria \(G^0\) aggiunge a \(G\) il nodo artificiale \(r=n+1\), con \(b_r=0\), e un arco artificiale per ogni nodo \(i \in N\):

\[ (i,r) \ \text{ se } b_i \ge 0, \qquad\qquad (r,i) \ \text{ se } b_i<0, \]

con capacità \(+\infty\). I costi della Fase 0 sono \(c^0_{ij}=1\) sugli archi artificiali e \(c^0_{ij}=0\) sugli archi di \(A\). La Fase 0 applica l'algoritmo del simplesso su reti a \(G^0\) con i costi \(c^0_{ij}\), partendo dall'albero degli archi artificiali, con \(L=A\) e \(U=\emptyset\); la radice è l'ultimo nodo, \(r\).

Proposizione 8.21: l'albero iniziale della Fase 0

Gli archi artificiali formano un albero ricoprente di \(G^0\). La sua soluzione ad albero ha \(x_{ir}=b_i\) se \(b_i \ge 0\), \(x_{ri}=-b_i\) se \(b_i<0\), e \(x_{ij}=0\) su \(A\); il suo costo è \(\sum_{i \in N}|b_i|\), e la struttura ad albero è fortemente ammissibile.

Dimostrazione

Gli \(n\) archi artificiali collegano ogni nodo di \(N\) a \(r\): formano un grafo connesso con \(n+1\) nodi e \(n\) archi, cioè un albero ricoprente.

  • In un nodo \(i \in N\) l'unico arco con flusso è il suo arco artificiale, quindi la conservazione vale. In \(r\) il flusso uscente meno il flusso entrante è \(\sum_{i:\,b_i<0}(-b_i)-\sum_{i:\,b_i \ge 0}b_i=-\sum_{i \in N}b_i=0=b_r\).

  • Gli archi dell'albero con flusso nullo sono gli archi \((i,r)\) con \(b_i=0\): la loro coda è \(i\), quindi puntano verso la radice. Nessun arco dell'albero è alla sua capacità, che è \(+\infty\).

□

Teorema 8.22: Fase 0

La Fase 0 si ferma dopo un numero finito di pivot con un valore ottimo \(z_0 \ge 0\). La rete \(G\) ha un flusso ammissibile se e solo se \(z_0=0\), e in tal caso il flusso finale della Fase 0, ristretto ad \(A\), è un flusso ammissibile di \(G\).

Dimostrazione

Tutte le capacità di \(G^0\) sono positive e la struttura ad albero iniziale è fortemente ammissibile (Proposizione 8.21), quindi la Fase 0 si ferma per il Teorema 8.19.

  1. Non può fermarsi nel Passo 3: i costi \(c^0_{ij}\) sono non negativi, quindi nessun ciclo ha costo negativo (Proposizione 8.14). Si ferma nel Passo 1 con un flusso ottimo, di valore \(z_0 \ge 0\).

  2. Se \(G\) ha un flusso ammissibile, lo stesso flusso con zero sugli archi artificiali è ammissibile per \(G^0\) con costo \(0\), quindi \(z_0=0\).

  3. Se \(z_0=0\), ogni arco artificiale ha flusso nullo, quindi i vincoli di conservazione dei nodi di \(N\) coinvolgono solo archi di \(A\): la restrizione ad \(A\) è un flusso ammissibile di \(G\). □

  • Quando \(z_0=0\) l'albero finale della Fase 0 contiene ancora almeno un arco artificiale, perché la radice \(r\) deve essere collegata agli altri nodi. La proposizione seguente mostra come proseguire da questo albero.

Proposizione 8.23: dalla Fase 0 al simplesso su reti

Sia la Fase 0 terminata con \(z_0=0\), con flusso \(\tilde{\vet{x}}^0\), struttura ad albero \((T,L,U)\) e costi ridotti \(\bar{c}^0_{ij}\). Applichiamo l'algoritmo del simplesso su reti a \(G^0\) a partire da \((T,L,U)\), con i costi \(c_{ij}\) su \(A\) e \(0\) sugli archi artificiali, facendo entrare solo gli archi con \(\bar{c}^0_{ij}=0\). Allora ogni flusso incontrato ha flusso nullo sugli archi artificiali, e l'algoritmo termina con un flusso ottimo di \(G\), oppure dimostra che il modello \(\mathrm{MCF}\) è illimitato.

Dimostrazione

Chiamiamo fissati gli archi con \(\bar{c}^0_{ij} \neq 0\). Non sono in \(T\) e, per l'ottimalità della Fase 0, quelli con \(\bar{c}^0_{ij}>0\) sono in \(L\), con flusso \(0\), e quelli con \(\bar{c}^0_{ij}<0\) sono in \(U\), con flusso \(u_{ij}\).

  1. Un'identità chiave. Sia \(\vet{y}\) un flusso di \(G^0\) che soddisfa la conservazione e i limiti. Per il Lemma «costo e costo ridotto» del Capitolo 4, e poiché il costo di \(\tilde{\vet{x}}^0\) è \(z_0=0\),

    \[ \sum_{a}c^0_ay_a=\sum_{a}\bar{c}^0_a\,(y_a-\tilde{x}^0_a) . \]

    Ogni termine vale \(\bar{c}^0_ay_a \ge 0\) sugli archi fissati di \(L\), \(\bar{c}^0_a(y_a-u_a) \ge 0\) sugli archi fissati di \(U\), e \(0\) altrove.

  2. Nessun flusso artificiale. Gli archi fissati non entrano mai nell'albero, quindi ogni flusso incontrato ne mantiene i valori, e ogni termine dell'identità è \(0\). Quindi il flusso artificiale totale \(\sum_{a}c^0_ay_a\) è \(0\), e ogni arco artificiale ha flusso nullo.

  3. I flussi ammissibili di \(G\) mantengono i valori fissati. Un flusso ammissibile \(\vet{y}\) di \(G\), con zero sugli archi artificiali, ha \(\sum_{a}c^0_ay_a=0\): ogni termine dell'identità si annulla, quindi \(y_a=0\) sugli archi fissati di \(L\) e \(y_a=u_a\) su quelli di \(U\).

  4. Ottimalità. Sia \(\vet{x}\) il flusso e \(\vet{\pi}\) i potenziali con cui l'algoritmo si ferma. Come nel Teorema 8.10, \(\vet{c}'\vet{y}-\vet{c}'\vet{x}=\sum_{a}\bar{c}_a(y_a-x_a)\). Gli archi fissati danno \(0\) per il punto 3, gli archi dell'albero danno \(0\), e gli altri archi di \(L\) e \(U\) soddisfano le condizioni di arresto e danno un termine non negativo. Quindi \(\vet{c}'\vet{y} \ge \vet{c}'\vet{x}\).

  5. Illimitatezza. Se l'algoritmo si ferma nel Passo 3, i flussi \(\vet{x}+t\vet{x}^C\) della Proposizione 8.14 mantengono i valori fissati: per l'identità del punto 1 hanno flusso artificiale nullo, quindi sono flussi di \(G\) con costo che tende a \(-\infty\).

Le strutture incontrate restano fortemente ammissibili, e l'algoritmo si ferma, per il Teorema 8.19. □

Esempio 8.8: la Fase 0 sulla rete di riferimento

Per la rete di riferimento con capacità, la rete ausiliaria ha il nodo artificiale \(7\) e gli archi artificiali \((1,7)\), \((2,7)\), \((3,7)\), \((5,7)\), perché \(b_1,b_2,b_3,b_5 \ge 0\), e \((7,4)\), \((7,6)\). L'albero iniziale (blu) porta \(5\), \(2\), \(0\), \(0\), \(3\), \(4\) unità su questi archi, tutti gli archi di \(A\) sono vuoti (non sono disegnati), e \(z_0=14\). I potenziali iniziali sono \(\pi_i=1\) per i nodi con un arco \((i,7)\) e \(\pi_i=-1\) per quelli con un arco \((7,i)\).

Figura 8

La Fase 0 esegue sei pivot; ogni arco entrante ha \(\bar{c}^0_{ij}=-2\), e ogni apice è la radice \(7\).

pivot entrante \(\bar{c}^0_{ij}\) apice \(\theta\) archi bloccanti uscente \(z_0\) dopo
\(1\) \((2,4)\) \(-2\) \(7\) \(2\) \((2,7)\) \((2,7)\) \(10\)
\(2\) \((1,2)\) \(-2\) \(7\) \(1\) \((7,4)\) \((7,4)\) \(8\)
\(3\) \((4,6)\) \(-2\) \(7\) \(1\) \((2,4)\) \((2,4)\) \(6\)
\(4\) \((5,4)\) \(-2\) \(7\) \(0\) \((5,7)\) \((5,7)\) \(6\)
\(5\) \((3,5)\) \(-2\) \(7\) \(0\) \((3,7)\) \((3,7)\) \(6\)
\(6\) \((1,3)\) \(-2\) \(7\) \(3\) \((1,7)\), \((5,4)\), \((7,6)\) \((7,6)\) \(0\)

  • I pivot \(4\) e \(5\) sono degeneri. Nel pivot \(3\) l'arco \((2,4)\) raggiunge la sua capacità e va in \(U\).

  • Nel pivot \(6\) il ciclo è \(7,1,3,5,4,6,7\), con tre archi bloccanti. La regola sceglie \((7,6)\), l'ultimo a partire dall'apice. Con \((1,7)\) l'albero conterrebbe \((5,4)\) saturo che punta verso la radice e \((7,6)\) vuoto che punta in senso opposto alla radice; con \((5,4)\), l'arco vuoto \((7,6)\) che punta in senso opposto: nessuno dei due alberi sarebbe fortemente ammissibile.

  • La Fase 0 termina con \(z_0=0\), l'albero \((1,2)\), \((1,3)\), \((1,7)\), \((3,5)\), \((4,6)\), \((5,4)\) e \(U=\{(2,4)\}\). Tutti i potenziali di \(N\) valgono \(1\), quindi \(\bar{c}^0_{ij}=0\) su ogni arco tranne \((7,4)\) e \((7,6)\), che hanno \(\bar{c}^0_{ij}=2\) e sono fissati.

Con i costi \(c_{ij}\) la soluzione ad albero costa \(74\). Gli archi \((7,4)\) e \((7,6)\) hanno costi ridotti \(-10\) e \(-15\), ma sono fissati: l'unico arco che può entrare è \((5,6)\), con \(\bar{c}_{56}=-7\). La sua capacità residua \(u_{56}=2\) è la minima lungo il suo ciclo, quindi \((5,6)\) stesso è l'arco uscente e passa in \(U\), e il costo diventa \(74-2 \cdot 7=60\): l'ottimo dell'Esempio 8.7. Se \((7,6)\) potesse entrare, \(3\) unità viaggerebbero da \(1\) a \(6\) attraverso il nodo artificiale, a costo \(29\): non sarebbe un flusso di \(G\).

La Fase 0 parte dalla stella fortemente ammissibile degli archi artificiali e minimizza il flusso artificiale: \(z_0>0\) dimostra che non esiste un flusso ammissibile. Se \(z_0=0\), il simplesso su reti prosegue dall'albero finale, con i costi originali, e possono entrare solo gli archi con costo ridotto nullo nella Fase 0.

8.10 Errori tipici

Attenzione

  • Chiamare di base gli archi con flusso positivo. La base è l'albero \(T\): un arco di \(U\) ha flusso positivo ma è fuori base, e un arco dell'albero può avere flusso \(0\) o \(u_{ij}\).

  • Usare il test dei segni di un problema di massimo. Nel modello \(\mathrm{MCF}\), che è di minimo, un arco di \(L\) è ammissibile per l'ingresso se \(\bar{c}_{ij}<0\) e un arco di \(U\) se \(\bar{c}_{ij}>0\).

  • Orientare il ciclo come l'arco entrante quando questo è in \(U\). Il suo flusso deve diminuire, quindi il ciclo va contro di esso, e l'arco entrante è all'indietro.

  • Dimenticare l'arco entrante nel test dei rapporti. La sua capacità residua è \(u_{kl}\); se è l'unico arco bloccante, l'albero non cambia e l'arco passa da \(L\) a \(U\) o viceversa.

  • Aggiornare tutti i potenziali. Cambiano solo i potenziali del sottoalbero staccato dall'arco uscente, tutti di \(\bar{c}_{kl}\) o di \(-\bar{c}_{kl}\).

  • Scegliere un arco bloccante qualsiasi. L'ultimo arco bloccante a partire dall'apice mantiene l'albero fortemente ammissibile; un'altra scelta può far perdere questa proprietà e la garanzia contro il ciclaggio.

  • Far entrare gli archi fissati dopo la Fase 0. Un arco con \(\bar{c}^0_{ij} \neq 0\) può mettere flusso sugli archi artificiali; possono entrare solo gli archi con \(\bar{c}^0_{ij}=0\).

8.11 In sintesi

In sintesi

  • In una rete connessa l'equazione del nodo \(n\) è ridondante, e le basi del modello \(\mathrm{MCF}\) sono gli alberi ricoprenti; le loro matrici sono triangolari con determinante \(\pm 1\).

  • Una struttura ad albero \((T,L,U)\) fissa gli archi fuori base a \(0\) o alla loro capacità; la soluzione ad albero si ottiene dalle foglie, e i potenziali dalla radice, con \(\pi_n=0\).

  • Il costo ridotto di un arco fuori base è il costo del suo ciclo fondamentale; \(\bar{c} \ge 0\) su \(L\) e \(\bar{c} \le 0\) su \(U\) certificano l'ottimalità.

  • Un pivot invia \(\theta\) unità lungo il ciclo dell'arco entrante e riduce il costo di \(\theta|\bar{c}_{kl}|\); l'arco uscente è l'ultimo arco bloccante a partire dall'apice, e cambiano solo i potenziali di un sottoalbero.

  • Gli alberi fortemente ammissibili e questa regola dell'arco uscente impediscono il ciclaggio. La Fase 0 sulla rete ausiliaria dà un albero iniziale fortemente ammissibile, oppure dimostra che non esiste un flusso ammissibile.

La rete di riferimento in breve.

senza capacità costi \(80\), \(52\), \(49\); albero ottimo \((1,2),(1,3),(2,4),(3,5),(5,6)\)
con capacità, da \(\bar{\vet{x}}\) costi \(63\), \(63\) (degenere), \(60\); \(U=\{(2,4),(5,6)\}\)
potenziali ottimi (\(\pi_6=0\)) \((8,6,6,1,3,0)\) senza capacità, \((15,13,13,5,10,0)\) con
Fase 0 \(z_0\) da \(14\) a \(0\) in sei pivot, poi un pivot da \(74\) a \(60\)


Esercizi su questo capitolo: Simplesso su reti