Solu tions des exer cices du cha pitre 4
473
© Dunod – Toute reproduction non autorisée est un délit.
L’algo rithme hon grois per met de mar quer les lignes Ε et F, puis la colonne a, ensuite
la ligne A, puis la colonne d et enfin, la ligne C (cf. Tab. 3). Après avoir rayé les lignes non
marquées Β et D, ainsi que les colonnes marquées a et d, le plus petit élé ment du tableau res -
tant est 7 ; on le sous trait des élé ments non rayés et on l’ajoute aux élé ments rayés 2 fois (Tab.
4). L’affec ta tion, telle qu’elle est réa li sée sur le tableau 4 consti tue un cou plage maximal,
comme on le vérifie sur le graphe associé ou tableau 4 :
Le couplage ne portant que sur cinq
lettres, on applique donc, une nou velle fois,
l’algo rithme hon grois.
L’élé ment non rayé plus petit est main te nant 6.
On obtient sans dif fi culté le tableau 5 ci-dessous :
Ce tableau per met d’obte nir une affec ta tion d’un zéro par ligne et par colonne. Elle donne
donc la solu tion opti male qui, ici, est unique.
L’affectation optimale est : A S c ; B S f ; C S d ; D S e ; E S a ; F S b
En reve nant à la matrice de l’énoncé, on voit qu’elle a pour valeur :
V * 5 27 1 13 1 02 1 16 1 15 1 44 5 117.
Remarque 1.
En affec tant par ordre crois sant des coûts
(« méthode gourmande »), on obtien drait une
solution de coût : V = 172.
En employant une méthode de regret une
solution de coût : V = 154 ;
On constate la supé riorité de l’algo rithme
hon grois, le coût de la solution optimal
n’étant que : V * 5 117.
Remarque 2.
Mon trons sur un exemple 4 × 4 la néces sité
de véri fier, avant appli ca tion de l’algo rithme
hon grois, que l’on a un cou plage maximal.
La matrice ci-dessous contient deux zéros par ligne, sauf sur la ligne C où elle en pos -
sède 3, et au moins un zéro par colonne.
A
B
C
D
E
F
0
0
0
53
66
0
7
94
45
0
7
37
44
44
57
61
31
8
0
6
3
27
19
63
52 25
37
54
61
19
26
0
0
0
0
0
a
b
c
d
e
f
tableau 4
�0
�a
�A
�d
�
0
E
S
�E
a
d
f
e
b
c
F
A
C
B
D
Graphe associé au tableau 4
A
B
C
D
E
F
0
0
0
47
66
0
1
100
45
0
13
31
44
38
57
55
25
2
0
0
3
33
19
69
46 25
37
48
55
19
20
0
0
0
0
6
a
b
c
d
e
f
tableau 5
473
© Dunod – Toute reproduction non autorisée est un délit.
L’algo rithme hon grois per met de mar quer les lignes Ε et F, puis la colonne a, ensuite
la ligne A, puis la colonne d et enfin, la ligne C (cf. Tab. 3). Après avoir rayé les lignes non
marquées Β et D, ainsi que les colonnes marquées a et d, le plus petit élé ment du tableau res -
tant est 7 ; on le sous trait des élé ments non rayés et on l’ajoute aux élé ments rayés 2 fois (Tab.
4). L’affec ta tion, telle qu’elle est réa li sée sur le tableau 4 consti tue un cou plage maximal,
comme on le vérifie sur le graphe associé ou tableau 4 :
Le couplage ne portant que sur cinq
lettres, on applique donc, une nou velle fois,
l’algo rithme hon grois.
L’élé ment non rayé plus petit est main te nant 6.
On obtient sans dif fi culté le tableau 5 ci-dessous :
Ce tableau per met d’obte nir une affec ta tion d’un zéro par ligne et par colonne. Elle donne
donc la solu tion opti male qui, ici, est unique.
L’affectation optimale est : A S c ; B S f ; C S d ; D S e ; E S a ; F S b
En reve nant à la matrice de l’énoncé, on voit qu’elle a pour valeur :
V * 5 27 1 13 1 02 1 16 1 15 1 44 5 117.
Remarque 1.
En affec tant par ordre crois sant des coûts
(« méthode gourmande »), on obtien drait une
solution de coût : V = 172.
En employant une méthode de regret une
solution de coût : V = 154 ;
On constate la supé riorité de l’algo rithme
hon grois, le coût de la solution optimal
n’étant que : V * 5 117.
Remarque 2.
Mon trons sur un exemple 4 × 4 la néces sité
de véri fier, avant appli ca tion de l’algo rithme
hon grois, que l’on a un cou plage maximal.
La matrice ci-dessous contient deux zéros par ligne, sauf sur la ligne C où elle en pos -
sède 3, et au moins un zéro par colonne.
A
B
C
D
E
F
0
0
0
53
66
0
7
94
45
0
7
37
44
44
57
61
31
8
0
6
3
27
19
63
52 25
37
54
61
19
26
0
0
0
0
0
a
b
c
d
e
f
tableau 4
�0
�a
�A
�d
�
0
E
S
�E
a
d
f
e
b
c
F
A
C
B
D
Graphe associé au tableau 4
A
B
C
D
E
F
0
0
0
47
66
0
1
100
45
0
13
31
44
38
57
55
25
2
0
0
3
33
19
69
46 25
37
48
55
19
20
0
0
0
0
6
a
b
c
d
e
f
tableau 5