Che materia stai cercando?

Anteprima

ESTRATTO DOCUMENTO

Problema di assegnazione

D D D D D D D D

1 2 3 4 1 2 3 4

2 0 0 0

O 2 0 0 0 O

1 1

∗ ∗

1 0

O 1 0 1 1 O 1 1

2 2

∗ ∗

0 0

O 0 0 3 2 O 3 2

3 3

∗ ∗

0 2

O 0 2 3 2 O 3 2

4 4

∗ ∗ ∗ ∗

L’elemento minimo tra quelli non evidenziati risulta 1 e la nuova tabella

equivalente è D D D D

1 2 3 4

3 1

O 0 0

1

O 1 0 0 0

2

O 0 0 2 1

3

O 0 2 2 1

4 dsm

a

Marco Castellani (L’Aquila) Ricerca Operativa Algoritmi su grafi (2 parte) 18 / 49

Problema di assegnazione

Fortunatamente questa sarà l’ultima volta che ripeteremo la procedura

di localizzazione:

D D D D D D D D

1 2 3 4 1 2 3 4

O 3 1 0 0 O 3 1 0 0

1 1

O 1 0 0 0 O 1 0 0 0

2 2

O 0 0 2 1 O 0 0 2 1

3 3

O 0 2 2 1 O 0 2 2 1

4 4

D D D D D D D D

1 2 3 4 1 2 3 4

O 3 1 0 0 O 3 1 0 0

1 1

O 1 0 0 0 O 1 0 0 0

2 2

O 0 0 2 1 O 0 0 2 1

3 3

O 0 2 2 1 O 0 2 2 1

4 4 dsm

a

Marco Castellani (L’Aquila) Ricerca Operativa Algoritmi su grafi (2 parte) 19 / 49

Problema di assegnazione

D D D D D D D D

1 2 3 4 1 2 3 4

O 3 1 0 0 O 3 1 0 0

1 1

O 1 0 0 0 O 1 0 0 0

2 2

O 0 0 2 1 O 0 0 2 1

3 3

O 0 2 2 1 O 0 2 2 1

4 4

D D D D L’assegnazione ottima è

1 2 3 4 D

O 3 1 0 0 (O , )

1 1 3

O 1 0 0 0 D

(O , )

2 2 4

O 0 0 2 1 D

(O , )

3 3 2

O 0 2 2 1 D

(O , )

4 4 1

Il costo totale è 4 6 5 1 16.

+ + + = dsm

a

Marco Castellani (L’Aquila) Ricerca Operativa Algoritmi su grafi (2 parte) 20 / 49

Problema di assegnazione

Visualizziamo gli accoppiamenti / 4 D

O 9

L 2 =

L 1

1 L |

L |

2 L |

L |

L

4 |

L

L |

L

3 |

L |

L

L *

|

3 L /

|

L 4

i

|

L D

O 9

i

L 5 L i

|

L i 2

2 L i

L | i

L

L i

i

| L

7 i L

i

L |

i L

L i

|

i L

L

6 i

i | L

L i L

i

L |

i L

L

i

2 |

i L

L

i | %

L

i

i

i L *

|

5 L /

| L 4

| L D

O 9 L

| 3

3 L

| L

| L

7 L

L

| L

1

| L

| L

L

| 6 L

| !

% *

8 / D

O 6 4

4 dsm

a

Marco Castellani (L’Aquila) Ricerca Operativa Algoritmi su grafi (2 parte) 21 / 49

Problema di assegnazione

Osservazione

Nel caso in cui una o più assegnazioni fossero vietate dal

problema, è sufficiente porre in ogni casella corrispondente un

valore molto grande: ad esempio superiore alla somma di tutti gli

altri costi. In questa maniera tale assegnazione non verrà mai

effettuata.

Nel caso in cui origini e destinazioni non fossero dello stesso

numero è sufficiente aggiungere dei nodi fittizi come origine

