1.4 Appli ca tions élé men taires
© Dunod – Toute reproduction non autorisée est un délit.
37
Ainsi les coefficients de F et des contraintes sont désormais tous positifs.
Le tableau cor res pon dant s’écrit :
Coefficients des contraintes et de F
Seconds membres
X
1
2 X
1
2 X
2
2 X
2
2 X
1
1 X
1
1 X
3
2 X
3
2 X
2
1 X
2
1 X
3
1 X
3
1 0 1 1a 2 2a 2 2a 1 1a 1b
16
8
4
4
2
1
20 4 4 0 0 4 1 20 4 4
8
4
4
2
2
1
11 3 3 1 1 3 0 11 1 1
8
4
12
2
6
3
19 11 11 9 9 11 2 19 1 1
4
2 16
1 8
4
29 29 27 27 27 26 14 25 9 9
32
16
12
8
6
3 77 77 49 49 40 41 41 45 45 39
1*
1
1 2*
2
2
Résultat : x 1 5 0, x 2 5 5 ; F 5 40
2* 2r
2r
Résultat : x 1 5 3, x 2 5 4 ; F 5 41
1* 1r
1r
1r
1
F < 39. Sans intérêt
et le dérou le ment des cal culs (cf aussi l’arborescence de la fig. 1.21) est ana logue
au cas a). La pre mière solu tion obte nue vaut 40, avec x 1 5 0 et x 2 5 5. Elle n’est
pas opti male, puisque la seconde, à laquelle on abou tit en remet tant en cause le
choix 2*, four nit F 5 41, avec x 1 5 3 et x 2 5 4.
Enfin, la remise en ques tion du choix 1* implique F < 39 (en fait F 5 36), d’où
l’arrêt de l’explo ra tion.
Remarque. Le pro blème se prête à une inter pré ta tion dans le plan, car il ne
comporte que deux variables, x 1 et x 2 . La figure 1.20 fait appa raître le domaine
admis sible, avec ses 28 solu tions entières (cf les 28 points gras).
Figure 1.20
En nombres ration nels fractionnaires, la solu tion opti male est :
x 1 5 2, x 2 5
9
2
avec F 5 42 (point M) ;
mais x 1 et x 2 doivent avoir, ici, des valeurs entières.