Cammino MinimoMassimo Flusso

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

Questa sezione è derivata dal materiale del prof. A. SassanoCorso di: Ottimizzazione Combinatoria

Docente: Renato Brunibruni@dis.uniroma1.it

Cammino di costo minimo da s a tTROVARE: Il CAMMINO ORIENTATO P* da s a t avente COSTO MINIMOP*: 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*)=7P={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 wuv ∀ uv∈ A ft3 ba d1 2 c

s2 1wsd =310 17Il costo di un cammino P di G(N,A) siaw(A(P)) = w(P) = ∑ wuvuv∈A(P)

Vettore di Incidenza di un CamminoDef.: xP∈{0,1}A vettore di incidenza di P=1 uv∈ P=0 uv∉ PxPuvxPuv

Rappresentazione di un camminoProprietà di xP∑ xPus= 0us∈ δG(s)- ∑su∈ δG(s)+ xPsu = 1(i) Da s esce un solo arco di un cammino P∑ xPut = 1ut∈ δG(t)- ∑tu∈ δG(t)+ xPtu = 0(ii) In t entra un solo arco di P∑ xPuvuv∈ δG(v)- ∑vu∈ δG(v)+xPvu= (iii) In ogni altro nodo v∉ {s,t}Numero archi di P entranti = = Numero archi di P uscenti

fba d

cs tPxP

ft 1sacfdadftdacbcsb 1110000csct

000

Cammino min come problema di Flusso Intero

4

DATI: Un grafo orientato G(N,A)Un vettore capacità c = ∞|A|Un vettore domanda dst =

100001-

t4321s ∞s 2

3 45 t-1 0

0 100∞∞ ∞∞ ∞ ∞∞

possiamo scrivere il problema del Cammino Minimo (CM) come:Cioè come flusso intero di (G, dst, ∞|A|)Poliedro dei cammini da s a tQst ={x: Mx = dst , x ≥ 0|A|}min {wTx : x∈Qst }

Rappresentazione grafica di una soluzione x∈QstDEFINIZIONE: Dato un vettore x diremo SUPPORTO di xl’insieme di archi S(x)={e∈A: xe >0}Rappresenteremo un vettore x evidenziando gli archi del supporto (ad es. in rosso) e (a volte) indicando il valore della componente di xe accanto all’arco e

10s 23 4

5 t1 110 1 0≡01011110 t5t4345325322s3s

Vettori del Poliedro dei Cammini (Esempi)Qst = { x∈ℜ|A|: Mx=b, x ≥0|A|} 2s t1s1s2121t2ts1s2121t2t

xP

xP’

1001010101 Non è un cammino !

s1s2121t2t1/21/21/41/43/4x̂

s t121/21/2 1/41/4 3/4x∈ Qst^

- xs1 - xs2 = -1xs2 + x12 - x2t= 0xs1 - x12 - x1t = 0x1t + x2t= 1s t12

xP∈ QstP cammino s-t1 000 1

s t12xP’∈ QstP’ cammino s-t1 110 0

Vettore di incidenza di un cammino ⇒ flusso intero

7

(0, ∞)s 23 4

5 t- 1 00 10

0(1, ∞) (0,∞)(1,∞)(0,∞) (0,∞) (0, ∞)(1, ∞)(i) da s esce un solo arco di P(iii) In ogni nodo v∉ {s,t}

- un arco di P entrante e un arco di P uscente OPPURE- nessun arco di P entrante o uscentexP vettore di incidenza di un cammino orientato P(ii) in t entra un solo arco di P

xP flusso intero di (G, dst,∞|A|)Viceversa? (0, ∞)(0, ∞)s 23 4

5 t-1 00 10

0(1, ∞) (0,∞)(2,∞)(1,∞) (1,∞) (1,∞)No! ⇒

I vertici di Qst sono (flussi) interi (M totalmente unimodulare)

Flussi interi e vertici di Qstma ( non tutti i flussi interi x∈Qst sono vertici: combinando i due seguenti flussi interi ho un nuovo flusso intero che quindi non è un vertice(0, ∞)s 2

3 45 t- 1 0

0 100(1,∞) (0,∞)

(2,∞)(1,∞) (1,∞) (1,∞)= + 1/2E allora ( quali sono i vertici di Qst ? (SBA)

(0, ∞)s 23 4

5 t- 1 00 10

0(1, ∞) (0,∞)(3,∞)(2,∞) (2,∞) (1,∞)(0, ∞)s 2

3 45 t- 1 0

0 100(1, ∞) (0,∞)

(1,∞)(0,∞) (0,∞) (1,∞)1/2

Come è una Matrice di Base per M ?Poliedro dei cammini da s a t

Base B sottomatrice (n-1 × n-1) non-singolare di M′

rango(M) ≤ n-1|N|=n; |A|=muna riga di M è ridondante (righe=nodi) ⇒stb1000

1uv11000 01100 10110 00001 00011Mx =

−=

−−−−−=M

M

M

M ⇒ M ′Inoltre G è connesso (contiene un albero ricoprente), quindi haalmeno n-1 archi senza cicli (=colonne ind.) ⇒=′ 1000bstPossiamo eliminare la prima riga ottenendo la matricerango(M) ≥ n-1⇒ rango(M)=n-1

Qst ={x: Mx = dst , x ≥ 0|A|}

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

B sottomatrice (n-1 × n-1) non-singolare di MPerchè un ciclo nel grafo corrisponde a colonne linearmente dipendentiGli archi TB corrispondenti alle colonne di B definiscono un Albero RicoprenteVertice (SBA) mnm stbBx 00 11 ≥ ′=′ +−−

M =1 23

...2222 22000 22-110 ...20-11 ......10-1

...2000Quindi n-1 colonne indipendenti danno una foresta con n-1 archi, che quindi copre tutti gli n nodi del grafo e quindi è un albero ricoprente

Soluzioni Ammissibili di Base (SBA)

SBA e Forestex’ è una soluzione di base NON-DEGENERE (nessun componente corrispondente alle colonne di base è nullo) ⇒ S(x’) =TB ⇒ S(x’) Alberox’ è una soluzione di base DEGENERE (qualche componente corrispondente a colonne di base è nullo) ⇒ S(x’) ⊂ TB ⇒ S(x’) Foresta

Dato che gli archi TB corrispondenti alle colonne di B definiscono un ALBERO RICOPRENTEViceversa: se x’∈ Qst ha S(x’) che è una FORESTA∃ albero ricoprente T ⊇ S(x’)G(N,A) connessoLa sottomatrice B di M le cui colonne corrispondonoagli archi di T (e le cui righe sono n-1 righe di M)è non-singolare ⇒ T=TB

se x’ è una SBA

TB ALBERO RICOPRENTE corrispondente alla matrice Bx’ ha componenti non-nulle solo in corrispondenza delle colonne di B cioè B x’B= M x’ = bst ⇒ x’B= B-1 bst ⇒ x’ è Soluzione di Base

Soluzioni di Base e CamminiTEOREMA F2: x′∈ Qst è una SOLUZIONE AMMISSIBILE DI BASE se e solo seè VETTORE DI INCIDENZA DI UN CAMMINO ORIENTATO P da s a t.Sia z una foglia di H diversa da s e t e sia f∈S(x′ ) l’unico arco incidente su zL’equazione del sistema Mx′ =b corrispondente a z sarà:

Contraddicendo l’ipotesi che f∈S(x′ )⇒ Nessun nodo z ≠ s,t è una foglia di H stzfx’(δG(z)) = 0 = -xf’ se f∈δG(z)+x’(δG(z))- - +x’(δG(z)) = 0 = xf’ se f∈δG(z)+

x’(δG(z))- - -

DIMOSTRAZIONE: x′ è una SOLUZIONE AMMISSIBILE DI BASEGli archi in S(x′ ) definiscono una FORESTA H(N,S(x′ )) di G(N,A)[Teorema F1]

Teorema F2 (...)Ma H è una foresta e ogni sua componenteconnessa che contiene un arco ha almeno due foglieOvvero: H è un CAMMINO P CON ESTREMI s e t

(più eventuali nodi isolati)P=(s=v0,e0,v1,e1,v2,...,vp,ep,t=vp+1)

Quindi: Nessun nodo z≠s,t è una foglia di H s tzf H⇒ H ha solo due foglie s e ts=v0e0 v1 tepvp HMa x′∈Qst e quindi deve essere un flusso ammissibileIn ogni nodo z ≠ s,t ho un arco entrante e uno uscentex′ è il vettore di incidenza di un cammino orientato da s a te0 v1 t =vp+1epvpv2 v3e1s =v0

⇒ H ha una sola compon. connessa contenente archi

Cammini Minimi e Programmazione LineareTROVARE: 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 xP di un CAMMINO ORIENTATO Pda s a t avente COSTO MINIMO wTxPw(P)= ∑ wuv = ∑ wuv xPuv = wTxPuv∈A(P) uv∈ATROVARE: Una SOLUZIONE DI BASE (VERTICE) x del PoliedroQst ={x∈ ℜ|A|: Mx=b, x ≥ 0|A|} avente COSTO MINIMO wTx[Teorema F1]RISOLVERE IL PROBLEMA DI PROGRAMMAZIONE LINEARE: (CM) min wTx min wTx

Mx=b x∈Qst = {x∈ℜ|A|: Mx=b, x ≥ 0|A|}x ≥ 0|A| ≡ [Teoria della Programmazione Lineare]

Problema Primale e Problema DualeM b

Cioè, vista la struttura di b e di M:(DCM) max yt -ysyv - yu ≤ cuv per ogni uv∈A

PROBLEMA PRIMALE:(CM) min cTx

Mx=bx ≥0|A| uv -11000 00

tuv 1-1 sPROBLEMA DUALE:(DCM) max bTy

MTy ≤ c

1 0 0bTt u v-1 1uv

MT0 00-1s

Possiamo eliminare la riga corrispondente ad s e porre ys=0Una (qualunque) riga di M è ridondanterango(M)=n-1

Esempi di soluzioni primali e dualiPROBLEMA PRIMALE:(CM) min cTx

Mx=bx ≥ 0|A|

PROBLEMA DUALE:(DCM) max ytyv - yu ≤ cuv per ogni uv∈Ays=0

s t121 1 31 32 3210

s t121 1 31 32 2110

s t12 31 1 100s t12 30 0 101

x y

Ammissibilità e LimitatezzaPROBLEMA PRIMALE:(CM) min cTx

Mx=bx ≥ 0|A|

PROBLEMA DUALE:(DCM) max ytyv - yu ≤ cuv per ogni uv∈Ays=0IPOTESI: Esiste un cammino orientato da s a tIl problema primale ammette sempre una soluzioneIl problema primale può essere illimitato inferiormente ?ovvero: il problema duale può non ammettere soluzioni ?

non ammette soluzioni !-52 32ESEMPIO1s t

2 1111 y3 - y2 ≤ 2y1 - y3 ≤ -5y2 - y1 ≤ 2yt – y3 ≤ 1yt - y1 ≤ 1y1 ≤ 1y2 ≤ 1

Condizione di LimitatezzaTEOREMA 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)+cuv< c(P*v) CONTRADDIZIONE

(parte se)c(P*v)–c(P*u) > cuvSe 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 uc(P*v) >c(P*u)+cuv

CICLO NEGATIVO ! CONTRADDIZIONE perchè ipotesi niente cicli negativi

Infatti, se per assurdo y’v – y’u > cuv per un qualche uv∈AAllora esiste soluzione duale per es. y’ dato che y’v – y’u ≤ cuv per ogni uv∈A

c(P*v)>c(P*v)+c(P’)+cuv 0>c(P’)+cuv=c(C)C= P’∪{uv} è un ciclov uP’P*uP*vs

s P’ uv CP*v

Condizione di Limitatezza (…)Se y’ è una soluzione dualeSupponi (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 negativiPoiché y’ è una soluzione duale abbiamo:y2’ – y’1 ≤ c12y3’ – y’2 ≤ c23y1’ – y’k ≤ ck1

k-1k1 2 30 ≤ c(C)<0+

CONTRADDIZIONE

Condizioni di Scarto ComplementarePROBLEMA PRIMALE:(CM) min cTx

Mx=bx ≥ 0|A|x’ soluzione del primale y’ soluzione del duale(x’,y’) sono OTTIME per i rispettivi problemi se e solo se:CONDIZIONI DI SCARTO COMPLEMENTAREx’uv(cuv - y’v + y’u)=0 per ogni uv∈ A

PROBLEMA DUALE:(DCM) max ytyv - yu ≤ cuv per ogni uv∈Ays=0

Cioè: x* VETTORE DI INCIDENZA DI UN CAMMINO P* è OTTIMOse e solo se esiste una soluzione duale y* tale che: y*v = y*u+cuv per ogni uv∈A con x*uv=1 (uv∈ P*)

Grafo RidottoDEFINIZIONE: 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 +cuv }

s t121 1 31 32 3210 s t121 1 31 32 21

10G(y’) è il sottografo ricoprente di G(N,A) definito dagli archi associatiai vincoli duali yv - yu ≤ cuv soddisfatti all’uguaglianza da y’ uv ∈ F’ y’v - y’u = cuv

y’1 - y’s = 1-0=1=cs1y’2 - y’1 = 2-1=1=c12 y’1 - y’s = 1-0=1=cs1y’t - y’2 = 2-1=1=c2ty’t - y’2 = 3-2=1=c2ty’2 - y’s = 2-0=2=cs2

Condizione di Ottimalità[CONDIZIONI DI SCARTO COMPLEMENTARE]Sia xP il suo vettore di incidenzaSia 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:xP è OTTIMO se e solo seEsiste y’: y’v = y’u+cuv per ogni uv∈P (xPuv=1)ESEMPI s t121 1 31 32 3210 s t121 1 31 32 21

10P cammino orientato da s a t in G(y’)y’ ottima y’ non-ottima

Esiste una soluzione duale y’: xPuv(cuv-y’v +y’u)=0 per ogni uv

L’arborescenza dei cammini minimi1 3-12

21 4132 511 3 1 3-1221 4132 511 3

• Un’arborescenza può essere descritta mediante il vettore dei predecessori, precOSS. 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

Algoritmo iterativo di Bellman FordPer 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 y0 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 yj > yi + cij violando l’ammissibilità duale, si rende ammissibile ponendo yj = yi + cij• 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

Schema algoritmo Bellman FordCalcolo dell’arborescenza dei cammini minimi dal nodo 1 a i per i = 1, …, nInizializzazione: y1 = 0, yi = ∞ e prec(i) = 0 per i = 2, …, n. Ordina gli archi A = {e1, …, em}Repeat (finchè y non si modifica più)For k = 1 to m (per ogni arco)If ek = (i,j) è tale che yj > yi + cijponi yj = yi + cijponi prec(j) = iEndforEndRepeat• L’algoritmo termina fornendo yi = 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”

Esempio di applicazioneInizializzazione: y(1) = 0, y(2) = y(3) = y(4) = ∞Ordino gli archi: e1 = (1,2), e2 = (1,3), e3 = (3,1), e4 = (2,4), e5 = (3,4), e6 = (3,2) Repeat 1Iter 1. k = 1. y(2) = ∞ > y(1) + 2 ⇒ y(2) = y(1) + 2 = 2 prec(2) = 1Iter 2. k = 2. y(3) = ∞ > y(1) + 4 ⇒ y(3) = y(1) + 4 = 4 prec(3) = 1Iter 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) = 2Iter 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) = 3Repeat 2Iter 1. k = 1. y(2)= 1 <= y(1) + 2Iter 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) = 2Iter 5. k = 5. y(4) = 5 <= y(3) + 3 Iter 6. k = 6. y(2) = 1 <= y(3) - 3

