Problèmes de flots - Laboratoire Génie Industriel - … général de l’algorithme de Ford-Fulkerson Construction d’un flot complet Amélioration d’un flot réalisable

Reseaux de transports et flotsDifferents types de problemes de flot

Recherche d’un flot de valeur maximaleFlot de cout minimum

Problemes de flots

Vincent Mousseau

Ecole Centrale Paris,[email protected]

January 29, 2009

Vincent Mousseau Problemes de flots



Reseaux de transportsFlot, fluxCoupe

1 Reseaux de transports et flotsReseaux de transportsFlot, fluxCoupe

2 Differents types de problemes de flotDetermination d’un flot realisable sur un reseau de transportDetermination d’un flot maximumDetermination d’un flot de cout minimum

3 Recherche d’un flot de valeur maximalePrincipe general de l’algorithme de Ford-FulkersonConstruction d’un flot completAmelioration d’un flot realisableJustification de l’algorithme, convergence et complexiteGraphe d’ecart

4 Flot de cout minimum













Reseau de transport et flots

Definition : un reseau de transport de E a S est un grapheG = (X ,U) sans boucle, comporte une racine unique E

(appelee entree ou source) et une antiracine unique S

(appelee sortie ou puit),

a chaque arc u = (xi , xj ) ∈ U est associe :

une capacite notee k(u) (ou k(xi , xj) ou kij) representant laquantite max. de matiere pouvant circuler sur u, k(u) ≥ 0,une borne notee b(u) (ou b(xi , xj) ou bij) representant laquantite minimum de matiere pouvant circuler sur l’arc u,k(u) ≥ b(u) ≥ 0,un cout unitaire note c(u) (ou c(xi , xj) ou cij) representant lecout d’acheminement d’une unite de matiere sur l’arc u,





Reseau de transport

Remarque 1 :

si G comporte plusieurs racines e1, e2, ..., en, on se ramene aun reseau en ajoutant a X un sommet E et a U (E , ei ),∀i = 1, . . . , n, avec k(E , ei ) = +∞, b(E , ei ) = 0,c(E , ei ) = 0.

3

2

1

d

c

b

a





Reseau de transport

Remarque 1 :

si G comporte plusieurs racines e1, e2, ..., en, on se ramene aun reseau en ajoutant a X un sommet E et a U (E , ei ),∀i = 1, . . . , n, avec k(E , ei ) = +∞, b(E , ei ) = 0,c(E , ei ) = 0.

3

2

1

d

c

b

a

E

[0,∞

]

[0,∞]

[0,∞]





Reseau de transport

Remarque 2 :

si G n’a pas de racine,

3

2

1

d

c

b

a





Reseau de transport

Remarque 2 :

si G n’a pas de racine, on ajoute un sommet E predecesseurde tous les sommets x t.q. Γ−1(x) = ∅, k(E , x) = +∞,b(E , x) = 0, c(E , x) = 0.

3

2

1

d

c

b

a

E

[0,∞

]

[0,∞]

[0,∞]





Reseau de transport

Remarque 3 :

si G comporte plusieurs antiracines s1, s2, ..., sn,

3

2

1

d

c

b

a

E

[0,∞

]

[0,∞]

[0,∞]





Reseau de transport

Remarque 3 :

si G comporte plusieurs antiracines s1, s2, ..., sn, on se ramenea un reseau en ajoutant a X un sommet S et a U (si ,S),∀i = 1, . . . , n, avec k(si ,S) = +∞, b(si ,S) = 0, c(si ,S) = 0.

3

2

1

d

c

b

a

E S

[0,∞

]

[0,∞]

[0,∞]

[0,∞]

[0,∞]

[0,∞]

[0,∞

]





Reseau de transport

Remarque 4 :

si G n’a pas d’antiracine,

3

2

1

d

c

b

a

E

[0,∞

]

[0,∞]

[0,∞]





Reseau de transport

Remarque 4 :

si G n’a pas d’antiracine, on ajoute un sommet S successeurde tous les sommets x t.q. Γ(x) = ∅, k(x ,S) = +∞,b(x ,S) = 0, c(x ,S) = 0.

3

2

1

d

c

b

a

E S

[0,∞

]

[0,∞]

[0,∞]

[0,∞]

[0,∞]

[0,∞]

[0,∞

]





Exemple

Transport d’un produit d’entrepots a des clients

3 depots (1, 2 et 3), quantite en stock : 45, 25 et 25 resp.,

4 clients (a, b, c et d), demande : 30, 10, 20 et 30 resp.,

Les limitations en matiere de transport de produit d’unentrepot a un client sont definies par :

a b c d

1 10 15 - 202 20 5 5 -3 - - 10 10

Questions :Peut-on satisfaire toutes les demandes ? Si oui, comment?Sinon comment les satisfaire au mieux?





