4.9 Un'istanza di traslato

Parte 3 · Flussi · Capitolo 4 · Capitolo 4: Modelli di flusso · Dispensa, volume 3 (PDF) · Esercizi: Modelli di flusso

- Risolviamo il modello \(\mathrm{MCF}\) di Esempio 4.2: la rete di riferimento, con due nodi di alimentazione, due nodi di domanda e due nodi di traslato. La soluzione ottima viene calcolata con Gurobi (gurobipy), e poi certificato a mano con Corollario 4.20.

Esempio 4.9: il flusso ottimale

Il flusso ottimale \(\tilde{\vet{x}}\) e il suo valore ottimale 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 tra i loro limiti sono blu, gli archi a capacità rossa, gli archi vuoti grigi e tratteggiati. Accanto ad ogni nodo, il suo potenziale.

Il flusso è intero, come garantisce 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 uno albero ricoprente. Chiediamo costi ridotti zero su di essi, \(\pi_i-\pi_j=c_{ij}\) e normalizza con \(\pi_6=0\).

2. Andando indietro 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 percorso dell'albero da \(i\) a \(6\): ad 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 al completo. Per Corollario 4.20, \(\tilde{\vet{x}}\) è ottimale.

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

• Unicità. Ogni flusso ottimale ha gap zero con \((\vet{\pi},\vet{\alpha})\), quindi per Teorema 4.19 ha \(x_{32}=x_{43}=0\), \(x_{24}=4\) e \(x_{56}=2\). Il flusso sui cinque gli archi degli alberi viene quindi fissato per conservazione, poiché le loro colonne sono linearmente indipendenti: \(\tilde{\vet{x}}\) è il flusso ottimale unico.

• Il flusso \(\bar{\vet{x}}\). Il flusso ammissibile \(\bar{\vet{x}}\) di Esempio 4.1 costi \(63\), e il suo divario con la stessa soluzione duale è \(63-60=3=\alpha_{24}(u_{24}-\bar{x}_{24})=3 \cdot (4-3)\): l'arco \((2,4)\) non è utilizzato abbastanza.

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

4.10 Errori tipici

Attenzione

• Scambio di flusso in uscita e in entrata. Il vincolo di conservazione è il flusso in uscita meno l'afflusso pari a \(b_i\), con \(b_i>0\) in corrispondenza di un nodo di fornitura: i segni seguono la matrice di incidenza, \(+1\) in coda.

• Prendere \(\sum_i b_i=0\) come sufficiente. Una rete bilanciata non può avere un flusso fattibile: un taglio potrebbe essere troppo piccolo per portare la scorta al suo interno.

• Sbagliare i segni di sostituzione. Con \(\vet{x}=\vet{l}+\vet{x}'\) la coda di \((i,j)\) perde \(l_{ij}\) unità di equilibrio e la testa ne guadagna; al valore deve essere aggiunta nuovamente la costante \(\vet{c}'\vet{l}\).

• Dimenticando il nodo fittizio. Un'istanza con più offerta che domanda non ha un flusso fattibile con uguaglianze; gli archi fittizi devono costare zero, altrimenti la fornitura inutilizzata viene addebitata.

• Rivendicare l'integralità per qualsiasi matrice. I vertici interi necessitano di una matrice TU e di un intero \(\vet{b}\), \(\vet{l}\), \(\vet{u}\); 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.

• Attesi potenziali unici. I potenziali sono definiti fino a una costante additiva; sono fissati da a normalizzazione come \(\pi_n=0\).

4.11 In sintesi

In sintesi

• Una rete ha saldi \(b_i\), limiti inferiori \(l_{ij}\), capacità \(u_{ij}\) e costi \(c_{ij}\); il costo minimo il problema del flusso è 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 deflusso netto è uguale al saldo interno; una rete ammissibile è equilibrata e soddisfa i condizione di taglio.

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

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

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

• Percorso più breve, flusso massimo, trasporto e assegnazione sono i modelli \(\mathrm{MCF}\).

La rete di riferimento in sintesi.

saldi	\(\vet{b}=(5,2,0,-3,0,-4)\)
flusso ottimale	\(\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 ottimale \(62\)
con \(b_2=4\) (nodo fittizio \(7\)) e \(x_{17}=2\), valore ottimale \(56\)

---

Esercizi su questo capitolo: Modelli di flusso