oppure destinazione con costi sugli archi nulli: questo si traduce,

a seconda dei casi, nell’aggiunta di righe o colonne con tutti gli

elementi uguali a zero. dsm

a

Marco Castellani (L’Aquila) Ricerca Operativa Algoritmi su grafi (2 parte) 22 / 49

Problema di flusso massimo

G

Sia A) un grafo orientato con n ed ipotizziamo che su

= (N, #N =

ogni arco sia assegnata una capacità massima u (ma, questa volta,

ij

nessun costo) e su ogni nodo, eccetto i nodi 1 e n, il bilancio sia nullo.

Il problema di flusso massimo consiste nel determinare, tra tutti i flussi

ammissibili (cioè che rispettano sia il vincolo di capacità sia la legge di

conservazione di Bernoulli–Kirchoff) quello che permette di inviare un

maggior quantitativo di “materia” dal nodo 1 al nodo n e può essere

formulato come PL:

 X

max x

1j

 (1,j)∈A

 X X

− ∀k −

x x 0, 2, n 1

= = . . . ,

kj ik

 (k ,j)∈A (i,k )∈A

 ≤ ≤

0 x u

 ij ij dsm

a

Marco Castellani (L’Aquila) Ricerca Operativa Algoritmi su grafi (2 parte) 23 / 49

Problema di flusso massimo

Se il grafo fosse il seguente

()*+

/.-, /

()*+

.-,

/

7 =

= @

@ ^ 5

2 === =

=

=

=

==

()*+

/.-, ()*+

/.-, /.-,

()*+

=

5 7

13 10

=

==

=

/ /

9 8

N 7

N p

3 6

1 O

N p

N p

N p

N p

N p

p

N p

N /.-,

()*+ p

N

9 13 p

N p

N p

N 16

N p

' p

4

allora il problema di flusso massimo avrebbe la seguente formulazione

dsm

a

Marco Castellani (L’Aquila) Ricerca Operativa Algoritmi su grafi (2 parte) 24 / 49

Problema di flusso massimo

 max x x x

+ +

12 13 14

 −

x x x 0

+ =

 12 32 25

 − − −

x x x x x 0

+ =

 13 43 32 35 36

 − −

 x x x 0

=

 14 43 46

 −

x x x 0

+ =

 25 35 56

 ≤ ≤

0 x 13

 12

 ≤ ≤

0 x 9

 13

 ≤ ≤

0 x 9

14

≤ ≤

0 x 7

 25

 ≤ ≤

0 x 10

 32

 ≤ ≤

 0 x 5

 35

 ≤ ≤

0 x 8

 36

 ≤ ≤

0 x 13

 43

 ≤ ≤

0 x 16

 46

 ≤ ≤

0 x 7

 56 dsm

a

Marco Castellani (L’Aquila) Ricerca Operativa Algoritmi su grafi (2 parte) 25 / 49

Problema di flusso massimo −1

Aggiungendo un arco fittizio 1) di costo e capacità superiore