Modelisation

Remarques :

X = {1, 2, 3} ∪ {a, b, c , d} ∪ {E} ∪ {S},

U represente :

les possibilites de transport d’un d’entrepot a un client,les arcs ajoutes pour constituer la racine E et l’antiracine S .

le flux represente :

le destockage de produits a un depot,le transport de produits d’un depot a un client,l’arrivee de produit chez un client.





3

2

1

d

c

b

a

E S

[0,45]

[0,25]

[0,25]

[0,10]

[0,15]

[0,20]

[0,20

]

[0,5]

[0,5]

[0,10]

[0,10]

[0,30]

[0,10]

[0,20]

[0,30

]

︸︷︷︸︸︷︷︸︸︷︷︸

arc

existence d’unedisponibilite audepot i

existence d’uneliaison depot i

client j

existence d’unedemande chez leclient j

flux

quantitede matiereprovenant dudepot i

quantiteachemineepar la liaisondepot i client j

quantiteachemineeau client i

On note sur chaque arc u l’intervalle [b(u), k(u)] ainsi que φ(u).Vincent Mousseau Problemes de flots




Flot, flux

La quantite qui transite sur chaque arc u ∈ U s’appelle le flux

associe a (ou passant par) l’arc u. On note φ(u),

Definition : un flot Φ defini sur un reseau de transport est unvecteur Φ = (φ1, φ2, . . . , φm) avec φi = φ(ui ), i = 1, 2, . . . ,mverifiant la loi de conservation (loi de Kirshhoff), i.e.,

∑

u∈ω−(x) φ(u) =∑

u∈ω+(x) φ(u),

∀x ∈ X \ {E ,S}

.

.

.

x.

.

︸︷︷︸︸︷︷︸

ω−(x) ω+(x)





Flot, flux

Dans certains cas on ajoutera un arc “retour” (S ,E ) de sorteque la loi de conservation soit verifiee ∀x ∈ X ,

Un flot realisable (ou compatible) est un flot verifiantb(u) ≤ φ(u) ≤ k(u),∀u ∈ U.

3

2

1

d

c

b

a

E S

20, [0,

45]

25, [0,25]

20, [0,25]

0,[0,10]

0,[0,15]20,

[0,20]

15, [0,

20]

5, [0,5]

5, [0,5]

10, [0,10]

10, [0,10]

15, [0,30]5, [0,10]

15, [0,20]

30, [

0,30]

Figure: exemple de flot realisable





Flot, flux

v(Φ), la valeur d’un flot Φ represente la quantite totale dematiere circulant sur le reseau. Elle est definie par :v(Φ) =

∑

u∈ω+(E) φ(u) =∑

u∈ω−(S) φ(u)

E

1

2

S E S

1 2

3

5

2

31

1

4

1

0

1

0

5

Le cout d’un flot represente le cout associe au transport del’ensemble de la matiere sur le reseau, i.e.,c(Φ) =

∑

u∈U c(u).φ(u),

si le cout sur chaque arc des l’exemples est egal a 1,c(Φ1) = (2 × 1) + (3 × 1) + (1 × 1) + (1 × 1) + (4 × 1) = 11

c(Φ2) = (1 × 1) + (1 × 1) + (5 × 1) + (5 × 1) = 12





Coupe

Definition : Soit A ⊂ X , t.q. E ∈ A, S /∈ A. On appellecoupe engendree par A (notee ω(A)) l’ensemble des arcsdont une des extremites appartient a A et l’autre a X \ A,

On distingue :ω+(A) = {u ∈ ω(A) t.q. l’extremite init. de u appartient a A},ω−(A) = {u ∈ ω(A) t.q. l’extremite term. de u ∈ A}

Exemple : A = {E , 1, 3} ⊂ X .3

2

1

4

E S

La coupe engendree par A est :ω(A) = ω+(A) ∪ ω−(A)

= {(e, 2), (1, 2), (3, s)} ∪ {(4, 1), (4, 3)}





Coupe

Definition : On appelle valeur d’une coupe ω(A) (noteev(ω(A))) la quantite de matiere pouvant circuler sur les arcsde la coupe, i.e.,

v(ω(A)) =∑

u∈ω+(a) k(u)−∑

u∈ω−(a) b(u)





Coupe

Exemple : A = {E , 1, 2, a}, B = {E , 1, b}.

3

2

1

d

c

b

a

E S

[0,45]

[0,25]

[0,25]

[0,10]

[0,15]

[0,20]

[0,20

]

[0,5]

[0,5]

[0,10]

[0,10]

[0,30]

[0,10]

[0,20]

[0,30

]

ω(A) = ω+(A) ∪ ω−(A)= {(E , 3), (1, b), (1, d), (2, b), (2, c), (a, S)} ∪ ∅

