4.10 Recherches arbo res centes
173
© Dunod – Toute reproduction non autorisée est un délit.
x 1 5 1, x 2 5 1/2, x 3 5 x 4 5 x 5 5 x 6 5 0, de valeur z 5 24. L’éva lua tion de la racine
S 0 sera donc E(S 0 ) 5 24.
Cette solu tion conti nue obte nue n’étant pas entière (x 2 5 0,5), l’ensemble S 0 des
solu tions admis sibles est séparé en S 1 : l’ensemble des solu tions telles que x 2 5 1, et
S 2 : l’ensemble des solu tions telles que x 2 5 0. Le pro blème asso cié à S 1 est alors :
•
max z 5 15x 1 1 4x 3 1 7x 4 1 2x 5 1 x 6
3x 1 1 x 3 1 3x 4 1 x 5 1 x 6 < 1
x i H 50, 16, 1 < i < 6.
Celui asso cié à S 2 est :
•
max z 5 15x 1 1 4x 3 1 7x 4 1 2x 5 1 x 6
3x 1 1 x 3 1 3x 4 1 x 5 1 x 6 < 5
x i H 50, 16, 1 < i < 6.
Ces deux pro blèmes sont aussi des pro blèmes de sac à dos, nous pou vons leur
appli quer le même trai te ment que celui effec tué à S 0 . Nous obte nons, pour S 1 , la
solu tion opti male en variables conti nues :
x 1 5
1
3
, x 2 5 1, x 3 5 x 4 5 x 5 5 x 6 5 0, de valeur z 5 23,
et, pour S 2 , la solu tion en variables conti nues :
x 1 5 1, x 2 5 0, x 3 5 1, x 4 5
1
3
, x 5 5 x 6 5 0, de valeur z 5 21.
Pour ces deux pro blèmes les solu tions obte nues ne sont pas entières, les ensembles
cor res pon dant devront être à nou veau sépa rés.
En appli quant le prin cipe d’explo ra tion consis tant à exa mi ner en priorité
l’ensemble ayant la meilleure éva lua tion, S 1 est par titionné en S 3 , l’ensemble des
solu tions telles que x 1 5 1 et S 4 , l’ensemble des solu tions telles que x 1 5 0. Le pro -
blème asso cié à S 3 n’admet pas de solu tion, la contrainte de capa cité du sac à dos
étant vio lée ; l’explo ra tion de S 3 est ter mi née. Le pro blème asso cié à S 4 est :
•
max z 5 4x 3 1 7x 4 1 2x 5 1 x 6
x 3 1 3x 4 1 x 5 1 x 6 < 1
x 1 H 50, 16, 1 < i < 6
qui admet pour solu tion en variables conti nues (x 1 5 0, x 2 5 1,) x 3 5 1, x 4 5 x 5 5
x 6 5 0, de valeur z 5 22. Cette solu tion est entière, l’explo ra tion de S 4 se ter mine et
une solu tion réa li sable du pro blème ini tial est trou vée.
Nous reve nons alors au som met S 2 . Son éva lua tion E(S 2 ) 5 21 est infé rieure à la
valeur de la solu tion que nous venons de trouver, l’ensemble des solu tions conte nues
dans S 1 , qu’on sait être a priori moins inté res santes que celles conte nues dans S 4 ,
n’est donc pas exploré. Tous les som mets de l’arbo res cence ont alors été explo rés,
l’algo rithme s’arrête. La solu tion opti male (unique) est celle obte nue pour S 4 :
x 1 5 0, x 2 5 1, x 3 5 1, x 4 5 x 5 5 x 6 5 0 d’uti lité 22, de volume (maximal) 5.
173
© Dunod – Toute reproduction non autorisée est un délit.
x 1 5 1, x 2 5 1/2, x 3 5 x 4 5 x 5 5 x 6 5 0, de valeur z 5 24. L’éva lua tion de la racine
S 0 sera donc E(S 0 ) 5 24.
Cette solu tion conti nue obte nue n’étant pas entière (x 2 5 0,5), l’ensemble S 0 des
solu tions admis sibles est séparé en S 1 : l’ensemble des solu tions telles que x 2 5 1, et
S 2 : l’ensemble des solu tions telles que x 2 5 0. Le pro blème asso cié à S 1 est alors :
•
max z 5 15x 1 1 4x 3 1 7x 4 1 2x 5 1 x 6
3x 1 1 x 3 1 3x 4 1 x 5 1 x 6 < 1
x i H 50, 16, 1 < i < 6.
Celui asso cié à S 2 est :
•
max z 5 15x 1 1 4x 3 1 7x 4 1 2x 5 1 x 6
3x 1 1 x 3 1 3x 4 1 x 5 1 x 6 < 5
x i H 50, 16, 1 < i < 6.
Ces deux pro blèmes sont aussi des pro blèmes de sac à dos, nous pou vons leur
appli quer le même trai te ment que celui effec tué à S 0 . Nous obte nons, pour S 1 , la
solu tion opti male en variables conti nues :
x 1 5
1
3
, x 2 5 1, x 3 5 x 4 5 x 5 5 x 6 5 0, de valeur z 5 23,
et, pour S 2 , la solu tion en variables conti nues :
x 1 5 1, x 2 5 0, x 3 5 1, x 4 5
1
3
, x 5 5 x 6 5 0, de valeur z 5 21.
Pour ces deux pro blèmes les solu tions obte nues ne sont pas entières, les ensembles
cor res pon dant devront être à nou veau sépa rés.
En appli quant le prin cipe d’explo ra tion consis tant à exa mi ner en priorité
l’ensemble ayant la meilleure éva lua tion, S 1 est par titionné en S 3 , l’ensemble des
solu tions telles que x 1 5 1 et S 4 , l’ensemble des solu tions telles que x 1 5 0. Le pro -
blème asso cié à S 3 n’admet pas de solu tion, la contrainte de capa cité du sac à dos
étant vio lée ; l’explo ra tion de S 3 est ter mi née. Le pro blème asso cié à S 4 est :
•
max z 5 4x 3 1 7x 4 1 2x 5 1 x 6
x 3 1 3x 4 1 x 5 1 x 6 < 1
x 1 H 50, 16, 1 < i < 6
qui admet pour solu tion en variables conti nues (x 1 5 0, x 2 5 1,) x 3 5 1, x 4 5 x 5 5
x 6 5 0, de valeur z 5 22. Cette solu tion est entière, l’explo ra tion de S 4 se ter mine et
une solu tion réa li sable du pro blème ini tial est trou vée.
Nous reve nons alors au som met S 2 . Son éva lua tion E(S 2 ) 5 21 est infé rieure à la
valeur de la solu tion que nous venons de trouver, l’ensemble des solu tions conte nues
dans S 1 , qu’on sait être a priori moins inté res santes que celles conte nues dans S 4 ,
n’est donc pas exploré. Tous les som mets de l’arbo res cence ont alors été explo rés,
l’algo rithme s’arrête. La solu tion opti male (unique) est celle obte nue pour S 4 :
x 1 5 0, x 2 5 1, x 3 5 1, x 4 5 x 5 5 x 6 5 0 d’uti lité 22, de volume (maximal) 5.