INDEX 
VI. Exemple
Résoudre le programme linéaire suivant en utilisant la méthode de simplexe.
Max 3x1 + 2x2
SC - x1 + 2x2
£ 43x1 + 2x2 £ 14
x1 + x2 £ 3
x1 ³ 0 x2 ³ 0
®
La forme standard du programme linéaire s'écrit comme suit :Max 3x1 + 2x2
SC - x1 + 2x2 + S1 = 4
3x1 + 2x2 + S2 = 4
x1 - x2 + S3 = 3
x1
³ 0, x2³ 0, S1³ 0, S2³ 0, S3³ 0® Tableau de simplexe initial (1ère itération)
|
|
|
|
3 |
2 |
0 |
0 |
0 |
|
|
|
|
|
x1 |
x2 |
S1 |
S2 |
S3 |
|
|
0 |
S1 |
4 |
-1 |
2 |
1 |
0 |
0 |
-4 |
|
0 |
S2 |
14 |
3 |
2 |
0 |
1 |
0 |
14/3 |
|
0 |
S3 |
3 |
(1) |
-1 |
0 |
0 |
1 |
3 |
|
|
|
|
0 |
0 |
0 |
0 |
0 |
|
|
|
|
|
3 |
2 |
0 |
0 |
0 |
|
La variable entrante est x1 puisqu’elle présente le plus grand effet net positif. La variable sortante est S3 car elle correspond au plus petit quotient positif.
®
2ème itération|
|
|
|
3 |
2 |
0 |
0 |
0 |
|
|
|
|
|
x1 |
x2 |
S1 |
S2 |
S3 |
|
|
0 |
S1 |
7 |
0 |
1 |
1 |
0 |
1 |
7 |
|
0 |
S2 |
5 |
0 |
(5) |
0 |
1 |
-3 |
1 |
|
3 |
x1 |
3 |
1 |
1 |
0 |
0 |
1 |
3 |
|
|
|
|
3 |
0 |
0 |
0 |
3 |
|
|
|
|
|
0 |
2 |
0 |
0 |
-3 |
|
La variable entrante est x2 et la variable sortante est S2
®
3ème itération|
|
|
|
3 |
2 |
0 |
0 |
0 |
|
|
|
|
x1 |
x2 |
S1 |
S2 |
S3 |
|
0 |
S1 |
6 |
0 |
0 |
1 |
-1/5 |
8/5 |
|
2 |
x2 |
1 |
0 |
1 |
0 |
1/5 |
-3/5 |
|
3 |
x1 |
4 |
1 |
0 |
0 |
1/5 |
2/5 |
|
|
|
|
3 |
2 |
0 |
1 |
0 |
|
|
|
|
0 |
0 |
0 |
-10 |
0 |
Tous les cj-zj
£ 0 donc le tableau de simplexe est optimal et la solution optimal du programme linéaire estx1 = 4
x2 = 1
S1 = 6
S2 = 0
S3 = 0
La valeur de la fonction objectif est 14.
Remarque : L’effet net de l’augmentation d’une unité de la valeur de S3 (variable hors base) est nul. Donc si on introduit S3 dans la base, on ne modifie pas la valeur de la fonction objectif. Ainsi une autre solution optimale peut être trouvée pour notre programme linéaire. Ceci confirme le résultat de la méthode graphique qui indique que ce problème admet un ensemble de solution optimale décrit par le segment [BC].
La solution optimale donnée par le dernier tableau de simplexe correspond au point C.
Le tableau du simplexe suivant est :
|
|
|
|
3 |
2 |
0 |
0 |
0 |
|
|
|
|
x1 |
x2 |
S1 |
S2 |
S3 |
|
0 |
S3 |
15/4 |
0 |
0 |
5/8 |
-1/8 |
1 |
|
2 |
x2 |
13/4 |
0 |
1 |
3/8 |
1/8 |
0 |
|
3 |
x1 |
5/2 |
1 |
0 |
-1/4 |
1/4 |
0 |
|
|
|
|
3 |
2 |
0 |
1 |
0 |
|
|
|
|
0 |
0 |
0 |
-1 |
0 |
Le tableau est optimal et la solution correspondante est :
x1 = 5/2
x2 = 13/4
S1 = 0
S2 = 0
S3 = 15/4
La valeur de la fonction objectif est 14.
Cliquer ici pour enregistrer le chapitre 3 en format Word sur votre disque dur (151 Ko)
Pour tout commentaire envoyer un mail à hatem_masri@yahoo.com