v(ω(A)) = 115ω(B) = ω+(B) ∪ ω−(B)

= {(E , 2), (E , 3), (1, a), (1, d), (b, S)} ∪ ∅v(ω(B)) = 90





Coupe

Chaque coupe constitue un “goulot d’etranglement” qui limitela valeur du flot.

Theoreme (relation entre flot et coupe): soit Φ un flotrealisable quelconque, soit un ensemble de sommets A ⊂ X telque E ∈ A, S /∈ A, on a : v(Φ) ≤ v(ω(A))Interpretation : la valeur de tout flot est majoree par la valeurd’une coupe quelconque ; ceci est vrai en particulier pour leflot maximum,

La notion de coupe correspond bien a l’idee de gouletd’etranglement.




Determination d’un flot realisable sur un reseau de transportDetermination d’un flot maximumDetermination d’un flot de cout minimum









Differents types de problemes de flot

un flot realisable est un flot Φ verifiant b(u) ≤ φ(u) ≤ k(u),∀u ∈ U et

∑

u∈ω−(x) φ(u) =∑

u∈ω+(x) φ(u), ∀x ∈ X \ {E ,S},

un reseau de transport n’admet pas necessairement de flotrealisable,

Exemple :3

2

1

4

E S

[0,3]

[0,3][1,

4]

[1,2]

[1,3]

[5,7]

[1,3]

on a φ(2, 4) ≥ 1 et φ(E , 2) ≤ 3⇒ φ(2, 3) ≤ 2or φ(1, 3) ≤ 2 donc φ(3,S) ≤ 4 ≤ b(3,S)





Flot realisable sur un reseau de transport

Cas particulier important :si le reseau de transport ne comporte aucune borne(b(u) = 0,∀u ∈ U) alors il existe toujours un flot realisable,i.e., le flot nul Φ0 t.q. φ(u) = 0,∀u ∈ U.





Determination d’un flot maximum

Objectif : faire transiter dans le reseau de transport la plusgrande quantite de matiere,

Rechercher parmi tous les flots realisables, le flot Φ∗ tel quev(Φ∗) soit maximale,

Ce probleme peut s’ecrire sous la forme d’un programmelineaire:

max∑

u∈ω+(E) φ(u)

s.c.∑

u∈ω−(x) φ(u) =∑

u∈ω+(x) φ(u), ∀x 6= E ,S

b(u) ≤ φ(u) ≤ k(u), ∀u ∈ U

φ(u) ≥ 0





Determination d’un flot de cout minimum

Objectif : rechercher parmi les flots d’une valeur v donnee,celui (ou ceux) qui minimise(nt) le cout,

Ce probleme peut s’ecrire sous la forme d’un programmelineaire:

min∑

u∈U c(u).φ(u)s.c.

∑

u∈ω−(x) φ(u) =∑

u∈ω+(x) φ(u), ∀x 6= E ,S

b(u) ≤ φ(u) ≤ k(u), ∀u ∈ U∑

u∈ω+(E) φ(u) = v

φ(u) ≥ 0

Cas particulier : determination d’un flot maximum a coutminimum (v = v(Φ∗))




Principe general de l’algorithme de Ford-FulkersonConstruction d’un flot completAmelioration d’un flot realisableJustification de l’algorithme, convergence et complexiteGraphe d’ecart

Recherche d’un flot de valeur maximale

Principe general de l’algorithme de Ford-Fulkerson

Principe general : on part d’un flot realisable (flot nul si

b(u) = 0, ∀u ∈ U) que l’on ameliore iterativement,

Definitions :

un arc u ∈ U est dit sature si φ(u) = k(u),un flot Φ est dit complet si tout chemin µ de E vers S

comporte au moins un arc sature,

Remarque : un flot non complet ne peut pas etre maximum

Φ maximum ⇒ Φ complet,mais Φ complet ; Φ maximum ,

Construire un flot complet lors de la premiere etape del’algorithme → on part d’un flot complet au lieu de Φ0,





Construction d’un flot complet

Partir d’un flot realisable (flot nul si b(u) = 0,∀u ∈ U),

Examiner tous les chemins de E a S de facon systematique,

Pour chaque chemin µ de E a S , faire passer un flot egal a lacapacite residuelle minimale des arcs de µ.

Exemple :

3

2

1

d

c

b

a

E S

[0,45]

[0,25]

[0,25]

[0,10]

[0,15]

[0,20]

[0,20]

[0,5]

[0,5]

[0,10]

[0,10]

[0,30]

[0,10]

[0,20]

[0,30]






3

2

1

d

c

b

a

E S

[0,45]

[0,25]

10, [0,25]

[0,10]

[0,15]

[0,20]

[0,20]

