Le problème de flot maximum : explication de l’algorithme de Ford et Fulkerson

Résumé du document

Lors de la première itération, on va chercher à augmenter le flux allant du nœud d'entrée au nœud de sortie. On teste pour cela différents nœuds (l'ordre dans lequel on les examine est l'ordre chronologique ou alphabétique des nœuds indiqué en T. Autrement dit, si T= {A, B, C } on examinera tout d'abord A puis B puis C.

Ensuite, à l'itération 2 : il faut refaire un nouveau schéma avec les augmentations de flux effectives trouvées à l'itération 1. Autrement dit, si on a trouvé une augmentation de 100 du flux de sortie, il faut augmenter de 100 le flux d'entrée quand bien même on aurait indiqué qu'il pouvait augmenter de 150, il s'agit là d'une augmentation théorique et on indique par conséquent '+100' sur notre schéma.

Extraits

[...] Le problème de flot maximum: explication de l'algorithme de Ford et Fulkerson 1. Formulation mathématique d'un problème de flux maximum 1. Variables de décision fij = flux dans l'arc 2. Fonction objective Maximiser le flux dans l'arc de retour. [...]

[...] Exemple : si on a trouvé une augmentation de 100 du flux de sortie, il faut augmenter de 100 le flux d'entrée (même si on a indiqué qu'il pouvait augmenter de 150 çà c'est une augmentation théorique on indique + 100 dans notre schéma) Explications de l'algorithme de Ford et Fulkerson Prenons l'exemple suivant : À partir de deux arcs peuvent être augmentés deux routes) : - A dont la capacité est actuellement de 2 (maximum : - B dont la capacité est actuellement de 6 (maximum : Il faudra donc étudier ces deux chemins 2 itérations 1. [...]

[...] maxz = fn1 avec i = le noeud d'entre´e et i = le noeud de sortie Contraintes Équations de conservation aux noeuds : bornes supe´rieures et infe´rieures sur les flux : Explication de l'algorithme de Ford et Fulkerson : Lors de la première itération, on va chercher à augmenter le flux allant du nœud d'entrée au nœud de sortie. On teste différents nœuds (l'ordre dans lequel on les examine est l'ordre chronologique ou alphabétique des nœuds indiqué en T. Exemple : si C } on examine A puis B puis C). [...]

[...] Étude du chemin 2 : arc À partir du graphique de départ, on remarque qu'un second arc peut-être augmenté, l'arc on étudie ce chemin. La chaîne d'arcs utilisable est : On utilise la même procédure que ci-dessus. La solution obtenue est donc celle-ci : Le flux sortant a pu être augmenté de Application de l'algorithme de Ford et Fulkerson Reprenons l'exemple précédent auquel, pour chaque nœud, nous indiquons le couple : (Nom de l'arc à partir duquel la capacité peut être augmentée, capacité qui peut être augmentée) 1. [...]

[...] On essaie donc de tester cette route : Initialisations T = S = F } E = Examen de A : = Label(B) = T = S = F } E = Examen de B : = Label(C ) = T = C } S = F } E = Examen de C : T = C } S = F } E = C } Stop : le crite`re d'arreˆt est satisfait car T = E La coupe minimum est : , avec T = C } et S = F En effet, on se rend compte qu'on ne sait plus sortir de B car, en augmentant le flux de C vers on est en surcapacité et on ne sait plus avancer, car est saturé et pris à rebours conduirait à former un cycle et non plus une chaîne. Le flot maximum est de 10 unite´s. [...]