Solu tions des exer cices du cha pitre 4
457
© Dunod – Toute reproduction non autorisée est un délit.
Solu tionS deS exer ciceS du cha pitre 4
4.1 1) Chaque phase k fait inter ve nir le sous- ensemble de variables x 1 , c , x k , la phase n fait
donc inter ve nir l’ensemble des variables du pro blème. Les valeurs z k (d ) cor res pondent aux
pro blèmes pour les quels le second membre de l’inéga lité a pour valeur d : ainsi pour d = b et
k = n, nous retrou vons le pro blème ini tial, donc z(b) = z k (b).
2) Les pro blèmes de la phase k = 1 sont de la forme : z 1 (d ) = max c 1 x 1 avec a 1 x 1 < d où c 1 est
posi tif et où d est un paramètre entier variant de 0 à b. Lorsque a 1 . d, la seule valeur pos sible de
la variable x 1 est x 1 = 0 et alors z 1 (d ) = 0 ; inver se ment, lorsque a 1 < d, les deux valeurs 0 ou 1 sont
pos sibles pour x 1 , donc c 1 x 1 est maximal lorsque x 1 = 1 et a pour valeur z 1 (d ) = c 1 .
3) À la phase k, si x k = 1, on a a
k
i51
a i x i 5 a
k 2 1
i51
a i x i 1 a k < d. Les coef fi cients a 1 ainsi que les
variables x i étant posi tifs, on a bien a k < d. Nous avonc donc d’une part a
k 2 1
i51
a i x i < d 2 a k , et
d’autre part max a
k
i51
c i x i 5 max a a
k 2 1
i51
c i x i b 1 c k . La valeur de x k étant fixée, les variables sont
x 1 , c , x k – 1 , ce qui cor res pond à résoudre les pro blèmes (paramétrés par d ) :
max a
k 2 1
i51
c i x i 5 z k 2 1 (d 2 a k ) ;
ainsi nous avons bien : z k (d) 5 z k 2 1 (d 2 a k ) 1 c k .
4) Durant la phase k, si x k = 0, on a : a
k
i51
a i x i 5 a
k 2 1
i51
a i x i < d et d’autre part :
max a
k
i51
c i x i 5 max a
k 2 1
i51
c i x i .
Les variables étant x 1 , c , x k – 1 , les pro blèmes (paramétrés par d) à résoudre sont :
max a
k 2 1
i51
c i x i 5 z k 2 1 (d) et nous obte nons z k (d) = z k – 1 (d) .
5) Lorsque a k . d, néces sai re ment x k = 0 et, ainsi que nous venons de le voir dans la ques tion
pré cé dente, z k (d ) = z k–1 (d ) ; si a k < d, x k peut a priori prendre l’une des deux valeurs 0 ou 1 ;
si x k = 0, alors comme nous venons de le voir, z k (d ) = z k–1 (d ) ; dans le cas contraire, lorsque
x k = 1, nous avons vu que : z k (d) 5 c k 1 z k 2 1 (d 2 a k ) ; en com pa rant ces deux pos si bi li tés, il
vient : z k (d) 5 max (z k 2 1 (d), c k 1 z k 2 1 (d 2 a k )).
6) Nous devons déter mi ner z 4 (7).
Com men çons par effec tuer la phase k = 1, c’est- à-dire cal cu ler z 1 (0), z 1 (1), c , z 1 (7) ; a 1 = 2,
nous obte nons alors z 1 (0) = z 1 (1) = 0 avec x 1 = 0 et z 1 (2), c , z 1 (7) = 16 avec x 1 = 1.
Effec tuons la phase k = 2 : puisque a 2 = 3, nous obte nons z 2 (0) = z 1 (0) = 0, z 2 (1) = z 1 (1) = 0,
et z 2 (2) = z 1 (2) = 16 avec x 2 = 0 ; cal cu lons z 2 (3), nous avons :
457
© Dunod – Toute reproduction non autorisée est un délit.
Solu tionS deS exer ciceS du cha pitre 4
4.1 1) Chaque phase k fait inter ve nir le sous- ensemble de variables x 1 , c , x k , la phase n fait
donc inter ve nir l’ensemble des variables du pro blème. Les valeurs z k (d ) cor res pondent aux
pro blèmes pour les quels le second membre de l’inéga lité a pour valeur d : ainsi pour d = b et
k = n, nous retrou vons le pro blème ini tial, donc z(b) = z k (b).
2) Les pro blèmes de la phase k = 1 sont de la forme : z 1 (d ) = max c 1 x 1 avec a 1 x 1 < d où c 1 est
posi tif et où d est un paramètre entier variant de 0 à b. Lorsque a 1 . d, la seule valeur pos sible de
la variable x 1 est x 1 = 0 et alors z 1 (d ) = 0 ; inver se ment, lorsque a 1 < d, les deux valeurs 0 ou 1 sont
pos sibles pour x 1 , donc c 1 x 1 est maximal lorsque x 1 = 1 et a pour valeur z 1 (d ) = c 1 .
3) À la phase k, si x k = 1, on a a
k
i51
a i x i 5 a
k 2 1
i51
a i x i 1 a k < d. Les coef fi cients a 1 ainsi que les
variables x i étant posi tifs, on a bien a k < d. Nous avonc donc d’une part a
k 2 1
i51
a i x i < d 2 a k , et
d’autre part max a
k
i51
c i x i 5 max a a
k 2 1
i51
c i x i b 1 c k . La valeur de x k étant fixée, les variables sont
x 1 , c , x k – 1 , ce qui cor res pond à résoudre les pro blèmes (paramétrés par d ) :
max a
k 2 1
i51
c i x i 5 z k 2 1 (d 2 a k ) ;
ainsi nous avons bien : z k (d) 5 z k 2 1 (d 2 a k ) 1 c k .
4) Durant la phase k, si x k = 0, on a : a
k
i51
a i x i 5 a
k 2 1
i51
a i x i < d et d’autre part :
max a
k
i51
c i x i 5 max a
k 2 1
i51
c i x i .
Les variables étant x 1 , c , x k – 1 , les pro blèmes (paramétrés par d) à résoudre sont :
max a
k 2 1
i51
c i x i 5 z k 2 1 (d) et nous obte nons z k (d) = z k – 1 (d) .
5) Lorsque a k . d, néces sai re ment x k = 0 et, ainsi que nous venons de le voir dans la ques tion
pré cé dente, z k (d ) = z k–1 (d ) ; si a k < d, x k peut a priori prendre l’une des deux valeurs 0 ou 1 ;
si x k = 0, alors comme nous venons de le voir, z k (d ) = z k–1 (d ) ; dans le cas contraire, lorsque
x k = 1, nous avons vu que : z k (d) 5 c k 1 z k 2 1 (d 2 a k ) ; en com pa rant ces deux pos si bi li tés, il
vient : z k (d) 5 max (z k 2 1 (d), c k 1 z k 2 1 (d 2 a k )).
6) Nous devons déter mi ner z 4 (7).
Com men çons par effec tuer la phase k = 1, c’est- à-dire cal cu ler z 1 (0), z 1 (1), c , z 1 (7) ; a 1 = 2,
nous obte nons alors z 1 (0) = z 1 (1) = 0 avec x 1 = 0 et z 1 (2), c , z 1 (7) = 16 avec x 1 = 1.
Effec tuons la phase k = 2 : puisque a 2 = 3, nous obte nons z 2 (0) = z 1 (0) = 0, z 2 (1) = z 1 (1) = 0,
et z 2 (2) = z 1 (2) = 16 avec x 2 = 0 ; cal cu lons z 2 (3), nous avons :