LP : méthode du grand M

Lorsque le problème linéaire possède des contraintes avec bi négatif ainsi que des contraintes égalités (sans variables d’écart), alors il est complexe de trouver une solution de départ. Il faut alors utiliser la méthode du grand M qui consiste à rajouter des variables artificielles ayant un grand impact sur la fonction objectif (négatif si max, positif si min) avec des bi positifs. Voici un exemple de problème linéaire avant et après la transformation du grand M :

LP28

Ce qui donne la résolution du simplexe suivant :

LP29

Le vecteur solution est (6, 10, 0, 5, 0, 0), nous pouvons donc enlever les variables artificielles est partir du vecteur (6, 10, 0, 5) afin de résoudre le simplexe. Il faut alors continuer la résolution du simplexe en retirant les colonnes en grand M.

Publicités