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.
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.
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)
| Base | x₁ | x₂ | e₁ | s₂ | a₁ | MD | Ratio Minimum |
|---|---|---|---|---|---|---|---|
| Z | -(3 + M) | -(5 + M) | M | 0 | 0 | -2M | — |
| a₁ | 1 | 1 | -1 | 0 | 1 | 2 | 2 / 1 = 2 (min) ← Ligne Pivot |
| s₂ | 2 | 3 | 0 | 1 | 0 | 12 | 12 / 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) :
| Base | x₁ | x₂ | e₁ | s₂ | a₁ | MD | Ratio Minimum |
|---|---|---|---|---|---|---|---|
| Z | 2 | 0 | -5 | 0 | 5 + M | 10 | — |
| x₂ | 1 | 1 | -1 | 0 | 1 | 2 | -1 ≤ 0 (ignoré) |
| s₂ | -1 | 0 | 3 | 1 | -3 | 6 | 6 / 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$ :
| Base | x₁ | x₂ | e₁ | s₂ | a₁ | MD |
|---|---|---|---|---|---|---|
| Z | 1/3 | 0 | 0 | 5/3 | M | 20 |
| x₂ | 2/3 | 1 | 0 | 1/3 | 0 | 4 |
| e₁ | -1/3 | 0 | 1 | 1/3 | -1 | 2 |
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
- Oublier l'élimination préalable de $M$ dans la ligne Z avant la première itération.
- Erreur de signe sur $M$ ($-M$ en maximisation, $+M$ en minimisation).
- Division par un nombre négatif dans le test du ratio minimum.
- 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.