Recherche opérationnelle
Le flot maximal
- Présentation du cours
- Qu'est-ce que la recherche opérationnelle
- Modéliser un problème de décision
- Le programme linéaire et ses formes
- La résolution graphique
- Le simplexe, la méthode
- Le simplexe, les cas particuliers
- La dualité
- L'analyse de sensibilité
- Le problème de transport
- Le problème d'affectation
- Les graphes, vocabulaire et représentation
- Le plus court chemin
- Le flot maximal
- L'ordonnancement de projet
- La programmation en nombres entiers
- Gestion des stocks et files d'attente
Recherche opérationnelle
Chapitre 12 : Le flot maximal
Le problème
Les données
Un réseau de transport
Un graphe orienté, une source s, un puits t, et sur chaque arc une capacité c(i,j) \geq 0.
Un flot
Une fonction f(i,j) vérifiant deux conditions :
Capacité : 0 \leq f(i,j) \leq c(i,j) sur chaque arc.
Conservation : en tout sommet autre que s et t, ce qui entre est égal à ce qui sort.
La valeur du flot
C’est ce qui sort de s — ou, ce qui revient au même, ce qui entre en t.
Le problème : la rendre maximale.
L’exemple
Le même réseau, valué en capacités
| Arc | capacité | Arc | capacité | |
|---|---|---|---|---|
| A \to B | 10 | C \to E | 10 | |
| A \to C | \phantom{0}8 | E \to D | \phantom{0}6 | |
| B \to C | \phantom{0}2 | E \to F | \phantom{0}4 | |
| B \to D | \phantom{0}5 | D \to F | \phantom{0}7 |
Ford et Fulkerson
L’algorithme
Les chaînes améliorantes
Tant qu’il existe un chemin de s à t dont tous les arcs ont de la capacité résiduelle, y pousser le maximum possible.
Le maximum est le minimum des capacités résiduelles le long du chemin.
Le graphe résiduel
Pousser \varphi unités sur l’arc (i,j) crée un arc retour (j,i) de capacité \varphi.
Cet arc retour permet d’annuler plus tard une décision qui s’avérerait mauvaise.
Pourquoi l’arc retour est indispensable
Sans lui, l’algorithme dépendrait de l’ordre dans lequel on choisit les chemins, et pourrait s’arrêter avant l’optimum.
L’arc retour rend l’algorithme correct quel que soit l’ordre.
Le déroulement sur l’exemple
Trois chaînes
| Chaîne | Goulot | Flot poussé |
|---|---|---|
| A \to B \to D \to F | B \to D | 5 |
| A \to C \to E \to F | E \to F | 4 |
| A \to C \to E \to D \to F | D \to F | 2 |
| 11 |
Pourquoi on s’arrête là
Le puits F n’est atteignable que par D \to F et E \to F.
D \to F transporte 5 + 2 = 7, sa capacité entière. E \to F transporte 4, sa capacité entière. Plus rien ne peut entrer en F.
Le théorème du flot maximal
L’énoncé
Une coupe
Une partition des sommets en deux ensembles S \ni s et T \ni t. Sa capacité est la somme des capacités des arcs allant de S vers T.
Ford-Fulkerson, 1956
\max_{\text{flots}} \; |f| \;=\; \min_{\text{coupes}} \; c(S,T)
La valeur du flot maximal est égale à la capacité de la coupe minimale.
Vérification
Prenons S = \{A, B, C, D, E\} et T = \{F\}. Les arcs qui traversent sont D \to F et E \to F :
c(S,T) = 7 + 4 = 11 = |f|
Ce que le théorème signifie
Un certificat d’optimalité
Exhiber une coupe de capacité 11 prouve qu’aucun flot ne peut dépasser 11 — sans avoir à examiner les autres flots.
C’est la dualité du chapitre 6 sous une autre forme : le flot est le primal, la coupe est le dual, et leurs valeurs coïncident.
La lecture de gestion
La coupe minimale désigne les goulots d’étranglement. Ici, les deux liaisons qui aboutissent à F.
Investir ailleurs ne servirait à rien. Élargir un arc qui n’est pas dans la coupe minimale n’augmente pas d’une unité la capacité du réseau.
Que se passe-t-il si l’on élargit
Deux investissements comparés
Élargir A \to B de 10 à 20 : le flot reste 11. Zéro gain.
Élargir D \to F de 7 à 9 : la coupe passe à 13, mais d’autres arcs deviennent limitants — B \to D à 5 et E \to D à 6 bornent l’entrée de D.
La leçon
Lever un goulot en révèle un autre. La capacité d’un réseau ne s’améliore que par une suite d’investissements ciblés, chacun recalculé après le précédent.
Les variantes
Ce que le modèle sait aussi traiter
Trois extensions
Plusieurs sources ou puits : on ajoute une super-source reliée à toutes les sources par des arcs de capacité infinie.
Capacité sur un sommet : on le dédouble en deux sommets reliés par un arc de cette capacité.
Flot minimal imposé : borne inférieure sur un arc, traitée par un problème auxiliaire.
Trois domaines d’application
Réseaux électriques et hydrauliques, trafic routier, capacité d’un système d’information.
Et, plus inattendu : le couplage maximal dans un graphe biparti — donc le problème d’affectation du chapitre 9, qui se résout aussi comme un flot.
Ce qu’il faut retenir
Le résumé du chapitre
Six points
- Un flot respecte les capacités et conserve la matière en chaque sommet interne.
- Ford-Fulkerson pousse des unités le long de chaînes améliorantes.
- Les arcs retour rendent l’algorithme correct quel que soit l’ordre des chemins.
- Sur l’exemple : trois chaînes, flot maximal de \mathbf{11}.
- Flot maximal = coupe minimale : la coupe est un certificat d’optimalité.
- La coupe minimale désigne les goulots : investir ailleurs ne rapporte rien.
La suite
Le chapitre 13 applique le plus long chemin à un graphe de tâches, et en tire l’outil de gestion de projet le plus répandu au monde.
Ressources du chapitre
- Diapositives
- Polycopié du chapitre
- Exercices corrigés
- Application interactive
- — Vidéo
- QCM (bientôt)