234
Recherche opérationnelle
On retourne avec cette nouvelle matrice de coûts, équivalente aux premières, à la phase
2, pour trouver sur le nouveau graphe associé le couplage maximal.
Pour cela, on peut partir du couplage obtenu précédemment, et examiner si on peut
l'améliorer.
Il est évident que l'on peut remarquer ; après amélioration, on obtient :
On ne peut plus marquer
avec ce flot et le couplage est donc maximal : c'est le
couplage
. Il est de taille 4 et il conviendra d'essayer de
l'améliorer encore.
Pour cela, on transforme la matrice 4 suivant les opérations exposées ci-dessus, après
avoir encadré les zéros du couplage et barré les autres zéros.
x 0
A
B
C
D
E
F
a
b
c
d
e
f
z +f
x 0
A
B
C
D
E
F
a
b
c
d
e
f
z
x 0
+f
x 0
-d
+D