Solutions
448
La seconde contrainte implique : x 3 0
= .
Finalement on a obtenu la solution x x
x x
4
1
2
3
1
0
= =
= =
,
de valeur F = 5. Mais nous ne
savons pas, pour l’instant, si cette solution est optimale ou non.
Deuxième phase : recherche de la solution optimale
On va remettre en cause les choix effectués, en partant du dernier, puis de l’avant dernier,
etc.
c′. Si on prend x 1 0
= (en gardant x x
2
4
1
= = ), les contraintes deviennent :
x
x
x
3
3
3
5
2
4
3
≤
≤
≤
et F′ :
x
F'
3
3
+ =
Manifestement F′≤ 4 (au mieux ; si x 3 = 1) alors qu’on connaît une solution de valeur
F' = 5 : il n’existe pas de meilleure solution avec x 1 0
= . On va remonter alors à la mise en
cause du choix précédent.
b′. Si on prend x 4 0
= (en gardant x 2 1
= ), les contraintes deviennent :
2
4
3
2
5
3
1
3
1
3
1
3
x x
x
x
x x
+ ≤
+
≤
+ ≤
et F′ :
2 1 3
x x F′
+ =
Manifestement F' ≤ 3. On va alors alors remonter alors à la mise en cause du premier
choix.
a′. Si on prend x 2 0
= (c’est­à­dire x 2 1
= ) :
2
1
3
2
7
2
1
3
4
1
3
4
1
3
4
x x x
x
x x
x x x
+ + ≤
+
+ ≤
+ + ≤
et F' :
2
4
1
3
4
x x x
F'
+ + − = .