École Supérieure en Informatique Sidi Bel

Abbes-Algérie

TD RECHERCHE OPERATIONNELLE
Groupes 03 et 05

Problème du Flot Maximum

Melle A.TAOULI
[email protected]
[email protected]
 Problème du flot maximum
• Réseau à flot , c’est un graphe orienté qui a des caractéristiques
spécifiques.
• Il est composé des sommets internes et deux sommets spécifiques:
S=> Source (n’a pas d’arcs entrants)
T=> Puits (n’a pas d’arcs sortants)
• Sur chaque arc on met une étiquette qui présente la capacité de l’arc.
• Valeur du flot : quantité du flot qui entre en T ou quantité du flot qui
sort de S.
 objectif est de maximiser la valeur du flot.

1
 Exercice 01
Q1:Problème de flot maximum dans un réseau. Algorithme de Ford-Fulkerson
Q2: Application de l’algorithme Ford-Fulkerson.

A 3 Étape 0: Initialisation A 0/3

3 7 0/3 0/7
2 4 0/2 0/4
6 3 0/6 0/3 D T
S B D T S B

1 5 0/1 0/5
2 0/2

C C 0/6
6

Graphe Orienté élémentaire Flot Initial

Flot=0

2
 Étape 0: Initialisation
Flot=0

A 3 A 0/3

3 7 0/3 0/7
2 4 0/2 0/4
6 3 0/6 0/3 D T
S B D T S B

1 5 0/1 0/5
2 0/2

C C 0/6
6
Graphe d’écart Flot Initial

Chemins améliorants: 1. Sélectionner un chemin améliorant.

SADT 2 SADT 2 SCBT 1 2. Calculer le minimum des capacités de ce chemin.
SABDT 2 SBDT 3 SCDT 1
SABT 2 SBT 5 SCBDT 1
SBT=> min{6,5}=5 3
 Étape 1
Flot=0

A 3 A 0/3

3 7 0/3 0/7
2 4 0/2 0/4
1 3 0/6 0/3 D T
S B D T S B
0
1 5 5 0/1 0/5
2 0/2

C C 0/6
6
Graphe d’écart Flot

Chemins améliorants: Sélectionnez le chemin améliorant sur le graphe d’écart

SADT 2 SADT 2 SCBT 1 en ajoutant des arcs de retour.
SABDT 2 SBDT 3 SCDT 1
SABT 2 SBT 5 SCBDT 1
SBT=> min{6,5}=5 4
 Étape 1 Flot=0+5

3 A 0/3
A
3 7 0/3 0/7
2 4 0/2 0/4
1 3 5/6 0/3 D T
S B D T S B

1 5 5 0/1 5/5
2 0/2

C C 0/6
6
Graphe d’écart Flot
Chemins améliorants: 1. Supprimez les arcs avec capacité 0
SADT 2 SADT 2 SCDT 1 2. Mettre à jour le flot.
SABDT 2 SBDT 1 SCBDT 1 3. Mettre à jour les capacités sur le réseau du flot.
4. Sélectionnez le chemin améliorant pour la
SADT=> min{2,7,4}=2 2éme étape.
5. Calculer le min entre ces capacités. 5
 Étape 2 Flot=0+5

A A 0/3
3
3 0/3 0/7
0 2 2 5
2 0/2 0/4
1 3 5/6 0/3 D T
S B D T S B
2
1 5 5 0/1 5/5
2 0/2

C C 0/6
6
Graphe d’écart Flot
Chemins améliorants: Sélectionnez le chemin améliorant sur le graphe
SAD 2 SADT 2 SCBT 1 d’écart en ajoutant des arcs de retour.
SABD 2 SBDT 1 SCDT 1
SABT 2 SCBDT 1

SADT=> min{2,7,4}=2 6
 Étape 2 Flot=0+5+2

A A 0/3
5 3 0/3 2/7
2 3 2/2
2 2 2/4
1 3 5/6 0/3 D T
S B D T S B
2
1 5 5 0/1 5/5
2 0/2

C C 0/6
6
Graphe d’écart Flot
Chemins améliorants: 1. Supprimez les arcs avec capacité 0.
SCBT 1 2. Mettre à jour le flot.
SBDT 1 SCDT 1 3. Mettre à jour les capacités sur le réseau du flot.
SCBDT 1 4. Sélectionnez le chemin améliorant de la 3éme
étape.
SBDT=> min{1,3,2}=1 5. Calculer le min entre ces capacités. 7
 Étape 3 Flot=0+5+2

A A 0/3
3
3 5 0/3 2/7
2 2 2/2
1 0/3 2/4
0 2 5/6 D T
S B D T S B
1 3
1 6 5 0/1 5/5
2 0/2

C C 0/6
6
Graphe d’écart Flot
Chemins améliorants: Sélectionnez le chemin améliorant sur le graphe
SCBT 1 en ajoutant des arcs de retour.
SBDT 1 SCDT 1
SCBDT 1

SBDT=> min{1,3,2}=1 8
 Étape 3
Flot=0+5+2+1

A 3 A 0/3
5 2/7
2 3 2 2/2 0/3
1 1/3 3/4
2 S 6/6 B D T
S B D 3 T
6 1
1 5 0/1 5/5
2 0/2

