Cammino Minimo Massimo Flusso

(1)

Cammino Minimo Massimo Flusso

“Sapienza” Università di Roma - Dipartimento di Ingegneria Informatica, Automatica e Gestionale

Questa sezione è derivata dal materiale del prof. A. Sassano Corso di:

Ottimizzazione Combinatoria

Docente:

Renato Bruni

[email protected]

(2)

Cammino di costo minimo da

Cammino di costo minimo da s s a a t t

TROVARE: Il CAMMINO ORIENTATO P* da s a t avente COSTO MINIMO

**P: w(P) ≤ w(P) ∀ cammino orientato P da s a t di G(N,A)**

A volte, per semplicità di notazione, e quando questo non produce confusione denoteremo con P l’insieme A(P)

P*={sd,dc,cf,ft} c(P*)=7 P={sf,ft} c(P)=8

DATI:

- Grafo orientato e connesso G(N,A) - Due nodi speciali s e t

- ∃ ∃ cammino orientato da s ad ogni u∈N - Costi sugli archi w

_uv

∀ uv∈ A

f 3 b t

a

d 1

2

c

s

2 1

w w

_sd_sd

=

³

10

1

Il costo di un cammino P di G(N,A) sia

7

w(A(P)) = w(P) = ∑ ^w

uv

uv∈A(P)

(3)

Vettore di Incidenza di un Cammino Vettore di Incidenza di un Cammino

Def.: x^P∈{0,1}^A vettore di incidenza di P

=1 uv∈ P

=0 uv∉ P x^P

uv

x^P

uv

Rappresentazione di un cammino

Proprietà di x^P

∑

^x^P_us^{= 0}

us∈ δ_G^-(s)

∑

su∈ δ_G⁺(s)

x^P

su = 1

(i) Da s esce un solo arco di un cammino P

∑

^x^P_ut ^{= 1}

ut∈ δ_G^-(t)

∑

tu∈ δ_G⁺(t)

x^P

tu = 0

(ii) In t entra un solo arco di P

∑

^x^P_uv

uv∈ δ_G^-(v)

∑

vu∈ δ_G⁺(v)

x^P

= vu ⁽ⁱⁱⁱ⁾ In ogni altro nodo v∉ {s,t}

Numero archi di P entranti =

= Numero archi di P uscenti

f b

a

d

s c

t

P

x^P

ft 1 sa

cf da df td ac bc sb

1

1 1 0 0 0 0 cs

ct 0 0 0

(4)

Cammino

Cammino min come min come problema problema di di Flusso Flusso Intero Intero

4

DATI:

Un grafo orientato G(N,A)

Un vettore capacità c = = ∞ ∞

_|A|_|A|

Un vettore domanda d

_st

=

















1 0 0 0 0 1 -

t 4 3 2 1

s

∞ ∞

ss

22

33 44

55

tt

-1-1

00

11 00

00

∞ ∞

possiamo scrivere il problema del Cammino Minimo (CM) come:

Cioè come flusso intero di

( ^G, ^d

_st

^, ∞

_|A|

)

Poliedro dei cammini da s a t

Q

_st

={x: Mx = d

_st

, x ≥ 0

_|A|

}

min {w

^T

x : x ∈ Q

_st

}

(5)

Rappresentazione grafica di una soluzione

Rappresentazione grafica di una soluzione x x ∈Q ∈ Q

_st_st

DEFINIZIONE: Dato un vettore x diremo SUPPORTO di x l’insieme di archi S(x)={e∈A: x_e >0}

Rappresenteremo un vettore x evidenziando gli archi del

supporto (ad es. in rosso) e (a volte) indicando il valore della componente di x_e accanto all’arco e

11 00

ss

22

33 44

55

tt

11

11 00 11

00

≡

00 11 00 11 11 11 11

00 ⁵^t t 4 34 53 25 32 2 s

3 s

(6)

Vettori del Poliedro dei Cammini (Esempi) Vettori del Poliedro dei Cammini (Esempi)

Q_st =

{

^x∈^ℜ^|A|^: ^{Mx=b, x}^≥⁰_|A|

}

2

s t

1

