Solu tions des exer cices du cha pitre 1
447
© Dunod – Toute reproduction non autorisée est un délit.
c’est cet ordre que nous allons tenter de donner aux variables de valeur 1.
Ci-dessous nous présentons les calculs à l’aide d’une arborescence (ce qui est équivalent au
calcul en tableau de la page 33).
Première phase : obtention d’une « bonne » solution admissible
a. x 2 ayant le plus grand coefficient dans F, on a intérêt semble­t­il, à prendre x 2 1
= (et
donc x 2 0
= ) si c’est possible (c’est­à­dire si les contraintes sont respectées). Les contraintes
deviennent :
2
5
3
2
5
3
1
3
4
1
3
4
1
3
4
x x x
x
x x
x x x
+ + ≤
+
+ ≤
+ + ≤
et Fr :
3
2
4
1
x
x x F'
+
+ =
On remarque que dans chaque contrainte ci-dessus, le coefficient de toute variable est
inférieur au second membre : le choix de x 2 1
= n’a pas d’implication sur les valeurs des
autres variables. (Si l’on avait : 2
7
5
1
3
4
x
x x
+
+ ≤ puisque 7 > 5, une implication serait
x 3 0
= ; mais ce n’est pas le cas ici.)
b. x 4 ayant le second plus grand coefficient dans F : 3, on prend x 4 1
= . Les contraintes
deviennent :
2
5
3
2
4
2
1
3
1
3
1
3
x x
x
x
x x
+ ≤
+
≤
+ ≤
et Fr :
2
3
1
3
x x
F'
+ + = .
À nouveau on n’a pas d’implication.
c. x 1 ayant alors le plus grand coefficient dans F, on prend x 1 1
= . Les contraintes
deviennent :
x
x
x
3
3
3
3
1
2
2
≤
≤
≤
et F :
x
F'
3
5
+ =