Chapitre 1 • Structures ordonnées Applications des treillis
36
Soit à résoudre le pro blème sui vant :
[MAX] F 5 3x 1 + 8x 2
sous les contraintes :
x 1 1 4x 2 < 20 1 12
x 1 1 2x 2 < 11 1 22
3x 1 1 2x 2 < 19 1 32
4x 1 2 x 2 < 22 1 42 ,
les variables x 1 et x 2 étant astreintes à être entières, positives ou nulles.
1. Obten­ ­ tion­de­bornes­supé­ ­ rieures­des­variables
La pre mière inéga lité entraîne : x 2 < 5. Une combi nai son linéaire posi tive des
deux der nières : 1 3 1 32 1 2 3 1 42 four ni 11x 1 < 63, d’où x 1 < 5 puisque x 1 est
entier.
2. Rem­ ­ pla­ ­ ce­ ­ ment­des­variables­entières­par­des­variables­boo­ ­ léennes
On peut écrire : x 1 5 4X
1
1 1 2X
2
1 1 X
3
1 , les variables X
1
1 , X
2
1 et X
3
1 étant binaires ; cela revient en somme, tenant compte de sa borne supé rieure, à décom po ser x 1
en ses poids binaires.
De même : x 2 5 4X
1
2 1 2X
2
2 1 X
3
2 . Si X
1
2 5 X
2
2 5 X
3
2 5 1, alors x 2 5 7, ce qui
viole (1) et (2) : ces trois variables ne pourront donc pas être simultanément égales
à 1.
3. Trans­ ­ for­ ­ ma­ ­ tion­des­expres­ ­ sions­pour­faire­dis­ ­ pa­ ­ raître­les­coef­ ­ fi­ ­ cients­néga­ ­ tifs
On a, par exemple : x 2 1 x 2 5 7 (attention : ici x 2 est le complément de x 2 à 7 et
non pas à 1), en posant :
x 2 5 4X
1
2 1 2X
2
2 1 X
3
2 ; en effet : X
1
2 1 X
1
2 5 X
2
2 1 X
2
2 5 X
3
2 1 X
3
2 5 1.
Par consé quent : 2x 2 5 x 2 2 7 et la qua trième inéga lité s’écrira :
4x 1 1 x 2 < 29.
Rem pla çons les variables par leur déve lop pe ment binaire dans toutes les rela tions
et ordon nons par rap port aux coef fi cients décrois sants des variables binaires dans F.
On obtient :
3MAX4F 5 32X
1
2 1 16X
2
2 1 12X
1
1 1 8X
3
2 1 6X
2
1 1 3X
3
1
sous les contraintes :
16X
1
2 1 8X
2
2 1
4X
1
1 1 4X
3
2 1 2X
2
2 1
X
3
1 < 20
8X
1
2 1 4X
2
2 1
4X
1
1 1 2X
3
2 1 2X
2
2 1
X
3
1 < 11
8X
1
2 1 4X
2
2 1 12X
1
1 1 2X
3
2 1 6X
2
2 1 3X
3
1 < 19
4X
1
2 1 2X
2
2 1 16X
1
1 1
X
3
2 1 8X
2
2 1 4X
3
1 < 29