Problème du flot de coût minimum

En théorie des graphes, le problème du flot de coût minimum est le problème algorithmique 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 exemple 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

Soit $G=(N,A)$ un réseau de transport, c'est-à-dire un graphe orienté sur lequel sont définies :

$d:N\rightarrow \mathbb {R} ^{+}$ 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 ;
$c:A\rightarrow \mathbb {R} ^{+}$ une fonction associant à chaque arc sa capacité, i.e. le flot maximum qu'il peut supporter ;
$w:A\rightarrow \mathbb {R}$ une fonction mesurant le coût (positif ou négatif) du transport par unité de flot pour un arc donné.

En supposant qu'il existe un flot réalisable, le problème du flot de coût minimal consiste, à trouver un flot $f:A\rightarrow \mathbb {R}$ minimisant le coût total : $\sum _{a\in A}w(a)f(a)$ sous les contraintes :

contrainte de capacité : $\forall a\in A,0\leq f(a)\leq c(a)$ . Autrement dit, le flot dans l'arc $a$ est majoré par la capacité $c(a)$ .
conservation du flot : $\forall n\in N,\sum _{a=(n,s)\in A}f(a)-\sum _{a=(s,n)\in A}f(a)=d(n)$ . Autrement dit, la demande en le nœud $n$ est égale à la différence entre le flot sortant et le flot entrant en $n$ .

Existence d'une solution

Il est possible de montrer qu'il existe un flot admissible si et seulement si[1], pour toute coupe du graphe $N=N_{1}\cup N_{2}$ :

\sum _{a\in (N_{1}\times N_{2})\cap A}c(a)\geq \sum _{n\in N_{1}}d(n)

Résolution

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

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

Problème de flot maximum

Résoudre le problème du flot maximum entre une source unique $s$ et un puits unique $p$ dans un graphe $G=(N,A)$ revient à résoudre l'instance du problème de flot de coût minimum dans le graphe $G'$ qui est le graphe $G$ dans lequel on ajoute un nouvel arc du puits $p$ vers la source $s$ , autrement dit $G'=(N,A\cup \{(p,s)\})$ où :

$\forall n\in N,d(n)=0$
il n'y a pas de contrainte de capacité sur le nouvel arc : $c((p,s))=+\infty$ ;
la nouvelle arête a un coût négatif $w((p,s))=-1$ et, $\forall a\in A,w(a)=0$ .

Puisque le coût entre $p$ et $s$ 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 $s\in N$ et $p\in N$ revient à résoudre l'instance du problème de flot de coût minimum où :

$s$ est l'unique source et $p$ l'unique puits : $d(s)=1$ , $d(p)=-1$ et $d(n)=0$ pour les autres nœuds ;
il n'y a pas de contrainte de capacité : $\forall a\in A,c(a)=+\infty$ ;
le coût unitaire est fixe : $\forall a\in A,w(a)=1$

Recherche du plus court chemin d'un nœud à tous les autres

Trouver le plus court chemin entre une source $s\in N$ et les autres nœuds revient à résoudre l'instance du problème de flot de coût minimum où :

$s$ est l'unique source ( $d(s)=|N|-1$ ) alimentant tous les autres nœuds ( $\forall n\in N,d(n)=-1{\text{ si }}n\neq s$ ) ;
il n'y a pas de contrainte de capacité : $\forall a\in A,c(a)=+\infty$ ;
le coût unitaire est fixe : $\forall a\in A,w(a)=1$ .

Notes et références

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

Bibliographie

(en) Dieter Jungnickel, Graphs, Networks and Algorithms, Springer, 2013, 4^e éd. (ISBN 978-3-642-32277-8, lire en ligne), chap. section 11.1
(en) Ravindra K. Ahuja, Thomas L. Magnanti et James B. Orlin, Network Flows : Theory, Algorithms, and Applications, Prentice-Hall, Inc., 1993, 846 p. (ISBN 0-13-617549-X)
(en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Minimum-cost flow problem » (voir la liste des auteurs).

Liens externes

Articles liés

Cet article est issu de wikipedia. Text licence: CC BY-SA 4.0, Des conditions supplémentaires peuvent s’appliquer aux fichiers multimédias.