6.4 Condizioni di ottimalità con i potenziali¶
Parte 3 · Flussi · Capitolo 6 · Capitolo 6: Flusso di costo minimo · Dispensa, volume 3 (PDF) · Slide · Esercizi: Flusso di costo minimo · App: Flusso di costo minimo: cancellazione dei cicli e cammini minimi successivi
-
Dati i potenziali \(\vet{\pi} \in \R^n\), il costo ridotto di un arco \((i,j)\) di \(G(\vet{x})\) è \(c^x_{ij}-\pi_i+ \pi_j\). Per un arco in avanti è \(\bar{c}_{ij}=c_{ij}-\pi_i+\pi_j\), il costo ridotto del Capitolo 4; per l'arco all'indietro \((j,i)\) di \((i,j)\) è \(-c_{ij}-\pi_j+\pi_i=-\bar{c}_{ij}\).
-
Lungo un ciclo \(W\) di \(G(\vet{x})\) i potenziali si elidono a due a due (somma telescopica), come nel Capitolo 3:
\[ c(W)=\sum_{(i,j) \in W}\big(c^x_{ij}-\pi_i+\pi_j\big). \]
Teorema 6.9: ottimalità con i costi ridotti
Un flusso ammissibile \(\vet{x}\) è ottimo se e solo se esistono potenziali \(\vet{\pi} \in \R^n\) tali che
Dimostrazione
Se. Per la somma telescopica ogni ciclo di \(G(\vet{x})\) ha \(c(W) \ge 0\), e \(\vet{x}\) è ottimo per il Teorema 6.7.
Solo se. Sia \(\vet{x}\) ottimo: per il Teorema 6.7, \(G(\vet{x})\) non ha cicli negativi.
-
Aggiungiamo un nodo \(r\) e un arco \((r,i)\) di costo \(0\) per ogni \(i \in N\). Nel nuovo grafo ogni nodo è raggiungibile da \(r\), e i cicli sono quelli di \(G(\vet{x})\), perché nessun arco entra in \(r\): nessuno è negativo.
-
Per il Teorema «equazioni di Bellman» del Capitolo 3, le distanze \(d(i)\) da \(r\) sono finite e \(d(j) \le d(i)+c^x_{ij}\) per ogni arco \((i,j)\) di \(G(\vet{x})\).
-
Con \(\pi_i=-d(i)\) otteniamo \(c^x_{ij}-\pi_i+\pi_j=c^x_{ij}+d(i)-d(j) \ge 0\). □
Corollario 6.10: scarti complementari
Sia \(\vet{x}\) un flusso ammissibile e \(\vet{\pi} \in \R^n\). La condizione del Teorema 6.9 vale se e solo se, per ogni arco \((i,j) \in A\),
In particolare, \(l_{ij}<x_{ij}<u_{ij}\) implica \(\bar{c}_{ij}=0\).
Dimostrazione
L'arco \((i,j) \in A\) dà l'arco in avanti, di costo ridotto \(\bar{c}_{ij}\), quando \(x_{ij}<u_{ij}\), e l'arco all'indietro, di costo ridotto \(-\bar{c}_{ij}\), quando \(x_{ij}>l_{ij}\). Quindi la condizione sugli archi che vengono da \((i,j)\) si scrive
Poiché \(l_{ij} \le x_{ij} \le u_{ij}\), la prima implicazione equivale a \(\bar{c}_{ij}<0 \Rightarrow x_{ij}=u_{ij}\), e la seconda a \(\bar{c}_{ij}>0 \Rightarrow x_{ij}=l_{ij}\). Se \(l_{ij}<x_{ij}<u_{ij}\), valgono entrambe le implicazioni e \(\bar{c}_{ij}=0\). □
-
Con \(\vet{l}=\vet{0}\) queste sono le condizioni del Corollario «certificato dei costi ridotti» del Capitolo 4. Lì abbiamo dimostrato con la dualità della PL che sono sufficienti; il Teorema 6.9 mostra che ogni flusso ottimo ha potenziali di questo tipo, che con \(\alpha_{ij}=\max\{0,-\bar{c}_{ij}\}\) formano una soluzione duale ottima.
-
I potenziali della dimostrazione sono \(\pi_i=-d(i)\), le distanze da \(r\) cambiate di segno, come \(\pi_i=-\tilde{d}(i)\) nel Capitolo 3. Si possono traslare di una costante; li normalizziamo con \(\pi_n=0\).
Esempio 6.4: il certificato del flusso ottimo
Prendiamo \(\tilde{\vet{x}}\) e i potenziali \(\vet{\pi}=(15,13,13,5,10,0)\) del Capitolo 4. I costi ridotti degli archi di \(G(\tilde{\vet{x}})\) sono \(\bar{c}_{ij}\) sugli archi in avanti e \(-\bar{c}_{ij}\) sugli archi all'indietro:
| arco \((i,j)\) | \((1,2)\) | \((1,3)\) | \((2,4)\) | \((3,2)\) | \((3,5)\) | \((4,3)\) | \((4,6)\) | \((5,4)\) | \((5,6)\) |
|---|---|---|---|---|---|---|---|---|---|
| \(\tilde{x}_{ij}\) | \(2\) | \(3\) | \(4\) | \(0\) | \(3\) | \(0\) | \(2\) | \(1\) | \(2\) |
| \(\bar{c}_{ij}\) | \(0\) | \(0\) | \(-3\) | \(2\) | \(0\) | \(11\) | \(0\) | \(0\) | \(-7\) |
| in avanti \((i,j)\) | \(0\) | \(0\) | – | \(2\) | \(0\) | \(11\) | \(0\) | \(0\) | – |
| all'indietro \((j,i)\) | \(0\) | \(0\) | \(3\) | – | \(0\) | – | \(0\) | \(0\) | \(7\) |
-
Tutti i \(14\) archi di \(G(\tilde{\vet{x}})\) hanno costo ridotto non negativo: per il Teorema 6.9, \(\tilde{\vet{x}}\) è ottimo. Nella forma del Corollario 6.10: \((3,2)\) e \((4,3)\) sono vuoti, \((2,4)\) e \((5,6)\) sono saturi.
-
I potenziali sono i costi delle passeggiate più economiche di \(G(\tilde{\vet{x}})\) che terminano in ciascun nodo, cambiati di segno. Per esempio, la passeggiata \(6,4,5,3,1\) usa quattro archi all'indietro e costa \(-5-5-3-2=-15=-\pi_1\): in \(G\) è il cammino \(1,3,5,4,6\) dell'albero ricoprente del Capitolo 4.
Un flusso ammissibile è ottimo se e solo se esistono potenziali che danno costi ridotti non negativi su tutti gli archi di \(G(\vet{x})\): \(\bar{c}_{ij}\) positivo solo sugli archi al limite inferiore, negativo solo sugli archi saturi. Questi potenziali sono le distanze in \(G(\vet{x})\) da un nodo collegato a tutti gli altri, cambiate di segno.
Avanti: 6.5 Un primo flusso ammissibile