(n,

alla somma delle altre capacità, ponendo 0 i bilanci su i nodi 1 e n e 0 i

costi su tutti gli altri archi, il problema di flusso massimo equivale ad un

problema di flusso di costo minimo.

−x

 min n1

 X X

− ∀k

x x 0, 1, n

= = . . . ,

 kj ik

(k ,j)∈A (i,k )∈A

 ≤ ≤

 0 x u

ij ij dsm

a

Marco Castellani (L’Aquila) Ricerca Operativa Algoritmi su grafi (2 parte) 26 / 49

Problema di flusso massimo

Nel nostro caso avremmo /

()*+

.-,

()*+

/.-, / =

=== @

^

@ 5

2 (0,7) =

=

=

==

()*+

/.-, /.-,

()*+

()*+

/.-, (0,7)

(0,13) (0,10) (0,5) =

=

=

/ /

N 7

N p 6

3

1 (0,8)

(0,9)

N

Y O p

N p

N p

N p

p

N /.-,

()*+

(0,9) (0,13) (0,16)

N p

N p

N p

N p

N p

' p

4

(−1,100)

la cui rappresentazione algebrica, togliendo la prima equazione in

quanto combinazione lineare delle altre, è . . . dsm

a

Marco Castellani (L’Aquila) Ricerca Operativa Algoritmi su grafi (2 parte) 27 / 49

Problema di flusso massimo

 −x

min 61

 −

x x x 0

+ =

 12 32 25

 − − −

x x x x x 0

 + =

 13 43 32 35 36

 − −

 x x x 0

=

 14 43 46

 −

x x x 0

+ =

 25 35 56

 −

x x x x 0

+ + =

 36 46 56 61

 ≤ ≤

0 x x 13

,

 12 43

≤ ≤

0 x x 9

,

13 14

 ≤ ≤

0 x x 7

,

 25 56

 ≤ ≤

0 x 10

 32

 ≤ ≤

 0 x 5

 35

 ≤ ≤

0 x 8

 36

 ≤ ≤

0 x 16

 46

 ≤ ≤

0 x 100

 61 dsm

a

Marco Castellani (L’Aquila) Ricerca Operativa Algoritmi su grafi (2 parte) 28 / 49

Problema di flusso massimo

Introduciamo i seguenti concetti utili per la discussione teorica del

problema.

Definizione

Si chiama ⊆

taglio la coppia N con N N N tale che

(N , ) ,

− −

+ +

∪ ∩ ∅;

N N N & N N

= =

− −

+ +

taglio ammissibile un taglio N tale che

(N , )

+

∈ ∈

1 N & n N −

+

Dato un taglio N indichiamo

(N , )

+

+ {(i, ∈ ∈ ∈ }

A j) A i N j N l’insieme degli archi diretti,

= : , −

+

− {(i, ∈ ∈ ∈ }

A j) A i N j N l’insieme degli archi inversi.

= : ,

− + dsm

a

Marco Castellani (L’Aquila) Ricerca Operativa Algoritmi su grafi (2 parte) 29 / 49

Problema di flusso massimo

Definizione x

Dato un taglio N ed un flusso ammissibile si chiama

(N , )

+

capacità del taglio la somma delle capacità degli archi diretti, cioè

X u

u(N N ;

, ) =

+ ij

+

(i,j)∈A

flusso sul taglio X X

x(N x

N x

, ) =

+ ij

ij −

+

(i,j)∈A (i,j)∈A dsm

a

Marco Castellani (L’Aquila) Ricerca Operativa Algoritmi su grafi (2 parte) 30 / 49

Problema di flusso massimo

Il concetto di taglio risulta importante se analizziamo il problema duale

del problema di flusso massimo (che viene chiamato problema del

taglio di capacità minima) X

 min u y

ij ij

 (i,j)∈A

 − ≥ ∀(i, ∈

y 0, j) A

π π +

i j ij

 − 1

 π π =

 n 1

 ≥

 y 0

ij

Ad ogni taglio ammissibile N associamo la seguente soluzione

(N , )

+

ammissibile per il problema duale: +

∈ ∈

0 se i N 1 se j) A