[0,5]

[0,5]

10, [0,10]

[0,10]

[0,30]

[0,10]

[0,20]

10, [0,

30]

E → 3→ d → S : 10Total : 10






3

2

1

d

c

b

a

E S

[0,45]

[0,25]

10+10, [0,25]

[0,10]

[0,15]

[0,20]

[0,20]

[0,5]

[0,5]

10, [0,10]

10, [0,10]

[0,30]

[0,10]

10, [0,20]

10, [0,

30]

E → 3→ d → S : 10E → 3→ c → S : 10

Total : 20






3

2

1

d

c

b

a

E S

[0,45]

5, [0,25]

10+10, [0,25]

[0,10]

[0,15]

[0,20]

[0,20]

[0,5]

5, [0,5]

10, [0,10]

10, [0,10]

[0,30]

[0,10]

10+5, [0,20]

10, [0,

30]

E → 3→ d → S : 10, E → 3→ c → S : 10E → 2→ c → S : 5

Total : 25






3

2

1

d

c

b

a

E S

[0,45]

5+5, [0,25]

10+10, [0,25]

[0,10]

[0,15]

[0,20]

[0,20]

5, [0,5]

5, [0,5]

10, [0,10]

10, [0,10]

[0,30]

5, [0,10]

10+5, [0,20]

10, [0,

30]

E → 3→ d → S : 10, E → 3→ c → S : 10E → 2→ c → S : 5E → 2→ b → S : 5

Total : 30






3

2

1

d

c

b

a

E S

[0,45]

5+5+15, [0,25]

10+10, [0,25]

[0,10]

[0,15]

[0,20]

15, [0,

20]

5, [0,5]

5, [0,5]

10, [0,10]

10, [0,10]

15, [0,30]5, [0,10]

10+5, [0,20]

10, [0,

30]

E → 3→ d → S : 10, E → 3→ c → S : 10E → 2→ c → S : 5, E → 2→ b → S : 5E → 2→ a→ S : 15

Total : 45






3

2

1

d

c

b

a

E S

20,[0,4

5]

5+5+15, [0,25]

10+10, [0,25]

[0,10]

[0,15]

20, [0,20]

15, [0,

20]

5, [0,5]

5, [0,5]

10, [0,10]

10, [0,10]

15, [0,30]5, [0,10]

10+5, [0,20]

10+20

, [0,30]

E → 3→ d → S : 10, E → 3→ c → S : 10E → 2→ c → S : 5, E → 2→ b → S : 5E → 2→ a→ S : 15E → 1→ d → S : 20

Total : 65






3

2

1

d

c

b

a

E S

20+5, [0,4

5]

5+5+15, [0,25]

10+10, [0,25]

[0,10]

5, [0,15]

20, [0,20]

15, [0,

20]

5, [0,5]

5, [0,5]

10, [0,10]

10, [0,10]

15, [0,30]5+5, [0,10]

10+5, [0,20]

10+20

, [0,30]

E → 3→ d → S : 10, E → 3→ c → S : 10E → 2→ c → S : 5, E → 2→ b → S : 5E → 2→ a→ S : 15, E → 1→ d → S : 20E → 1→ b → S : 5

Total : 70






3

2

1

d

c

b

a

E S

20+5+

10,[0,4

5]

5+5+15, [0,25]

10+10, [0,25]

10, [0,10]

5, [0,15]

20, [0,20]

15, [0,

20]

5, [0,5]

5, [0,5]

10, [0,10]

10, [0,10]

15+10, [0,30]5+5, [0,10]

10+5, [0,20]

10+20

, [0,30]

E → 3→ d → S : 10, E → 3→ c → S : 10E → 2→ c → S : 5, E → 2→ b → S : 5E → 2→ a→ S : 15, E → 1→ d → S : 20E → 1→ b → S : 5E → 1→ a→ S : 10

Total : 80





Flot complet

3

2

1

d

c

b

a

E S

35,[0,4

5]

25, [0,25]

20, [0,25]

10, [0,10]

5, [0,15]

20, [0,20]

15, [0,

20]

5, [0,5]

5, [0,5]

10, [0,10]

10, [0,10]

25, [0,30]10, [0,10]

15, [0,20]

30, [0,

30]

E → 3→ d → S : 10, E → 3→ c → S : 10E → 2→ c → S : 5, E → 2→ b → S : 5E → 2→ a→ S : 15, E → 1→ d → S : 20E → 1→ b → S : 5, E → 1→ a→ S : 10

Total : 80





Amelioration d’un flot realisable

L’algorithme de Ford-Fulkerson se decompose en deux etapes :

procedure de marquage + procedure de changement de flot.

1 : Procedure de marquagedebut

marquer [+] le sommet Erepeter

