Post on 02-May-2015
Lezione n° 20: 19-20 Maggio 2009
Problema del Massimo Flusso:
- Formulazione Matematica
- Algoritmo del grafo ausiliario
Anno accademico 2008/2009
Prof. Cerulli – Dott.ssa Gentili
Lezioni di Ricerca OperativaCorso di Laurea in Informatica ed Informatica Applicata
Università di Salerno
2
Il Problema del Massimo Flusso
Nodo sorgente: s
10
15
4
156
8
12
5
6
10
Nodo destinazione: t
Capacità: uij
1
2 3
4 5
6
3
Il Problema del Massimo Flusso
Nodo sorgente fornisce flusso fNodo destinazione assorbe flusso -fTutti gli altri nodi sono nodi di transito
Voglio spedire dalla sorgente la massima quantità di flusso fino al pozzo senza violare i vincoli di capacità
4
Il Problema del Massimo Flusso: esempio
10
15
4
156
8
12
5
6
10
1
2 3
4 5
6
5
Il Problema del Massimo Flusso: esempio
3,10
3,15
3,4
1,15
68
12
5
1,6
1,10
1
2 3
4 5
6
1 1 1 3 3 3 564514342312 xxxxxx
6
Il Problema del Massimo Flusso:Formulazione
pozzo al sorgentedalla inviato totaleflusso
j)(i, arcosull' viaggia che flusso diquantità
f
xij
Parametri di input:- Grafo orientato G=(V,A)- Nodo sorgente s- Nodo destinazione t
Variabili decisionali
7
Problema del Massimo Flusso
FORMULAZIONE
A j)(i, 0
: vincolicon
max
)( )(
ijij
iFSj iBSkkiij
ux
ti sef-
si sef
ts,i Vi 0
xx
f
8
Il Problema del massimo flusso: concetti fondamentali
ts10 68
flusso massimo su questo grafo è pari a 6 corrispondente all’arco del cammino con capacità minima
9
ts10 68 9
Riesco ad individuare un taglio sul grafo
9
Il Problema del massimo flusso: concetti fondamentali
10 68 9
ho individuato un taglio: cioè una partizione dei nodi in due insiemi tali V1 e V2 tali che:
- Il nodo sorgente appartiene a V1
- Il nodo pozzo appartiene a V2
- V1 V2 = V - V1 V2 = Ø
estendiamo questo concetto di taglio ad un grafo più complesso
10
Taglio e archi di un taglio
1
10
15
4
156
8
12
5
6
10
Taglio 3: V1 ={1,4,5} V2 = {2,3,6} archi del taglio ={(1,2) (4,3) (5,3) (5,6)}
2 3
4 5
6
Taglio 1: V1 ={1,2,3} V2 = {4,5,6} archi del taglio ={(1,4) (2,4) (2,5) (3,6)}
Taglio 2: V1 ={1,3,5} V2 = {2,4,6} archi del taglio ={(1,2) (1,4) (3,6) (5,6)}
11
Capacità di un Taglio
1
10
15
4
156
8
12
5
6
10
2 3
4 5
6
Dato il taglio (V1, V2) la capacità del taglio è la somma delle capacità degli archi del taglio
12
Capacità di un Taglio
1
10
15
4
156
8
12
5
6
10
Taglio 3: V1 ={1,4,5} V2 = {2,3,6} archi del taglio ={(1,2) (4,3) (5,3) (5,6)}Capacità = 10 + 8 + 6 + 15 = 39
2 3
4 5
6
Taglio 2: V1 ={1,3,5} V2 = {2,4,6} archi del taglio ={(1,2) (1,4) (3,6) (5,6)}Capacità = 10 + 6 + 4 + 15 = 35
Taglio 1: V1 ={1,2,3} V2 = {4,5,6} archi del taglio ={(1,4) (2,4) (2,5) (3,6)}Capacità = 6 + 5 + 12 + 4 =27
13
Relazione tra il massimo flusso e la capacità di un taglio
La capacità di un taglio mi fornisce un limite superiore al valore di flusso che posso spedire dalla sorgente al pozzo
Mi interessa il taglio di capacità minima
se riuscissi ad individuare tutti i tagli del grafo quello di capacità minima mi individuerebbe la strozzatura della rete
la capacità del taglio minimo mi individua il massimo flusso (relazione di dualità)
metodo per testare l’ottimalità di una soluzione
14
Grafo ausiliario e Capacità residua
2;5
1
1;3
2;4
1;4
s t
2
3
3
1
2
2
3
s t
2
3
3
1
2
2
3
2
1
2
1
Grafo ausiliario
15
Grafo ausiliario e Capacità residua
Dato un grafo G=(V,A) ed un flusso ammissibile X, il grafo ausiliario G’=(V,A’) è tale che:
1. se xij<uij esiste in G’ l’arco (i,j) con capacità pari a uij-xij
2. Se xij>0 esiste in G’ l’arco (j,i) con capacità pari a xij
Tutti gli algoritmi risolutivi del problema utilizzano il grafo ausiliario (o rete residua) per decidere come spedire il flusso sulla rete
16
Grafo ausiliario e Cammino aumentante
5
1
3
4
4
s t
2
3
Potrei spedire flusso da s a t tramite cammini
Spedisco 4 unità di flusso tramite il cammino P2 : s – 2 – t
f = 1 +4 =5
4
1
3
4
3s t
3
1 2
1
Spedisco 1 unità di flusso tramite il cammino P1 : s – 2 – 3 – t
f = 1
17
Grafo ausiliario e Cammino aumentante
1
3
4
3s t
3
5Spedisco 3 unità di flusso tramite il cammino P3 : s – 3 – t
f = 5 +3 =8
2
1
1
3
4
s t
3
5 2
4
Il flusso che ho individuato è ottimo?
18
Grafo ausiliario e Cammino aumentante
1
3
4
s t
3
5 2
4
Il flusso che ho individuato è ottimo?
Se riuscissi ad individuare un taglio con capacità uguale al flusso che ho individuato potrei dire che è ottimo
V1= {s} V2= {2,3,t}Archi del taglio: (s,2) (s,3)Capacità = 5 + 3= 8
5
1
3
4
4
s t
2
3
19
Cammino aumentante
1
3
4
3s t
3
5 Cammino : s – 3 – tIndividuato sul grafo ausiliario
2
1 Cammino aumentante
Capacità del Cammino aumentante: = min{u’ij : (i,j) appartiene al cammino }
20
1. Dato un grafo G=(V,A,u): 1.1 definisci un flusso iniziale X ammissibile, in particolare il flusso nullo: xij=0 per ogni i e per ogni j1.2 f=0
2. Costruisci il grafo ausiliario G(X)3. Cerca in G(X) un cammino aumentante p dalla sorgente al pozzo
3.1 Se non esiste alcun cammino allora STOP: il flusso corrente è massimo
4. Sia =min{u’ij: (i,j) appartiene a p }5. Aggiorna il flusso:
5.1 f=f+ 5.2 xij= xij + se (i,j) appartiene ad A5.3 xij= xij - se (j,i) non appartiene ad A
6. Torna al passo 2
L’algoritmo del grafo ausiliario (1/3)
21
L’algoritmo del grafo ausiliario (2/3)Nota:Questo algoritmo è generico: c’e’ almeno un passo che non è
univocamente interpretabileIl passo 3:Cerca in G(X) un qualsiasi cammino orientato p dalla sorgente al pozzo
Può essere realizzato in diversi modi che influenzano la complessità computazionale dell’algoritmo:
- posso cercare un cammino a caso
- posso cercare un cammino con il numero minimo di archi (shortest augmenting path algorithm )
- posso cercare un cammino con una capacità almeno pari ad una quantità fissata di volta in volta (capacity scaling algorithm)
22
21000
1
21000
21000
21000
L’algoritmo del grafo ausiliario (3/3)