(i,

+ & y

π = =

i ij

1 se i N 0 altrimenti

− dsm

a

Marco Castellani (L’Aquila) Ricerca Operativa Algoritmi su grafi (2 parte) 31 / 49

Problema di flusso massimo

Il valore che la funzione obiettivo del problema duale assume in tale

punto coincide con la capacità del taglio

X X

u y u u(N N

= = , ).

+

ij ij ij

+

(i,j)∈A (i,j)∈A

Quindi la teoria della dualità ci fornisce i seguenti risultati.

Teorema (di dualità debole)

x

Dato un flusso ammissibile ed un taglio ammissibile N si ha

(N , )

+

x(N N u(N N

, ) , ).

− −

+ + dsm

a

Marco Castellani (L’Aquila) Ricerca Operativa Algoritmi su grafi (2 parte) 32 / 49

Problema di flusso massimo

Ed il Teorema di dualità forte.

Teorema (max flow – min cut) x

Se esistono un flusso ammissibile ed un taglio ammissibile N

(N , )

+

tali che x(N N u(N N

, ) = , )

− −

+ +

x

allora è il massimo flusso mentre u(N N è il taglio di capacità

, )

+

minima.

L’algoritmo di Ford–Fulkerson si basa su questo risultato. dsm

a

Marco Castellani (L’Aquila) Ricerca Operativa Algoritmi su grafi (2 parte) 33 / 49

Problema di flusso massimo

Per poter descrivere l’algoritmo di Ford–Fulkerson necessitiamo delle

seguenti nozioni.

Definizione G x,

Dato un grafo A) ed un flusso ammissibile si chiama

= (N, G(x)

x

grafo residuo associato al flusso il grafo A(x)) che ha

= (N,

G

gli stessi nodi di ed i seguenti archi

∈ ∈ −

se j) A e x u allora j) A(x) con capacità v u x

(i, < (i, =

I ij ij ij ij ij

(detta capacità in eccesso),

∈ ∈

se j) A e x 0 allora i) A(x) con capacità v x ;