- selectionner un sommet marque x,- marquer [+] tout sommet y non marque,

extremite terminale d’un arc (x , y) non sature- marquer [-] tout sommet y non marque,

l’extremite initiale d’un arc (y , x)tel que φ(y , x) > b(y , x)

jusqu’a (aucun sommet ne peut etre marque) ou (S marque)

si S n’est pas marquealors le flot est maximumsinon le flot peut etre ameliore

fin si

fin





procedure de changement de flot

Cette procedure ne s’applique que si S est marque a l’issue dela procedure de marquage.

Soit µ une chaıne de E a S .

e xi xi+1 xj xj+1 s

Soit µ+ l’ensembles des arcs de la chaıne de type (xi , xi+1)“arcs avant”.

Soit µ− l’ensembles des arcs de la chaıne de type (xj , xj+1)“arcs arriere”.

Les arcs de µ+ sont tels qu’il est possible d’augmenter lavaleur du flux associe d’une quantite ε+ ≥ 0.

Les arcs de µ− sont tels qu’il est possible de diminuer lavaleur du flux associe d’une quantite ε− ≥ 0.





Procedure de changement de flot

Une chaıne µ est dite ameliorante si ε+ > 0 et ε− > 0.

Si on augmente la valeur du flux sur les arcs de µ+ et diminuela valeur du flux d’une meme valeur sur les arcs de µ−, la loide Kirshhoff est preservee en chaque sommet,

Procedure de changement de flot (Φ → Φ′) :debut

ε+ ← minu∈µ+{k(u)− φ(u)}ε− ← minu∈µ−{φ(u) − b(u)}ε← min{ε+, ε−}construire Φ′ tel que

φ′(u)← φ(u) + ε, ∀u ∈ µ+

φ′(u)← φ(u)− ε, ∀u ∈ µ−

φ′(u)← φ(u), ∀u /∈ µreappliquer la procedure de marquage

fin





Marquage

3

2

1

d

c

b

a

E S

+ 35,[0,4

5]

25, [0,25]

20, [0,25]

10, [0,10]

5, [0,15]

20, [0,20]

15, [0,

20]

5, [0,5]

5, [0,5]

10, [0,10]

10, [0,10]

25, [0,30]10, [0,10]

15, [0,20]

30, [0,

30]





Marquage

3

2

1

d

c

b

a

E S

+

+

+

35,[0,4

5]

25, [0,25]

20, [0,25]

10, [0,10]

5, [0,15]

20, [0,20]

15, [0,

20]

5, [0,5]

5, [0,5]

10, [0,10]

10, [0,10]

25, [0,30]10, [0,10]

15, [0,20]

30, [0,

30]





Marquage

3

2

1

d

c

b

a

E S

+

+

+

+35,

[0,45]

25, [0,25]

20, [0,25]

10, [0,10]

5, [0,15]

20, [0,20]

15, [0,

20]

5, [0,5]

5, [0,5]

10, [0,10]

10, [0,10]

25, [0,30]10, [0,10]

15, [0,20]

30, [0,

30]





Marquage

3

2

1

d

c

b

a

E S

+

+

+

-

+35,

[0,45]

25, [0,25]

20, [0,25]

10, [0,10]

5, [0,15]

20, [0,20]

15, [0,

20]

5, [0,5]

5, [0,5]

10, [0,10]

10, [0,10]

25, [0,30]10, [0,10]

15, [0,20]

30, [0,

30]





Marquage

3

2

1

d

c

b

a

E S

+

+

+

-

+

+

35,[0,4

5]

25, [0,25]

20, [0,25]

10, [0,10]

5, [0,15]

20, [0,20]

15, [0,

20]

5, [0,5]

5, [0,5]

10, [0,10]

10, [0,10]

25, [0,30]10, [0,10]

15, [0,20]

30, [0,

30]





Marquage

3

2

1

d

c

b

a

E S

+

+

+

-

+

+

+35,[0,4

5]

25, [0,25]

20, [0,25]

10, [0,10]

5, [0,15]

20, [0,20]

15, [0,

20]

5, [0,5]

5, [0,5]

10, [0,10]

10, [0,10]

25, [0,30]10, [0,10]

15, [0,20]

30, [0,

30]





chaıne ameliorante

3

2

1

d

c

b

a

E S+

+

+

-

+

+

+35,[0,4

5]

25, [0,25]

20, [0,25]

10, [0,10]

5, [0,15]

20, [0,20]

15, [0,

20]

5, [0,5]

5, [0,5]

10, [0,10]

10, [0,10]

25, [0,30]10, [0,10]

15, [0,20]

30, [0,

30]

E→1→b→2→a→S : 5





Nouveau flot

3

2

1

d

c

b

a

E S

35+5, [0,4

5]

25, [0,25]

