230
Recherche opérationnelle
- les zéros n'appartenant pas au couplage sont barrés.
Pour la matrice , on obtient :
Phase 3 - Amélioration du couplage
Analysons le graphe ci-dessus. Nous pouvons, comme nous l'avons fait pour le
programme de transport, décomposer , ensemble des moyens, et ensemble des tâches
en deux sous-ensembles.
: ensemble des sommets marqués de
: ensemble des sommets non marqués de
: ensemble des sommets marqués de
: ensemble des sommets non marqués de
Cette décomposition donne ici :
À propos de cette décomposition, deux résultats très simples vont nous servir pour la
suite du raisonnement :
1) il n'existe pas d'arc de flux = 1 entre
.
2) il n'existe pas d'arc entre
.
B
D
E
F
d
X 1
Y 1
A
C
a
b
c
e
f
X 2
Y 2
a
b
c
d
e
f
A
4
1
9
0
0
10
B
14
4
8
0
7
4
C
0
0
0
1
3
0
D
6
5
7
0
7
5
E
5
4
10
0
2
4
F
2
7
13
0
4
1