(i, > (j, =

I ij ij ij

C

cammino aumentante un qualsiasi cammino orientato nel grafo

G(x)

residuo A(x)).

= (N, dsm

a

Marco Castellani (L’Aquila) Ricerca Operativa Algoritmi su grafi (2 parte) 34 / 49

Problema di flusso massimo

x

Supponiamo di avere un flusso 8, 5, 6, 10, 1, 8, 1, 4, 7) sul grafo

= (6,

iniziale, allora il grafo residuo associato diventa

/.-,

()*+ /.-,

()*+

6

x / 7 ==

== ^

@ ^ 5

2 1

= ==

=

6 ==

4

=

()*+

/.-, ()*+

/.-, /.-,

()*+

=

7 7

10 ==

==

1

8

x w

/ o

N 7

N p

3 6

1 8

1

[ H

N p

N p

N p

N p

N p

N

N /.-,

()*+ p

N

4 12 1 12

p

N p

N p

N

N p

' p

5 4

o

4

C {1, G(x)

Il cammino 3, 4, 6} è un cammino aumentante per ma non

= G:

è un cammino orientato nel grafo inziale comporta un aumento di 1

unità di flusso! L’algoritmo di Ford–Fulkerson cerca ad ogni iterazione

un cammino aumentante rispetto al flusso corrente. dsm

a

Marco Castellani (L’Aquila) Ricerca Operativa Algoritmi su grafi (2 parte) 35 / 49

Problema di flusso massimo

Algoritmo di Ford–Fulkerson

0

x 0

Poniamo il flusso ammissibile iniziale;

=

1 k k k

G(x

x

se è un flusso ammissibile, si costruisce A(x

) = (N, ));

2 k k

+1

C G(x

se esiste un cammino aumentante per )

3 allora si calcola

I k

k k

+1

+1 +1

∈ C };

min{v j)

δ = : (i,

ij

k k k

+1 +1 +1

C x

si invia unità di flusso lungo ottenendo il flusso

δ

I k k k

+1 +1

∈ C

 x se j)

+ δ (i,

ij

k +1 k k k

+1 +1

− ∈ C

x se i)

δ (j,

x = ij

ij k

x altrimenti

 ij

si torna al punto 2.

I dsm

altrimenti STOP a

Marco Castellani (L’Aquila) Ricerca Operativa Algoritmi su grafi (2 parte) 36 / 49

Problema di flusso massimo

Quando l’algoritmo si arresta

k

x risulta il flusso massimo,

N è il taglio di capacità minima dove

(N , )

+ {i ∈

N N esiste un cammino orientato da 1 a n}

= :

+ \

N N N

=

− +

Per individuare un cammino aumentante presentiamo la procedura

proposta da Edmonds e Karp nel 1972 su Journal of the Association

k

G(x

for Computing Machinery. Se nel grafo residuo esiste almeno un

)

cammino aumentante, tale algoritmo determina quello formato dal

numero minimo di archi; altrimenti fornisce il taglio di capacità minima.

dsm

a

Marco Castellani (L’Aquila) Ricerca Operativa Algoritmi su grafi (2 parte) 37 / 49

Problema di flusso massimo

Algoritmo di Edmonds–Karp

G(x)

x

Siano un flusso ammissibile e A(x)) il grafo residuo.

= (N, n

{1} −1, −1) ∈

p

Poniamo Q e ;

= = (p ) = (0, . . . ,

1 R

i

se Q =

2 p

allora STOP e fornisce un taglio di capacità minima,

I

altrimenti estraiamo il primo elemento i da Q;

se n) A(x)

(i,

3 p

allora p i STOP e fornisce un cammino aumentante,

=

I n

altrimenti, esplorando in ordine lessicografico tutti i nodi, se

∈ −1

j) A(x) e p poniamo p i, aggiungiamo j a Q e

(i, = =

j j

ritorniamo al Passo 2. dsm

a

Marco Castellani (L’Aquila) Ricerca Operativa Algoritmi su grafi (2 parte) 38 / 49

Problema di flusso massimo

L’ultimo problema che rimane è come si individuano sia il taglio di

capacità minima sia il cammino aumentante quando l’algoritmo di

Edmonds–Karp si arresta: ∅

se l’algoritmo si è arrestato perché Q allora il taglio di

=

capacità minima N sarà formato dagli insiemi

(N , )

+

{i ∈ 6 −1} {i ∈ −1};

N N p & N N p

= : = = : =

+ i i

se l’algoritmo si è arrestato perché n) A(x) allora il cammino

(i,

p

aumentante si ricava da procedendo a ritroso andando alla

ricerca dei predecessori (come avviene per l’algoritmo di Dijkstra).

dsm

a

Marco Castellani (L’Aquila) Ricerca Operativa Algoritmi su grafi (2 parte) 39 / 49


PAGINE

49

PESO

492.03 KB

AUTORE

Atreyu

PUBBLICATO

+1 anno fa


DESCRIZIONE DISPENSA

In questo materiale didattico vengono trattati i seguenti argomenti. Problema di assegnazione: applicazione ed esempi (caso particolare del problema di trasporto). Problema di flusso massimo: applicazioni ed esempi; Teorema di dualità debole; Teorema del max flow-min cut; Algoritmo di Ford-Fulkerson; Algortimo di Edmonds-Karp; applicazioni ed esempi dei due algoritmi.


DETTAGLI
Corso di laurea: Corso di laurea in economia e amministrazione delle imprese
SSD:
Università: L'Aquila - Univaq
A.A.: 2011-2012

I contenuti di questa pagina costituiscono rielaborazioni personali del Publisher Atreyu di informazioni apprese con la frequenza delle lezioni di Ricerca Operativa e studio autonomo di eventuali libri di riferimento in preparazione dell'esame finale o della tesi. Non devono intendersi come materiale ufficiale dell'università L'Aquila - Univaq o del prof Castellani Marco.

Acquista con carta o conto PayPal

Scarica il file tutte le volte che vuoi

Paga con un conto PayPal per usufruire della garanzia Soddisfatto o rimborsato

Recensioni
Ti è piaciuto questo appunto? Valutalo!

Altri appunti di Ricerca operativa

Programmazione Lineare Intera
Dispensa
Programmazione lineare
Dispensa
Algoritmi su grafi - Prima parte
Dispensa
Modelli
Dispensa