Chapitre 4 • Appli ca tions des graphes à la recherche opé ra tion nelle
176
ExEr cicEs
I PRo gRAM MA TIoN DyNA MIquE
**4.1 Pro blème du sac à dos : réso lu tion par la pro gram ma tion
dyna mique
Un alpiniste choisit les aliments qu’il va emporter dans son sac-à-dos. Pour chacun
des aliments possibles, on connaît sa valeur nutritive c i et son poids a i
Nous consi dé rons le pro gramme linéaire en variables 0 2 1 sui vant :
L’alpiniste peut porter au plus b kilos. Il veut maximiser la valeur nutritive globale
des aliments emportés.
max z 5 a
n
i 51
c i x i
a
n
i 51
a i x i < b
x i H 50, 16, 1 < i < n; x i 5 1 si l’aliment i est emporté, = 0 sinon.
où les coefficients a i , c i , b sont entiers et posi tifs. L’objec tif de cet exer cice est de
mon trer com ment résoudre ce pro blème en uti li sant un prin cipe de pro gram ma tion
dyna mique. Le pro blème est décom posé en n phases de la façon sui vante :
à la phase k, 1 < k < n, on cal cule la valeur nutritive optimale du sac chargé à d
kilos en choisissant des aliments seulement parmi les k premiers aliments
z k (d) 5 maxb a
k
i 51
c i x i ` a
k
i 51
a i x i < d, x i H 50, 16 r
pour toutes les valeurs de d, 0 < d < b. On note z(b) la solu tion (valeur nutritive)
opti male du pro blème de sac- à-dos à résoudre, en considérant ici les n aliments.
1. Mon trer que z(b) 5 z n (b).
Notre objec tif est alors de cal cu ler z n (b) à par tir des valeurs de z n21 qui
seront elles mêmes cal cu lées à par tir de z n22 et ainsi de suite.
2. Mon trer que la récur rence est ini tia li sée par z 1 1 d 2 5 b
c 1 si a 1 < d
0 si a 1 . d
(ici k = 1 : on ne considère que le premier aliment)
3. Sup po sons qu’à la phase k, pour la valeur d, x k 5 1 soit dans une solu
tion opti male. Mon trer que d 2 a k > 0. En déduire que dans ce cas que :
z k 1 d 2 5c k 1 z k21 1 d 2 a k 2 .
µ
176
ExEr cicEs
I PRo gRAM MA TIoN DyNA MIquE
**4.1 Pro blème du sac à dos : réso lu tion par la pro gram ma tion
dyna mique
Un alpiniste choisit les aliments qu’il va emporter dans son sac-à-dos. Pour chacun
des aliments possibles, on connaît sa valeur nutritive c i et son poids a i
Nous consi dé rons le pro gramme linéaire en variables 0 2 1 sui vant :
L’alpiniste peut porter au plus b kilos. Il veut maximiser la valeur nutritive globale
des aliments emportés.
max z 5 a
n
i 51
c i x i
a
n
i 51
a i x i < b
x i H 50, 16, 1 < i < n; x i 5 1 si l’aliment i est emporté, = 0 sinon.
où les coefficients a i , c i , b sont entiers et posi tifs. L’objec tif de cet exer cice est de
mon trer com ment résoudre ce pro blème en uti li sant un prin cipe de pro gram ma tion
dyna mique. Le pro blème est décom posé en n phases de la façon sui vante :
à la phase k, 1 < k < n, on cal cule la valeur nutritive optimale du sac chargé à d
kilos en choisissant des aliments seulement parmi les k premiers aliments
z k (d) 5 maxb a
k
i 51
c i x i ` a
k
i 51
a i x i < d, x i H 50, 16 r
pour toutes les valeurs de d, 0 < d < b. On note z(b) la solu tion (valeur nutritive)
opti male du pro blème de sac- à-dos à résoudre, en considérant ici les n aliments.
1. Mon trer que z(b) 5 z n (b).
Notre objec tif est alors de cal cu ler z n (b) à par tir des valeurs de z n21 qui
seront elles mêmes cal cu lées à par tir de z n22 et ainsi de suite.
2. Mon trer que la récur rence est ini tia li sée par z 1 1 d 2 5 b
c 1 si a 1 < d
0 si a 1 . d
(ici k = 1 : on ne considère que le premier aliment)
3. Sup po sons qu’à la phase k, pour la valeur d, x k 5 1 soit dans une solu
tion opti male. Mon trer que d 2 a k > 0. En déduire que dans ce cas que :
z k 1 d 2 5c k 1 z k21 1 d 2 a k 2 .
µ