20, [0,25]

10, [0,10]

5+5

[0,15]

20, [0,20]

15+5[0,

20]

5-5, [0,5]

5, [0,5]

10, [0,10]

10, [0,10]

25+5, [0,30]10, [0,10]

15, [0,20]

30, [0,

30]





Marquage

3

2

1

d

c

b

a

E S

+ 40,[0,4

5]

25, [0,25]

20, [0,25]

10, [0,10]

10, [0,15]

20, [0,20]

20, [0,

20]

0, [0,5]

5, [0,5]

10, [0,10]

10, [0,10]

30, [0,30]10, [0,10]

15, [0,20]

30, [0,

30]





Marquage

3

2

1

d

c

b

a

E S

+

+

+

40,[0,4

5]

25, [0,25]

20, [0,25]

10, [0,10]

10, [0,15]

20, [0,20]

20, [0,

20]

0, [0,5]

5, [0,5]

10, [0,10]

10, [0,10]

30, [0,30]10, [0,10]

15, [0,20]

30, [0,

30]





Marquage

3

2

1

d

c

b

a

E S+

+

+

+

40,[0,4

5]

25, [0,25]

20, [0,25]

10, [0,10]

10, [0,15]

20, [0,20]

20, [0,

20]

0, [0,5]

5, [0,5]

10, [0,10]

10, [0,10]

30, [0,30]10, [0,10]

15, [0,20]

30, [0,

30]

On ne peut plus marquer de sommets,S n’est pas marque

→ le flot est maximum.





Marquage

3

2

1

d

c

b

a

E S

+

+

+

+

40,[0,4

5]

25, [0,25]

20, [0,25]

10, [0,10]

10, [0,15]

20, [0,20]

20, [0,

20]

0, [0,5]

5, [0,5]

10, [0,10]

10, [0,10]

30, [0,30]10, [0,10]

15, [0,20]

30, [0,

30]

On ne peut plus marquer de sommets,S n’est pas marque

→ le flot est maximum, v(Φ∗) = 85.La coupe de valeur minimale est engendree par le sous-ensemble A

des sommets marques → v(ω(A∗)) = 85.





Justification de l’algorithme

Theoreme (de Ford-Fulkerson) : La valeur d’un flot maximumest egale a la valeur d’une coupe minimum,

Ce theoreme traduit le fait que rechercher un flot maximumest equivalent a rechercher une coupe minimum,

A la fin de l’algorithme de Ford-Fulkerson, soit A∗ lessommets marques (E ∈ A∗,S /∈ A∗), la coupe ω(A∗) est devaleur minimale,

Lemme 1 : Soit Φ un flot definit sur un reseau de transport(de racine E et d’antiracine S), ∀A ⊂ X t.q. E ∈ A,S /∈ A, on a:

v(Φ) =∑

u∈ω+(A)

φ(u)−∑

u∈ω−(A)

φ(u)

i.e.,“la valeur d’un flot peut etre determinee sur toute coupe”





Preuved’apres la loi de Kirshhoff on a :

∑

u∈ω+(x) φ(u) =∑

u∈ω−(x) φ(u), ∀x 6= E

d’ou :∑

x∈A\{E}

∑

u∈ω+(x) φ(u) =∑

x∈A\{E}

∑

u∈ω−(x) φ(u)

C’est-a-dire :∑

x∈A

∑

u∈ω+(x) φ(u) −∑

u∈ω+(E ) φ(u) =∑

x∈A

∑

u∈ω−(x) φ(u) −∑

u∈ω−(E ) φ(u),

or,∑

u∈ω+(E ) φ(u) = v(Φ) et∑

u∈ω−(E ) φ(u) = 0

donc,

v(Φ) =∑

x∈A

∑

u∈ω+(x) φ(u) −∑

x∈A

∑

u∈ω−(x) φ(u)

=(∑

(y,z):y∈A,z∈A φ(y , z) +∑

(y,z):y∈A,z /∈A φ(y , z))

−(∑

(y,z):y /∈A,z∈A φ(y , z) +∑

(y,z):y /∈A,z /∈A φ(y , z))

=∑

u∈ω+(A) φ(u) −∑

u∈ω−(A) φ(u) �





Corollaire : v(Φ) =∑

u∈ω−(S) φ(u)Preuve : application du lemme 1 avec A = {S} �

Lemme 2 (relation fondamentale flot-coupe) :∀Φ flot realisable, ∀A ⊂ X t.q. E ∈ A,S /∈ A,on a : v(Φ) ≤ v(ω(A))

Preuve :

d’apres le lemme 1 on a :v(Φ) =

∑

u∈ω+(A) φ(u)−∑

u∈ω−(A) φ(u),

or Φ est realisable donc b(u) ≤ φ(u) ≤ k(u), ∀u ∈ U,

