Reti di flusso

(1)

Claudio Arbib

Università di L’Aquila

Ricerca Operativa

Reti di flusso

(2)

Sommario

• Definizioni di base

– Flusso di un campo vettoriale – Divergenza

– Integrale di Gauss-Greene

• Flusso in una rete

• Sorgenti, pozzi e nodi di transito

• Circolazioni e potenziali

• Il problema del flusso ottimo

– Problemi con funzione costo separabile – Problemi concavi e lineari

• Gerarchia dei problemi di flusso ottimo

(3)

Definizioni di base

Sia x(u) = (x

₁

, …, x

_p

) un campo vettoriale in u = (u

₁

, …, u

_p

) ∈ R

^p

Siano S una superficie in R

^p

e n(u) il versore normale a S in u.

∂ x

₁

∂ u

₁

∂ x

_p

∂ u

_p

div(x) =

^_____

+ … +

^_____

divergenza di x

Integrale di Gauss-Greene:

S chiusa

W volume racchiuso da S

ϕ (x, S) = ⌠ ⌡

W

div(x)dW

S

u n(u)

x

ϕ (x, S) = ⌠ ⌡

_S

x(u)·n(u)dS flusso di x attraverso S

(4)

Flusso in una rete

In questo caso si assume che il campo vettoriale x sia diverso da 0 solo sugli archi di una rete, rappresentata come un grafo G = (V, E) con n nodi e m archi.

Se la rete è conservativa, dato un qualsiasi arco uv, il flusso in uv si mantiene costante. Il campo x diviene un vettore con componenti associate agli archi di G:

x ∈ R

^m

distribuzione di flusso

x

₆

x

₅

x

₄

x

₃

x

₂

x

₇

x

₁

S

L’integrale di Gauss-Greene diventa una sommatoria e in ogni

punto ϕ (x, S) eguaglia la differenza tra il flusso uscente da S e

quello entrante in S.

(5)

Esempio:

4

2 –1 0

5 –3

2 S

div(x) = 0

flusso entrante in u flusso uscente da u

Se si riferisce l’integrale volumetrico della divergenza a un volume unitario contenente il punto u, si può scrivere

div

_u

(x) = ϕ (x, S) divergenza di x nel punto u

Flusso in una rete

Poiché nei punti interni di ogni arco la divergenza del campo x è nulla, i suoi valori significativi sono solo quelli associati ai nodi di G.

Questi vengono raccolti in un vettore che rappresenta il bilancio del flusso ai nodi:

div(x) ∈ R

ⁿ

divergenza della distribuzione x

div(x) = (4 – 1 + 0) – (– 3 + 2) = 4

(6)

transito pozzo sorgente

Sorgenti, pozzi e nodi di transito

Si può esprimere la divergenza di x in forma compatta utilizzando la matrice di incidenza nodi-archi G del grafo G.

div(x) = − Gx

Nell’esempio, x = (2, 2, 4, 3, 2, 0, 6, 2)

div

₁

(x) = – (–1, 0, 0, 0, 1, 0, 0, 0)·x = – (– 2 + 2) = 0 div

₃

(x) = – (0, –1, 0, 1, 0, 0, 0, 0)·x = – (– 2 + 3) = –1 div

₄

(x) = – (0, 0,–1,–1, 0, 1, 1, 0)·x = – (– 4 – 3 + 0 + 6) = 1

x

₄₂

x

₆₄

x

₄₃

x

₅₄

x

₆₅

x

₁₂

1

x

₃₆

2

3

6 5

x

₅₁ 4

2 4 3 6 2

2 0 2

12 36 42 43 51 54 64 65 1 –1 0 0 0 1 0 0 0 2 1 0 1 0 0 0 0 0 3 0 –1 0 1 0 0 0 0 4 0 0 –1 –1 0 1 1 0 5 0 0 0 0 –1 –1 0 1 6 0 1 0 0 0 0 –1 –1

G =

0 – 6

–1

6 0

1

flusso uscente dalla rete

flusso entrante nella rete

(7)

Circolazioni

x

₄₂

x

₆₄

x

₄₃

x

₅₄

x

₆₅

x

₁₂

1

x

₃₆

2

3

6 5

x

₅₁ 4

12 36 42 43 51 54 64 65 1 –1 0 0 0 1 0 0 0 2 1 0 1 0 0 0 0 0 3 0 –1 0 1 0 0 0 0 4 0 0 –1 –1 0 1 1 0 5 0 0 0 0 –1 –1 0 1 6 0 1 0 0 0 0 –1 –1

G =

0 0 2 -4 2

6 6 0

La distribuzione banale x = 0 è una circolazione, ma una circolazione non è necessariamente banale.

La somma delle componenti della divergenza è sempre nulla (rete conservativa ⇒ flusso entrante = flusso uscente).

Si definisce circolazione una distribuzione di flusso x a divergenza

identicamente nulla (solo nodi di transito).

(8)

Potenziali

Si dice potenziale un qualsiasi vettore y ∈ R

ⁿ

(Ad esempio, div(x) è un potenziale).

La differenza di potenziale è un vettore ∆ y ∈ R

^m

.

La componente di ∆ y associata al generico arco uv ∈ E è

∆ y

_uv

= y

_v

– y

_u

-5

2 -2 6

3

1

5

6

2

3

6 5

2

4

2 -1 2 1

-3

1 3

Si ha evidentemente ∆ y = yE

_G

Proprietà: per ogni distribuzione di flusso x e ogni potenziale y si ha

x · ∆ y = yGx = – y · div(x)

Inoltre x e ∆ y sono ortogonali per ogni y se e solo se x è una circolazione.

3 0

0 -1 0

-2

(9)

Il problema del flusso ottimo

**Consiste nel determinare una coppia di vettori x* e y*,** appartenenti a determinate regioni ammissibili Φ e Ω ,

che rappresentino una distribuzione e un potenziale in una rete e minimizzino una data funzione f (x, y):

min f (x, y)

div(x) = y

x ∈ Φ ⊆ R

^m

y ∈ Ω ⊆ R

ⁿ

(10)

Funzione di costo separabile

La funzione f (x, y) si dice separabile se può essere espressa come somma di funzioni dipendenti

individualmente dal valore del flusso in ciascun arco o del potenziale in ciascun nodo:

f (x, y) = Σ

uv∈E

f

_uv

(x

_uv

) + Σ

u∈V

f

_u

(y

_u

)

Esempio: la forma lineare f (x, y) = cx + c’y è evidentemente separabile.

Esempio: la forma quadratica x

^T

Ax, con A ∈ R

^m×m

, non è in genere separabile in quanto

x

^T

Ax = Σ

^h∈E

Σ

^k∈E

^a

^hk

^x

^h

^x

^k

contiene termini misti, cioè dipendenti da flussi in archi distinti.

(11)

Gerarchia dei problemi di flusso ottimo

flusso ottimo flusso ottimo

flusso con costo separabile flusso con costo

separabile

flusso con costo lineare

flusso max flusso max cammino min

cammino min matching perfetto

bipartito matching perfetto

bipartito CPMCPM

CPM duale CPM duale

taglio min taglio min