1.4 Appli ca tions élé men taires
© Dunod – Toute reproduction non autorisée est un délit.
29
Nous indi que rons ces chan ge ments de date par une barre ver ti cale :
sens ABCDBA
sens ABDCBA
par cours ABC : ab ; a k b
parcours ABD : ac ; ac ; ac ; a c
BCD : bd
BDC : c k d ; c k d
CDB : d k g ; d k g
DCB : d k b
DBA : ga ; g a ; ga ; ga ;
CBA : ba ; ba
Dans la deuxième colonne (sens ABDCBA), nous remar quons qu’il y a tou jours
deux chan ge ments de date. Dans la pre mière colonne, il n’y en a qu’un si nous
emprun tons la suite ab. Il reste fina le ment à exa mi ner les suites :
abdga ; abdg a ; abd g a ; abd g a.
En uti li sant les moyens indi qués, le voya geur pourra par tir un jour quel conque et
de retour le len de main. Il n’est pas dif fi cile de voir que les suites :
abd ga et abd g a
sont équi va lentes, comme fai sant par tir le voya geur le jour J, à 09h00 et le fai sant,
toutes deux, ren trer le jour J 1 1, à 20h00.
abd 09h00 10h00 10h30 12h30 14h00 15h00 14h00 15h00 17h00 20h00
d
a
d
a
d
a
d
a
d
a
A
B
C
D
D
B
A
J
J  1
abd   09h00 10h00 10h30 12h30 14h00 15h00 14h30 16h30 17h00 20h00
Ville
Solution
avion
train
train
train
bateau
avion
La seconde solu tion est plus éco no mique, mais la pre mière pro cure un arrêt plus
long dans la ville B, au retour.
1.4.2 Choix d’inves tis se ments
Un ate lier reçoit trois commandes C 1 , C 2 , C 3 , qui peuvent être exé cu tées au moyen
d’au plus cinq machines M 1 , M 2 , M 3 , M 4 et M 5 . On désigne par c i (i 5 1, 2, 3) la
variable boo léenne égale à 1 si la commande C i est exé cu tée (et à 0 sinon) ; de même
la variable boo léenne x j 1 j 5 1, 2, c , 52 est égale à 1 si la machine M j est uti li sée
(et à 0 sinon).