Chapitre 1 • Structures ordonnées Applications des treillis
38
On aurait tort de croire que la par tie entière (l’arrondi à la valeur inférieure) des
valeurs des variables consti tuant la solu tion opti male en ration nels donne l’opti mum
entier ; en effet :
E(x 1 ) 5 2, E(x 2 ) 5 4, d’où F 5 38 (cf le point N).
L’explo ra tion arbo res cente conduit d’abord au point Q, avec F 5 40, ensuite au
point P, avec F 5 41 et c’est l’opti mum entier. Toute autre solu tion, avec le deuxième
choix 2* ne peut que don ner F , 41 (ex. x 1 5 4, x 2 5 2, F 5 38) ; c’est pour quoi
cette solu tion n’est pas explo rée.
Avec la remise en cause du choix 1*, on abou ti rait au point R (F 5 36), mais on
ne s’y rend pas, puisque l’on s’arrête dès que l’on constate que F < 39 si X
1
2 5 0.
Voici l’arbo res cence illus trant cette recherche (et son par cours) :
Figure 1.21
38
On aurait tort de croire que la par tie entière (l’arrondi à la valeur inférieure) des
valeurs des variables consti tuant la solu tion opti male en ration nels donne l’opti mum
entier ; en effet :
E(x 1 ) 5 2, E(x 2 ) 5 4, d’où F 5 38 (cf le point N).
L’explo ra tion arbo res cente conduit d’abord au point Q, avec F 5 40, ensuite au
point P, avec F 5 41 et c’est l’opti mum entier. Toute autre solu tion, avec le deuxième
choix 2* ne peut que don ner F , 41 (ex. x 1 5 4, x 2 5 2, F 5 38) ; c’est pour quoi
cette solu tion n’est pas explo rée.
Avec la remise en cause du choix 1*, on abou ti rait au point R (F 5 36), mais on
ne s’y rend pas, puisque l’on s’arrête dès que l’on constate que F < 39 si X
1
2 5 0.
Voici l’arbo res cence illus trant cette recherche (et son par cours) :
Figure 1.21