6.1 La rete residua con i costi¶
Parte 3 · Flussi · Capitolo 6 · Capitolo 6: Flusso di costo minimo · Dispensa, volume 3 (PDF) · Esercizi: Flusso di costo minimo
-
In questo capitolo la rete \(G=(N,A)\) ha saldi \(b_i\) con \(\sum_{i \in N} b_i=0\), limiti inferiori \(l_{ij}\), capacità \(u_{ij}\) (finite o \(+\infty\)) e costi \(c_{ij}\), come in Capitolo 4. Gli archi sono numerati \(a_1,a_2,\dots,a_m\) in ordine lessicografo.
-
L'insieme \(A\) non ha coppia di archi opposti \((i,j)\), \((j,i)\). Un arco \((j,i)\) opposto a \((i,j)\) può essere sostituito da gli archi \((j,k)\) e \((k,i)\) attraverso un nuovo nodo di traslato \(k\), entrambi con i limiti di \((j,i)\), il primo con il suo costo e il secondo con costo \(0\): i flussi ed i relativi costi non cambiano.
Definizione 6.1: rete residua
Sia \(\vet{x}\) un vettore con \(l_{ij} \le x_{ij} \le u_{ij}\) per ogni arco. La rete residua \(G(\vet{x})=(N,A(\vet{x}))\) ha, per ogni arco \((i,j) \in A\):
-
il arco avanti \((i,j)\), se \(x_{ij}<u_{ij}\), con capacità residua \(r_{ij}=u_{ij}-x_{ij}\) e costo \(c_{ij}\);
-
il arco all'indietro \((j,i)\), se \(x_{ij}>l_{ij}\), con capacità residua \(r_{ji}=x_{ij}-l_{ij}\) e costo \(-c_{ij}\).
Scriviamo \(c^x_{ij}\) per il costo dell'arco \((i,j)\) di \(G(\vet{x})\).
-
Un arco in avanti può trasportare \(r_{ij}\) più unità su \((i,j)\). Un arco all'indietro \((j,i)\) rimanda le unità da \(j\) a \(i\) diminuendo \(x_{ij}\) e risparmia \(c_{ij}\) per unità.
-
Un arco di \(A\) dà due archi di \(G(\vet{x})\) esattamente quando \(l_{ij}<x_{ij}<u_{ij}\). Con \(\vet{l}=\vet{0}\) e senza i costi, \(G(\vet{x})\) è la rete residua di Capitolo 5 «Flusso massimo».
Definizione 6.2: cicli della rete residua
Sia \(W\) un ciclo diretto di \(G(\vet{x})\). Il suo costo e il suo capacità residua sono
e \(W\) è un ciclo negativo se \(c(W)<0\). Aumento \(\vet{x}\) insieme a \(W\) di \(\theta\), con \(0<\theta \le r(W)\), significa aumentare \(x_{ij}\) di \(\theta\) per ogni arco in avanti \((i,j)\) di \(W\) e diminuire \(x_{ij}\) da \(\theta\) per ogni arco \((i,j) \in A\) il cui arco all'indietro \((j,i)\) è in \(W\).
Proposizione 6.3: aumentare lungo un ciclo
Sia \(\vet{l} \le \vet{x} \le \vet{u}\), sia \(W\) un ciclo di \(G(\vet{x})\) e \(0<\theta \le r(W)\), e sia \(\vet{x}'\) può essere \(\vet{x}\) ampliato insieme a \(W\) da \(\theta\). Quindi \(\vet{l} \le \vet{x}' \le \vet{u}\), ogni nodo ha il file stesso deflusso meno afflusso in \(\vet{x}'\) e in \(\vet{x}\), e
Dimostrazione
Controlliamo le tre affermazioni arco per arco.
-
Bounds. Su un arco in avanti, \(x'_{ij}=x_{ij}+\theta \le x_{ij}+r_{ij}=u_{ij}\). Se l'arco all'indietro \((j,i)\) è in \(W\), quindi \(x'_{ij}=x_{ij}-\theta \ge x_{ij}-r_{ji}=l_{ij}\).
-
Saldi. Aumentando di \(\theta\) lungo un arco \((i,k)\) di \(G(\vet{x})\) aumenta il deflusso meno l'afflusso di \(i\) di \(\theta\) e abbassa quello di \(k\) di \(\theta\): un arco in avanti invia più flusso da \(i\) a \(k\), un arco all'indietro invia meno flusso da \(k\) a \(i\). Ogni nodo di \(W\) è la coda di un arco di \(W\) e la testa di un altro, quindi le modifiche annullare.
-
Costo. Un arco in avanti modifica il costo di \(c_{ij}\theta=c^x_{ij}\theta\); un arco all'indietro \((j,i)\) lo cambia di \(-c_{ij}\theta=c^x_{ji}\theta\). La somma di \(W\) dà \(\theta\, c(W)\). □
- Se \(\vet{x}\) è un flusso ammissibile, lo è anche \(\vet{x}'\). Durante un ciclo negativo il costo diminuisce di \(\theta\, |c(W)|\).
Esempio 6.1: la rete residua del flusso più costoso
Utilizziamo la rete di riferimento di Capitolo 4, con limiti inferiori pari a zero, i saldi \(\vet{b}=(5,2,0,-3,0,-4)\) e i costi e le capacità
| arco | \((1,2)\) | \((1,3)\) | \((2,4)\) | \((3,2)\) | \((3,5)\) | \((4,3)\) | \((4,6)\) | \((5,4)\) | \((5,6)\) |
|---|---|---|---|---|---|---|---|---|---|
| \(c_{ij}\) | \(2\) | \(2\) | \(5\) | \(2\) | \(3\) | \(3\) | \(5\) | \(5\) | \(3\) |
| \(u_{ij}\) | \(4\) | \(4\) | \(4\) | \(2\) | \(4\) | \(3\) | \(5\) | \(3\) | \(2\) |
Il suo flusso ammissibile più costoso, calcolato con Gurobi massimizzando il costo, è
con le voci nell'ordine degli archi; è l'unico flusso di costo \(80\), come enumerazione dell'intero \(12\) confermano i flussi fattibili. Ogni arco dà i seguenti archi di \(G(\vet{x}^0)\), con capacità residua e costo:
| arco \((i,j)\) | \((1,2)\) | \((1,3)\) | \((2,4)\) | \((3,2)\) | \((3,5)\) | \((4,3)\) | \((4,6)\) | \((5,4)\) | \((5,6)\) |
|---|---|---|---|---|---|---|---|---|---|
| \(x^0_{ij}\) | \(1\) | \(4\) | \(4\) | \(1\) | \(4\) | \(1\) | \(3\) | \(3\) | \(1\) |
| avanti \((i,j)\): \(r,c\) | \(3,2\) | – | – | \(1,2\) | – | \(2,3\) | \(2,5\) | – | \(1,3\) |
| indietro \((j,i)\): \(r,c\) | \(1,-2\) | \(4,-2\) | \(4,-5\) | \(1,-2\) | \(4,-3\) | \(1,-3\) | \(3,-5\) | \(3,-5\) | \(1,-3\) |
Nella figura ogni arco di \(G(\vet{x}^0)\) porta la coppia \(r_{ij},c^x_{ij}\); il ciclo \(W=4,5,3,4\) è rosso.
-
Il ciclo \(W=4,5,3,4\) utilizza gli archi indietro di \((5,4)\), \((3,5)\) e \((4,3)\):
\[ c(W)=-5-3-3=-11, \qquad r(W)=\min\{3,4,1\}=1. \] -
L'aumento di \(\theta=1\) diminuisce \(x_{54}\), \(x_{35}\) e \(x_{43}\) di un'unità. Il nuovo flusso \(\vet{x}^1=(1,4,4,1,3,0,3,2,1)\) è fattibile e costa \(80-11=69\): l'unità che ha fatto il giro del ciclo diretto \(3,5,4,3\) di \(G\) costa \(11\) e non consegna nulla.
La rete residua \(G(\vet{x})\) ha un arco di costo in avanti \(c_{ij}\) dove \(x_{ij}\) può crescere e un arco all'indietro di costo \(-c_{ij}\) dove \(x_{ij}\) può diminuire. L'aumento lungo un ciclo di \(G(\vet{x})\) mantiene i limiti e il saldi e modifica il costo di \(\theta\, c(W)\).