Problèmes de flots
229
Ce flot est-il maximal ? Pour répondre, effectuons le marquage de Ford-Fulkerson. Ce
marquage aboutit à par la chaîne
. On peut donc améliorer le flot, en
modifiant les flots sur cette chaîne.
Le flot obtenu peut alors se représenter par la figure suivante :
Un nouveau marquage ne permet pas de marquer . On a donc obtenu le flot maximal et
le couplage optimal (ou plutôt un couplage optimal). Ce couplage, constitué de
est de taille égale à
: nous n'avons donc pas affecté tous les
moyens aux tâches et il sera nécessaire d'améliorer le couplage.
Auparavant, convenons de repérer le couplage obtenu dans la matrice des coûts (la
matrice 3) de la manière suivante :
- les zéros appartenant au couplage (correspondant aux arcs
saturés) sont
encadrés,
x 0
A
B
d
z
+1
+1
+1
-1
e
+1
x 0
A
B
C
D
E
F
a
b
c
d
e
f
z