La Méthode des Deux Phases en Programmation Linéaire (Guide Pas à Pas)
Apprenez à résoudre les programmes linéaires avec variables artificielles grâce à la méthode des deux phases, une alternative numériquement stable au Grand M.
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 privilégier la Méthode des Deux Phases ?
Pour amorcer le simplexe en présence de contraintes $\ge$ ou $=$, la méthode du Grand M introduit une constante artificielle (consultez notre guide de la Méthode du Grand M) $M$, susceptible d'engendrer des instabilités de précision numérique sur ordinateur. La méthode des deux phases résout élégamment cette difficulté en scindant la recherche de faisabilité et l'optimisation en deux étapes rigoureuses.
Exemple d'Application sous Forme Standard
Soit le programme linéaire :
Maximiser Z = 2x₁ + 3x₂
Sous contraintes :
x₁ + x₂ ≤ 4 (contrainte 1)
x₁ + 2x₂ ≥ 6 (contrainte 2)
x₁, x₂ ≥ 0
Sous forme standard :
- Contrainte 1 (≤) : x₁ + x₂ + s₁ = 4
- Contrainte 2 (≥) : x₁ + 2x₂ − s₂ + a₁ = 6
Phase I : Recherche d'une Solution Réalisable de Base
On écarte provisoirement la fonction objectif d'origine et l'on minimise la somme des variables artificielles :
Minimiser W = a₁
Si la valeur minimale de $W$ atteint zéro, toutes les variables artificielles sont chassées de la base, fournissant une Solution Réalisable de Base (SRB) initiale pour le problème originel.
Tableau Initial de la Phase I
| Base | x₁ | x₂ | s₁ | s₂ | a₁ | MD |
|---|---|---|---|---|---|---|
| W | 1 | 2 | 0 | −1 | 0 | 6 |
| s₁ | 1 | 1 | 1 | 0 | 0 | 4 |
| a₁ | 1 | 2 | 0 | −1 | 1 | 6 |
Itération de la Phase I
- Variable entrante : Colonne x₂ (coefficient 2).
- Ratio minimum : Ligne a₁ (6/2 = 3). La variable a₁ quitte la base.
- Pivot : Coefficient 2 sur la ligne a₁.
Tableau après pivotage :
| Base | x₁ | x₂ | s₁ | s₂ | a₁ | MD |
|---|---|---|---|---|---|---|
| W | 0 | 0 | 0 | 0 | −1 | 0 |
| s₁ | 1/2 | 0 | 1 | 1/2 | −1/2 | 1 |
| x₂ | 1/2 | 1 | 0 | −1/2 | 1/2 | 3 |
W = 0. Les variables artificielles sont totalement éliminées. La Phase I est accomplie avec succès !
Phase II : Optimisation de la Fonction Objectif Initiale
On supprime la colonne de la variable artificielle a₁. On réintroduit la fonction objectif originale $Z = 2x_1 + 3x_2$ exprimée en fonction des variables hors base actuelles.
Tableau Final de la Phase II
| Base | x₁ | x₂ | s₁ | s₂ | MD |
|---|---|---|---|---|---|
| Z | 2 | 0 | 3 | 0 | −12 |
| s₂ | 1 | 0 | 2 | 1 | 2 |
| x₂ | 1 | 1 | 1 | 0 | 4 |
Tous les coefficients de la ligne Z sont positifs ou nuls. Validez ce calcul sur notre Calculateur du Simplexe. → solution optimale atteinte :
- x₁ = 0, x₂ = 4, Z = 12
- s₂ = 2 (la contrainte 2 dispose d'un surplus de 2 unités).
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.