8.8 Un esempio con capacità e un pivot degenere¶
Parte 4 · Il simplesso su reti · Capitolo 8 · Capitolo 8: Simplesso su reti · Dispensa, volume 4 (PDF) · Slide · Esercizi: Simplesso su reti · App: Il simplesso su reti, pivot per pivot
-
Risolviamo l'istanza di trasbordo del Capitolo 4, la rete di riferimento con capacità, a partire dal flusso \(\bar{\vet{x}}\) di costo \(63\) con la struttura ad albero fortemente ammissibile dell'Esempio 8.2:
\[ T=\{(1,2),(2,4),(3,2),(4,6),(5,4)\}, \qquad L=\{(4,3)\}, \qquad U=\{(1,3),(3,5),(5,6)\} . \]
Esempio 8.7: il simplesso su reti con capacità
Iterazione 1
I potenziali sono \(\vet{\pi}=(12,10,12,5,10,0)\) e il costo è \(63\).
| arco | \((1,2)\) | \((1,3)\) | \((2,4)\) | \((3,2)\) | \((3,5)\) | \((4,3)\) | \((4,6)\) | \((5,4)\) | \((5,6)\) |
|---|---|---|---|---|---|---|---|---|---|
| stato | \(\mathrm{T}\) | \(\mathrm{U}\) | \(\mathrm{T}\) | \(\mathrm{T}\) | \(\mathrm{U}\) | \(\mathrm{L}\) | \(\mathrm{T}\) | \(\mathrm{T}\) | \(\mathrm{U}\) |
| \(x_{ij}\) | \(1\) | \(4\) | \(3\) | \(0\) | \(4\) | \(0\) | \(2\) | \(2\) | \(2\) |
| \(\bar{c}_{ij}\) | \(0\) | \(2\) | \(0\) | \(0\) | \(1\) | \(10\) | \(0\) | \(0\) | \(-7\) |
-
È il pivot dell'Esempio 8.4: \(e=(1,3) \in U\), apice \(w=2\), \(C=2,3,1,2\), capacità residue \(0\), \(4\), \(3\).
-
\(\theta=0\): il pivot è degenere. L'arco \((3,2)\) esce dall'albero e va in \(L\), e \((1,3)\) vi entra alla sua capacità. Il costo resta \(63\), e \(\pi_3\) scende da \(12\) a \(10\).
Iterazione 2
I potenziali sono \(\vet{\pi}=(12,10,10,5,10,0)\) e il costo è \(63\).
| arco | \((1,2)\) | \((1,3)\) | \((2,4)\) | \((3,2)\) | \((3,5)\) | \((4,3)\) | \((4,6)\) | \((5,4)\) | \((5,6)\) |
|---|---|---|---|---|---|---|---|---|---|
| stato | \(\mathrm{T}\) | \(\mathrm{T}\) | \(\mathrm{T}\) | \(\mathrm{L}\) | \(\mathrm{U}\) | \(\mathrm{L}\) | \(\mathrm{T}\) | \(\mathrm{T}\) | \(\mathrm{U}\) |
| \(x_{ij}\) | \(1\) | \(4\) | \(3\) | \(0\) | \(4\) | \(0\) | \(2\) | \(2\) | \(2\) |
| \(\bar{c}_{ij}\) | \(0\) | \(0\) | \(0\) | \(2\) | \(3\) | \(8\) | \(0\) | \(0\) | \(-7\) |
-
L'unico arco ammissibile per l'ingresso è \(e=(3,5) \in U\), con \(\bar{c}_{35}=3\): \(C\) è percorso contro di esso, con \(p=5\) e \(q=3\).
-
I cammini nell'albero fino alla radice sono \(3,1,2,4,6\) e \(5,4,6\): l'apice è \(w=4\), e \(C\) è \(4,5,3,1,2,4\).
arco di \(C\) \((5,4)\) \((3,5)\) \((1,3)\) \((1,2)\) \((2,4)\) direzione \(-\) \(-\) \(-\) \(+\) \(+\) residuo \(2\) \(4\) \(4\) \(3\) \(1\) -
\(\theta=1\), e l'arco bloccante \((2,4)\), in avanti, esce dall'albero e va in \(U\). Un'unità passa dal cammino \(1,3,5,4\) al cammino \(1,2,4\), e il costo diventa \(63-1 \cdot 3=60\).
-
Togliendo \((2,4)\) si stacca \(S=\{1,2,3\}\), che contiene \(k=3\): questi potenziali cambiano di \(\bar{c}_{35}=3\).
Iterazione 3
I potenziali sono \(\vet{\pi}=(15,13,13,5,10,0)\) e il costo è \(60\).
| arco | \((1,2)\) | \((1,3)\) | \((2,4)\) | \((3,2)\) | \((3,5)\) | \((4,3)\) | \((4,6)\) | \((5,4)\) | \((5,6)\) |
|---|---|---|---|---|---|---|---|---|---|
| stato | \(\mathrm{T}\) | \(\mathrm{T}\) | \(\mathrm{U}\) | \(\mathrm{L}\) | \(\mathrm{T}\) | \(\mathrm{L}\) | \(\mathrm{T}\) | \(\mathrm{T}\) | \(\mathrm{U}\) |
| \(x_{ij}\) | \(2\) | \(3\) | \(4\) | \(0\) | \(3\) | \(0\) | \(2\) | \(1\) | \(2\) |
| \(\bar{c}_{ij}\) | \(0\) | \(0\) | \(-3\) | \(2\) | \(0\) | \(11\) | \(0\) | \(0\) | \(-7\) |
Gli archi di \(L\) hanno \(\bar{c}_{32}=2>0\) e \(\bar{c}_{43}=11>0\), gli archi di \(U\) hanno \(\bar{c}_{24}=-3<0\) e \(\bar{c}_{56}=-7<0\): STOP. Il flusso è l'unico flusso ottimo del Capitolo 4, con valore \(60\), e i potenziali sono quelli del suo certificato.
-
Le tre strutture ad albero sono fortemente ammissibili. Nella seconda l'arco di base \((1,3)\) è alla sua capacità e punta in senso opposto alla radice, come richiede la definizione.
-
Il pivot degenere non riduce il costo: sostituisce soltanto \((3,2)\) con \((1,3)\) nella base. Viene per primo perché la regola di ingresso preferisce \(|\bar{c}_{13}|=2\) a \(|\bar{c}_{35}|=1\).
-
Gurobi conferma il valore ottimo \(60\), e l'enumerazione delle strutture ad albero ammissibili dà lo stesso ottimo unico.
Con le capacità, gli archi di \(U\) entrano diminuendo il loro flusso, e un arco saturo può uscire dall'albero verso \(U\). Dal flusso \(\bar{\vet{x}}\) un pivot degenere e un pivot con \(\theta=1\) raggiungono il flusso ottimo del Capitolo 4, di valore \(60\).
Avanti: 8.9 L'albero iniziale: la Fase 0