Problèmes de flots
211
La condition nécessaire et suffisante pour qu'un flot compatible existe est que pour
tout
, on ait
Par ailleurs, sur des graphes munis de ces contraintes de capacité, on peut également
résoudre le problème du flot maximal, c'est-à-dire
(le graphe étant muni d'un
arc de retour), avec
pour tout
L'algorithme devient
a) Trouver un flot compatible, grâce à l'algorithme précédent.
b) Marquer les sommets par le marquage suivant :
si est marqué et si
, on marque ,
si est marqué et si
alors on marque ,
si ne peut être marqué, le flot est maximal.
c) Si peut être marqué, on trouve un cycle sur lequel on peut améliorer le flot. On
retourne en b).
9.4. PROBLEME DU FLOT DE COUT MINIMAL
Sur un réseau de transport muni des contraintes précédentes (pour un flot , on doit
avoir
, on définit par ailleurs des coûts unitaires
de transport
par arc. Le problème est de trouver le flot tel que :
On voit qu'il s'agit là d'un problème plus général que les deux précédentes (le flot
maximal et le flot compatible) qui n'en sont que des sous-ensembles.
Il existe à présent plusieurs algorithmes permettant de traiter ce problème et utilisant
directement la théorie des graphes (ce problème est par ailleurs de toute évidence un
programme linéaire que l'on pourrait résoudre en tant que tel, ce qui ne fournirait pas
dans la plupart des cas la procédure la plus économique).
Nous allons, sans le détailler, donner l'algorithme le plus proche de ceux que nous
venons d'utiliser. Ce n'est pas nécessairement l'algorithme le plus performant. Par la
suite, nous détaillerons deux cas particuliers importants de ce problème : le programme
de transport et le programme d'affectation.
211
La condition nécessaire et suffisante pour qu'un flot compatible existe est que pour
tout
, on ait
Par ailleurs, sur des graphes munis de ces contraintes de capacité, on peut également
résoudre le problème du flot maximal, c'est-à-dire
(le graphe étant muni d'un
arc de retour), avec
pour tout
L'algorithme devient
a) Trouver un flot compatible, grâce à l'algorithme précédent.
b) Marquer les sommets par le marquage suivant :
si est marqué et si
, on marque ,
si est marqué et si
alors on marque ,
si ne peut être marqué, le flot est maximal.
c) Si peut être marqué, on trouve un cycle sur lequel on peut améliorer le flot. On
retourne en b).
9.4. PROBLEME DU FLOT DE COUT MINIMAL
Sur un réseau de transport muni des contraintes précédentes (pour un flot , on doit
avoir
, on définit par ailleurs des coûts unitaires
de transport
par arc. Le problème est de trouver le flot tel que :
On voit qu'il s'agit là d'un problème plus général que les deux précédentes (le flot
maximal et le flot compatible) qui n'en sont que des sous-ensembles.
Il existe à présent plusieurs algorithmes permettant de traiter ce problème et utilisant
directement la théorie des graphes (ce problème est par ailleurs de toute évidence un
programme linéaire que l'on pourrait résoudre en tant que tel, ce qui ne fournirait pas
dans la plupart des cas la procédure la plus économique).
Nous allons, sans le détailler, donner l'algorithme le plus proche de ceux que nous
venons d'utiliser. Ce n'est pas nécessairement l'algorithme le plus performant. Par la
suite, nous détaillerons deux cas particuliers importants de ce problème : le programme
de transport et le programme d'affectation.