Chapitre 4 • Appli ca tions des graphes à la recherche opé ra tion nelle
164
Nous divi se rons les ité ra tions en blocs.
– Bloc A. On sous trait le plus petit élé ment de chaque
ran gée (d’abord dans les lignes, puis dans les colonnes) ;
la matrice résul tante com porte donc au moins un zéro
par ran gée : alors il se pour rait que l’opti mum ait un
coût nul. Cette opé ra tion (comme dans les pro blèmes
d’affec ta tion) conduit à un pro blème équi va lent.
– Bloc B. On cal cule une borne infé rieure de la valeur
du cir cuit de valeur mini male cherché. Elle est égale à
la somme des valeurs sous traites de la matrice, au bloc
A. En effet, si la matrice 3 per met tait de trou ver un cir
cuit hamiltonien uti li sant uni que ment des arcs de coût
0, la valeur de ce cir cuit coïn ci de rait avec la somme des
coûts retran chés à la matrice ini tiale.
Dans le cas présent, cette borne vaut :
B 5 1 1 1 2 1 1 1 1 1 4 1 32 1 1 3 1 3 1 22 5 20.
La racine R de l’arbo res cence rece vra la valuation B 5 20.
– Bloc C. On cal cule les coûts de
subs ti tution (ou regrets) des arcs
de coût nul (ou “zéros”) et l’on
retient le maxi mum d’entre eux
(ou l’un d’eux en cas d’éga lité).
Expli quons d’abord cette notion
de regret : soit, par exemple, le 0
qui value l’arc (B, D) dans la
matrice 3 ; il signi fie qu’on a inté
rêt à employer l’arc (B, D) qui, a
priori, est à recom man der, étant
de coût rési duel le plus petit sur la
ligne B. Com bien paierait- on en
plus si l’on déci dait de ne pas l’uti -
li ser ? Comme il fau drait tout de
même pas ser par les points B et D,
la meilleure solu tion consis te rait à atteindre D par (A, D) : coût 2 – ou encore (F, D) :
coût 2 – et à quit ter B par (B, A) : coût 2.
La somme de ces deux minima, soit 2 1 2 5 4, donne
le regret (mini mal) rela tif au zéro de la rela tion (B, D).
On déter mine ainsi le coût de subs ti tution (regret)
pour tout zéro de la matrice 3 (cf matrice 4). Puis, on
choi sit d’exa mi ner les consé quences qu’auraient la
sélec tion ou le rejet de l’arc cor res pon dant au plus fort
des regrets mini maux.
6 7 3 1 3 1
2
1
1
4
3
5 10 10 1 7
8 6 5 5 1
7 7 6 7 4
9 8 8 5 3
7 8 2 9 7
A B C D E F
B
A
C
D
E
F
1. Matrice des coûts : à
droite de chaque ligne
on a figuré son plus
petit coût.
5 6 2 0 2
4 9 9 0 6
7 5 4 4 0
3 3 2 3 0
6 5 5 2 0
3 3 2 0 0 0
5 6 0 7 5
A B C D E F
B
A
C
D
E
F
2. Après sous trac tion
du plus petit élé ment
de chaque ligne. Au
dessous de chaque
colonne on a figuré son
plus petit coût.
A B C D E F
2 4 2 0 2
1 6 9 0 6
4 2 2 4 0
0 0 0 3 0
3 2 3 2 0
2 4 0 7 5
B
A
C
D
E
F
3. Après sous trac tion
du plus petit élé ment
de chaque colonne de la
matrice 2.
Figure 4.47
164
Nous divi se rons les ité ra tions en blocs.
– Bloc A. On sous trait le plus petit élé ment de chaque
ran gée (d’abord dans les lignes, puis dans les colonnes) ;
la matrice résul tante com porte donc au moins un zéro
par ran gée : alors il se pour rait que l’opti mum ait un
coût nul. Cette opé ra tion (comme dans les pro blèmes
d’affec ta tion) conduit à un pro blème équi va lent.
– Bloc B. On cal cule une borne infé rieure de la valeur
du cir cuit de valeur mini male cherché. Elle est égale à
la somme des valeurs sous traites de la matrice, au bloc
A. En effet, si la matrice 3 per met tait de trou ver un cir
cuit hamiltonien uti li sant uni que ment des arcs de coût
0, la valeur de ce cir cuit coïn ci de rait avec la somme des
coûts retran chés à la matrice ini tiale.
Dans le cas présent, cette borne vaut :
B 5 1 1 1 2 1 1 1 1 1 4 1 32 1 1 3 1 3 1 22 5 20.
La racine R de l’arbo res cence rece vra la valuation B 5 20.
– Bloc C. On cal cule les coûts de
subs ti tution (ou regrets) des arcs
de coût nul (ou “zéros”) et l’on
retient le maxi mum d’entre eux
(ou l’un d’eux en cas d’éga lité).
Expli quons d’abord cette notion
de regret : soit, par exemple, le 0
qui value l’arc (B, D) dans la
matrice 3 ; il signi fie qu’on a inté
rêt à employer l’arc (B, D) qui, a
priori, est à recom man der, étant
de coût rési duel le plus petit sur la
ligne B. Com bien paierait- on en
plus si l’on déci dait de ne pas l’uti -
li ser ? Comme il fau drait tout de
même pas ser par les points B et D,
la meilleure solu tion consis te rait à atteindre D par (A, D) : coût 2 – ou encore (F, D) :
coût 2 – et à quit ter B par (B, A) : coût 2.
La somme de ces deux minima, soit 2 1 2 5 4, donne
le regret (mini mal) rela tif au zéro de la rela tion (B, D).
On déter mine ainsi le coût de subs ti tution (regret)
pour tout zéro de la matrice 3 (cf matrice 4). Puis, on
choi sit d’exa mi ner les consé quences qu’auraient la
sélec tion ou le rejet de l’arc cor res pon dant au plus fort
des regrets mini maux.
6 7 3 1 3 1
2
1
1
4
3
5 10 10 1 7
8 6 5 5 1
7 7 6 7 4
9 8 8 5 3
7 8 2 9 7
A B C D E F
B
A
C
D
E
F
1. Matrice des coûts : à
droite de chaque ligne
on a figuré son plus
petit coût.
5 6 2 0 2
4 9 9 0 6
7 5 4 4 0
3 3 2 3 0
6 5 5 2 0
3 3 2 0 0 0
5 6 0 7 5
A B C D E F
B
A
C
D
E
F
2. Après sous trac tion
du plus petit élé ment
de chaque ligne. Au
dessous de chaque
colonne on a figuré son
plus petit coût.
A B C D E F
2 4 2 0 2
1 6 9 0 6
4 2 2 4 0
0 0 0 3 0
3 2 3 2 0
2 4 0 7 5
B
A
C
D
E
F
3. Après sous trac tion
du plus petit élé ment
de chaque colonne de la
matrice 2.
Figure 4.47