C C 0/6
6
Graphe d’écart Flot
Chemins améliorants: 1. Supprimez les arcs avec capacité 0.
SCDT 1 SCBDT 1 2. Mettre à jour le flot.
3. Mettre à jour les capacités sur le réseau du flot.
4. Sélectionnez le chemin améliorant de la 4éme
étape.
SCBDT=> min{1,2,2,1}=1 5. Calculer le min entre ces capacités. 9
 Étape 4
Flot=0+5+2+1

A 3 A 0/3
5
3 2 0/3 2/7
2 2/2
0 1/3 3/4
1 S 6/6 B D T
S B D 4 T
6 2
5 0/1 5/5
0 11 0/2
1
C C 0/6
6
Graphe d’écart Flot
Chemins améliorants: Sélectionnez le chemin améliorant sur le graphe
SCDT 1 SCBDT 1 en ajoutant des arcs de retour.

SCBDT=> min{1,2,2,1}=1 10
 Étape4 Flot=0+5+2+1+1=9

A 3 A 0/3
5 2/7
2 3 2 2/2 0/3
6/6 2/3 4/4
1 D T S B D T
S B 4
6 2
5 1/1 5/5
1 1/2
1
1
C C 0/6
6
Graphe d’écart Flot

Q3:Le débit maximal:0+5+2+1+1=9 1. Supprimez les arcs avec capacité 0.

il est réalisé par le routage suivant(la somme de 4 flots : 2. Mettre à jour le flot.
5 sur SBT, 2 sur SADT, 1 sur SBDT, 1 sur SCBDT) 3. Mettre à jour les capacités sur le réseau du flot.
Critère d’arrêt: quand il n’existe pas un chemin
améliorant dans le graphe d’écart.
11
Exercice 02:

Q1:Compléter le flot suivant :

2/7
a d  0≤f(x,y)≤c(x,y)
3/7  La somme des flux qui sorte de E = la
3/7 2/4
1/7 somme des flux qui entre en S.
1/4 S  En chaque sommet intermédiaire, la somme
E 2/4 f des flux qui entrent = la somme des flux qui
4/4 1/4
sortent.
3/10 3/4
b c
1/7 Flot réalisable(admissible)

(E,a) (E,b) (a,b) (a,d) (b,c) (b,f) (c,S) (d,c) (d,S) (f,a) (f,c) (f,d)
3 3 2 2 1 4 3 1 3 1 1 2

Q2:le flot précédent n’est pas maximale, Un flot sera dit maximal lorsqu’il n'existe pas un chemin de E à S dans le graphe
d’écart.
12
 Graphe d’écart
Flot réalisable
2
2/7 3
a d a d
5
3/7 4 1
3/7 2/4 2 4
1/7 3 6
S 2
1/4 2 2 1 S
E 2/4 f E f 3
3 1
4/4 1/4 1
4 3
3/10 3/4 7 1
b c b c 3
1/7 6

Flot =6

Q2:le flot précédent n’est pas maximale, Un flot sera dit maximal lorsqu’il n'existe pas un chemin de E à S dans le graphe
d’écart.
13
 Q3:Trouver le flot maximal en appliquant l’algorithme de Ford- Fulkerson.

Étape 0 Graphe d’écart

Flot réalisable
6
2/7 7
a d a d
1
3/7 0 1
3/7 2/4 2 0
1/7 7 6
1/4 S 2 2 2 S
E 2/4 f E f 3 1
3 1
4/4 1/4 1
4 3
3/10 3/4 7 1
b c b c 3
1/7 6

Flot =6

Chemin améliorant: EadS

EadS=> min{4,5,4}=4

14
 Q3:Trouver le flot maximal en appliquant l’algorithme de Ford- Fulkerson.

Étape 0 Graphe d’écart

6
6/7 7
a d a d
1
7/7 1
7/7 2/4 7 2
1/7 6
1/4 S 2 2 2 S
E 2/4 f E f 3 1
3 1
4/4 1/4 1
4 3
3/10 3/4 7 1
b c b c 3
1/7 6

Flot réalisable

Flot =6+4

Chemin améliorant: EbadcS

EbadcS => min{7,2,1,3,1}=1

15
 Q3:Trouver le flot maximal en appliquant l’algorithme de Ford- Fulkerson.

Étape 1 Graphe d’écart

7
6/7 7
a d a d
0
7/7 1
7/7 2/4 7 2
1/7 6
1/4 S 3 1 2 S
E 2/4 f E f 2 2
4 1
4/4 1/4 0
4 3
3/10 3/4 6 1
b c b c 4
1/7 6

Flot réalisable

Flot =6+4

Chemin améliorant: EbadcS

EbadcS=> min{7,2,1,3,1}=1

16
 Q3:Trouver le flot maximal en appliquant l’algorithme de Ford- Fulkerson.

Étape 1 Graphe d’écart

Flot maximum
Flot =6+4+1 7
7/7 7
a d a d
7/7 1
7/7 2/4 7 2
1/7 6
2/4 S 3 1 2 S
E 1/4 f E f /2 2
4 1
4/4 1/4
4 3
4/10 4/4 6 1
b c b c 4
1/7 6

17
 TD 05: Algorithme DANTZIG
0 4 5 2 7 6 1 4 4 1 6 3
3 0 8 5 10 9 2 2 4 1 6 3
D6 4 3 0 1 2 1 P6 5 4 3 3 6 3
5 2 3 0 5 4 2 4 4 4 6 3
2 6 7 4 0 8 5 4 4 1 5 3
3 3 4 1 1 0 5 4 4 6 6 6

18