4.10 Recherches arbo res centes
175
© Dunod – Toute reproduction non autorisée est un délit.
La racine S 0 de l’arbo res cence cor res pond au pro blème ini tial qui a pour solu tion
optimale conti nue :
x 1 5 2, x 2 5
9
2
, de coût z 5 42.
La solu tion opti male du pro gramme linéaire continu étant unique, toute autre solu -
tion en nombres entiers aura un coût stric te ment infé rieur à 42, l’éva lua tion (entière)
de S 0 est alors E(S 0 ) 5 41.
En ajou tant la contrainte x 2 > 5, nous obte nons le pro blème sui vant asso cié au
som met S 1 , suc ces seur de S 0 dans l’arborescence :
max z 5 3x 1 1 8x 2
x 1 1 4x 2 < 20
x 1 1 2x 2 < 11
3x 1 1 2x 2 < 22
x 2 > 5
x 1 ,
x 2 H N
La solu tion conti nue de ce pro blème donne x 1 5 0, x 2 5 5 de coût z 5 40. Cette
solu tion étant entière, l’explo ra tion du som met S 1 s’arrête. Une pre mière solu tion
réa li sable de coût 40 est obte nue.
S 2 , le second suc ces seur de la racine S 0 , est obtenu en ajou tant la contrainte x 2 < 4
au pro blème ini tial. Le pro gramme asso cié à S 2 est alors :
max z 5 3x 1 1 8x 2
x 1 1 4x 2 < 20
x 1 1 2x 2 < 11
3x 1 1 2x 2 < 22
x 2 < 4
x 1 ,
x 2 H N
La solu tion conti nue de ce pro blème donne x 1 5 3, x 2 5 4 de coût z 5 41. Cette
solu tion est entière, de coût égal à l’éva lua tion de S 0 , elle est donc opti male.
f
f