Vai al contenuto

8.8 Un esempio con capacità e un pivot degenere

  • 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\).

Figura 6

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.

Figura 7

  • 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