Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

TD 7 : Exercice corrigé Algorithme du simplexe Méthode des deux phases Exercice

TD 7 : Exercice corrigé Algorithme du simplexe Méthode des deux phases Exercice Résoudre par la méthode des deux phases le modèle de programmation linéaire suivant :   1 2 1 2 1 2 1 2 1 2 12 20 . . 6 10 60 8 25 200 2 8 80 0 , 0 Maximiser Z x x s c x x P x x x x x x                     a) Standardisation de (P) par ajout des variables d’écart :   1 2 3 4 5 1 2 3 1 2 4 1 2 5 1 2 3 4 5 12 20 0 0 0 . . 6 10 60 8 25 200 2 8 80 , , , , 0 S Maximiser Z x x x x x s c x x x P x x x x x x x x x x x                          b) Peut-on obtenir une solution de base réalisable de départ avec le système d’équations obtenu en a) ? Nous avons 5 variables et 3 équations ; donc, nous devons annuler (n-m)=(5-3)=2 variables. Annulons les 2 variables de décision : 1 2 0 x x       1 2 3 4 5 , ; , , horsbase x x base x x x   Calculons les valeurs des variables de base 3 4 5 60; 200; 80. x x x    La solution de base     1 2 3 4 5 , , , , 0,0, 60, 200,80 . x x x x x x     Cette solution n’est pas réalisable vu que les variables 3 4 x et x sont nulles; Donc, nous n’avons pas de S.B.R. de départ pour appliquer l’algorithme du simplexe. a) Introduisez les variables artificielles et appliquer la méthode des deux phases.   1 2 3 4 5 6 7 1 2 3 6 1 2 4 7 1 2 5 1 2 3 4 5 6 7 12 20 0 0 0 . . 6 10 60 8 25 200 2 8 80 , , , , , , 0 S Maximiser Z x x x x x x x s c x x x x P x x x x x x x x x x x x x x                              Après avoir introduit les variables artificielles, nous avons modifié profondément l’expression de la fonction objectif ; ceci va influencer la valeur de Z. Pour cela nous allons appliquer la phase I de la méthode des deux phases en espérant une solution de base réalisable optimale qui serait la S.B.R. de départ du (PS) et nous allons pouvoir entamer la phase II. Ceci se ferait en minimisant la somme des valeurs des valeurs artificielles * 6 7 Z x x   dans la Z.   * 6 7 1 2 3 6 1 2 4 7 1 2 5 1 2 3 4 5 6 7 . . 6 10 60 8 25 200 2 8 80 , , , , , , 0 A Min Z x x s c x x x x P x x x x x x x x x x x x x x                         Tableau 0 : Phase I j c 0 0 0 0 0 1 1 B C Variables de base 1 2 3 4 5 6 7 x x x x x x x Solution de base Quotient 1 6 x 1 7 x 0 5 x 6 -1 0 0 1 0 8 25 0 -1 0 0 1 2 8 0 0 1 0 0 60 200 80 60/10 = 10 200/25 = 8 80/8 = 10 ' j B J z C x  j j c z  14 35 -1 -1 0 1 1 -14 -35 1 1 0 -1 -1 Z* = 260 Tableau 1 : Phase I j c 0 0 0 0 0 1 1 B C Variables de base 1 2 3 4 5 6 7 x x x x x x x Sol de base Quot 0 2 x 1 7 x 0 5 x 6/10 1 -1/10 0 0 1/10 0 -7 0 25/10 -1 0 -25/10 1 -28/10 0 8/10 0 1 -8/10 0 6 50 32 ' j B J z C x  j j c z  -64/10 1 24/10 -1 0 -24/10 1 64/10 -1 -24/10 1 0 24/10 -1 Z*=50 10 Tableau 2 : Phase I j c 0 0 0 0 0 1 1 B C Variables de base 1 2 3 4 5 6 7 x x x x x x x Sol de base 0 2 x 0 3 x 0 5 x 8/25 1 0 -1/25 0 0 1/25 -14/5 0 1 -2/5 0 -1 2/5 -14/25 0 0 8/25 1 0 -8/25 8 20 16 ' j B J z C x  j j c z  0 0 0 0 0 0 0 0 0 0 0 0 0 0 Z*= 0 La valeur de la fonction Z*= 0 et les variables artificielles sont éliminées de la base. Donc, la phase II peut commencer avec la S. B. R.     0 1 2 3 4 5 , , , , 0,8,20,0,16 x x x x x x   Mais vérifions d’abord que 0 x vérifie le problème standard   S P :   6*0 10*8 20 60 8*0 25*8 0 200 2*0 8*8 16 80 S P                Phase II Tableau 0 : Phase II j c 12 20 0 0 0 B C Variables de base 1 2 3 4 5 x x x x x Sol de base 20 2 x 0 3 x 0 5 x 8/25 1 0 -1/25 0 -14/5 0 1 -2/5 0 -14/25 0 0 8/25 1 8 20 16 ' j B J z C x  j j c z  160/25 20 0 -2/25 0 140/25 0 0 2/25 0 Z* = 16 Tableau 1 : Phase II j c 12 20 0 0 0 B C Variables de base 1 2 3 4 5 x x x x x Sol de base Quotient 12 1 x 0 3 x 0 5 x 1 25/8 0 -1/8 0 0 35/4 1 -3/4 0 0 7/4 0 1/4 1 25 90 30 ---- ---- 120 ' j B J z C x  j j c z  12 75/2 0 -3/2 0 0 -35/2 0 3/2 0 Z* = 300 Tableau 2 : Phase II j c 12 20 0 0 0 B C Variables de base 1 2 3 4 5 x x x x x Sol de base 12 1 x 0 3 x 0 4 x 1 25/8 0 0 1/2 0 4 1 0 3 0 7 0 1 4 40 180 120 ' j B J z C x  j j c z  12 75/2 0 0 6 0 -35/2 0 -3/2 0 Z* = 480 Tous les j j c z  sont négatifs donc la solution est optimale :     1 2 3 4 5 * , , , , 40, 0, 180, 120, 0 480 x x x x x x Z    uploads/s3/ exercice-corrige-simplexe 1 .pdf