1.4 Appli ca tions élé men taires
© Dunod – Toute reproduction non autorisée est un délit.
33
nous serons contraints d’adop ter x i 5 1 et ainsi F sera dimi nuée de la valeur du coef
fi cient de x i dans F 5 10 2 1 5x 2 1 3x 1 1 2x 4 1 x 3 2 ; c’est évi dem ment le contraire
pour x 3 .
Dans ces condi tions, nous écri rons les coef fi cients de 10 2 F 5 5x 2 1 3x 1 1
2x 4 1 x 3 , sur la der nière ligne du tableau, dans les colonnes vou lues.
5. Nous dis po sons alors des ins tru ments néces saires pour résoudre le pro blème par
énu mé ra tion impli cite, c’est- à-dire en n’énu mé rant qu’un petit nombre de solu tions
admis sibles (ce qui veut dire qu’elles véri fient les contraintes, sans être néces sai re
ment opti males), parmi les meilleures du pro blème, jus qu’à ce que l’on ait trouvé
la solu tion opti male et mon tré qu’elle est unique ou, au contraire, exhibé toutes les
solu tions équi va lentes.
Coefficients des contraintes
et de la fonctionnelle
Seconds membres
x 2 x 2 x 1 x 1 x 4 x 4 x 3 x 3 0
1
2 2a 2 2a 2b 1
4
3
1
2
7
3
0
0
3
2
0
7
1
2
1
3
6
6
4
0
6
6
6
5
1
4
2
1
7
7
3
3
7
5
4
6
5
3
2
1
10 10 10 7
7
7
7
5
1*
2*
2
2
Résultat : x 1 5 x 2 5 x 3 5 1 ; x 4 5 0 ; F 5 7
2* 2r
2r Résultat : x 2 5 x 4 5 1 ; x 1 5 x 3 5 0 ; F 5 7
1*
F < 5. Sans intérêt
Les deux phases de cette méthode sont illus trées par la Fig. 1.19
Il est conseillé de suivre la réso lu tion en paral lèle avec cette figure.
• Pre mière phase : obten tion d’une « bonne » solu tion admis sible
Nous avons, semble til, tout inté rêt à prendre x 2 5 1, si c’est pos sible, puisque x 2 a
le coef fi cient le plus élevé dans F (cette démarche est qualifiée de « gourmande »).
Essayons donc x 2 5 1 ; nous dirons que nous effec tuons le choix 1* et nous note -
rons ce choix sur la ligne et dans la colonne appro priées du tableau. Les valeurs
figu rant au second membre ne peuvent plus être celles de la colonne 0 ; en effet,
si l’on fait x 2 5 1, la pre mière inéga lité devient 3x 1 1 x 4 1 2x 3 < 3 ; en revanche,
la seconde et la troi sième ne sont pas modi fiées et nous conser vons l’espoir que F
atteigne 10. C’est ce que nous tra dui sons avec les nou velles valeurs du second membre figu rant dans la colonne 1. Exa mi nons alors si rien ne s’oppose main te nant à la
liberté de nos choix ulté rieurs. Pour cela, compa rons les coef fi cients des colonnes
du tableau, au- delà de x 2 , et pour chaque ligne, avec les valeurs de la colonne 1 du
second membre. On constate que tous les choix sont pos sibles car les coef fi cients de
© Dunod – Toute reproduction non autorisée est un délit.
33
nous serons contraints d’adop ter x i 5 1 et ainsi F sera dimi nuée de la valeur du coef
fi cient de x i dans F 5 10 2 1 5x 2 1 3x 1 1 2x 4 1 x 3 2 ; c’est évi dem ment le contraire
pour x 3 .
Dans ces condi tions, nous écri rons les coef fi cients de 10 2 F 5 5x 2 1 3x 1 1
2x 4 1 x 3 , sur la der nière ligne du tableau, dans les colonnes vou lues.
5. Nous dis po sons alors des ins tru ments néces saires pour résoudre le pro blème par
énu mé ra tion impli cite, c’est- à-dire en n’énu mé rant qu’un petit nombre de solu tions
admis sibles (ce qui veut dire qu’elles véri fient les contraintes, sans être néces sai re
ment opti males), parmi les meilleures du pro blème, jus qu’à ce que l’on ait trouvé
la solu tion opti male et mon tré qu’elle est unique ou, au contraire, exhibé toutes les
solu tions équi va lentes.
Coefficients des contraintes
et de la fonctionnelle
Seconds membres
x 2 x 2 x 1 x 1 x 4 x 4 x 3 x 3 0
1
2 2a 2 2a 2b 1
4
3
1
2
7
3
0
0
3
2
0
7
1
2
1
3
6
6
4
0
6
6
6
5
1
4
2
1
7
7
3
3
7
5
4
6
5
3
2
1
10 10 10 7
7
7
7
5
1*
2*
2
2
Résultat : x 1 5 x 2 5 x 3 5 1 ; x 4 5 0 ; F 5 7
2* 2r
2r Résultat : x 2 5 x 4 5 1 ; x 1 5 x 3 5 0 ; F 5 7
1*
F < 5. Sans intérêt
Les deux phases de cette méthode sont illus trées par la Fig. 1.19
Il est conseillé de suivre la réso lu tion en paral lèle avec cette figure.
• Pre mière phase : obten tion d’une « bonne » solu tion admis sible
Nous avons, semble til, tout inté rêt à prendre x 2 5 1, si c’est pos sible, puisque x 2 a
le coef fi cient le plus élevé dans F (cette démarche est qualifiée de « gourmande »).
Essayons donc x 2 5 1 ; nous dirons que nous effec tuons le choix 1* et nous note -
rons ce choix sur la ligne et dans la colonne appro priées du tableau. Les valeurs
figu rant au second membre ne peuvent plus être celles de la colonne 0 ; en effet,
si l’on fait x 2 5 1, la pre mière inéga lité devient 3x 1 1 x 4 1 2x 3 < 3 ; en revanche,
la seconde et la troi sième ne sont pas modi fiées et nous conser vons l’espoir que F
atteigne 10. C’est ce que nous tra dui sons avec les nou velles valeurs du second membre figu rant dans la colonne 1. Exa mi nons alors si rien ne s’oppose main te nant à la
liberté de nos choix ulté rieurs. Pour cela, compa rons les coef fi cients des colonnes
du tableau, au- delà de x 2 , et pour chaque ligne, avec les valeurs de la colonne 1 du
second membre. On constate que tous les choix sont pos sibles car les coef fi cients de