Lezioni di Ricerca Operativa
Corso di Laurea in Informatica ed Informatica Applicata
Università di Salerno
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
Il Problema del Massimo Flusso
Capacità: uij
15
2
10
6
4
12
5
1
3
6
8
4
Nodo sorgente: s
6
15
10
5
Nodo destinazione: t
2
Il Problema del Massimo Flusso
Nodo sorgente fornisce flusso f
Nodo destinazione assorbe flusso -f
Tutti 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à
3
Il Problema del Massimo Flusso: esempio
15
2
10
6
4
12
5
1
3
6
8
4
6
15
10
5
4
Il Problema del Massimo Flusso: esempio
3,15
2
3,10
1,6
3,4
12
5
1
3
6
8
6
1,15
4
1,10
5
x12  3 x23  3 x34  3 x14  1 x45  1 x56  1
5
Il Problema del Massimo Flusso:
Formulazione
Parametri di input:
- Grafo orientato G=(V,A)
- Nodo sorgente s
- Nodo destinazione t
Variabili decisionali
xij  quantità di flusso che viaggia sull' arco (i, j)
f  flusso totale inviato dalla sorgente al pozzo
6
Problema del Massimo Flusso
FORMULAZIONE
max f
con vincoli :
 0 i V i  s,t

xij   xki   f
se i  s

jFS ( i )
kBS ( i )
- f
se i  t

0  xij  uij
 (i, j)  A
7
Il Problema del massimo flusso: concetti
fondamentali
s
10
8
t
6
9
flusso massimo su questo grafo è pari a 6
corrispondente all’arco del cammino con capacità minima
s
10
8
t
6
9
Riesco ad individuare un taglio sul grafo
8
Il Problema del massimo flusso: concetti
fondamentali
10
8
6
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
9
Taglio e archi di un taglio
15
2
10
6
4
12
5
1
3
6
8
6
15
4
5
10
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)}
Taglio 3: V1 ={1,4,5} V2 = {2,3,6}  archi del taglio ={(1,2) (4,3) (5,3) (5,6)}
10
Capacità di un Taglio
15
2
10
6
4
12
5
1
3
6
8
6
15
4
5
10
Dato il taglio (V1, V2) la capacità del taglio è la somma delle
capacità degli archi del taglio
11
Capacità di un Taglio
15
2
10
6
4
12
5
1
3
6
8
6
15
4
5
10
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
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 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
12
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
13
Grafo ausiliario e Capacità residua
2
2
2;5
s
s
t
1
1;3
3
2;4
3
2
3
3
2
3
Grafo ausiliario
t
1
1;4
2
2
2
1
2
1
3
1
14
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
15
Grafo ausiliario e Cammino aumentante
Potrei spedire flusso da s a t tramite cammini
2
5
4
s
t
1
3
4
3
2
1
4
s
Spedisco 1 unità di flusso tramite il
cammino P1 : s – 2 – 3 – t
f=1
4
t
1
Spedisco 4 unità di flusso tramite il cammino
P2 : s – 2 – t
f = 1 +4 =5
3
3
3
1
16
Grafo ausiliario e Cammino aumentante
2
5
s
4
t
1
Spedisco 3 unità di flusso tramite il cammino
P3 : s – 3 – t
f = 5 +3 =8
3
3
3
2
5
s
1
t
1
3
3
Il flusso che ho individuato è ottimo?
4
4
17
Grafo ausiliario e Cammino aumentante
2
5
s
t
1
3
Il flusso che ho individuato è ottimo?
4
3
Se riuscissi ad individuare un taglio
con capacità uguale al flusso che ho
individuato potrei dire che è ottimo
4
2
5
s
4
t
1
3
3
V1= {s} V2= {2,3,t}
Archi del taglio: (s,2) (s,3)
Capacità = 5 + 3= 8
4
18
Cammino aumentante
2
5
s
4
Cammino : s – 3 – t
Individuato sul grafo ausiliario
t
1
3
3
3
1
Cammino aumentante
Capacità del Cammino aumentante:
 = min{u’ij : (i,j) appartiene al cammino }
19
L’algoritmo del grafo ausiliario (1/3)
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 j
1.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 A
5.3 xij= xij -  se (j,i) non appartiene ad A
6. Torna al passo 2
20
L’algoritmo del grafo ausiliario (2/3)
Nota:
Questo algoritmo è generico: c’e’ almeno un passo che non è
univocamente interpretabile
Il 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)
21
L’algoritmo del grafo ausiliario (3/3)
21000
21000
1
21000
21000
22