s1 s2 12 1t 2t

x^P

x^P’

1 0

0 1 0

1 0

1 0 1

Non è un cammino ma sta nel poliedro dei cammini !

s1 s2 12 1t 2t

1/2 1/2 1/4 1/4 3/4

^x

s t

1

2 1/2

1/2

1/4 1/4

3/4

x∈ Q_st

^

- x_s1- xs2 = -1

x_s2+ x12 - x_2t= 0

xs1 - x₁₂- x1t = 0

x_1t+ x_2t= 1

s t

1

2

x^P∈ Q_st

P cammino s-t

1

0 0 0

1

s t

1

2

x^P’∈ Q_st

P’ cammino s-t

1

1 1 0

0

(7)

Vettore di incidenza di un cammino

Vettore di incidenza di un cammino ⇒ ⇒ flusso intero flusso intero

7

(0(0, ,

∞ ∞

))

ss

22

33 44

55

tt

-- 11

00

11 00

00

(1(1, ,

∞ ∞

))

(0(0,,

∞ ∞

))

(1(1,,

∞ ∞

)) (0(0,,

∞ ∞

)) (0(0,,

∞ ∞

))

(0(0, ,

∞ ∞

))

(1(1, ,

∞ ∞

))

(i) da s esce un solo arco di P P

(iii) In ogni nodo v∉ {s,t}

--

un arco di P P entrante e un arco di P P uscente

OPPUREOPPURE

- - nessun arco di P P entrante o uscente

x

^P vettore di incidenza di un cammino orientato

P P

(ii) in t entra un solo arco di P P

x

^P

flusso intero di ( ( G, G, d d

_st_st

, , ∞ ∞

_|A|_|A|

) )

Viceversa?

(0(0, ,

∞ ∞

)) (0(0, ,

∞ ∞

))

ss

22

33 44

55

tt

-1-1

00

11 00

00

(1(1, ,

∞ ∞

))

(0(0,,

∞ ∞

))

(2(2,,

∞ ∞

))

(1(1,,

∞ ∞

)) (1(1,,

∞ ∞

))

(1(1,,

∞ ∞

))

No! ⇒ ⇒

(8)

I vertici di Q

_st

sono (flussi) interi ( M totalmente unimodulare) M

Flussi interi e vertici di Q

_st

