6.4 Condizioni di ottimalità con potenziali¶
Parte 3 · Flussi · Capitolo 6 · Capitolo 6: Flusso di costo minimo · Dispensa, volume 3 (PDF) · Esercizi: Flusso di costo minimo
-
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\). For a forward arc it is \(\bar{c}_{ij}=c_{ij}-\pi_i+\pi_j\), il costo ridotto di 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 telescopio, come in Capitolo 3:
\[ c(W)=\sum_{(i,j) \in W}\big(c^x_{ij}-\pi_i+\pi_j\big). \]
Teorema 6.9: ottimizzazione dei costi ridotti
Un flusso ammissibile \(\vet{x}\) è ottimale se e solo se esistono potenziali \(\vet{\pi} \in \R^n\) tali che
Dimostrazione
If. Con la formula telescopica ogni ciclo di \(G(\vet{x})\) ha \(c(W) \ge 0\) e \(\vet{x}\) è ottimale per Teorema 6.7.
Solo se. Sia \(\vet{x}\) ottimale: per Teorema 6.7, \(G(\vet{x})\) non ha ciclo negativo.
-
Aggiungere 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})\), poiché nessun arco entra in \(r\): nessuno è negativo.
-
Per il Teorema «Equazioni di Bellman» di 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: allentamento complementare
Sia \(\vet{x}\) un flusso ammissibile e \(\vet{\pi} \in \R^n\). La condizione di 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à luogo all'arco in avanti, di costo ridotto \(\bar{c}_{ij}\), quando \(x_{ij}<u_{ij}\), e all'arco all'indietro, di costo ridotto \(-\bar{c}_{ij}\), quando \(x_{ij}>l_{ij}\). Quindi la condizione sugli archi del grafo residuo è
Poiché \(l_{ij} \le x_{ij} \le u_{ij}\), la prima implicazione è equivalente a \(\bar{c}_{ij}<0 \Rightarrow x_{ij}=u_{ij}\), mentre la seconda equivale a \(\bar{c}_{ij}>0 \Rightarrow x_{ij}=l_{ij}\). Se \(l_{ij}<x_{ij}<u_{ij}\), si applicano entrambe le implicazioni e \(\bar{c}_{ij}=0\). □
-
Con \(\vet{l}=\vet{0}\) queste sono le condizioni del Corollario «certificato a costo ridotto» di Capitolo 4. Lì si sono dimostrati sufficienti con la dualità LP; Teorema 6.9 mostra che ogni il flusso ottimale ha tali potenziali che con \(\alpha_{ij}=\max\{0,-\bar{c}_{ij}\}\) formano una soluzione duale ottimale.
-
I potenziali della prova sono \(\pi_i=-d(i)\), meno le distanze da \(r\), come \(\pi_i=-\tilde{d}(i)\) in Capitolo 3. Possono essere spostati di una costante; li normalizziamo con \(\pi_n=0\).
Esempio 6.4: il certificato del flusso ottimale
Prendiamo \(\tilde{\vet{x}}\) e i potenziali \(\vet{\pi}=(15,13,13,5,10,0)\) del capitolo 4. I costi ridotti del gli 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\) |
| avanti \((i,j)\) | \(0\) | \(0\) | – | \(2\) | \(0\) | \(11\) | \(0\) | \(0\) | – |
| indietro \((j,i)\) | \(0\) | \(0\) | \(3\) | – | \(0\) | – | \(0\) | \(0\) | \(7\) |
-
Tutti gli archi \(14\) di \(G(\tilde{\vet{x}})\) hanno costo ridotto non negativo: da Teorema 6.9, \(\tilde{\vet{x}}\) è ottimale. Sotto forma di Corollario 6.10: \((3,2)\) e \((4,3)\) sono vuoti, \((2,4)\) e \((5,6)\) sono saturati.
-
I potenziali sono meno i costi delle passeggiate più economiche di \(G(\tilde{\vet{x}})\) che terminano in ciascun nodo. Per per esempio, il cammino \(6,4,5,3,1\) utilizza quattro archi all'indietro e costa \(-5-5-3-2=-15=-\pi_1\): in \(G\) è il percorso \(1,3,5,4,6\) dello albero ricoprente del capitolo 4.
Un flusso ammissibile è ottimo se e solo se alcuni potenziali danno costi ridotti non negativi su tutti gli archi di \(G(\vet{x})\): positivo \(\bar{c}_{ij}\) solo sugli archi al limite inferiore, negativo solo sugli archi saturati. Tale i potenziali sono meno le distanze in \(G(\vet{x})\) da un nodo unito a tutti gli altri.
Avanti: 6.5 Un primo flusso fattibile