Chapitre 4 • Appli ca tions des graphes à la recherche opé ra tion nelle
166
C’est ce qu’on doit faire en pour sui vant le trai te ment de l’exemple.
– Bloc F.
1) À cette étape du pro blème, ins pec ter d’abord les bornes des som mets pen dants de
l’arbo res cence et choi sir le som met pendant de borne la plus petite.
Dans l’exemple, on a NON (B, D) : 24, et (B, D) : 20 ; on choi sit donc (B, D)
(cf. fig. 4.48).
2) Si ce som met cor res pond au type II : (X, Y), il faut reve nir au bloc C. Sinon, il
faut aller au bloc G.
Dans l’exemple, on ira au bloc C, puisque l’on a choisi un som met de type II : (B, D).
– Bloc G. Il s’agit du cas où l’on a choisi, au bloc F, d’après la valeur de sa borne,
un som met de type I, c’est àdire NON (X, Y).
Dans ce cas, inter dire l’arc (X, Y) en met tant un coût infini dans la case cor res
pon dante de la matrice des coûts réduits. Puis sous traire le plus petit élé ment de la
ligne X et de la colonne Y, ce qui cor res pond à l’emploi de la subs ti tution envi sa gée
au bloc C.
Enfin, reve nir au bloc C. (Ne pas modi fier la borne du som met de l’arbo res cence
asso cié : la somme des élé ments ainsi retran chés est égale au regret du zéro en case
(X, Y), soit p(X, Y), qui a déjà été rajouté à la borne : cf. bloc D.)
Suite de l’exemple (le lec teur consul tera en paral lèle l’arbo res cence p. 169).
Rap pe lons d’abord la situa tion à laquelle la
pro cé dure nous a conduit. Le pro blème se ramène
main te nant à l’étude de la matrice 5 bis (qui se
confond avec la matrice 5, dans l’exemple). Sur
l’arbo res cence, on a créé les deux som mets NON
(B, D) et (B, D) ; le pre mier a 24 pour valeur de la
borne infé rieure, le second, 20. On a choisi le som -
met (B, D), de type II ; il faut donc reve nir au bloc
C pour évaluer les regrets des zéros de la matrice.
1. Prendre en consi dé ra tion le regret concer nant (A, E), qui est un des regrets
maximaux dans la matrice 6.
À par tir du som met (B, D), de
borne 20, déve lop per la branche
de l’arbo res cence : NON (A, E), la
borne pas sant à 20 1 2 5 22.
Sup pri mer la ligne A et la
colonne E de la matrice 5 bis, inter -
dire l’arc (E, A) qui fer me rait un
cir cuit para site, d’où la matrice 7.
Cette matrice ne com por tant
plus un zéro sur cha cune de ses
ran gées, il faut sous traire 1 de la
ligne C et 2 de la ligne F.
Figure 4.48
Matrice 6.
Regrets des zéros de la
matrice 5
Matrice 7.
4 � 2 0
� 0 0 0
A B C E F
A B C F
A
C
C
D
D
E
E
F
F
3 2 3 �
1 2 2
0
1
2
�2
�1
2
1 6 � 6
2
166
C’est ce qu’on doit faire en pour sui vant le trai te ment de l’exemple.
– Bloc F.
1) À cette étape du pro blème, ins pec ter d’abord les bornes des som mets pen dants de
l’arbo res cence et choi sir le som met pendant de borne la plus petite.
Dans l’exemple, on a NON (B, D) : 24, et (B, D) : 20 ; on choi sit donc (B, D)
(cf. fig. 4.48).
2) Si ce som met cor res pond au type II : (X, Y), il faut reve nir au bloc C. Sinon, il
faut aller au bloc G.
Dans l’exemple, on ira au bloc C, puisque l’on a choisi un som met de type II : (B, D).
– Bloc G. Il s’agit du cas où l’on a choisi, au bloc F, d’après la valeur de sa borne,
un som met de type I, c’est àdire NON (X, Y).
Dans ce cas, inter dire l’arc (X, Y) en met tant un coût infini dans la case cor res
pon dante de la matrice des coûts réduits. Puis sous traire le plus petit élé ment de la
ligne X et de la colonne Y, ce qui cor res pond à l’emploi de la subs ti tution envi sa gée
au bloc C.
Enfin, reve nir au bloc C. (Ne pas modi fier la borne du som met de l’arbo res cence
asso cié : la somme des élé ments ainsi retran chés est égale au regret du zéro en case
(X, Y), soit p(X, Y), qui a déjà été rajouté à la borne : cf. bloc D.)
Suite de l’exemple (le lec teur consul tera en paral lèle l’arbo res cence p. 169).
Rap pe lons d’abord la situa tion à laquelle la
pro cé dure nous a conduit. Le pro blème se ramène
main te nant à l’étude de la matrice 5 bis (qui se
confond avec la matrice 5, dans l’exemple). Sur
l’arbo res cence, on a créé les deux som mets NON
(B, D) et (B, D) ; le pre mier a 24 pour valeur de la
borne infé rieure, le second, 20. On a choisi le som -
met (B, D), de type II ; il faut donc reve nir au bloc
C pour évaluer les regrets des zéros de la matrice.
1. Prendre en consi dé ra tion le regret concer nant (A, E), qui est un des regrets
maximaux dans la matrice 6.
À par tir du som met (B, D), de
borne 20, déve lop per la branche
de l’arbo res cence : NON (A, E), la
borne pas sant à 20 1 2 5 22.
Sup pri mer la ligne A et la
colonne E de la matrice 5 bis, inter -
dire l’arc (E, A) qui fer me rait un
cir cuit para site, d’où la matrice 7.
Cette matrice ne com por tant
plus un zéro sur cha cune de ses
ran gées, il faut sous traire 1 de la
ligne C et 2 de la ligne F.
Figure 4.48
Matrice 6.
Regrets des zéros de la
matrice 5
Matrice 7.
4 � 2 0
� 0 0 0
A B C E F
A B C F
A
C
C
D
D
E
E
F
F
3 2 3 �
1 2 2
0
1
2
�2
�1
2
1 6 � 6
2