6.3 Condizioni di ottimalità dei cicli negativi¶
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
Teorema 6.7: ottimalità dei cicli negativi
Un flusso ammissibile \(\vet{x}\) è ottimo se e solo se la sua rete residua \(G(\vet{x})\) non ha cicli negativi.
Dimostrazione
Dimostriamo le due implicazioni.
-
Un ciclo negativo migliora \(\vet{x}\). Sia \(W\) un ciclo negativo di \(G(\vet{x})\) e \(\theta=\min\{r(W), 1\}>0\). Per la Proposizione 6.3, \(\vet{x}\) aumentato lungo \(W\) di \(\theta\) è un flusso ammissibile di costo \(\vet{c}'\vet{x}+\theta\,c(W)<\vet{c}'\vet{x}\), quindi \(\vet{x}\) non è ottimo.
-
Senza cicli negativi \(\vet{x}\) è ottimo. Sia \(\vet{x}'\) un qualsiasi flusso ammissibile. Per il Lemma 6.6, \(\vet{c}'\vet{x}'=\vet{c}'\vet{x}+\sum_h\theta_h\,c(W_h)\) con cicli \(W_h\) di \(G(\vet{x})\) e \(\theta_h>0\). Ogni \(c(W_h)\) è non negativo, quindi \(\vet{c}'\vet{x}' \ge \vet{c}'\vet{x}\).
□
-
La dimostrazione confronta due flussi attraverso la loro differenza, e non usa la dualità della PL.
-
Quando alcune capacità sono infinite il modello può essere illimitato, e la proposizione seguente dice esattamente quando.
Proposizione 6.8: istanze illimitate
Supponiamo che il modello \(\mathrm{MCF}\) abbia un flusso ammissibile. Il modello è illimitato se e solo se \(G\) ha un ciclo orientato \(C\) di costo negativo, \(\sum_{(i,j) \in C} c_{ij}<0\), i cui archi hanno tutti \(u_{ij}=+\infty\).
Dimostrazione
Se. Sia \(\vet{x}\) ammissibile. Ogni arco di \(C\) ha \(x_{ij}<u_{ij}=+\infty\), quindi \(C\) è un ciclo di archi in avanti di \(G(\vet{x})\) con \(r(C)=+\infty\). Aumentando lungo \(C\) di un qualsiasi \(\theta>0\) otteniamo flussi ammissibili di costo \(\vet{c}'\vet{x}+\theta\,c(C)\), che tende a \(-\infty\).
Solo se. Supponiamo che un tale ciclo \(C\) non esista, e fissiamo un flusso ammissibile \(\vet{x}\). Sia \(R\) la massima capacità residua finita di un arco di \(G(\vet{x})\) (\(R=0\) se non ce ne sono), e \(K=\max_{(i,j) \in A}|c_{ij}|\). Sia \(\vet{x}'\) un qualsiasi flusso ammissibile, scomposto come nel Lemma 6.6.
-
Un ciclo \(W_h\) con \(c(W_h)<0\) ha un arco \(a\) di capacità residua finita: gli archi all'indietro hanno capacità residua finita, e un ciclo di archi in avanti con capacità infinita sarebbe un ciclo \(C\). Quindi \(\theta_h \le y_a \le r_a \le R\).
-
\(W_h\) ha al più \(n\) archi, quindi \(c(W_h) \ge -nK\); i cicli sono al più \(m\).
Quindi \(\vet{c}'\vet{x}' \ge \vet{c}'\vet{x}-m\,R\,n\,K\) per ogni \(\vet{x}'\) ammissibile: il modello è limitato. □
- Un problema di PL ammissibile e limitato ha una soluzione ottima (Programmazione lineare, Capitolo 15 «La geometria della programmazione lineare»). Con capacità finite il modello \(\mathrm{MCF}\) non è mai illimitato.
Esempio 6.3: un flusso non ottimo e un'istanza illimitata
-
Il flusso ammissibile \(\bar{\vet{x}}=(1,4,3,0,4,0,2,2,2)\) del Capitolo 4 costa \(63\). La sua rete residua ha il ciclo \(W=1,2,4,5,3,1\), formato dagli archi in avanti \((1,2)\), \((2,4)\) e dagli archi all'indietro \((4,5)\), \((5,3)\), \((3,1)\):
\[ c(W)=2+5-5-3-2=-3, \qquad r(W)=\min\{3,1,2,4,4\}=1 . \]Per il Teorema 6.7 \(\bar{\vet{x}}\) non è ottimo. Aumentando di \(1\) otteniamo \(\tilde{\vet{x}}\), di costo \(63-3=60\): il gap \(3\) di \(\bar{\vet{x}}\) calcolato con la soluzione duale nel Capitolo 4.
-
Con \(c_{54}=-12\) e \(u_{35}=u_{54}=u_{43}=+\infty\), il ciclo orientato \(3,5,4,3\) di \(G\) costa \(3-12+3=-6\) e ha capacità infinite. Per la Proposizione 6.8 il modello è illimitato, come conferma Gurobi: ogni unità mandata lungo il ciclo abbassa il costo di \(6\).
Un flusso ammissibile è ottimo se e solo se la sua rete residua non ha cicli negativi. Un modello ammissibile è illimitato se e solo se un ciclo orientato negativo ha tutte le capacità infinite.