Vai al contenuto

4.9 Un'istanza di trasbordo

  • Risolviamo il modello \(\mathrm{MCF}\) dell'Esempio 4.2: la rete di riferimento, con due nodi di offerta, due nodi di domanda e due nodi di trasbordo. La soluzione ottima è calcolata con Gurobi (gurobipy), e poi certificata a mano con il Corollario 4.20.

Esempio 4.9: il flusso ottimo

Il flusso ottimo \(\tilde{\vet{x}}\) e il suo valore ottimo sono

arco \((1,2)\) \((1,3)\) \((2,4)\) \((3,2)\) \((3,5)\) \((4,3)\) \((4,6)\) \((5,4)\) \((5,6)\)
\(\tilde{x}_{ij}\) \(2\) \(3\) \(4\) \(0\) \(3\) \(0\) \(2\) \(1\) \(2\)
\(u_{ij}\) \(4\) \(4\) \(4\) \(2\) \(4\) \(3\) \(5\) \(3\) \(2\)

\(z(\mathrm{MCF})=60\).

Nella figura ogni arco porta \(\tilde{x}_{ij}/u_{ij}\): gli archi strettamente compresi fra i loro limiti sono blu, gli archi saturi rossi, gli archi vuoti grigi e tratteggiati. Accanto a ogni nodo, il suo potenziale.

Figura 3

Il flusso è intero, come garantisce il Corollario 4.16.

4.9.1 Il certificato di ottimalità

  1. I cinque archi blu \((1,2)\), \((1,3)\), \((3,5)\), \((4,6)\), \((5,4)\) formano un albero ricoprente. Imponiamo costo ridotto nullo su di essi, \(\pi_i-\pi_j=c_{ij}\), e normalizziamo con \(\pi_6=0\).

  2. Procedendo a ritroso dal nodo \(6\): \(\pi_4=\pi_6+c_{46}=5\), \(\pi_5=\pi_4+c_{54}=10\), \(\pi_3=\pi_5+c_{35}=13\), \(\pi_1=\pi_3+c_{13}=15\) e \(\pi_2=\pi_1-c_{12}=13\).

  3. Il potenziale \(\pi_i\) è il costo del cammino nell'albero da \(i\) a \(6\): per esempio, \(\pi_1=c_{13}+c_{35}+c_{54}+ c_{46}=2+3+5+5=15\).

Esempio 4.10: costi ridotti e ottimalità

I costi ridotti \(\bar{c}_{ij}=c_{ij}-\pi_i+\pi_j\) sono:

arco \((1,2)\) \((1,3)\) \((2,4)\) \((3,2)\) \((3,5)\) \((4,3)\) \((4,6)\) \((5,4)\) \((5,6)\)
\(\bar{c}_{ij}\) \(0\) \(0\) \(-3\) \(2\) \(0\) \(11\) \(0\) \(0\) \(-7\)
\(\alpha_{ij}\) \(0\) \(0\) \(3\) \(0\) \(0\) \(0\) \(0\) \(0\) \(7\)

  • Gli archi con \(\bar{c}_{ij}>0\), \((3,2)\) e \((4,3)\), sono vuoti; gli archi con \(\bar{c}_{ij}<0\), \((2,4)\) e \((5,6)\), sono saturi. Per il Corollario 4.20, \(\tilde{\vet{x}}\) è ottimo.

  • Il valore duale è \(\sum_{i \in N} b_i\pi_i-\sum_{(i,j) \in A} u_{ij}\alpha_{ij}=86-26=60\), uguale al costo di \(\tilde{\vet{x}}\). I potenziali coincidono con i valori duali restituiti da Gurobi, traslati in modo che \(\pi_6=0\).

  • Unicità. Ogni flusso ottimo ha gap nullo con \((\vet{\pi},\vet{\alpha})\), quindi per il Teorema 4.19 ha \(x_{32}=x_{43}=0\), \(x_{24}=4\) e \(x_{56}=2\). Il flusso sui cinque archi dell'albero è allora fissato dalla conservazione, perché le loro colonne sono linearmente indipendenti: \(\tilde{\vet{x}}\) è l'unico flusso ottimo.

  • Il flusso \(\bar{\vet{x}}\). Il flusso ammissibile \(\bar{\vet{x}}\) dell'Esempio 4.1 costa \(63\), e il suo gap con la stessa soluzione duale è \(63-60=3=\alpha_{24}(u_{24}-\bar{x}_{24})=3 \cdot (4-3)\): l'arco \((2,4)\) è usato troppo poco.

