Chapitre 1 • Structures ordonnées Applications des treillis
30
Pour exé cu ter C 1 , on peut avoir recours aux machines M 1 et M 3 ou à la machine
M 4 , ce qui peut s’écrire :
c 1 5 x 1 # x 3 1
# x 4 .
On a, de même, pour C 2 et C 3 :
c 2 5 x 2 # x 4 1
# x 1 # x 5 ,
c 3 5 x 2 # x 5 1
# x 3 .
D’autre part, une contrainte tech nique t 1 exige que l’on uti lise x 2 ou que l’on
n’uti lise pas x 4 :
t 1 5 x 2 1
# x 4 5 x 2 # x 4 ;
une autre contrainte tech nique peut s’écrire :
t 2 5 x 1 # x 2 1
# x 4 # x 5 1
# x 2 # x 3 .
Pour que les commandes soient hono rées, il faut et il suf fit que l’on ait :
c 1 5 c 2 5 c 3 5 1 ;
pour que les contraintes soient obser vées, il faut et il suf fit que :
t 1 5 t 2 5 1.
Tous les ensembles de cinq valeurs binaires (x 1 , x 2 , x 3 , x 4 , x 5 ) tels que :
F 5 c 1 # c 2 # c 3 # t 1 # t 2 5 1
sont solu tions du pro blème.
Ima gi nons main te nant que l’achat et l’ins tal la tion des machines entraîne les
dépenses sui vantes (en milliers d’uni tés moné taires) :
M 1
M 2
M 3
M 4
M 5
A 1
7
5
3
6
2
On désire minimi ser la dépense totale I, c’est- à-dire :
I 5 a
5
j51
A j # x j .
Il importe donc de trou ver tous les consti tuants pre miers de F 1 x 1 , x 2 , c , x 5 2
et de cal cu ler, pour cha cun d’eux, la valeur de I, de manière à pou voir sélec tion
ner la plus faible. En effet, un consti tuant pre mier implique la fonc tion (si ce
consti tuant vaut 1) et il n’est impli qué par aucun autre consti tuant impli quant
lui- même la fonc tion, si bien que les ensembles de machines repré sen tés par les
consti tuants pre miers sont les ensembles mini maux qui couvrent la fonc tion,
donc per mettent les fabri ca tions, tout en assu rant le respect des contraintes. Cal -
cu lons d’abord F :
F 5 1 x 1 # x 3 1
# x 4 2 # 1 x 2 # x 4 1
# x 1 # x 5 2 # 1 x 2 # x 5 1
# x 3 2 # 1 x 2 1
# x 4 2 # 1 x 1 # x 2 1
# x 4 # x 5 1
# x 2 # x 3 2
5 x 2 # x 4 # x 5 1
# x 2 # x 3 # x 4 1
# x 1 # x 2 # x 3 # x 5 1
# x 1 # x 2 # x 3 # x 4 # x 5 ,
30
Pour exé cu ter C 1 , on peut avoir recours aux machines M 1 et M 3 ou à la machine
M 4 , ce qui peut s’écrire :
c 1 5 x 1 # x 3 1
# x 4 .
On a, de même, pour C 2 et C 3 :
c 2 5 x 2 # x 4 1
# x 1 # x 5 ,
c 3 5 x 2 # x 5 1
# x 3 .
D’autre part, une contrainte tech nique t 1 exige que l’on uti lise x 2 ou que l’on
n’uti lise pas x 4 :
t 1 5 x 2 1
# x 4 5 x 2 # x 4 ;
une autre contrainte tech nique peut s’écrire :
t 2 5 x 1 # x 2 1
# x 4 # x 5 1
# x 2 # x 3 .
Pour que les commandes soient hono rées, il faut et il suf fit que l’on ait :
c 1 5 c 2 5 c 3 5 1 ;
pour que les contraintes soient obser vées, il faut et il suf fit que :
t 1 5 t 2 5 1.
Tous les ensembles de cinq valeurs binaires (x 1 , x 2 , x 3 , x 4 , x 5 ) tels que :
F 5 c 1 # c 2 # c 3 # t 1 # t 2 5 1
sont solu tions du pro blème.
Ima gi nons main te nant que l’achat et l’ins tal la tion des machines entraîne les
dépenses sui vantes (en milliers d’uni tés moné taires) :
M 1
M 2
M 3
M 4
M 5
A 1
7
5
3
6
2
On désire minimi ser la dépense totale I, c’est- à-dire :
I 5 a
5
j51
A j # x j .
Il importe donc de trou ver tous les consti tuants pre miers de F 1 x 1 , x 2 , c , x 5 2
et de cal cu ler, pour cha cun d’eux, la valeur de I, de manière à pou voir sélec tion
ner la plus faible. En effet, un consti tuant pre mier implique la fonc tion (si ce
consti tuant vaut 1) et il n’est impli qué par aucun autre consti tuant impli quant
lui- même la fonc tion, si bien que les ensembles de machines repré sen tés par les
consti tuants pre miers sont les ensembles mini maux qui couvrent la fonc tion,
donc per mettent les fabri ca tions, tout en assu rant le respect des contraintes. Cal -
cu lons d’abord F :
F 5 1 x 1 # x 3 1
# x 4 2 # 1 x 2 # x 4 1
# x 1 # x 5 2 # 1 x 2 # x 5 1
# x 3 2 # 1 x 2 1
# x 4 2 # 1 x 1 # x 2 1
# x 4 # x 5 1
# x 2 # x 3 2
5 x 2 # x 4 # x 5 1
# x 2 # x 3 # x 4 1
# x 1 # x 2 # x 3 # x 5 1
# x 1 # x 2 # x 3 # x 4 # x 5 ,