← Retour au blog••10 min de lecture

Comprendre la Méthode du Grand M en Programmation Linéaire (Exemple Pas à Pas)

Maîtrisez la méthode du Grand M pour les contraintes >= et = en Programmation Linéaire. Différence entre écart, excédent et variables artificielles avec un exemple pas à pas.

Solveur Interactif

Essayez le Calculateur de Simplexe et de Sensibilité Étape par Étape

Saisissez votre fonction objectif et vos contraintes pour voir chaque tableau d'itération, les pivots et l'analyse de sensibilité en direct.

Ouvrir le Solveur Simplexe →

Pourquoi la méthode du Grand M est-elle nécessaire ?

L'algorithme du simplexe standard démarre spontanément lorsque toutes les contraintes sont du type ≤ avec seconds membres positifs, les variables d'écart fournissant une base unitaire immédiate à l'origine $(x=0)$. Toutefois, lorsque des contraintes comportent des signes ≥ ou d'égalité stricte =, l'origine n'est pas réalisable. La Méthode du Grand M permet de contourner cet obstacle en introduisant des variables artificielles pénalisées dans notre Calculateur de la Méthode du Simplexe.

Variables d'Écart, d'Excédent et Artificielles

  • Variables d'Écart ($s_i ≥ 0$) : Ajoutées aux contraintes ≤ ($+s_i$). Représentent la capacité résiduelle non utilisée.
  • Variables d'Excédent ($e_i ≥ 0$) : Soustraites des contraintes ≥ ($-e_i$). Mesurent le surplus au-delà du seuil minimal. À $x=0$, $-e_i = b_i ⇒ e_i = -b_i < 0$, violant la non-négativité.
  • Variables Artificielles ($a_i ≥ 0$) : Ajoutées ($+a_i$) aux contraintes ≥ et =. Elles n'ont aucune signification concrète et servent uniquement d'artifice algébrique pour amorcer le simplexe.

La Pénalité du Grand M dans la Fonction Objectif

  • En Maximisation : On retranche $M \times a_i$ : $\max Z = \sum c_j x_j - M \sum a_i$.
  • En Minimisation : On ajoute $M \times a_i$ : $\min Z = \sum c_j x_j + M \sum a_i$.

Exemple Numérique Résolu Pas à Pas

Soit le programme linéaire suivant, vérifiable sur notre Calculateur de la Méthode du Simplexe :

  Maximiser   Z = 3x₁ + 5x₂
  Sous contraintes :
    x₁ +  x₂ ≥ 2     (Contrainte 1 : Exigence minimale)
   2x₁ + 3x₂ ≤ 12    (Contrainte 2 : Disponibilité de ressource)
    x₁, x₂ ≥ 0
        

Étape 1 : Mise sous Forme Standard

  • Contrainte 1 (≥) : $x_1 + x_2 - e_1 + a_1 = 2$
  • Contrainte 2 (≤) : $2x_1 + 3x_2 + s_2 = 12$
  • Variables : $x_1, x_2, e_1, s_2, a_1 ≥ 0$. Base initiale : ${a_1, s_2}$.

Étape 2 : Opération Préalable sur la Ligne Z

L'équation de l'objectif s'écrit $Z - 3x_1 - 5x_2 + M a_1 = 0$. On élimine $a_1$ de la ligne Z en soustrayant $M \times (\text{Ligne } 1)$ :

  Nouvelle Ligne Z = [Z - 3x₁ - 5x₂ + M a₁] - M × [x₁ + x₂ - e₁ + a₁ = 2]
  ⇒ Z - (3 + M)x₁ - (5 + M)x₂ + M e₁ + 0s₂ + 0a₁ = -2M
        

Étape 3 : Tableau Simplexe Initial (Itération 0)

Basex₁x₂e₁s₂a₁MDRatio Minimum
Z-(3 + M)-(5 + M)M00-2M—
a₁11-10122 / 1 = 2 (min) ← Ligne Pivot
s₂230101212 / 3 = 4

Étape 4 : Itération 1

La variable entrante est $x_2$ (coût le plus négatif $-(5+M)$) et la sortante est $a_1$ (ratio minimum 2). Le pivot est 1 sur la ligne $a_1$. Après pivotage de Gauss-Jordan, $a_1$ quitte la base et le terme $M$ s'annule du membre de droite (MD) :

Basex₁x₂e₁s₂a₁MDRatio Minimum
Z20-505 + M10—
x₂11-1012-1 ≤ 0 (ignoré)
s₂-1031-366 / 3 = 2 ← Ligne Pivot

Étape 5 : Itération 2 (Tableau Final Optimal)

La variable $e_1$ entre et $s_2$ sort. Le pivot est 3 sur la ligne $s_2$ :

Basex₁x₂e₁s₂a₁MD
Z1/3005/3M20
x₂2/3101/304
e₁-1/3011/3-12

Interprétation et Validation

Tous les coûts réduits de la ligne Z sont positifs ou nuls ($1/3 ≥ 0, 5/3 ≥ 0, M ≥ 0$). La solution optimale est validée :

  • Variables de décision : $x_1^* = 0$, $x_2^* = 4$.
  • Écart et excédent : $e_1 = 2$ (contrainte 1 satisfaite avec un excédent de 2), $s_2 = 0$ (contrainte 2 saturée).
  • Valeur optimale : $Z^* = 3(0) + 5(4) = 20$.
  • Réalisabilité : $a_1 = 0$, aucune variable artificielle ne subsiste.

Vous pouvez visualiser ce polyèdre sur notre Calculateur de la Méthode Graphique.

Grand M vs Méthode des Deux Phases

Bien que didactique, le Grand M peut être sujet à des imprécisions numériques sur ordinateur. En pratique logicielle, on privilégie souvent la Méthode des Deux Phases.

Erreurs Fréquentes

  1. Oublier l'élimination préalable de $M$ dans la ligne Z avant la première itération.
  2. Erreur de signe sur $M$ ($-M$ en maximisation, $+M$ en minimisation).
  3. Division par un nombre négatif dans le test du ratio minimum.
  4. Consultez également notre article sur les prix implicites en analyse de sensibilité.

Prêt à résoudre votre propre programme linéaire ?

Obtenez instantanément des solutions pas à pas avec analyse de sensibilité et prix implicites pour tout problème de PL.

Lancer le Calculateur Simplexe