← Retour au blog••10 min de lecture

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.

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 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

Basex₁x₂s₁s₂a₁MD
W120−106
s₁111004
a₁120−116

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 :

Basex₁x₂s₁s₂a₁MD
W0000−10
s₁1/2011/2−1/21
x₂1/210−1/21/23

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

Basex₁x₂s₁s₂MD
Z2030−12
s₂10212
x₂11104

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.

Lancer le Calculateur Simplexe