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)