8.4 Il perno¶
Parte 4 · Il simplesso su reti · Capitolo 8 · Capitolo 8: Simplesso su reti · Dispensa, volume 4 (PDF) · Esercizi: Simplesso su reti
Definizione 8.11: il pivot del simplesso su reti
Sia \((T,L,U)\) una struttura ad albero ammissibile, con soluzione ad albero \(\vet{x}\) e potenziali \(\vet{\pi}\).
-
Un arco è ammissibile per l'ingresso se appartiene a \(L\) e \(\bar{c}_{ij}<0\), oppure a \(U\) e \(\bar{c}_{ij}>0\). L'arco entrante \(e=(k,l)\) è quello ammissibile con il massimo valore di \(|\bar{c}_{ij}|\); in caso di parità, scegliamo il primo in ordine lessicografico.
-
Il ciclo del pivot \(C\) è il ciclo fondamentale di \(e\), percorso nella direzione di \(e\) se \(e \in L\), e nella direzione opposta se \(e \in U\).
-
La capacità residua di un arco di \(C\) è \(u_{ij}-x_{ij}\) se viene percorso in avanti (ed è \(+\infty\) se \(u_{ij}=+\infty\)) e \(x_{ij}\) se viene percorso all'indietro. Il passo \(\theta\) è la minima capacità residua lungo \(C\); gli archi che la raggiungono sono bloccanti.
-
L'apice \(w\) di \(C\) è il primo nodo comune ai cammini nell'albero da \(k\) e da \(l\) alla radice \(n\). L'arco uscente \(f\) è l'ultimo arco bloccante incontrato percorrendo \(C\) a partire da \(w\).
Un pivot con \(\theta=0\) è degenerato.
-
L'invio di una quantità \(\theta\) lungo \(C\) aumenta il flusso sugli archi percorsi in avanti e lo diminuisce su quelli percorsi all'indietro. L'arco entrante viene percorso in avanti se appartiene a \(L\) (il suo flusso aumenta) e all'indietro se appartiene a \(U\) (il suo flusso diminuisce).
-
Siano \(p\) e \(q\) gli estremi di \(e\) nell'ordine in cui è percorso in \(C\): \(p=k\), \(q=l\) se \(e \in L\) e \(p=l\), \(q=k\) se \(e \in U\). Partendo dall'apice, il ciclo segue il cammino nell'albero da \(w\) a \(p\), percorre l'arco \(e\) da \(p\) a \(q\) e torna da \(q\) a \(w\) lungo il cammino nell'albero.
-
Anche l'arco entrante può essere l'arco uscente: la sua capacità residua è \(u_{kl}\), quindi \(\theta \le u_{kl}\).
Proposizione 8.12: il pivot
Nell'impostazione di Definizione 8.11, lascia che \(\theta<+\infty\) e \(\vet{x}'\) siano ottenuti da \(\vet{x}\) aggiungendo \(\theta\) sugli archi anteriori di \(C\) e sottraendo \(\theta\) sugli archi posteriori.
-
(a) \(\vet{x}'\) è un flusso ammissibile e \(\vet{c}'\vet{x}'=\vet{c}'\vet{x}-\theta\,|\bar{c}_{kl}|\).
-
(b) \(T'=T \cup \{e\} \setminus \{f\}\) è un albero ricoprente e \(\vet{x}'\) è la soluzione ad albero della struttura \((T',L',U')\), dove \(f\) va a \(U\) se è avanti in \(C\) e a \(L\) se è indietro. Se \(f=e\), allora \(T'=T\) e \(e\) si sposta da \(L\) a \(U\) o da \(U\) a \(L\).
Dimostrazione
Sia \(\varepsilon_a=+1\) sugli archi anteriori e \(-1\) sugli archi posteriori di \(C\), e sia \(\vet{x}^C\) il vettore di incidenza con segno di \(C\), con \(x^C_a=\varepsilon_a\) su \(C\) e \(0\) altrove: quindi \(\vet{x}'=\vet{x}+\theta \vet{x}^C\).
-
Conservazione. Per il Lemma «Colonne di un ciclo» del Capitolo 1, \(\mat{B}\vet{x}^C=\sum_{a \in C}\varepsilon_a\mat{B}_a=\vet{0}\); quindi \(\mat{B}\vet{x}'=\vet{b}\).
-
Limiti. Il flusso su un arco percorso in avanti aumenta di \(\theta\le u_{ij}-x_{ij}\); su un arco percorso all'indietro diminuisce di \(\theta\le x_{ij}\). I flussi sugli altri archi non cambiano.
-
Costo. \(\vet{c}'\vet{x}'-\vet{c}'\vet{x}=\theta\,c(C)=\theta\,\varepsilon_e\bar{c}_{kl}\) per il Lemma 8.9, poiché gli archi dell'albero hanno \(\bar{c}_{ij}=0\). Se \(e \in L\), allora \(\varepsilon_e=+1\) e \(\bar{c}_{kl}<0\); se \(e \in U\), allora \(\varepsilon_e=-1\) e \(\bar{c}_{kl}>0\). In entrambi i casi \(\varepsilon_e\bar{c}_{kl}=-|\bar{c}_{kl}|\).
-
Il nuovo albero. \(C\) è l'unico ciclo di \(T \cup \{e\}\) (Proposizione «Ciclo fondamentale» del Capitolo 1). Rimuovendo \(f \in C\) si ottiene un grafo connesso, poiché il resto del ciclo collega ancora gli estremi di \(f\). Il grafo ha \(n-1\) archi, quindi è un albero ricoprente per la caratterizzazione degli alberi del Capitolo 1.
-
La nuova soluzione ad albero. Gli archi fuori base diversi da \(e\) e \(f\) mantengono flusso e limite. L'arco \(f\) è bloccante: dopo il pivot \(x'_f=u_f\) se è percorso in avanti e \(x'_f=0\) se è percorso all'indietro. Quindi \(\vet{x}'\) soddisfa \(\mat{B}\vet{x}'=\vet{b}\) e i limiti imposti da \((T',L',U')\); è pertanto la soluzione ad albero per il Teorema 8.3. □
Proposizione 8.13: l'aggiornamento dei potenziali
Nel pivot della Proposizione 8.12, sia \(f \neq e\) e siano \(R\) e \(S\) gli insiemi di nodi delle due componenti di \(T \setminus \{f\}\), con \(n \in R\). L'arco \(e\) ha quindi un estremo in \(R\) e uno in \(S\). I potenziali di \(T'\) sono
Dimostrazione
L'albero \(T'\) è connesso e \(T' \setminus \{e\}=T \setminus \{f\}\) non ha arco tra \(R\) e \(S\): quindi \(e\) si unisce \(R\) e \(S\). Verifichiamo che i valori \(\pi'\) dell'enunciato siano i potenziali di \(T'\), che sono unici per Lemma 8.8.
-
Ogni arco di \(T' \setminus \{e\}\) ha entrambi gli estremi in \(R\) oppure entrambi in \(S\). In ciascuna componente tutti i potenziali cambiano della stessa quantità, quindi il costo ridotto dell'arco resta nullo.
-
Se \(l \in S\), allora \(c_{kl}-\pi'_k+\pi'_l=c_{kl}-\pi_k+\pi_l-\bar{c}_{kl}=0\). Se \(k \in S\), allora \(c_{kl}-\pi'_k+\pi'_l=c_{kl}-\pi_k-\bar{c}_{kl}+\pi_l=0\).
-
La radice \(n\) è in \(R\), quindi \(\pi'_n=\pi_n=0\). □
-
Cambiano solo i potenziali dei nodi di \(S\), tutti della stessa quantità. Se \(f=e\), l'albero e i potenziali non cambiano.
-
Cambiano i costi ridotti soltanto degli archi che hanno un estremo in \(R\) e l'altro in \(S\).
Proposizione 8.14: problema illimitato
Se \(\theta=+\infty\), allora \(e \in L\), il ciclo \(C\) è diretto, tutti i suoi archi hanno capacità infinita e il suo costo è \(-|\bar{c}_{kl}|<0\). Il problema \(\mathrm{MCF}\) è quindi illimitato.
Dimostrazione
Un arco percorso all'indietro ha capacità residua finita \(x_{ij}\); anche un arco percorso in avanti con capacità finita ha capacità residua finita \(u_{ij}-x_{ij}\). Dunque ogni arco di \(C\) è percorso in avanti e ha capacità infinita; in particolare, \(e\) è percorso in avanti e appartiene a \(L\). Come nella Proposizione 8.12, il flusso \(\vet{x}+t\vet{x}^C\) è ammissibile per ogni \(t\ge0\) e ha costo \(\vet{c}'\vet{x}-t|\bar{c}_{kl}|\), che tende a \(-\infty\). □
Esempio 8.4: un pivot dall'albero di \(\bar{\vet{x}}\)
Riprendiamo l'Esempio 8.3. Gli archi ammissibili per l'ingresso sono \((1,3)\) e \((3,5)\), entrambi in \(U\), con \(\bar{c}_{13}=2\) e \(\bar{c}_{35}=1\).
-
Entrata nell'arco. Il più grande \(|\bar{c}_{ij}|\) è \(2\): \(e=(1,3)\). È in \(U\), quindi \(C\) viene attraversato \((1,3)\): \(p=3\) e \(q=1\).
-
Apex. I percorsi dell'albero fino alla radice sono \(1,2,4,6\) e \(3,2,4,6\): l'apice è \(w=2\). Da \(w\) il ciclo va \(2 \to 3\) lungo \((3,2)\), \(3 \to 1\) lungo \((1,3)\), \(1 \to 2\) lungo \((1,2)\):
arco di \(C\) \((3,2)\) \((1,3)\) \((1,2)\) direzione \(-\) \(-\) \(+\) residuo \(0\) \(4\) \(3\) -
Passo e uscita dall'arco. \(\theta=\min\{0,4,3\}=0\) e l'unico arco bloccante è \((3,2)\): lascia l'albero, all'indietro, quindi va a \(L\). Il perno è degenerato.
-
Aggiornamento. Il flusso non cambia e il costo rimane \(63\). Il nuovo albero è \(T'=\{(1,2),(1,3),(2,4),(4,6),(5,4)\}\), dove \((1,3)\) è un arco base alla sua capacità. La rimozione di \((3,2)\) da \(T\) interrompe \(S=\{3\}\), che contiene \(l=3\): \(\pi'_3=\pi_3-\bar{c}_{13}=12-2=10\).
Nella figura gli archi di \(C\) sono viola, l'arco entrante è tratteggiato; accanto ad ogni nodo il suo potenziale.
Un perno invia le unità \(\theta\) attorno al ciclo fondamentale dell'arco entrante, orientato in modo che il suo flusso si allontani da è limitato; il costo diminuisce di \(\theta|\bar{c}_{kl}|\). L'arco uscente è l'ultimo arco bloccante dall'apice e cambiano solo i potenziali del sottoalbero che taglia.