1 3-2422 443-3

27

L’arborescenza dei cammini minimiprec(4) = 2prec(2) = 3prec(3) = 1prec(1) non esiste

• L’arborescenza dei cammini minimi può essere ricostruita a partire dal vettore dei predecessori, prec()1 3-24

22 443-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

Algoritmo di Floyd-WarshallDATI: - Grafo orientato e connesso G(N,A)- Costi sugli archi wuv ∀ uv∈ AIl problema del cammino minimo ammette sempre una soluzioneAggiungiamo gli archi uv∉ A ponendo wuv=∞

∞Esiste un cammino orientato tra ogni coppia di nodi{ } n21N ,,, K=dato l’insieme dei nodi

TROVARE: il cammino orientato di costominimo tra ogni coppia di nodi

Sia: ( ) { }d21NkjkkkiP dhq21dij ,,,,,,,,, KK =∈= il cammino minimo tra i e j con nodi interni solo nell’insieme Nd{ } ( ) ( ) , 35P7236P321N 3533673 ,,,,,, ===Es:DEFINIZIONE:

2273 54 31 6

12 13

10 17

Algoritmo di Floyd-Warshall (II)2

273 54 31 6 12 13

10 17Sia: ( ) { }d21NkjkkkiP dhq21dij ,,,,,,,,, KK =∈= il cammino minimo tra i e j con nodi interni solo nell’insieme Ndcosto del cammino minimokijd kijPn,..,1j,ikijk ]d[D ==

∞∞∞∞∞∞ ∞∞∞∞ ∞∞∞∞∞ ∞∞∞∞∞∞ ∞∞∞ ∞∞∞∞∞ ∞∞∞∞= 0012 030 10201 10 370D0n,..,1j,iij0 ]w[D ==nD Matrice dei costi dei cammini minimicosti dei cammini minimi tra i e jcon nodi interni nell’insieme N

ALGORITMO: nk1k10 DDDDD →→→→ −LL

Algoritmo di Floyd-Warshall (III)n,..,1j,i1kij1k ]d[D =−− = costi dei cammini minimi che utilizzano i nodi { } 1,k-,2,1 N 1k K=−

Semplice formula per passare dalla matrice …alla matrice … n,..,1j,ikijk ]d[D ==i

k

j1kijP − 1kkjP −1kikP − due possibili casi: - non utilizza il nodo k- utilizza il nodo kkijPkijP

costi dei cammini minimi che utilizzano i nodi { } ,k,2,1 Nk K= kijP{ } dd,d mind )1k(kj)1k(ik)1k(ijkij −−− +=kijP

kijP

For i:=1 to nFor j:=1 to ndo beginD[i,j]:=w(i,j);pred[i,j]:=i;end;For k:=1 to nFor i:=1 to nFor j:=1 to ndo beginif D[i,j]>D[i,k]+D[k,j]then beginD[i,j]:= D[i,k]+D[k,j];pred[i,j]:= pred[k,j];end;end;

Inizializzazionepred[i,j] è il predecessore di j nel cammino tra i e jSe D[i,i]<0 c’è un ciclo negativo che passa per il nodo ii

k

j1kijP − 1kkjP −1kikP − pred[k,j]

Schema Algoritmo di Floyd-Warshall

Esempio Algoritmo di Floyd-Warshall ∞∞ ∞ ∞− −∞∞= 01 201 102 10D011 43

212 2-1 -1 = 4444 3333 2222 1111pred= 4444 1333 1222 1111pred ∞∞ ∞ − −∞∞= 01 001 1102 10D1

∞ − −∞∞= 0013 001 1102 10D2 = 4242 1333 1222 1111pred ∞ −− −∞∞= 0011 001 1100 103D = 4243 1333 1223 1111pred

−− −−= 0011 0011 1100 11004D= 4243 1343 1223 1241pred

11 43212 2-1 -1 −− −−= 0011 0011 1100 11004D = 4243 1343 3223 1241predCome si ricostruisce il cammino minimo tra i e j ?13PEs. Si parte dal nodo 3 e si cerca il predecessore … 2)3,1(pred = 1 43

2Poi si cerca il predecessore di 2 nel cammino da 1 a 2 … Infine il predecessore di 4 nel cammino da 1 a 4 …

4)2,1(pred = 1 432

1)4,1(pred = 1 432Raggiunto 1 STOP

Esempio Algoritmo di Floyd-Warshall

Algoritmo di Floyd-Warshall: Ciclo negativo11 43212 2-5 -1

−−− −−− −−−−= 4011 0431 5140 5544D4Se ho un ciclo di peso complessivo negativo (me ne accorgo dai valori sulla diagonale che diventano negativi)non esiste una soluzione ottima

35

Flusso s-t in un Grafo OrientatoUn nodo sorgente s∈NDIREMO: FLUSSO s-t di (G,c)Un nodo pozzo t∈N-{s}DATI: Un grafo orientato G(N,A)

un vettore x∈ ℜ|A| tale che:Un vettore capacità c ≥ 0|A|

= 0∑ xusus∈ δG(s)-∑ xtutu∈ δG(t)+ =[ nulla esce da t e nulla entra in s ]∑vu∈ δG(v)+xvu- v∉ {s,t}[ conservazione del flusso ]∑ xuvuv∈ δG(v)- = 0

3(1,2)(1,1)(0,3)(0,1) 40 ≤ xuv ≤ cuv[ vincolo di capacità ]vu (1,2)(xuv,cuv) (2,3) (1,1)(1,1)

(2,3) (3,3) (2,2)(2,2)(1,1)s 12 3

4 t

3 13 3 221s 12 3

4 t1

36x(A) - x(A) = 0 = ft(x) - fs(x)Sommando tutte le equazioni otteniamo Poichè ogni arco appartiene ad una (e una sola) stella entrantee ad una (e una sola) stella uscente,abbiamo che: ∪ δG(v) = ∪ δG(v) = A v∈N v∈N +-

x(∪ δG(v)) - x(∪ δG(v)) = ft(x) - fs(x)-v∈N v∈N +

flusso entrante in t = flusso uscente da s = = valore f(x) del flusso x ft (x) = fs(x) = f(x)

x(δG(v)) = 0+x(δG(v))- - per ogni nodo v∉ {s,t}x(δG(t)) = x(δG(t)) = ft(x)+x(δG(t)) -- - flusso entrante in tx(δG(s)) = - x(δG(s)) = - fs(x)+x(δG(s)) -- + flusso uscente da sFlusso s-t in un Grafo Orientato

37

t43

21s (1,2)

(1,3) (0,1) (0,1)(1,3)(1,2)(1,2)(1,2) (1,2)

(1,2)

t43

21s (2,2)

(2,3) (0,1) (0,1)(1,3)(1,2)(2,2)(2,2) (2,2)

(2,2)

flusso x1

flusso x2fs(x1)= ft(x1)=f(x1)=2fs(x2)= ft(x2)=f(x2)=4

Esempi di flusso

x(δG(v)) = 0+x(δG(v))- - per ogni nodo v∉{s,t}x(δG(t)) = x(δG(t)) = f(x)+x(δG(t)) -- -x(δG(s)) = - x(δG(s)) = - f(x)+x(δG(s)) -- +Si vuole massimizzare il flusso f(x) uscente da s (entrante in t)

(MF) max fMx-bf=0

0 ≤ xuv ≤ cuv ∀uv∈ Ab: bs=-1; bt=1; bv=0 ∀v∈N-{s,t}x(δG(v)) = 0+x(δG(v))- - per ogni nodo v∉{s,t}x(δG(t)) = f-+- x(δG(s)) = - f

(MF) max f0 ≤ xuv ≤ cuv per ogni arco uv∈ A

M: Matrice di Incidenza di Gproblema di Flusso a Minimo Costo (MCF)I vincoli diventano Mx=bf e ottengo un

Problema del Massimo Flusso (MF)

f max(MF) cx0 0bfMx|A| |N|≤≤ =− 3 13 3 221s 12 3

4 t1

= 1000

01-b t4321s

3 13 3 221s 12 3

4 t1Matrice di incidenza del grafoottenuto aggiungendo l’arco ts

[ ]bM −tsx max(MF) cx0 0bxMx|A| |N|ts≤≤ =− ∞

PROGRAMMAZIONE LINEARE

Problema del Massimo Flusso (MF)

Duale del Massimo Flussoyc min T

(MF) 0x ;0x cxI 0bxMxts|A||A| |N|ts ≥≥ ≤ =− 3 13 3 221s 1

2 34 t1

∞(DMF)tsx max(z∈R|N| )(y∈R|A|)

||||||0 1 0

Ast AATy zz yIzM≥ ≥− ≥+DUALE del Massimo Flusso ≡ |A|st uvvu 0y 1zz Auv 0yzz ≥ ≥− ∈∀≥+− yc min T(DMF)(x∈R|A| )( xts )

Soluzioni del Duale del Massimo Flusso3 13 3 221s 12 3

4 t1∞|A|st uvvu 0y 1zz Auv 0yzz ≥ ≥− ∈∀≥+− yc min T(DMF)TEOREMA F5: Il duale del massimo flusso

Ammette una soluzione ottima { } |A||N|1,0yz +∈DIM: Una riga della matrice [M –b] è ridondante possiamo fissare una var nel duale: zs = 0⇒ esiste una soluzione ottima intera (z°,y°) di (DMF)ora facciamo una partizione dei nodi { } 0z:Nu X ou ≤∈= { } 1z:Nu X ou ≥∈=La matrice dei vincoli è TUM il vettore dei termini noti è interoe osserviamo che s e t sono in insiemi diversi: Xt1zzz otosot ∈⇒≥=−

Soluzioni del Duale del Massimo Flusso(II)(z°,y°) soluzione ottima intera di (DMF){ } 0: ≤∈= ouzNuX { } 1: ≥∈= ouzNuX )0( =osz1≥−≥⇒ ouovouv zzy LBcycycyc Xv,Xu:Auv uvXv,Xu:Auv ouvuvAuv ouvuvT =≥≥=° ∑∑∑ ∈∈∈∈∈∈∈MA IL VETTORE: 0 ,1 v1 Xu0

**** = ∈∈= ∈= ∈= altrimentiy XvXuy Xzzuvuvvu ||* ** *** 0 1 Auv 0

Ast uvvuy zz yzz ≥ ≥− ∈∀≥+−è ammissibileper il duale: ]X t 0[ ∈= ez osgap=0 ⇒ (z*,y*) è OTTIMA per DMF e il suo valore è lo stesso dell’ottimo di MF (max flusso)LBc XvXuAuv uv =∑ ∈∈∈ ,: *il suo minimo cTy* =vale proprio LB

Se prendo due nodiu∈X e v∈X, devo avere quindi questo è un lower bound per il problema di min DMF e lo chiamiamo LB[c ≥ 0|A| , y ≥ 0|A|]

Capacità dei tagli s-tCosa rappresenta la soluzione duale ? : altrimenti0y Xv,Xu1y Xu1z Xu0zouvouvouou = ∈∈= ∈= ∈=

∑ ∈∈∈= Xv,Xu:Auv uvoT cyc3 13 3 221s 1

2 34 t1 X X

altrimenti0y 1yy 1zzz 0zzzouv o23o14 oto4o3 o2o1os = == === ===

.. e cosa rappresenta la funzione obiettivo duale ? :

ESEMPIO:TAGLIO s-t di (G,c)- Taglio che “separa” s da t - z vettore di incidenza di X- y vettore di incidenza di δ+(X)

La somma delle capacità degli archi di δ+(X)CAPACITA’ del TAGLIO s-t δ+(X) di (G,c)

Massimo Flusso e Minimo TaglioAbbiamo dimostrato due cose:

∑ ∈∈∈= *Xv*,Xu:Auv uv*T cyc altrimenti0 ,11 X0 = ∈∈= ∈= ∈=

uvuvuuy XvXuy Xuz uzFLUSSO MASSIMO f* ≤ Capacità di ogni taglio s-t

1. Per ogni TAGLIO s-t δ+(X) la soluzione:è ammissibile per il duale ed ha valorepari alla somma delle capacità degli archi del taglio∑ ∈∈∈= XvXuAuv uvT cyc ,:2. La soluzione ottima del problema duale ha valore pari allacapacità di un particolare taglio s-t: δ+(X*)dualità debole

FLUSSO MASSIMO f* = capacità minima di un taglio s-tdualità forte detto Max-Flow-Min-Cut Theorem

45

Esempi1 t4

32s (1,2)

(2,3) (1,1) (0,1)(1,3)(1,2)(1,2)(1,2) (1,2)

(1,2)(1,1)f(x)=2c({s})=4 c({s,1,2,4})=6c({s,1,2})=51 t4

32s (2,2)

(3,3) (1,1) (0,1)(1,3)(1,2)(2,2)(2,2) (2,2)

(2,2)(1,1)f(x’)=4c({s})=4Flusso x’

Flusso x

f(x’) è massimo !