Problème du flot de coût minimum

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

Le problème du flot de coût minimum est un problème algorithmique de théorie des graphes, qui consiste à trouver la manière la plus économe d'utiliser un réseau de transport tout en satisfaisant les contraintes de production et de demande des nœuds du réseau. Il permet de modéliser tout un ensemble de problèmes pratiques dans lesquels il s'agit de trouver une manière optimale d'acheminer une ressource (par ex. un fluide, de l'électricité) d'un ensemble de sources à un ensemble de puits.

Le problème du flot de coût minimum est fondamental dans la mesure où la plupart des autres problèmes de flots, comme le problème de flot maximum, peuvent en être vus comme des cas particuliers. De plus, il est possible de résoudre le problème dans certains cas de manière efficace en utilisant l'algorithme du simplexe pour les réseaux.

Définition du problème[modifier | modifier le code]

Soit un réseau de transport, c'est-à-dire un graphe orienté sur lequel sont définis :

  • une fonction prenant des valeurs positives pour les nœuds sources (i.e. produisant des ressources), négatives pour les nœuds puits (i.e. utilisant des ressources) et nulles pour les nœuds dits de transit ;
  • une fonction associant à chaque arête le flot maximum qu'elle peut supporter ;
  • une fonction mesurant le coût du transport par unité de flot pour une arrête donnée.

En supposant qu'il existe un flot réalisable, le problème du flot de coût minimal consiste, à trouver un flot minisant le cout total :

sous les contraintes :

  • conservation du flot :
  • contrainte de capacité :

Existence d'une solution[modifier | modifier le code]

Il est possible de montrer qu'il existe un flot admissible si et seulement si[1], pour toute coupe du graphe  :

.

Résolution[modifier | modifier le code]

Le problème peut être résolu par programmation linéaire, dans la mesure où la fonction à minimiser, et les différentes contraintes sont linéaires. Plusieurs autres algorithmes existent[2],[3], certains pouvant être considérés comme des généralisations de l'algorithme de Ford-Fulkerson[4], d'autres comme des généralisations de l'algorithme de poussage/réétiquetage[5], ou encore des variantes de l'algorithme du simplexe[6].

Problèmes liés[modifier | modifier le code]

En fixant certains paramètres, on obtient d'autres problèmes de cheminement.

Résoudre le problème du flot maximum entre une source unique et un puits unique dans un graphe revient à résoudre l'instance du problème de flot de coût minimum dans le graphe où :
  • il n'y a pas de contrainte de capacité :  ;
  • la nouvelle arrête a un coût négatif et, .
Puisque le coût entre et est négatif, la condition de minimisation revient à maximiser le flot.
  • Recherche du plus court chemin entre deux nœuds
Trouver le plus court chemin entre et revient à résoudre l'instance du problème de flot de coût minimum où :
  • est l'unique source et l'unique puits : , et pour les autres nœuds ;
  • il n'y a pas de contrainte de capacité :  ;
  • le coût unitaire est fixe : .
  • Recherche du plus court chemin d'un nœud à tous les autres
Trouver le plus court chemin entre une source et les autres nœuds revient à résoudre l'instance du problème de flot de coût minimum où :
  • est l'unique source () alimentant les tous les autres nœuds () ;
  • il n'y a pas de contrainte de capacité :  ;
  • le coût unitaire est fixe : .

Notes et références[modifier | modifier le code]

  1. Jungnickel 2013.
  2. Ahuja, Magnanti & Orlin 1993.
  3. (en) Morton Klein, « A primal method for minimal cost flows with applications to the assignment and transportation problems », Management Science, vol. 14,‎ , p. 205–220 (DOI 10.1287/mnsc.14.3.205)
  4. (en) Jack Edmonds et Richard M. Karp, « Theoretical improvements in algorithmic efficiency for network flow problems », Journal of the ACM, vol. 19,‎ , p. 248–264 (DOI 10.1145/321694.321699)
  5. (en) Andrew V. Goldberg et Robert E. Tarjan, « Finding minimum-cost circulations by successive approximation », Math. Oper. Res., vol. 15,‎ , p. 430–466 (DOI 10.1287/moor.15.3.430)
  6. (en) James B. Orlin, « A polynomial time primal network simplex algorithm for minimum cost flows », Mathematical Programming, vol. 78,‎ , p. 109–129 (DOI 10.1007/bf02614365)

Bibliographie[modifier | modifier le code]

Liens externes[modifier | modifier le code]

Articles liés[modifier | modifier le code]