Vai al contenuto

6.3 Condizioni di ottimalità del ciclo negativo

Parte 3 · Flussi · Capitolo 6 · Capitolo 6: Flusso di costo minimo · Dispensa, volume 3 (PDF) · Esercizi: Flusso di costo minimo

Teorema 6.7: ottimalità del ciclo negativo

Un flusso ammissibile \(\vet{x}\) è ottimale se e solo se la sua rete residua \(G(\vet{x})\) non ha ciclo negativo.

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\). By Proposizione 6.3, \(\vet{x}\) augmented along \(W\) by \(\theta\) è un flusso di costi fattibile \(\vet{c}'\vet{x}+\theta\,c(W)<\vet{c}'\vet{x}\), quindi \(\vet{x}\) non è ottimale.

  • Senza cicli negativi \(\vet{x}\) è ottimale. Sia \(\vet{x}'\) un flusso qualsiasi ammissibile. Di 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 utilizza la dualità LP.

  • Quando alcune capacità sono infinite, il modello può essere illimitato e la proposizione successiva dice esattamente quando.

Proposizione 6.8: istanze illimitate

Supponiamo che il modello \(\mathrm{MCF}\) abbia un flusso ammissibile. È illimitato se e solo se \(G\) ha un ciclo diretto \(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}\) fattibile. 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\). L'integrazione lungo \(C\) con qualsiasi \(\theta>0\) fornisce flussi di costi fattibili \(\vet{c}'\vet{x}+\theta\,c(C)\), che tende a \(-\infty\).

Solo se. Assumi che non esista un tale ciclo \(C\) e fissa un flusso ammissibile \(\vet{x}\). Lascia che \(R\) sia il più grande capacità residua finita di un arco di \(G(\vet{x})\) (\(R=0\) se non ce n'è) e \(K=\max_{(i,j) \in A}|c_{ij}|\). Lascia che \(\vet{x}'\) sia qualsiasi flusso ammissibile, scomposto come in Lemma 6.6.

  1. Un ciclo \(W_h\) con \(c(W_h)<0\) ha un arco \(a\) di capacità residua finita: gli archi all'indietro hanno residuo finito capacità 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\).

  2. \(W_h\) ha al massimo archi \(n\), quindi \(c(W_h) \ge -nK\); ci sono al massimo i cicli \(m\).

Quindi \(\vet{c}'\vet{x}' \ge \vet{c}'\vet{x}-m\,R\,n\,K\) per ogni \(\vet{x}'\) ammissibile: il modello è limitato. □

Esempio 6.3: un flusso non ottimale e un'istanza illimitata

  • Il flusso ammissibile \(\bar{\vet{x}}=(1,4,3,0,4,0,2,2,2)\) di Capitolo 4 costa \(63\). La sua rete residua ha il ciclo \(W=1,2,4,5,3,1\), composto dagli archi diretti \((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 Teorema 6.7 \(\bar{\vet{x}}\) non è ottimale. L'aumento di \(1\) dà \(\tilde{\vet{x}}\), del 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 diretto \(3,5,4,3\) di \(G\) costa \(3-12+3=-6\) e ha capacità infinite. Con Proposizione 6.8 il modello è illimitato, come Gurobi conferma: ogni unità inviata nel ciclo riduce il costo di \(6\).

Un flusso ammissibile è ottimale se e solo se la sua rete residua non ha ciclo negativo. Un modello fattibile è illimitato se e solo se un ciclo diretto negativamente ha tutte le sue capacità infinite.

Avanti: 6.4 Condizioni di ottimalità con potenziali