Liens entre le problème du flot maximal et le problème de la coupe minimale
Attention :
Vous pouvez ignorer cette section si vous n'avez pas travaillé les notions de dualité dans le module sur la programmation linéaire.
Il n'y a que quelques remarques sur l'évidence de résultats liés à la dualité que vous ne comprendrez pas et que vous devrez admettre dans les sections suivantes.
Notions de dualité
Les notions de dualité et les théorèmes associés sont présentées dans le module sur la programmation linéaire.
Nous avons modélisé le problème de recherche du flot maximal en utilisant uniquement des équations ou des inéquations linéaires.
En mettant ces équations sous une forme dite canonique dans la littérature et en construisant le dual de ce problème, on obtient un autre problème linéaire dont on peut montrer qu'il modélise le problème de recherche de la coupe minimale.
Nous ne développerons pas cette démonstration ici et nous admettrons le résultat suivant.
Fondamental : Théorème de la dualité
Le problème de recherche de la coupe minimale est le problème dual du problème de la recherche du flot maximal.
Remarque :
En conséquence, lorsque l'on trouve la solution d'un des deux problèmes, on peut en déduire la solution de l'autre problème.
L'algorithme de Ford et Fulkerson que nous allons présenter ici trouve simultanément un flot maximal et une coupe minimale.
Remarque : Non unicité des solutions optimales
Selon les graphes considérés, il peut exister plusieurs solutions pour le problème de flot maximal et/ou plusieurs solutions pour le problème de coupe minimale.
A une solution du problème de flot maximal correspond une (ou plusieurs) solution(s) du problème de coupe minimiale qui vérifi(ent) le théorème d'optimalité primale-duale.
A une solution du problème de la coupe minimale correspond une (ou plusieurs) solution(s) du problème du flot maximal qui vérifi(ent) l théorème d'optimalité primale-duale.
L'algorithme de Ford et Fulkerson construit un couple de solutions flot maximal et coupe minimale qui vérifient le théorème de la dualité primale-duale.