d’ou∑

u∈ω+(A) φ(u) ≤∑

u∈ω+(A) k(u) et−

∑

u∈ω−(A) φ(u) ≤ −∑

u∈ω−(A) b(u)

donc v(Φ) ≤∑

u∈ω+(A) k(u)−∑

u∈ω−(A) b(u)

= v(ω(A)) �





Theoreme : Si ∃ flot Φ∗ et une coupe engendree par A∗ tels quev(Φ∗) = v(ω(A∗)), alors Φ∗ est de valeur maximale et la coupeengendree par A∗ est de valeur minimale.

Preuve :

d’apres le lemme 2, ∀Φ′ un flot realisable, on a : v(Φ′) ≤ v(ω(A∗)),or v(ω(A∗)) = v(Φ∗) donc v(Φ′) ≤ v(Φ∗).

d’apres le lemme 2, ∀A′ ⊂ X t.q. E ∈ A, S /∈ A, on a :v(ω(A′)) ≥ v(Φ∗), or v(Φ∗) = v(ω(A∗)) doncv(ω(A′)) ≥ v(ω(A∗))

Montrons qu’il existe un flot Φ∗ et une coupe engendree par A∗ telsque v(Φ∗) = v(ω(A∗)),





A la fin de l’algorithme de Ford-Fulkerson, on obtient un flot Φff

(realisable par construction) et un ensemble de sommets marquesAff (avec E ∈ Aff et S /∈ Aff ),

on a:∀u = (x , y) ∈ ω+(Aff ), u sature (i.e. φ(u) = k(u)), sinon onaurait pu marquer + y et donc u = (x , y) /∈ ω+(Aff ),∀u = (x , y) ∈ ω−(Aff ), φ(u) = b(u), sinon on aurait pumarquer - x et donc u = (x , y) /∈ ω−(Aff ),

d’apres le lemme 1, on a :v(Φff ) =

∑

u∈ω+(Aff ) φ(u) −∑

u∈ω−(Aff ) φ(u)

=∑

u∈ω+(Aff ) k(u)−∑

u∈ω−(Aff ) b(u)

= v(ω(Aff )) �

l’algorithme de Ford-Fulkerson fournit permet donc de determinerun flot de valeur maximum et une coupe de valeur minimum,

La preuve du theoreme de Ford-Fulkerson est fournit parl’algorithme lui-meme.





Convergence et complexite

partant du flot nul Φ0 a chaque etape de l’algorithme (prise en

compte d’une chaıne ameliorante), le flot est augmente d’un valeurentiere >0

or v(Φ∗) ≤ v(ω(A)), ∀A ⊂ X t.q. E ∈ A, S /∈ A ⇒ il existeun nombre fini de chaınes ameliorantes,

b(u) et k(u) sont entier ⇒ l’algorithme converge en unnombre fini d’iterations.





Complexite de l’algorithme de Ford-Fulkerson,

nombre d’iterations ≤ v(Φ∗) = v(ω+({E})),

a chaque iteration, on examine tous les sommets (excepte E ),c’est-a-dire n− 1 sommets

examiner un sommet consiste a effectuer un nombred’operation proportionnel au degre du sommet (pour tester sion peut prolonger une chaıne ameliorante),

le nombre d’operations a effectuer a chaque iteration est doncborne par la somme des degres des sommets, i.e., 2m,

la complexite est donc de O(m.v(Φ∗)) ou O(m.v(ω({E}))),

or ω({E}) est majore par n.kmax , ou kmax = maxu∈U{k(u)},donc la complexite est de O(m.n.kmax)





Graphe d’ecart

On peut associer a un reseau de transport G = (X ,U)antisymetrique et un flot Φ, un graphe G e(Φ) = (X ,Ue(Φ))appele graphe d’ecart. Ue(Φ) est defini par :

a tout arc (x , y) ∈ U tel que b(u) < φ(u) < k(u), on associe :

un arc (x , y) ∈ Ue(Φ) t.q. ke(x , y) = k(u)− φ(u) etce(x , y) = c(u),un arc (y , x) ∈ Ue(Φ) t.q. ke(x , y) = φ(u) − b(u) etce(y , x) = −c(u),

a tout arc (x , y) ∈ U tel que φ(u) = k(u), on associe un arc(y , x) ∈ Ue(Φ) t.q. ke(x , y) = φ(u) − b(u) et ce(y , x) = −c(u),

a tout arc (x , y) ∈ U tel que φ(u) = b(u), on associe un arc(x , y) ∈ Ue(Φ) t.q. ke(x , y) = k(u)− φ(u) et ce(x , y) = c(u),





Graphe d’ecart

Dans le graphe G e(Φ) = (X ,Ue(Φ)), tout chemine de E a S

