Modelisation et Recherche Operationnelle : Reseaux d'ecarts

• Michel Strasser
• softwares
• Faculty

Menu

• index
• Exercice 1 : Recherche d'un flot maximum
• Algorithme de Ford-Fulkerson
• Adaptation de Ford-Fulkerson
• Exemple d'utilisation de l'adaptation
• Serialisation des etapes
• Le programme de FF modifie
• Exercice 2 : Recherche d'un flot maximum a cout minimum
• Introduction a la methode du chemin amplificateur de flot
• Algorithme de Bellman
• Adaptation de Bellman pour le reseau d'ecart
• Adaptation de Ford-Fulkerson pour l'optimalite
• Exemple de la methode du chemin amplificateur de flot
• Le programme, methode du chemin amplificateur

Adaptation de Ford-Fulkerson

Adaptation

[mist@savage mroProject]$ diff Arc_old.py Arc.py
1  17a18,22
2  >       def cUPlus(self):
3  >               return self.capacity - self.flow
4  > 
5  >       def cUMin(self):
6  >               return self.flow
[mist@savage mroProject]$ diff MaximumFlow.py FFModified.py
 1  2c2
 2  < Algorithm of Ford-Fulkerson
 3  ---
 4  > Algorithm of Ford-Fulkerson modified
 5  7c7
 6  < class MaximumFlow:
 7  ---
 8  > class FFModified:
 9  25c25
10  <                               if y not in self.Y and u.flow<u.capacity:
11  ---
12  >                               if y not in self.Y and u.cUPlus()>0:
13  28c28
14  <                                       y.delta=min(x.delta, u.capacity - u.flow)
15  ---
16  >                                       y.delta=min(x.delta, u.cUPlus())
17  46c46
18  <                               if y not in self.Y and u.flow>0:
19  ---
20  >                               if y not in self.Y and u.cUMin()>0:
21  49c49
22  <                                       y.delta=min(x.delta, u.flow)
23  ---
24  >                                       y.delta=min(x.delta, u.cUMin())
25  104,105d103
26  <               
27  < 
[mist@savage mroProject]$

On introduit le réseau d'écart non pas en faisant une copie du réseau mais en le définissant en fonction de l'ancien. On peut donc dire que le réseau d'écart est en quelque sorte un graphe virtuel. Pour chaque arc, on a deux méthodes, cUPlus qui correspond à c'(u⁺) et cUMin qui correspond à c'(u^-).

On peut faire un marquage direct s'il existe un arc de flôt non nul dans le graphe résiduel. On peut faire un marquage indirect s'il existe un arc de flôt non nul dans U'^-

Lorsqu'il n'y a plus de chemin de la source au puit dans U'⁺, l'algorithme s'arrête.