228
Recherche opérationnelle
- une sortie , reliée par un arc de capacité 1 à chacun des sommets
(les
tâches, qui constituent l'ensemble ).
- des arcs reliant un sommet de à un sommet de si et seulement si le coût de
la matrice est nul pour la ligne et la colonne correspondantes. Ces arcs ont
une capacité infinie.
Nous allons poser l'équivalence suivante : sélectionner un zéro dans la matrice pour
construire un couplage consistera à porter un flot d'une unité sur l'arc correspondant
allant de
.
On voit alors que chercher le couplage optimal revient à chercher le flot maximal sur le
réseau de transport
En effet, le fait que les arcs joignant
à et à soient de capacité 1 nous assurent
que deux arcs adjacents parmi ceux joignant à ne peuvent avoir tous les deux un flot
d'une unité : si l'on sélectionne les zéros correspondant aux arcs de flot non nul, il s'agira
donc bien d'un couplage; par ailleurs le flot total entrant en
ou sortant en
représentera bien le nombre total de zéros sélectionnés : maximiser ce flot revient bien à
chercher le couplage de taille maximale.
Pour maximiser le flot, utilisons l'algorithme de Ford-Fulkerson.
Tout d'abord, pour faire passer un flot au jugé convenable dans le graphe , il suffit
d'ordonner les deux ensembles de sommets et d'essayer de saturer dans l'ordre les
sommets de
(c'est-à-dire faire passer un flot d'une unité entre
et le sommet
considéré) ; à chaque fois, on relie un sommet de au premier sommet possible non
saturé de (flot nul entre ce sommet et ).
On obtient pour l'exemple pris : (arcs de flot égal à 1 en traits épais)
x 0
A
B
C
D
E
F
a
b
c
d
e
f
z
-d
+x 0
+x 0
+x 0
+x 0
+B
+A
(+e)