RECHERCHE OPERATIONNELLE

Programmation Linéaire — Méthode du Simplexe

Entrez votre fonction objectif et vos contraintes. L'outil transforme le problème en forme standard, résout par la méthode du simplexe (Big M) en affichant chaque itération, puis visualise la solution avec la méthode graphique.

1. Fonction objectif (2 variables : x1, x2)

Z = x1 + x2

2. Contraintes

Forme standard

Itérations du Simplexe

Méthode graphique

Comprendre la méthode du simplexe

1. Mise en forme standard

On transforme chaque inégalité en égalité :

  • Pour une contrainte ≤ : on ajoute une variable d'écart (s), coefficient 0 dans Z.
  • Pour une contrainte ≥ : on soustrait une variable de surplus (e) et on ajoute une variable artificielle (a).
  • Pour une contrainte = : on ajoute directement une variable artificielle (a).

Les variables artificielles reçoivent un coût −M (M très grand) dans Z, pour les forcer à sortir de la solution le plus vite possible : c'est la méthode du Big M.

2. Construction du tableau

Chaque tableau contient : les Variables de Base (VB), les coefficients de chaque variable, la colonne RHS (second membre), et la colonne Ratio (RHS ÷ coefficient de la colonne entrante, utilisée uniquement pour le test de sortie).

En bas du tableau :

  • Cz : coût de chaque variable actuellement en base
  • Zj = Σ (Cz × coefficient de la colonne)
  • Δj = Cj − Zj (aussi appelé coût réduit)

3. Règle d'entrée et de sortie

Variable entrante : la colonne avec le Δj le plus positif (on cherche à améliorer Z).

Variable sortante : parmi les lignes où le coefficient de la colonne entrante est > 0, celle qui donne le plus petit ratio RHS ÷ coefficient (règle du minimum, pour rester dans la zone faisable).

L'élément à l'intersection (ligne sortante, colonne entrante) est le pivot.

4. Le pivotage

  • On divise toute la ligne du pivot par la valeur du pivot (le pivot devient 1)
  • Pour chaque autre ligne : nouvelle ligne = ancienne ligne − (coefficient de la colonne entrante × ligne du pivot normalisée), pour annuler la colonne entrante partout ailleurs

5. Critère d'arrêt

On s'arrête dès que tous les Δj ≤ 0 : la solution est optimale. On lit alors les valeurs des variables de base dans la colonne RHS (les variables hors base valent 0), et Z se lit dans la colonne RHS de la ligne Z.

Cas particuliers : si une colonne entrante n'a aucun coefficient positif, le problème est non borné. Si une variable artificielle reste positive à l'optimum, le problème est infaisable (aucune solution ne respecte toutes les contraintes).