8.8 Un esempio capacitato con un perno degenere

Parte 4 · Il simplesso su reti · Capitolo 8 · Capitolo 8: Simplesso su reti · Dispensa, volume 4 (PDF) · Esercizi: Simplesso su reti

• Risolviamo l'istanza di traslato di Capitolo 4, la rete di riferimento con capacità, partendo dal flusso \(\bar{\vet{x}}\) di costo \(63\) con la struttura ad albero fortemente ammissibile di 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: rete 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\)

• Questo è il perno di Esempio 8.4: \(e=(1,3) \in U\), apice \(w=2\), \(C=2,3,1,2\), residuo capacità \(0\), \(4\), \(3\).

• \(\theta=0\): il perno è degenere. L'arco \((3,2)\) lascia l'albero verso \(L\) e \((1,3)\) vi entra nel suo capacità. Il costo rimane \(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 idoneo è \(e=(3,5) \in U\), con \(\bar{c}_{35}=3\): \(C\) viene attraversato contro di esso, con \(p=5\) e \(q=3\).

• I percorsi dell'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 di blocco \((2,4)\), in avanti, lascia l'albero e va a \(U\). Un'unità si muove dal percorso \(1,3,5,4\) al percorso \(1,2,4\) e il costo diventa \(63-1 \cdot 3=60\).

• La rimozione di \((2,4)\) elimina \(S=\{1,2,3\}\), che contiene \(k=3\): questi potenziali cambiano con \(\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 ottimale del Capitolo 4, con valore \(60\), e i potenziali sono quelli del suo certificato.

• Le tre strutture ad albero sono fortemente realizzabili. Nel secondo l'arco base \((1,3)\) è al massimo delle sue capacità e punti lontani dalla radice, come richiede la definizione.

• Il pivot degenere non abbassa il costo: sostituisce solo \((3,2)\) con \((1,3)\) nella base. Viene prima perché la regola di immissione preferisce \(|\bar{c}_{13}|=2\) a \(|\bar{c}_{35}|=1\).

• Gurobi conferma il valore ottimale \(60\) e l'enumerazione delle strutture ad albero realizzabili fornisce lo stesso ottimo unico.

Con le capacità, gli archi di \(U\) entrano diminuendo il loro flusso e un arco saturo può lasciare l'albero verso \(U\). Dal flusso \(\bar{\vet{x}}\) un pivot degenere e un pivot con \(\theta=1\) raggiungono il flusso ottimale del capitolo 4, di valore \(60\).

---

Avanti: 8.9 L'albero iniziale: Fase 0