Solutions
458
z 2 (3) = max (z 1 (3), 19 + z 1 (3 – 3 = 0)) = max(16, 19) = 19, ce maxi mum étant obtenu pour
x 2 = 1 ; de la même manière, nous obte nons :
z 2 (4) = max (z 1 (4), 19 + z 1 (1)) = max(16, 19) = 19, avec x 2 = 1 ;
z 2 (5) = max (z 1 (5), 19 + z 1 (2)) = max(16, 19 + 16) = 35, ce maxi mum étant obtenu avec
x 1 = x 2 = 1 ;
de même nous obte nons :
z 2 (6) = max (z 1 (6), 19 + z 1 (3)) = max(16, 35) = 35 et
z 2 (7) = max (z 1 (7), 19 + z 1 (4)) = max(16, 35) = 35, obtenu avec x 1 = x 2 = 1.
Effec tuons main te nant la phase k = 3 :
Puisque a 3 = 4, nous obte nons z 3 (0) = z 2 (0) = 0 , z 3 (1) = z 2 (1) = 0 , z 3 (2) = z 2 (2) = 16 , et
z 3 (3) = z 2 (3) = 19 avec x 3 = 0 ; nous avons :
z 3 (4) = max (z 2 (4), 23 + z 2 (0)) = max(19, 23) = 23, obtenu avec x 3 = 1 ;
z 3 (5) = max (z 2 (5), 23 + z 2 (1)) = max(35, 23) = 35, obtenu avec x 3 = 0 ;
z 3 (6) = max (z 2 (6), 23 + z 2 (2)) = max(35, 23 + 16) = 39, obtenu pour x 3 = 1 ;
z 3 (7) = max (z 2 (7), 23 + z 2 (3)) = max(35, 23 + 19) = 42, obtenu pour x 3 = 1 ;
Pour finir, la phase k = 4 consis tera uni que ment au cal cul de z 4 (7) = z(7), la solu tion du pro -
blème w nous obte nons, puisque a 4 5 5 < 7 :
z 4 (7) = max (z 3 (7), 28 + z 3 (2)) = max(42, 28 + 16) = 44,
et cette solu tion est obte nue avec x 4 = 1, x 3 = 0 venant du cal cul de z 3 (2) = 16, x 2 = 0 car pour
le cal cul de z 2 (2) nous avions z 2 (2) = z 1 (2), et x 1 = 1 venant du cal cul z 1 (2) = 16.
Le tableau et le graphe de décisions sui vants résument l’ensemble des cal culs (on y ajoute
les z 4 (d) pour d < 7) :
d 0
k 1
z k (d)
k 2
k 3
k 4
0
0
0
0
0
0
16
16
16
16
16
19
19
19
23
35
35
35
35
39
42
44
39
35
23
19
16
0
0
16
16
16
d 1
d 2
d 3
d 4
d 5
d 6
d 7
En résumé, l’optimum est : x 1 = 1, x 2 = x 3 = 0, x 4 = 1 et z
* = 44. Le lecteur se convaincra
aisément que résoudre ce problème est équivalent à chercher un chemin de valeur maximale
du sommet α au sommet ω dans le « graphe de décisions » ci-dessus (il est formé des arcs
figurés par un trait double). L’alpiniste emportera donc seulement les aliments 1 et 4.
458
z 2 (3) = max (z 1 (3), 19 + z 1 (3 – 3 = 0)) = max(16, 19) = 19, ce maxi mum étant obtenu pour
x 2 = 1 ; de la même manière, nous obte nons :
z 2 (4) = max (z 1 (4), 19 + z 1 (1)) = max(16, 19) = 19, avec x 2 = 1 ;
z 2 (5) = max (z 1 (5), 19 + z 1 (2)) = max(16, 19 + 16) = 35, ce maxi mum étant obtenu avec
x 1 = x 2 = 1 ;
de même nous obte nons :
z 2 (6) = max (z 1 (6), 19 + z 1 (3)) = max(16, 35) = 35 et
z 2 (7) = max (z 1 (7), 19 + z 1 (4)) = max(16, 35) = 35, obtenu avec x 1 = x 2 = 1.
Effec tuons main te nant la phase k = 3 :
Puisque a 3 = 4, nous obte nons z 3 (0) = z 2 (0) = 0 , z 3 (1) = z 2 (1) = 0 , z 3 (2) = z 2 (2) = 16 , et
z 3 (3) = z 2 (3) = 19 avec x 3 = 0 ; nous avons :
z 3 (4) = max (z 2 (4), 23 + z 2 (0)) = max(19, 23) = 23, obtenu avec x 3 = 1 ;
z 3 (5) = max (z 2 (5), 23 + z 2 (1)) = max(35, 23) = 35, obtenu avec x 3 = 0 ;
z 3 (6) = max (z 2 (6), 23 + z 2 (2)) = max(35, 23 + 16) = 39, obtenu pour x 3 = 1 ;
z 3 (7) = max (z 2 (7), 23 + z 2 (3)) = max(35, 23 + 19) = 42, obtenu pour x 3 = 1 ;
Pour finir, la phase k = 4 consis tera uni que ment au cal cul de z 4 (7) = z(7), la solu tion du pro -
blème w nous obte nons, puisque a 4 5 5 < 7 :
z 4 (7) = max (z 3 (7), 28 + z 3 (2)) = max(42, 28 + 16) = 44,
et cette solu tion est obte nue avec x 4 = 1, x 3 = 0 venant du cal cul de z 3 (2) = 16, x 2 = 0 car pour
le cal cul de z 2 (2) nous avions z 2 (2) = z 1 (2), et x 1 = 1 venant du cal cul z 1 (2) = 16.
Le tableau et le graphe de décisions sui vants résument l’ensemble des cal culs (on y ajoute
les z 4 (d) pour d < 7) :
d 0
k 1
z k (d)
k 2
k 3
k 4
0
0
0
0
0
0
16
16
16
16
16
19
19
19
23
35
35
35
35
39
42
44
39
35
23
19
16
0
0
16
16
16
d 1
d 2
d 3
d 4
d 5
d 6
d 7
En résumé, l’optimum est : x 1 = 1, x 2 = x 3 = 0, x 4 = 1 et z
* = 44. Le lecteur se convaincra
aisément que résoudre ce problème est équivalent à chercher un chemin de valeur maximale
du sommet α au sommet ω dans le « graphe de décisions » ci-dessus (il est formé des arcs
figurés par un trait double). L’alpiniste emportera donc seulement les aliments 1 et 4.