1.4 Appli ca tions élé men taires
© Dunod – Toute reproduction non autorisée est un délit.
31
puis, par une méthode quel conque, par exemple celle de Quine, consta tons que
les constituants x 1 # x 2 # x 3 # x 5 et x 1 # x 2 # x 3 # x 4 # x 5 donnent le consti tuant x 1 # x 3 # x 4 # x 5
(qui est le consensus de ces deux termes).
Or x 1 # x 2 # x 3 # x 4 # x 5 est inclus dans x 1 # x 3 # x 4 # x 5 .
D’où la liste des consti tuants pre miers de F :
F 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 3 # x 4 # x 5 .
Seules les valeurs affir mées nous inté ressent dans cha cun de ces consti tuants
pre miers pour éta blir les prix, car elles seules impliquent des achats de machines ;
d’où :
A i
7
5
3
6
2
Total
x 1
x 2
x 3
x 4
x 5
x 2 # x 4 # x 5
1
1
1
13
x 2 # x 3 # x 4
1
1
1
14
x 1 # x 3 # x 5 # x 4
1
1
1
12
On a volontairement omis le troi sième de ces consti tuants premiers : il condui rait
à acqué rir les machines M 1 , M 2 , M 3 et M 5 alors qu’avec le qua trième consti tuant,
il suf fit d’acqué rir M 1 et M 3 et M 5 (il y figure x 4 , ce qui signifie qu’on n’a pas à
acheter M 4 ).
La der nière solu tion est la moins coû teuse : son coût est I = 12 (au lieu de 13 et
14 pour les deux autres).
On véri fie bien que, pour : x 1 5 x 3 5 x 5 5 1, x 2 5 x 4 5 0, on a :
c 1 5 x 1 # x 3 1
# x 4 5 1
c 2 5 x 2 # x 4 1
# x 1 # x 5 5 1
c 3 5 x 2 # x 5 1
# x 3 5 1
t 1 5 x 2 1
# x 4 5 1
t 2 5 x 1 # x 2 1
# x 4 # x 5 1
# x 2 # x 3 5 1
1.4.3 Fonc tion à variables binaires à opti mi ser sous
contraintes
Le cha pitre 8 consa cré à la pro gram ma tion linéaire, défi nira le cadre d’appli ca tion
et la ter mi no logie uti li sée pour toute une famille de pro blèmes appe lés pro grammes
linéaires. Les méthodes per met tant de résoudre l’exemple sui vant (pro gramme
linéaire en variables boo léennes) seront reprises aux cha pitres 4 et 9.
Nous expo sons ci- dessous la méthode boo léenne de Faure et Malgrange. Il s’agit
d’une des toutes pre mières méthodes de recherche arbo res cente (1962). Elle uti lise
© Dunod – Toute reproduction non autorisée est un délit.
31
puis, par une méthode quel conque, par exemple celle de Quine, consta tons que
les constituants x 1 # x 2 # x 3 # x 5 et x 1 # x 2 # x 3 # x 4 # x 5 donnent le consti tuant x 1 # x 3 # x 4 # x 5
(qui est le consensus de ces deux termes).
Or x 1 # x 2 # x 3 # x 4 # x 5 est inclus dans x 1 # x 3 # x 4 # x 5 .
D’où la liste des consti tuants pre miers de F :
F 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 3 # x 4 # x 5 .
Seules les valeurs affir mées nous inté ressent dans cha cun de ces consti tuants
pre miers pour éta blir les prix, car elles seules impliquent des achats de machines ;
d’où :
A i
7
5
3
6
2
Total
x 1
x 2
x 3
x 4
x 5
x 2 # x 4 # x 5
1
1
1
13
x 2 # x 3 # x 4
1
1
1
14
x 1 # x 3 # x 5 # x 4
1
1
1
12
On a volontairement omis le troi sième de ces consti tuants premiers : il condui rait
à acqué rir les machines M 1 , M 2 , M 3 et M 5 alors qu’avec le qua trième consti tuant,
il suf fit d’acqué rir M 1 et M 3 et M 5 (il y figure x 4 , ce qui signifie qu’on n’a pas à
acheter M 4 ).
La der nière solu tion est la moins coû teuse : son coût est I = 12 (au lieu de 13 et
14 pour les deux autres).
On véri fie bien que, pour : x 1 5 x 3 5 x 5 5 1, x 2 5 x 4 5 0, on a :
c 1 5 x 1 # x 3 1
# x 4 5 1
c 2 5 x 2 # x 4 1
# x 1 # x 5 5 1
c 3 5 x 2 # x 5 1
# x 3 5 1
t 1 5 x 2 1
# x 4 5 1
t 2 5 x 1 # x 2 1
# x 4 # x 5 1
# x 2 # x 3 5 1
1.4.3 Fonc tion à variables binaires à opti mi ser sous
contraintes
Le cha pitre 8 consa cré à la pro gram ma tion linéaire, défi nira le cadre d’appli ca tion
et la ter mi no logie uti li sée pour toute une famille de pro blèmes appe lés pro grammes
linéaires. Les méthodes per met tant de résoudre l’exemple sui vant (pro gramme
linéaire en variables boo léennes) seront reprises aux cha pitres 4 et 9.
Nous expo sons ci- dessous la méthode boo léenne de Faure et Malgrange. Il s’agit
d’une des toutes pre mières méthodes de recherche arbo res cente (1962). Elle uti lise