4.9 Un'istanza di trasbordo¶
Parte 3 · Flussi · Capitolo 4 · Capitolo 4: Modelli di flusso · Dispensa, volume 3 (PDF) · Slide · Esercizi: Modelli di flusso
- 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.
Il flusso è intero, come garantisce il Corollario 4.16.
4.9.1 Il certificato di ottimalità¶
-
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\).
-
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\).
-
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