LP : méthode du grand M

Méthode du grand M

Lorsque le simplexe possède des variables artificielles, il est possible de ne pas trouver de solution de départ évident (tester si l’origine est dans le domaine de définition). Dans ce cas il faut trouver une solution de départ avec la méthode du grand M.

Cette méthode calcule un problème auxiliaire avant de résoudre le simplexe du programme linéaire, c’est pourquoi on parle d’un simplexe en deux phases.

Pourquoi une variable artificielle ?

Avant d’expliquer comment obtenir une solution pour commencer le simplexe, il est important de comprendre pourquoi il est nécessaire de rajouter une variable artificielle en plus de la variable d’écart.

Prenons comme exemple le programme linéaire suivant :

Rajoutons les variables d’écarts :

Le simplexe commence en prenant les variables de base à zéro, donc avec le vecteur suivant (0, 0, -19, 32). Cela est impossible car X3 ne peut pas prendre de valeur négative. C’est pourquoi il faut rajouter une nouvelle variable, qui sera donc artificielle.

Ici le vecteur (0, 0, 0, 19, 32) est une solution réalisable. Mais puisqu’il s’agit d’une variable artificielle, il faut pouvoir l’enlever du Simplexe afin de pouvoir trouver une solution globale. Il faut donc que X5=0. Pour vérifier si cela est possible, nous cherchons à minimiser X5.

Construction de la Phase 1

On prépare de manière analogue à le tableau initiale de la méthode du Simplexe, mais avec quelques différences. En reprenant l’exemple précédent, nous cherchons à résoudre le problème suivant :

Nous savons que seul X4 et X5 sont dans la base, donc la première étape est d’exprimer la fonction objectif avec les variables hors base (ici X1, X2, X3). Dans l’exemple, cela est possible grâce à la première contrainte.

La première étape consiste à résoudre le programme linéaire suivant :

Phase 2

La deuxième phase de la méthode des Deux Phases est élaborée exactement comme la méthode du Simplexe, sauf qu’avant de commencer les itérations il faut supprimer les colonnes correspondantes aux variables artificielles, et reconstruire le tableau d’origine.

• Supprimer les colonnes de variables artificielles : Si nous sommes parvenus à la conclusion que le problème initial a une solution, on doit préparer notre tableau pour la deuxième phase. Cette étape est très simple, il suffit de supprimer les colonnes correspondantes aux variables artificielles.
• Reconstruction du tableau initial : Le tableau initial, dans ce cas, reste à peu près égal au dernier tableau de la première phase. La ligne de la fonction objectif devrait être modifié seulement par celle du problème initial et recalculer la ligne Z (de la même manière que dans le premier tableau de la phase 1).

La condition d’arrêt est la même que dans la méthode du Simplexe. Autrement dit, lorsque dans la ligne indicatrice aucun des valeurs des coûts réduits est négatif (car nous sommes dans le cas d’une maximisation).

Le simplexe précédent donne pour solution optimale Z=0 avec le vecteur (0, 19/3, 0, 20/3, 0). Cela signifie qu’il est possible de se passer de la variable artificielle et que la solution trouvée est dans l’espace de définition du problème initial (puisque X5 n’intervient pas et qu’elle est hors base). La solution finale donne le simplexe suivant :

La dernière étape de la phase 1 consiste à reprendre la fonction objectif initiale (ici -2X1 – X2) et de remplacer toutes les variables de bases par des variables hors bases (ici X2 et X4 sont dans la base, X1 et X3 sont hors bases).

Nous avons pour la première contrainte X2 = 19/3 – 2/3X1 + 1/3X3, nous pouvons donc réécrire la fonction objectif par : Z = – 4/3X1 – 1/3X2 -19/3.

À partir de ce point, toutes les itérations, jusqu’à atteindre la solution optimale du problème, ne montrent aucune différence avec la méthode du Simplexe.

Algorithme du simplexe

Voici l’algorithme du simplexe revisité :