Solu tions des exer cices du cha pitre 4
481
© Dunod – Toute reproduction non autorisée est un délit.
• 5
ème
itération
On sépare s 3 , qui est le sommet pendant de plus faible borne, à l’aide de l’arc (A,D), qui a
le plus fort regret parmi les « zéros » (r
3
AD 5 1, cf Tab. 3), en s 7 (refus de (A,D)), avec (b 7 =
b 3 + r
3
AD 5 4 1 1 5 5) , et en s 8 (on accepte (A,D)) ; après suppression de la ligne A et de la
colonne D et l’interdiction de l’arc parasite (D,B) obtenue en faisant c
8
DB 5 1`, on obtient
le tableau Tab. 8, qui se trouve être « réduit » ; par suite b 8 = b 3 = 4.
• 6
ème
itération
On sépare le sommet pendant de plus faible borne : s 8 , à l’aide de (D,C) de regret 1, en s 9
(refus de (D,C), avec b 9 = b 8 + r
3
DC 5 4 + 1 = 5) et en s 10 (après suppression de la ligne D et
de la colonne C dans le tableau Tab. 8, et de l’arc parasite (C,B) obtenu en posant c
10
CB 5 1`,
on obtient le tableau 10 qui se trouve être réduit ; par suite b 10 = b 8 = 4). On constate alors le
choix forcé de (C,E) et (E,B) ; on obtient le C.H. (B,A,D,C,E,B) de coût 4 : il est optimal car
tous les sommets de l’arborescence ont une borne supérieure à 4. On arrête-là la recherche
arborescente.
Le C. H. optimal est : (B, A, D, C, E, B)
de coût 4. L’optimum est unique ; tout
autre C.H. a un coût au moins égal à 5.
tab. 10
arb. 4
tab. 8
arb. 3