Imane Hassani

Imane Hassani Étudiante - Bac+2
Dans Programmation | Niveau Bac+4

recherche opérationnelle

Pourriez-vous m'expliquer la méthode de Grand M?

cette méthode est étudié dans le cours de la recherche opérationnelle et la programmation linéaire,et je ne sais pas quand est ce qu'on doit l'appliquer,si qlq'un pourrait m'aider je lui serais vraiment reconnaissante et merci d'avance. 

Inscrivez-vous gratuitement pour voir la réponse

Vous ne comprenez pas une notion de cours ? Vous n'arrivez pas à faire un exercice ?
Vous avez besoin d'aide pour un exposé ou un devoir ?

Sur Beebac des milliers d'étudiants, d'enseignants et de professionnels sont prêts à vous aider.
Vous avez une question ? Inscrivez-vous et Posez la ?


Se connecter avec

Créer un compte avec votre adresse email

En cliquant sur "Valider", ci-dessous, vous acceptez les Conditions générales d'utilisation de Beebac.






5 réponses
Trier les réponses par :
Laureen Dupon
Laureen Dupon
Étudiante - Bac+1
Salut Sara,

La méthode du Grand M est présentée à la page 15.

05 Décembre 2011
Judes MBAITOLOUM
Judes MBAITOLOUM
Étudiant - Bac+4 - Sciences de Gestion
Merci de votre intervention. Je comprend la méthode.
Anonyme
Anonyme
Professionnel

Bonjour Sara,

J'ai pu trouvé ces informations :

La méthode des pénalités (ou du grand M) est une méthode qui permet de tenir compte des variables artificielles. 

On les pénalise en leur affectant un coefficient de valeur très élevée dans la fonction économique (- M pour un problème à maximum, + M pour un problème à minimum). Les pénalités ont pour objet de provoquer l'élimination des variables artificielles au fil des itérations. Normalement, à l'optimum (s'il existe) les variables artificielles sont hors base. Si celles-ci sont à l'optimum dans la base, avec une valeur non nulle, le programme n'a pas de solution.

Soit à résoudre le programme linéaire suivant sous sa forme canonique
         5 x1 + 6 x2 ³ 10
         2 x1 + 7 x2 ³ 14
Min  z = 3 x1 + 10 x2
         x1 ³ 0 ;  x2 ³ 0


* Forme standard

               5 x1 +   6 x2 - 1 t1 + 0 t2 +  1 e1   +  0 e2 = 10
               2 x1 +   7 x2 + 0 t1  - 1 t2 +  0 e1  +  1 e2 14
Min   z = 3 x1 + 10 x2 + 0 t1 + 0 t2 + M e1 + M e2
               x1 ³ 0 ;  x2 ³ 0 ;  t1 ³ 0 ;  t2 ³ 0;  e1 ³ 0 ;  e2 ³ 0


* Tableau 0

       HB
B
x1 x2t1 t2e1 e2C
 e16-101 010
 e2270-10 114
 D'1000M

La ligne D' donne les coefficients de la fonction économique, mais pas les valeurs marginales des variables HB; de plus les variables artificielles sont dans la base et devraient donc avoir des valeurs marginales nulles.
De manière générale, dans tout tableau du simplexe, si on note ck les coefficients de la fonction économique et aik les coefficients du tableau, 
* les valeurs marginales mj sont
     - nulles pour les variables dans la base
     - égales à cj - S aik ck  pour les variables hors base, la sommation étant faite sur toutes les variables de la base (les lignes du tableau)
* la valeur de la fonction économique est égale à - S aik ck

d'où le tableau 0 (les calculs annexes ont été rajoutés)

cj31000MM      

 aik ck
       HB
B
x1 x2t1 t2e1 e2C ck x1  x2 t1  t2 C
 e16-101 010 M 5M 6M -M 0 10M
 e2270-10 114 M 2M 7M 0 -M 14M
 D3-7M10-13MMM0-24 M  S aik ck 7M 13M -M -M
 24M


* Tableau 1
Puisqu'on recherche un minimum, la variable entrante est celle qui a le plus grand coefficient négatif, c.à.d. x2. En fait il suffit de regarder le coefficient de M car M est très grand; le coefficient indépendant de M n'intervient que dans le cas où plusieurs variables ont le même coefficient pour M.


       HB
B
x1 x2t1 t2e1 e2C R
 e16-1010105/3 
 e2270-10114
 D3-7M10-13MMM0-24M  
 
 variable sortant
 
 
  variable entrant 
 

la variable artificielle sortant de la base, va se trouver dans la ligne avec un fort coefficient positif et ne pourra donc plus y entrer; on peut donc supprimer la colonne correspondante dans la suite des itérations, d'où le tableau 1

       HB
B
x1 x2t1 t2  e2C
 x25/6 1-1/60  05/3
 e2-23/607/6-1 17/3
 D-16/3+(23/6)M05/3-(7/6)MM -50/3-(7/3)M 


* Tableau 2

       HB
B
x1 x2t1 t2  e2C R
 x25/6 1-1/60 05/3-10 
 e2-23/607/6-1 17/3
 D-16/3+(23/6)M05/3-(7/6)MM -50/3-(7/3)M  
 
 
 variable sortant
 
  variable entrant 
 


d'où le tableau 2

       HB
B
x1 x2t1 t2  C
 x26/21 10-1/7  2
 t1-23/701-6/7  2
 D1/70030/21  -20 

On a atteint la solution optimale qui est   x1 = 0; x2 = 2; t1 = 2; t2 = 0; z = 20.

Remarque: dans le cas particulier de cet exemple qui était sous forme standard, il aurait été plus rapide de traiter le problème dual et d'en déduire la solution du problème primal initial.


Bon courage dans ton travail.

05 Décembre 2011
Imane Hassani
Imane Hassani
Étudiante - Bac+2
Merci CLAUDE et merci LAUREEN vos réponses sont très enrichissantes et vous m'avez aidé c très gentil de votre part encore MILLE MERCI à vous deux :) :) :) :) 
06 Décembre 2011
Judes MBAITOLOUM
Judes MBAITOLOUM
Étudiant - Bac+4 - Sciences de Gestion
il faut un exemple à trois variables pour mieux comprendre. J'espère bien que ça va marcher