Chapitre 1 • Structures ordonnées Applications des treillis
32
une stra té gie « gour mande » dans une explo ra tion « en pro fon deur d’abord » : ces
termes seront pré ci sés aux cha pitres 3 et 4.
Variables boo léennes (binaires)
Soit à maxi mi ser la fonc tion économique : F 5 3x 1 + 5x 2 – x 3 + 2x 4 , où x 1 , x 2 , x 3 , et
x 4 sont des variables ne pou vant prendre que les valeurs 0 ou 1, sachant qu’elles sont
sou mises aux inéga li tés sui vantes :
3x 1
1
4x 2
2
2x 3
1
x 4
<
5
2x 1
2
x 2
1
3x 3
2
x 4
< 4
4x 1
2
x 2
2
x 3
1
2x 4
<
5,
expri mant les contraintes du pro blème.
1. Nous allons trans for mer toute variable x i ayant un coef fi cient néga tif dans l’une
des inéga li tés ou dans la fonc tion éco no mique, de manière à n’avoir que des coef fi
cients posi tifs, comme suit : x i 1 x i 5 1, donc : 2 x i 5 x i 2 1.
Le pro blème s’écrit alors :
3MAX4F 5 3x 1 1 5x 2 1 x 3 1 2x 4 2 1
sous les contraintes :
3x 1
1
4x 2
1
2x 3
1
x 4
< 7
2x 1
1
x 2
1
3x 3
1
x 4
< 6
4x 1
1
x 2
1
x 3
1
2x 4
< 7
2. Ran geons les coef fi cients de la fonc tion économique dans l’ordre décrois sant de
leur contri bu tion à la valeur F :
F 5 5x 2 1 3x 1 1 2x 4 1 x 3 2 1,
car c’est dans cet ordre que nous tente rons, ulté rieu re ment, de don ner aux variables
la valeur 1.
3. Remar quons que F ne peut pas dépas ser la valeur 10. On peut ainsi écrire :
10 2 F 5 10 2 5x 2 2 3x 1 2 2x 4 2 x 3 1 1
5 5x 2 1 3x 1 1 2x 4 1 x 3 ,
d’où :
F 5 10 2 1 5x 2 1 3x 1 1 2x 4 1 x 3 2 .
4. Dres sons un tableau où les variables x 1 et x i figurent dans l’ordre : x 2 , x 2 ; x 1 , x 1 ;
x 4 , x 4 ; x 3 , x 3 et où nous ins cri vons les valeurs des coef fi cients des inéga li tés dans les
colonnes et sur les lignes appro priées. La valeur du second membre de chaque inéga
lité prend place dans la colonne 0, à droite du tableau.
Notons, sur la der nière ligne du tableau, immé dia te ment au dessous de la valeur du
second membre de la der nière inéga lité, la valeur que ne peut pas dépas ser la fonc tion
éco no mique F. Chaque fois que nous ne pour rons pas prendre x i 5 1 (i = 1, 2 ou 4),
32
une stra té gie « gour mande » dans une explo ra tion « en pro fon deur d’abord » : ces
termes seront pré ci sés aux cha pitres 3 et 4.
Variables boo léennes (binaires)
Soit à maxi mi ser la fonc tion économique : F 5 3x 1 + 5x 2 – x 3 + 2x 4 , où x 1 , x 2 , x 3 , et
x 4 sont des variables ne pou vant prendre que les valeurs 0 ou 1, sachant qu’elles sont
sou mises aux inéga li tés sui vantes :
3x 1
1
4x 2
2
2x 3
1
x 4
<
5
2x 1
2
x 2
1
3x 3
2
x 4
< 4
4x 1
2
x 2
2
x 3
1
2x 4
<
5,
expri mant les contraintes du pro blème.
1. Nous allons trans for mer toute variable x i ayant un coef fi cient néga tif dans l’une
des inéga li tés ou dans la fonc tion éco no mique, de manière à n’avoir que des coef fi
cients posi tifs, comme suit : x i 1 x i 5 1, donc : 2 x i 5 x i 2 1.
Le pro blème s’écrit alors :
3MAX4F 5 3x 1 1 5x 2 1 x 3 1 2x 4 2 1
sous les contraintes :
3x 1
1
4x 2
1
2x 3
1
x 4
< 7
2x 1
1
x 2
1
3x 3
1
x 4
< 6
4x 1
1
x 2
1
x 3
1
2x 4
< 7
2. Ran geons les coef fi cients de la fonc tion économique dans l’ordre décrois sant de
leur contri bu tion à la valeur F :
F 5 5x 2 1 3x 1 1 2x 4 1 x 3 2 1,
car c’est dans cet ordre que nous tente rons, ulté rieu re ment, de don ner aux variables
la valeur 1.
3. Remar quons que F ne peut pas dépas ser la valeur 10. On peut ainsi écrire :
10 2 F 5 10 2 5x 2 2 3x 1 2 2x 4 2 x 3 1 1
5 5x 2 1 3x 1 1 2x 4 1 x 3 ,
d’où :
F 5 10 2 1 5x 2 1 3x 1 1 2x 4 1 x 3 2 .
4. Dres sons un tableau où les variables x 1 et x i figurent dans l’ordre : x 2 , x 2 ; x 1 , x 1 ;
x 4 , x 4 ; x 3 , x 3 et où nous ins cri vons les valeurs des coef fi cients des inéga li tés dans les
colonnes et sur les lignes appro priées. La valeur du second membre de chaque inéga
lité prend place dans la colonne 0, à droite du tableau.
Notons, sur la der nière ligne du tableau, immé dia te ment au dessous de la valeur du
second membre de la der nière inéga lité, la valeur que ne peut pas dépas ser la fonc tion
éco no mique F. Chaque fois que nous ne pour rons pas prendre x i 5 1 (i = 1, 2 ou 4),