Flusso di Costo Minimo
Trasformazioni Equivalenti e Trasformazioni Inverse
Viene data la seguente rete di flusso, in cui i valori riportati vicino agli archi sono i
costi, e quelli riportati vicino ai nodi sono le richieste di flusso (ovvero i termini noti b)
-2
1
1
1
2
1
-4
0
2
4
-1
1
3
2
L’arco (4,2) ha capacità superiore 3 e capacità inferiore 1; l’arco (2,3) ha capacità
superiore 1 e capacità inferiore -1; gli altri archi hanno capacità superiore 2 e
capacità inferiore 0.
1. Trasformiamo la rete data in una rete equivalente con costi non negativi,
capacità inferiori nulle, singola origine e singola destinazione. Determiniamo la
costante F aggiunta alla funzione obiettivo nel corso della trasformazione.
2. A partire dal flusso ottimo x sulla rete trasformata (che verrà dato
implicitamente fornendo il corrispondente grafo residuo), determiniamo il flusso
ottimo nella rete originale. Confrontiamo il costo delle due soluzioni ottime,
tenendo conto della costante F trovata al Passo 1.
Passo 1 passaggio alla rete trasformata
-2
1
1
4
arco (4,2)
•costo negativo,
•capacità superiore 3
•capacità inferiore 1
-4
0
2
-1
1
2
3
1
1
2
Fase 1: eliminazione costi negativi: si satura l’arco (4,2), spedendo un flusso 3.
Il nuovo arco (2,4) ha capacità superiore 2. Si aggiunge alla f.o. il valore -4*3=-12.
-2
1
1
2
2
-2
4
2
4
0
1
1
Nota: il nuovo arco ha
capacità inferiore nulla
3
2
F = -12
Passo 1 passaggio alla rete trasformata
-2
1
1
4
0
2
4
2
1
2
-2
arco (2,3)
•costo 1
•capacità superiore 1
•capacità inferiore -1
3
1
2
Fase 2: eliminazione capacità inferiori non nulle. Dopo la trasformazione, l’arco (2,3) ha
capacità superiore 2. Si aggiunge alla costante F il valore -1.
-2
1
1
2
2
-3
4
2
4
0
1
1
3
3
F = -12 -1 = -13
Passo 1 passaggio alla rete trasformata
-2
1
1
4
4
0
2
2
1
2
-3
3
1
3
Fase 3: singola origine e singola destinazione. In azzurro le capacità superiori degli archi
aggiuntivi, tutti gli altri archi hanno capacità superiore pari a due.
2
-5
1
0
s
0
4
0
2
4
0
2
3
1
t 5
1
2
1
3
0
3
F = -13
Passo 1 passaggio alla rete trasformata
Rete trasformata: a ciascun arco si associa la coppia [costo,capacità superiore]
1
[0, 2]
[1, 2]
4
[0, 2]
[4, 2]
-5
s
t
[1, 2]
[2, 2]
5
[0, 2]
[0, 3]
2
[1, 2]
3
[0, 3]
F = -13
Soluzione ottima sulla rete trasformata
Grafo residuo rispetto al flusso ottimo: il valore vicino ad ogni arco è la sua capacità
superiore; gli archi “inversi” appaiono in rosso
2
1
2
s
1
1
3
4
1
2
2
t
1
1
2
3
3
2
Nota: il grafo residuo rispetto al flusso ottimo sarà il risultato dell’applicazione
degli algoritmi per MCF
Soluzione ottima sulla rete trasformata
Partendo dal grafo residuo relativo al flusso ottimo troviamo tale flusso sulla rete
trasformata
2
1
2
s
1
1
1
3
4
2
2
t
1
1
2
3
3
2
[0, 2] 2
1
2 [1, 2]
4
[4, 2]
-5
s
[2, 2] 1
0
[0, 3]
3
2
1
[0, 2]
[1, 2]
2 [0, 2]
0
[1, 2]
3
t 5
3 [0, 3]
2
Il costo totale del flusso ottimo sulla rete trasformata è (costo × flusso)
(2 × 1) + (1 × 2) + (1 × 2) = 6
(2,1)
(1,4)
(2,3)
Passo 2 Flusso ottimo sulla rete originale
Per prima cosa, ignoriamo gli archi fittizi (trasformazione inversa della Fase 3).
-2
-2
1
2
4
[4, 2]
[2, 2] 1
0
-3
2
-3
2
[1, 2]
1
[0, 2]
[1, 2]
0
[1, 2]
3
2
2
3
3
Trasformazione inversa della Fase 2: archi a capacità inferiore non nulla.
arco (2,3) originale
L’arco (2,3) sulla rete originale ha un flusso –1 + 2 = 1
•costo 1
-2
2
2 [1, 2]
-2
2 •capacità superiore 1
1
4
•capacità inferiore -1
[4, 2]
0
[1, 2]
[2, 2] 1
1
0 [0, 2]
-2
2
3
2
[1, 2] 1
-2
2
Passo 2 Flusso ottimo sulla rete originale
Trasformazione inversa della Fase 1: archi a costo negativo. L’arco (4,2) ha un flusso
3 – 0 = 3.
arco (4,2) originale
-2
-1
2 [1, 2]
-2
-1 •costo negativo -4,
1
4
•capacità superiore 3
[-4, 2]
•capacità inferiore 1
0
[1, 2]
[2, 2] 1
1
3 [0, 2]
1
2
3
2
[1,
2]
1
1
2
I numeri vicini ai nodi sono le differenze flusso entrante meno flusso uscente;
si può verificare che corrispondono alle richieste (termini noti) sulla rete originale.
Passo 2 Flusso ottimo sulla rete originale
Calcolo e confronto dei costi delle soluzioni
-2
-2
1
2
4
[-4, 2]
[2, 2] 1
1
[0, 2]
3
1
2
1
-1
[1, 2]
[1, 2]
0
[1, 2]
3
1
-1
2
2
Il costo totale del flusso ottimo sulla rete originale è (costo × flusso)
2 × 1 + 1 × 1 + (– 4) × 3 + 0 × 1 + 1 × 2 = -7
(2,1)
(2,3)
(4,2)
(1,3)
(1,4)
Il costo del flusso ottimo sulla rete originale è dato dal costo sulla rete trasformata (6)
più la costante F (– 13).