Sulla rete di riferimento il flusso ottimo costa \(60\). I potenziali del suo albero ricoprente danno costi ridotti positivi solo su archi vuoti e negativi solo su archi saturi: certificano l'ottimalità senza un solutore.

4.10 Errori tipici

Attenzione

  • Scambiare flusso uscente e flusso entrante. Il vincolo di conservazione è flusso uscente meno flusso entrante uguale a \(b_i\), con \(b_i>0\) in un nodo di offerta: i segni seguono la matrice di incidenza, \(+1\) nella coda.

  • Considerare sufficiente \(\sum_i b_i=0\). Una rete bilanciata può non avere flussi ammissibili: un taglio può essere troppo piccolo per trasportare l'offerta dei nodi interni.

  • Sbagliare i segni della sostituzione. Con \(\vet{x}=\vet{l}+\vet{x}'\) la coda di \((i,j)\) perde \(l_{ij}\) unità di bilancio e la testa le guadagna; la costante \(\vet{c}'\vet{l}\) va aggiunta di nuovo al valore.

  • Dimenticare il nodo fittizio. Un'istanza con più offerta che domanda non ha flussi ammissibili con le uguaglianze; gli archi fittizi devono costare zero, altrimenti l'offerta non usata viene pagata.

  • Pretendere l'integralità per qualsiasi matrice. I vertici interi richiedono una matrice TU e \(\vet{b}\), \(\vet{l}\), \(\vet{u}\) interi; i costi possono essere frazionari.

  • Scrivere il costo ridotto con i segni sbagliati. In questo modulo \(\bar{c}_{ij}=c_{ij}-\pi_i+\pi_j\), con \(-\pi\) della coda e \(+\pi\) della testa.

  • Aspettarsi potenziali unici. I potenziali sono definiti a meno di una costante additiva; si fissano con una normalizzazione come \(\pi_n=0\).

4.11 In sintesi

In sintesi

  • Una rete ha bilanci \(b_i\), limiti inferiori \(l_{ij}\), capacità \(u_{ij}\) e costi \(c_{ij}\); il problema di flusso di costo minimo è l'LP \(\min\{\vet{c}'\vet{x} : \mat{B}\vet{x}=\vet{b},~\vet{l} \le \vet{x} \le \vet{u}\}\).

  • Attraverso ogni taglio il flusso uscente netto è uguale al bilancio dei nodi interni; una rete ammissibile è bilanciata e soddisfa la condizione di taglio.

  • I limiti inferiori si rimuovono con \(\vet{x}=\vet{l}+\vet{x}'\); un eccesso di offerta va a un nodo fittizio attraverso archi a costo zero.

  • La matrice di incidenza è totalmente unimodulare, quindi con \(\vet{b}\), \(\vet{l}\), \(\vet{u}\) interi ogni vertice è intero e il modello \(\mathrm{MCF}\) ha una soluzione ottima intera.

  • Il duale ha i potenziali \(\pi_i\); con \(\bar{c}_{ij}=c_{ij}-\pi_i+\pi_j\), un flusso con gli archi a costo positivo vuoti e gli archi a costo negativo saturi è ottimo.

  • Cammino minimo, flusso massimo, trasporto e assegnamento sono modelli \(\mathrm{MCF}\).

La rete di riferimento in breve.

bilanci \(\vet{b}=(5,2,0,-3,0,-4)\)
flusso ottimo \(\tilde{\vet{x}}=(2,3,4,0,3,0,2,1,2)\), \(z(\mathrm{MCF})=60\)
potenziali (\(\pi_6=0\)) \(\vet{\pi}=(15,13,13,5,10,0)\)
archi vuoti / saturi \((3,2)\), \((4,3)\) / \((2,4)\), \((5,6)\)
con \(l_{32}=1\) \(\vet{b}'=(5,3,-1,-3,0,-4)\), valore ottimo \(62\)
con \(b_2=4\) (nodo fittizio \(7\)) \(x_{17}=2\), valore ottimo \(56\)


Esercizi su questo capitolo: Modelli di flusso