Chapitre 4 • Appli ca tions des graphes à la recherche opé ra tion nelle
174
Remar quons qu’à l’opti mum, le sac-à-dos n’est pas néces sai re ment plein comme
c’est le cas ici. Ceci résulte du caractère non sécable des objets.
Pro gram ma tion linéaire en nombres entiers
L’exemple que nous allons trai ter est celui pré senté dans le cha pitre consa cré aux
appli ca tions de l’algèbre de Boole au cha pitre 1.
Consi dé rons le pro gramme linéaire (PL) en nombres entiers sui vant :
max z 5 3x 1 1 8x 2
x 1 1 4x 2 < 20
x 1 1 2x 2 < 11
3x 1 1 2x 2 < 22
x 1 ,
x 2 H N
À cha cun des som mets de l’arbo res cence est asso cié un pro gramme linéaire
(1)
obtenu en ajou tant une contrainte sup plé men taire au pro blème-père. L’éva lua tion
cal cu lée est la valeur opti male du pro gramme linéaire continu cor res pon dant (voir
le cha pitre 8 pour la réso lu tion de pro gramme linéaire continu). L’arrêt de l’explo ra -
tion se fait lorsque la solu tion du pro gramme linéaire continu se trouve être entière
ou bien s’il n’admet pas de solu tion. Dans le cas contraire, l’ensemble des solu tions
asso cié au som met consi déré est séparé en deux de la manière sui vante : si x i est une
variable de valeur ν non entière dans la solu tion conti nue, le pre mier sous- ensemble
de solu tions est obtenu en ajou tant la contrainte x i < :v; et le second sous- ensemble
est obtenu en ajou tant la contrainte x i >
La figure 4.51 repré sente l’arbo res cence que nous allons obte nir au long de la
réso lu tion de cet exemple que le lecteur pourra vérifier en résolvant graphiquement
le PL associé à chacun des sommets (ces PL n’ayant que deux variables).
Figure 4.51 Arbo res cence pour la réso lu tion du pro gramme linéaire en nombres entiers.
1. au besoin se reporter au chapitre 8
e
OPTIMUM
(1)
174
Remar quons qu’à l’opti mum, le sac-à-dos n’est pas néces sai re ment plein comme
c’est le cas ici. Ceci résulte du caractère non sécable des objets.
Pro gram ma tion linéaire en nombres entiers
L’exemple que nous allons trai ter est celui pré senté dans le cha pitre consa cré aux
appli ca tions de l’algèbre de Boole au cha pitre 1.
Consi dé rons le pro gramme linéaire (PL) en nombres entiers sui vant :
max z 5 3x 1 1 8x 2
x 1 1 4x 2 < 20
x 1 1 2x 2 < 11
3x 1 1 2x 2 < 22
x 1 ,
x 2 H N
À cha cun des som mets de l’arbo res cence est asso cié un pro gramme linéaire
(1)
obtenu en ajou tant une contrainte sup plé men taire au pro blème-père. L’éva lua tion
cal cu lée est la valeur opti male du pro gramme linéaire continu cor res pon dant (voir
le cha pitre 8 pour la réso lu tion de pro gramme linéaire continu). L’arrêt de l’explo ra -
tion se fait lorsque la solu tion du pro gramme linéaire continu se trouve être entière
ou bien s’il n’admet pas de solu tion. Dans le cas contraire, l’ensemble des solu tions
asso cié au som met consi déré est séparé en deux de la manière sui vante : si x i est une
variable de valeur ν non entière dans la solu tion conti nue, le pre mier sous- ensemble
de solu tions est obtenu en ajou tant la contrainte x i < :v; et le second sous- ensemble
est obtenu en ajou tant la contrainte x i >
La figure 4.51 repré sente l’arbo res cence que nous allons obte nir au long de la
réso lu tion de cet exemple que le lecteur pourra vérifier en résolvant graphiquement
le PL associé à chacun des sommets (ces PL n’ayant que deux variables).
Figure 4.51 Arbo res cence pour la réso lu tion du pro gramme linéaire en nombres entiers.
1. au besoin se reporter au chapitre 8
e
OPTIMUM
(1)