ma ( non tutti i flussi interi

x∈Q x

_st sono vertici: combinando i due seguenti flussi interi ho un nuovo flusso intero che quindi non è un vertice

(0(0, ,

∞ ∞

))

ss

22

33 44

55

tt

-- 11

00

11 00

00

(1(1,,

∞ ∞

))

(0(0,,

∞ ∞

))

(2(2,,

∞ ∞

))

(1(1,,

∞ ∞

)) (1(1,,

∞ ∞

))

(1(1,,

∞ ∞

))

=

+ 1/2

E allora ( quali sono i vertici di Q

_st

^? (SBA ( SBA) )

(0(0, ,

∞ ∞

))

ss

22

33 44

55

tt

-- 11

00

11 00

00

(1(1, ,

∞ ∞

))

(0(0,,

∞ ∞

))

(3(3,,

∞ ∞

))

(2(2,,

∞ ∞

)) (2(2,,

∞ ∞

))

(1(1,,

∞ ∞

)) (0(0, ,

∞ ∞

))

ss

22

33 44

55

tt

-- 11

00

11 00

00

(1(1, ,

∞ ∞

))

(0(0,,

∞ ∞

))

(1(1,,

∞ ∞

))

(0(0,,

∞ ∞

)) (0(0,,

∞ ∞

))

(1(1,,

∞ ∞

))

1/2

(9)

TEOREMA F1: x’∈Q_st è una Soluzione di Base (SBA) se e solo se S(x’)={e∈A: x’_e>0} (supporto di x’) è una FORESTA di G(N,A)

Soluzioni

Soluzioni Ammissibili Ammissibili di di Base (SBA) Base (SBA)

TEOREMA F2:

x ′ ∈ Q

_st ^{è una} SOLUZIONE AMMISSIBILE DI BASE se e solo se è VETTORE DI INCIDENZA DI UN CAMMINO ORIENTATO PP da ss a t.t

Abbiamo visto che nel poliedro dei cammini Q_st ci sono tanti punti che non sono cammini. Vediamo allora dove sono i cammini in questo poliedro. Si hanno 2 teoremi:

Quindi i cammini sono i vertici (SBA) del poliedro dei

cammini Q

_st

(10)

Cammini Minimi e Programmazione Lineare Cammini Minimi e Programmazione Lineare

TROVARE: Il CAMMINO ORIENTATO P* da s a t avente COSTO MINIMO

Il METODO DEL SIMPLESSO (eventualm. semplificato per questo specifico caso) individua la soluzione di base (vertice) avente costo minimo

TROVARE: Un VETTORE DI INCIDENZA x^P di un CAMMINO ORIENTATO P da s a t avente COSTO MINIMO w^Tx^P

w(P)=

∑

^wuv =

∑

^wuv x^P_uv= w^Tx^P

uv∈A(P) uv∈A

TROVARE: Una SOLUZIONE DI BASE (VERTICE) x del Poliedro Q_st ={x∈ ℜ^|A|: ^{Mx=b, x}≥ 0_|A|} avente COSTO MINIMO w^Tx

[Teorema F1]

RISOLVERE IL PROBLEMA DI PROGRAMMAZIONE LINEARE:

(CM) min w^Tx min w^Tx

Mx=b x∈Q_st=

{

^x∈^ℜ^|A|^: ^{Mx=b, x}^≥ ⁰_|A|

}

x ≥ 0_|A|

≡

[Teoria della Programmazione Lineare]

(11)

Problema

Problema Primale Primale e Problema Duale e Problema Duale

M b

Cioè, vista la struttura di b e di M:

(DCM) max y_t -y_s

y_v - y_u ≤ c_uv per ogni uv∈A

PROBLEMA PRIMALE:

(CM) min c^Tx

Mx=b x ≥0_|A|

u

v

-1

1 0

0

0 t uv

1 -1 s

PROBLEMA DUALE:

(DCM) max b^Ty

M^Ty ≤ c

1 0 0

b^T

t u v

-1 1

uv

M^T

0 0 0

-1 s

Possiamo eliminare la riga corrispondente ad s e porre y_s=0

Una (qualunque) riga di M è ridondante rango(M)=n-1

(12)

Esempi di soluzioni

Esempi di soluzioni primali primali e duali e duali

PROBLEMA PRIMALE:

(CM) min c^Tx

Mx=b x ≥ 0_|A|

PROBLEMA DUALE:

(DCM) max y_t

y_s=0

s t

1

2 1

1

3

1 3 2

3

2 1 0

s t

1

2 1

1

3

1 3 2

2

1 1 0

s t

1

2

3 1

1

1 0

0

s t

1

2

3 0

0

1 0

1

x

…

^y

…

La differenza tra le var agli estremi non supera il costo dell’arco

(13)

Ammissibilit

Ammissibilità à e Limitatezza e Limitatezza

PROBLEMA PRIMALE:

(CM) min c^Tx

Mx=b x ≥ 0_|A|

PROBLEMA DUALE:

(DCM) max y_t

y_s=0

IPOTESI: Esiste un cammino orientato da s a t

Il problema primale ammette sempre una soluzione Il problema primale può essere illimitato inferiormente ? ovvero: il problema duale può non ammettere soluzioni ?

non ammette soluzioni ! 2 -5

2 3

ESEMPIO

s 1 t

2

1 1 1

1

y₃ - y₂≤ 2 y₁ - y₃≤ -5 y₂ - y₁≤ 2 y_t – y₃≤ 1 y_t - y₁≤ 1

y₁≤ 1 y₂≤ 1

(14)

Condizione di Limitatezza Condizione di Limitatezza

TEOREMA F3: Il Problema Duale ammette soluzioni (il Problema Primale non è illimitato) se e solo se il grafo G(N,A) non ha cicli orientati di costo totale negativo.

DIMOSTRAZIONE: Se G(N,A) non contiene cicli con costo negativo Sia P^*_u il cammino di lunghezza minima da s ad un generico nodo

u∈N-{s} [esiste il cammino orientato da s ad ogni u]

Poni y’_u=c(P^*_u) per ogni u∈N-{s}

P’=(s,…,u,uv,v) è un cammino minore del minimo:

c(P’)=c(P^*_u)+c_uv< c(P^*_v) CONTRADDIZIONE (parte se)

c(P^*_v)–c(P^*_u) > c_uv

Se v non appartiene a P^*_u=(s,…,u)

Se invece v appartiene a P^*_u=(s,…,u)

Detto P’ =(v,…,u) il sotto-cammino di P^*_u da v ad u c(P^*_v) >c(P^*_u)+c_uv

CICLO NEGATIVO ! CONTRADDIZIONE perchè ipotesi niente cicli negativi Infatti, se per assurdo y’_v – y’_u> c_uvper un qualche uv∈A

Allora esiste soluzione duale per es. y’ dato che y’_v – y’_u≤ c_uvper ogni uv∈A

c(P^*_v)>c(P^*_v)+c(P’)+c_uv 0>c(P’)+c_uv=c(C) C= P’∪{uv} è un ciclo

v

u P^’

P^*_u P^*_v

s

P’ u v

C P^*_v

(15)

Condizione di Limitatezza

Condizione di Limitatezza ( ( … … ) )

Se y’ è una soluzione duale

Supponi (per assurdo) che C=(1,12,2,…,k,k1,1) sia un ciclo di G(N,A) avente costo totale c(C) negativo

(parte solo se) G(N,A) non contiene cicli negativi

Poiché y’ è una soluzione duale abbiamo:

y₂’ – y’₁≤ c₁₂ y₃’ – y’₂≤ c₂₃

y₁’ – y’_k≤ c_k1

k k-1

1

2

3

0 ≤ c(C)<0

+

CONTRADDIZIONE

(16)

Condizioni di Scarto Complementare Condizioni di Scarto Complementare

PROBLEMA PRIMALE:

(CM) min c^Tx

Mx=b x ≥ 0_|A|

x’ soluzione del primale y’ soluzione del duale

(x’,y’) sono OTTIME per i rispettivi problemi se e solo se:

Per tutte le coppie primale-duale ho CONDIZIONI DI SCARTO COMPLEMENTARE:

x’_uv(c_uv- y’_v+ y’_u)=0 per ogni uv∈ A PROBLEMA DUALE:

(DCM) max y_t

y_s=0

Cioè: x* VETTORE DI INCIDENZA DI UN CAMMINO P* è OTTIMO

se e solo se esiste una soluzione duale y* tale che:

y*_v= y*_u+c_uv per ogni uv∈A con x*_uv=1 (cioè uv∈P*)

(17)

Grafo Ridotto Grafo Ridotto

DEFINIZIONE: Data una soluzione duale y’ diremo GRAFO RIDOTTO rispetto ad y’ il grafo G(y’) (N,F’) con F’={uv∈A : y’_v = y’_u +c_uv }

s t

1

2 1

1

3

1 3 2

3

2 1 0

s t

1

2 1

1

3

1 3 2

2

1 1 0

G(y’) è il sottografo ricoprente di G(N,A) definito dagli archi associati ai vincoli duali y_v - y_u ≤ c_uv soddisfatti all’uguaglianza da y’

uv ∈ F’

y’_v - y’_u = c_uv

y’₁ - y’_s = 1-0=1=c_s1

y’₂ - y’₁= 2-1=1=c₁₂ y’₁ - y’_s = 1-0=1=c_s1 y’_t - y’₂= 2-1=1=c_2t

y’_t - y’₂= 3-2=1=c_2t y’₂ - y’_s = 2-0=2=c_s2

Esempi di GRAFO RIDOTTO

(18)

Condizione di

Condizione di Ottimalità Ottimalit à

[CONDIZIONI DI SCARTO COMPLEMENTARE]

Sia x^P il suo vettore di incidenza

Sia P un cammino orientato da s a t in G(N,A) TEOREMA F4: Un cammino orientato P da s a t in G(N,A) ha costo

minimo se e solo se esiste una soluzione duale y’ con la proprietà che

P è un cammino orientato da s a t nel grafo ridotto G(y’) DIMOSTRAZIONE:

x^P è OTTIMO se e solo se

Esiste y’: y’_v = y’_u+c_uv per ogni uv∈P (x^P_uv=1)

ESEMPI

s t

1

2 1

1

3

1 3 2

3

2 1 0

s t

1

2 1

1

3

1 3 2

2

1 1 0

P cammino orientato da s a t in G(y’)

y’ ottima y’ non-ottima

Esiste una soluzione duale y’: x^P_uv(c_uv-y’_v +y’_u)=0 per ogni uv

(19)

L’ L ’ arborescenza dei cammini minimi arborescenza dei cammini minimi

1

-1 3

2 1 2

4

1

3 2

5

1

3

1

-1 3

2 1 2

4

1

3 2

5

1

3

• Un’arborescenza può essere descritta mediante il vettore dei predecessori, prec OSS. Ogni nodo diverso dal nodo radice 1 ha un unico predecessore

nell’arborescenza.

Arborescenza (di radice 1): albero in cui, per ogni j∈V,

l’unico cammino dal nodo 1 al nodo j è un cammino orientato.

1

(20)

Algoritmo iterativo di

Algoritmo iterativo di Bellman Bellman Ford Ford

Per trovare l’arborescenza dei cammini minimi esistono vari algoritmi (Dijkstra, Algoritmo della numerazione topologica, Bellman-Ford, etc.) Vediamo l’algoritmo di Bellman-Ford, veloce e di vasta applicazione

• Inizialmente vengono ordinati gli archi e definita una particolare soluzione duale iniziale y⁰ che non è ammissibile ma è facile da scrivere

• A ogni iterazione gli archi vengono visitati nell’ordine prefissato: se per un arco (i,j) si ha y_j > y_i + c_ij violando l’ammissibilità duale, si rende ammissibile ponendo

y_j = y_i + c_ij

• Si dimostra che dopo al più un certo numero di iterazioni tutte le condizioni di ammissibilità duale saranno soddisfatte

Alla fine è possibile ricostruire l’arborescenza dei cammini massimi utilizzando il vettore dei predecessori prec

(21)

Schema algoritmo

Schema algoritmo Bellman Bellman Ford Ford

Calcolo dell’arborescenza dei cammini minimi dal nodo 1 a i per i = 1, …, n Inizializzazione:

y₁ = 0, y_i = ∞ e prec(i) = 0 per i = 2, …, n.

Ordina gli archi A = {e₁, …, e_m} Repeat (finchè y non si modifica più)

For k = 1 to m (per ogni arco)

If e_k = (i,j) è tale che y_j > y_i + c_ij poni y_j = y_i + c_ij

poni prec(j) = i Endfor

EndRepeat

• L’algoritmo termina fornendo y_i = cammini minimi da 1 a tutti gli altri nodi

• Il blocco {Repeat … EndRepeat} (iterazione grande) viene eseguito al più n volte

• Ogni iter. grande sono m iterazioni piccole, quindi la complessità è O(mn) (numero totale di iterazioni piccole)

Iterazioni

“piccole” Iterazioni “grandi”

(22)

Esempio di applicazione Esempio di applicazione

Inizializzazione: y(1) = 0, y(2) = y(3) = y(4) = ∞ Ordino gli archi: e₁ = (1,2), e₂ = (1,3), e₃ = (3,1), e₄ = (2,4), e₅ = (3,4), e₆ = (3,2)

Repeat 1

Iter 1. k = 1. y(2) = ∞ > y(1) + 2 ⇒ y(2) = y(1) + 2 = 2 prec(2) = 1 Iter 2. k = 2. y(3) = ∞ > y(1) + 4 ⇒ y(3) = y(1) + 4 = 4 prec(3) = 1 Iter 3. k = 3. y(1) = 0 <= y(3) -2

Iter 4. k = 4. y(4) = ∞ > y(2) + 4 ⇒ y(4) = y(2) + 4 = 6 prec(4) = 2 Iter 5. k = 5. y(4) = 6 <= y(3) + 3

Iter 6. k = 6. y(2) = 2 > y(3) - 3 ⇒ y(2) = y(3) - 3 = 1 prec(2) = 3 Repeat 2

Iter 1. k = 1. y(2)= 1 <= y(1) + 2 Iter 2. k = 2. y(3) = 4 <= y(1) + 4 Iter 3. k = 3. y(1) = 0 <= y(3) -2

Iter 4. k = 4. y(4) = 6 > y(2) + 4 ⇒ y(4) = y(2) + 4 = 5 prec(4) = 2 Iter 5. k = 5. y(4) = 5 <= y(3) + 3

Iter 6. k = 6. y(2) = 1 <= y(3) - 3

1

-2 3

4 2 2

4

3 -3

(23)

23

L L ’ ’ arborescenza dei cammini minimi arborescenza dei cammini minimi

prec(4) = 2 prec(2) = 3 prec(3) = 1

prec(1) non esiste

• L’arborescenza dei cammini minimi può essere

ricostruita a partire dal vettore dei predecessori, prec()

1

-2 3

4 2 2

4

3 -3

Nella successiva iterazione grande non vengono aggiornate le variabili, quindi stop.

La soluzione ottima è y(1) = 0, y(2) = 1, y(3) =4, y(4) = 5

(24)

Algoritmo

Algoritmo di di Floyd Floyd -Warshall - Warshall

DATI:

- Grafo orientato e connesso G(N,A) G(N,A) - Costi sugli archi w w

_uv_uv

∀ ∀ uv uv ∈ ∈ A A

Il problema del cammino minimo ammette sempre una soluzione Aggiungiamo

Aggiungiamo gli archi

uv uv ∉ ∉ A A

^ponendo

w w

_uv_uv

= = ∞ ∞

∞ ∞

Esiste un cammino orientato tra ogni coppia di nodi

{ ¹ ² ⁿ }

N = , K , ,

datodato l’l’insiemeinsieme deidei nodinodi

TROVARE:

TROVARE: il camminocammino orientatoorientato didi costocosto minimo

minimo tra ogniogni coppiacoppia didi nodinodi

Sia:Sia:

^P

_ij^d

⁼ ( ⁱ ^, ^k

₁

^, ^k

₂

^, ^K ^, ^k

_q

^, ^j ) ^, ^k

_h

^∈ ^N

_d

⁼ ^{ ¹ ^, ² ^, ^K ^, ^d ^}

il camminocammino minimominimo tra i e i jj con nodinodi interniinterni solosolo nell’insieme

N N

_d_d

{ ¹ ² ³ } ^P ( ⁶ ³ ² ⁷ ) ^, ^P ( ) ⁵ ³

N

₃

= , ,

₆₇³

= , , ,

₅₃³

= ,

Es:Es:

DEFINIZIONE:

2

2 7 3 5

4

3 1

6

1

2 1

3

10

1

7

(25)

Algoritmo

Algoritmo di di Floyd Floyd - - Warshall Warshall (II) (II)

2

2 3 5 7

4 3

1 6

1

2 1

3

10

1

7

Sia:Sia:

^P

_ij^d

⁼ ( ⁱ ^, ^k

₁

^, ^k

₂

^, ^K ^, ^k

_q

^, ^j ) ^, ^k

_h

^∈ ^N

_d

⁼ ^{ ¹ ^, ² ^, ^K ^, ^d ^}

il camminocammino minimominimo tra i e i jj con nodinodi interniinterni solosolo nell’insieme

N N

_d_d

costo del cammino minimo

k

d

ij

P

_ij^k

n ,.., 1 j , i k ij

k

[ d ]

D =

₌

















∞

=

0 0

1 2

0 3

0

10 2

0 1

1 0

3 7

0

D⁰ n

,.., 1 j , i ij

0

[ w ]

D =

₌

D

n

Matrice dei costi dei cammini minimi

costi dei camminicammini minimiminimi tra i e ji j con nodinodi interniinterni nell’insieme

N N

ALGORITMO:

n k

1 k 1

0

D D D D

D → L →

⁻

Cammino Minimo Massimo Flusso