Algorithme de ford-fulkerson

Algorithme de Ford-Fulkerson

L' algorithme de Ford-Fulkerson, du nom de ses auteurs L.R. Ford et D.R. Fulkerson, consiste en une procédure itérative qui permet de déterminer un flux (ou flot) de valeur maximale (ou minimale) à partir d'un flot constaté. Il s'agit donc d'un problème d'optimisation classique dans le domaine de la recherche opérationnelle.

Ce problème d'optimisation peut être représenté par un graphe comportant une entrée (à gauche) et une sortie (à droite). Le flot représente la circulation de l'entrée vers la sortie d'où l'utilisation de cet algorithme dans les problèmes de réseaux. Les applications sont multiples : problèmes informatiques, routiers, ferroviaires, etc. Il s'applique également à tous les autres problèmes de transferts comme les importations/exportations, les flux migratoires, démographiques mais aussi sur les flux plus abstraits tels que les transferts financiers. Pour les données de très grande taille, il existe plusieurs algorithmes plus performants pour résoudre le même problème connu sous le nom de problème de flot maximum.

Sommaire

Exemple

Une société de fret dispose de 3 centres : un à Paris, le deuxième à Lyon, le troisième à Marseille. Trois destinations sont possibles : la Pologne, la Suède, la Grèce.

Chacun des centres de fret a une capacité maximale de transport ainsi qu'un stock initial de marchandises. De même, chaque pays d'arrivée a une demande maximale pour les importations.

L'algorithme de Ford-Fulkerson va permettre d'optimiser ces flux à l'aide d'un outil de modélisation mathématique. La structure sous-jacente est représentée par un graphe orienté dont le sommet de gauche symbolise le stock initial. Celui-ci est relié à chacun des premiers arcs ou arêtes.

Dans l'exemple présent, la matrice associée porte donc dans sa première colonne les valeurs des dits stocks. Inversement, à l'extrémité de la chaîne, la matrice associée comprendra dans sa dernière colonne les demandes respectives des pays cités. Les sommets centraux comprendront les différentes combinaisons de fret maximal d'un point à l'autre.

Le problème peut être généralisé à toute circulation dans un réseau (véhicules, fluides, monnaie, etc. Les grandeurs mathématiques remplaçant indistinctement les faits réels qu'elles sont censées représenter.

Algorithme

Il s'agit d'un algorithme itératif. A chaque itération, la solution courante est un flot qui satisfait les contraintes de capacité (c'est donc un flot réalisable) et l'algorithme essaie d'augmenter la valeur de ce flot.

Considérons un flux possible dont les sous-ensembles sont les différents flux associés à chaque arête ou arc du graphe. A chaque itération de la boucle, deux sous procédures viennent compléter le processus :

  • le "marquage" qui consiste à tester si une amélioration du flux est possible.
  • le changement de flux, soit la procédure qui donne la meilleure solution à partir de l'observation précédente.

En pseudo-code informatique, l'algorithme peut se présenter ainsi :

  • initialisation
  • tant que les sommets ne sont pas marqués
    • sélectionner un sommet non marqué, tous les précédents ayant été marqués et en déterminer la marque
    • mettre à jour l'ensemble des sommets marqués
  • fin

Liens

Bibliographie

  • A simplex algorithm finding maximal networks flows and an application to the Hitchock problem(FORD L.R. ,FULKERSON D.R ), Rand Report Rand Corporation, Santa Monica, décembre 1955.
  • The transhipment problem (ORDEN A.), Management Science 2 , 1956.
  • Sur la déficience d'un réseau infini (BERGE C.), Comptes rendus de l'Académie des Sciences 245, 1957.
  • Invitation à la recherche opérationnelle (KAUFMANN A., FAURE R.) Dunod Entreprise , 1979.
  • Contribution de la théorie des graphes à l'étude des problèmes d'ordonnancement (ROY B.) Congrès international de recherche opérationnelle, 1960.
Ce document provient de « Algorithme de Ford-Fulkerson ».

Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Algorithme de ford-fulkerson de Wikipédia en français (auteurs)

Regardez d'autres dictionnaires:

  • Algorithme De Ford-Fulkerson — L algorithme de Ford Fulkerson, du nom de ses auteurs L.R. Ford et D.R. Fulkerson, consiste en une procédure itérative qui permet de déterminer un flux (ou flot) de valeur maximale (ou minimale) à partir d un flot constaté. Il s agit donc d un… …   Wikipédia en Français

  • Algorithme de Ford-Fulkerson — L algorithme de Ford Fulkerson, du nom de ses auteurs L.R. Ford et D.R. Fulkerson, consiste en une procédure itérative qui permet de déterminer un flot (ou flux) de valeur maximale (ou minimale) à partir d un flot constaté. Il s agit donc d un… …   Wikipédia en Français

  • Ford (Homonymie) — Cette page d’homonymie répertorie les différents sujets et articles partageant un même nom …   Wikipédia en Français

  • Ford (homonymie) — Cette page d’homonymie répertorie les différents sujets et articles partageant un même nom. Sur les autres projets Wikimedia : « Ford (homonymie) », sur le Wiktionnaire (dictionnaire universel) En anglais, le mot ford signifie gué …   Wikipédia en Français

  • Projet:Mathématiques/Liste des articles de mathématiques — Cette page n est plus mise à jour depuis l arrêt de DumZiBoT. Pour demander sa remise en service, faire une requête sur WP:RBOT Cette page recense les articles relatifs aux mathématiques, qui sont liés aux portails de mathématiques, géométrie ou… …   Wikipédia en Français

  • Probleme de flot maximum — Problème de flot maximum Un exemple de graphe de flot avec un flot maximum. la source est s, et le puits t. Les nombres indiquent le flot et la capacite. Le problème de flot maximum consiste a trouver un flot réalisable depuis une source unique… …   Wikipédia en Français

  • Problème de flot maximum — Un exemple de graphe de flot avec un flot maximum. la source est s, et le puits t. Les nombres indiquent le flot et la capacité. Le problème de flot maximum consiste à trouver un flot réalisable depuis une source unique et vers un puits unique… …   Wikipédia en Français

  • Liste Des Algorithmes De La Théorie Des Graphes — Cette page présente une liste non exhaustive des principaux algorithmes de la théorie des graphes. Sommaire 1 Algorithmes de parcours d un graphe 2 Algorithmes de Plus Courts Chemins (PCC) 3 …   Wikipédia en Français

  • Liste des algorithmes de la theorie des graphes — Liste des algorithmes de la théorie des graphes Cette page présente une liste non exhaustive des principaux algorithmes de la théorie des graphes. Sommaire 1 Algorithmes de parcours d un graphe 2 Algorithmes de Plus Courts Chemins (PCC) 3 …   Wikipédia en Français

  • Liste des algorithmes de la théorie des graphes — Cette page présente une liste non exhaustive des principaux algorithmes de la théorie des graphes. Sommaire 1 Algorithmes de parcours d un graphe 2 Algorithmes de Plus Courts Chemins (PCC) 3 Algorithmes d arbres couvrants de poids …   Wikipédia en Français

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”