represente une chaıne ameliorante ,

Considerons le flot Φ correspondant au flot complet determineau §3.2. le graphe G e(Φ) est le suivant. On retrouve la chaıneameliorante E1b2aS

3

2

1

d

c

b

a

E S

[10]

[35]

[25]

[20]

[5]

[10]

[10]

[5]

[20]

[15]

[5]

[5][5]

[10]

[10]

[25]

[5]

[10]

[15]

[5]

[30]





Changement de flot avec G e(Φ)

Soit µe un chemin de E a S dans G e(Φ) et µ la chaınecorrespondante (concept non-oriente) dans G ,

Soit δ = Minu∈µe ke(u),

On peut obtenir un flot realisable Φ′ en faisant varier les fluxsur les arcs de G comme suit :

∀u ∈ µ t.q. l’arc correspondant dans µe a la meme orientation: φ′(u) = φ(u) + ε (ε ≤ δ),∀u ∈ µ pour lequel l’arc correspondant dans µe a l’orientationinverse : φ′(u) = φ(u) − ε (ε ≤ δ),∀u /∈ µ, φ′(u) = φ(u)





Changement de flot avec G e(Φ)

Φ est un flot (loi de Kirshhoff preservee) realisable (ε ≤ δ),

En appliquant la procedure a un chemin de E a S , onaugmente la valeur du flot Φ de ε,

En appliquant la procedure a un circuit, on ne modifie pas lavaleur du flot mais on a : c(Φ′) = c(Φ) +

∑

u∈µe ce(u).ε,

Exemple : circuit 1b2a1, δ = min{10, 5, 10, 10} = 5

ajouter 5 a φ(1, b),retirer 5 a φ(2, b),ajouter 5 a φ(2, a),retirer 5 a φ(1, a),




Flot de cout minimum

Soit un reseau de transport G = (X , U) sur lequel sont associes achaque arc u ∈ U, b(u) (borne), k(u) (capacite) et c(u) (coutunitaire),

Le probleme consiste a determiner parmi les flots realisables devaleur v , un flot de cout minimum,

Formulation en Programmation Lineaire :

min∑

u∈U c(u).φ(u)s.c.

∑

u∈ω−(x) φ(u) =∑

u∈ω+(x) φ(u), ∀x 6= E , S

b(u) ≤ φ(u) ≤ k(u), ∀u ∈ U∑

u∈ω+(E) c(u).φ(u) = v

φ(u) ≥ 0, ∀u ∈ U

Les variables du PL sont φ(u), ∀u ∈ U, les deux premierescontraintes assurent que le flot est realisable,

La derniere contrainte assure que les flots consideres sont de valeurVincent Mousseau Problemes de flots




Theoreme : Φ, un flot de valeur v , est de cout minimum ssiG e(Φ) ne contient pas de circuit de valeur negative au sensdes couts,

Algorithme de construction d’un flot de valeur v et de coutminimum :

debutconstruire un flot Φ de valeur v de cout krepeter

- construire G e(Φ),- si ∃µ un circuit de valeur kµ < 0 dans G e(Φ),

alors construire Φ′ en appliquant laprocedure de changement de flotsur µ avec ε = δ

Finsi- le flot Φ′ est de valeur v ′ = v et de

cout k′ = k − δ.kµ

jusqu’a ∄µ circuit de valeur negative dans G e(Φ)

fin





On peut appliquer differents algorithmes pour la detection decircuits de valeur negative (Bellman-Kalaba, Floyd,...).

Probleme : A partir d’un flot Φ de valeur v (v < v(Φ∗)) et decout minimum, comment determiner un flot Φ′ de valeurv ′ > v et de cout minimum ?

Theoreme :Soit Φ un flot de valeur v (v < v(Φ∗)) et de cout minimum,soit µe un chemin de cout minimum de E a S dans G e(Φ).On obtient un flot Φ′ de valeur v ′ > v et de cout minimum enappliquant la procedure de changement de flot sur µe .

Algorithme de construction d’un flot Φ′ de valeur v ′ > v et decout minimum a partir d’un flot Φ de valeur v et de coutminimum :





debut- soit Φ un flot de cout minimum parmi

les flots de valeur v

- construire G e(Φ),

- choisir dans G e(Φ) un chemin µe de E a S

minimal au sens des couts

- construire Φ′ en appliquant la procedure de

changement de flot en utilisant avec ε = δ

fin

Probleme : pour appliquer l’algorithme, il faut disposer d’unflot de cout minimum. On peut soit appliquer l’algorithmeprecedent, soit considerer le flot nul.


Documents

Problèmes de flots - Laboratoire Génie Industriel - … général de l’algorithme de Ford-Fulkerson Construction d’un flot complet Amélioration d’un flot réalisable