Chapitre 4 • Appli ca tions des graphes à la recherche opé ra tion nelle
172
Dans la solu tion obte nue, les objets mis dans le sac à dos sont ceux pour les quels la
variable cor res pon dante x i vaut 1. Ceux pour les quels x i vaut 0 ne sont pas empor tés.
Sans perte de géné ra lité, dans tout ce qui suit, nous sup po se rons que a i < B pour
tout indice i et que :
a
n
i 51
a i . B (sinon on pourrait mettre les n objets dans le sac !).
Nous sup po se rons aussi que ces objets sont indi cés de sorte que :
c 1
a 1
>
c 2
a 2
> c >
c n
a n
.
et sont donc classés par utilité décroissante.
Pour illus trer l’effi ca cité des méthodes par sépa ra tion et éva lua tion, consi dé rons
le pro blème du sac à dos sui vant :
•
max z 5 15x 1 1 18x 2 1 4x 3 1 7x 4 1 2x 5 1 x 6
3x 1 1 4x 2 1 x 3 1 3x 4 1 x 5 1 x 6 < 5
x i H 50, 16, 1 < i < 6.
On vérifie que 15/3 . 18/4 . 4/1 . 7/3 . 2/1 . 1/1.
La figure 4.50 repré sente l’arbo res cence que nous allons obte nir au long de la
réso lu tion de cet exemple :
Figure 4.50 Arbo res cence obte nue pour la réso lu tion du pro blème de sac à dos.
Une borne supé rieure de la solu tion opti male, l’éva lua tion de la racine de l’arbo -
res cence, est obte nue en “relâ chant” les contraintes d’inté grité sur les variables, c’està-dire en rem pla çant les contraintes x i 5 0 ou x i 5 1 par : 0 < x i < 1. Dans le cas
spé ci fique du pro blème du sac à dos, la solu tion opti male du pro gramme linéaire cor
res pon dant est faci le ment obte nue sans même uti li ser les algo rithmes pré sen tés dans
le cha pitre 8. Pour notre exemple, nous obte nons la solu tion relâchée (continue) :
172
Dans la solu tion obte nue, les objets mis dans le sac à dos sont ceux pour les quels la
variable cor res pon dante x i vaut 1. Ceux pour les quels x i vaut 0 ne sont pas empor tés.
Sans perte de géné ra lité, dans tout ce qui suit, nous sup po se rons que a i < B pour
tout indice i et que :
a
n
i 51
a i . B (sinon on pourrait mettre les n objets dans le sac !).
Nous sup po se rons aussi que ces objets sont indi cés de sorte que :
c 1
a 1
>
c 2
a 2
> c >
c n
a n
.
et sont donc classés par utilité décroissante.
Pour illus trer l’effi ca cité des méthodes par sépa ra tion et éva lua tion, consi dé rons
le pro blème du sac à dos sui vant :
•
max z 5 15x 1 1 18x 2 1 4x 3 1 7x 4 1 2x 5 1 x 6
3x 1 1 4x 2 1 x 3 1 3x 4 1 x 5 1 x 6 < 5
x i H 50, 16, 1 < i < 6.
On vérifie que 15/3 . 18/4 . 4/1 . 7/3 . 2/1 . 1/1.
La figure 4.50 repré sente l’arbo res cence que nous allons obte nir au long de la
réso lu tion de cet exemple :
Figure 4.50 Arbo res cence obte nue pour la réso lu tion du pro blème de sac à dos.
Une borne supé rieure de la solu tion opti male, l’éva lua tion de la racine de l’arbo -
res cence, est obte nue en “relâ chant” les contraintes d’inté grité sur les variables, c’està-dire en rem pla çant les contraintes x i 5 0 ou x i 5 1 par : 0 < x i < 1. Dans le cas
spé ci fique du pro blème du sac à dos, la solu tion opti male du pro gramme linéaire cor
res pon dant est faci le ment obte nue sans même uti li ser les algo rithmes pré sen tés dans
le cha pitre 8. Pour notre exemple, nous obte nons la solu tion relâchée (continue) :