Chapitre 3: Autres techniques de la méthode du simplexe :

Variables artificielles, Méthode des deux phases, Méthodes

grand M

1 Introduction
Dans le chapitre précédent tous les programmes linéaires qu’on a traité sont du type :
Maximiser une fonction linéaire sous contraintes de type inférieur ou égale (et avec un second
membre positif).
Or dans beaucoup de problèmes réels, on peut retrouver des contraintes de type supérieur ou
égale et/ou de type égale, ainsi que des problèmes où on a à minimiser au lieu de maximiser.

Dans ce chapitre, on étudiera les modifications à apporter à la méthode du simplexe pour

qu’elle puisse résoudre tous ces types de programmes.

1.1Définition
Une solution de base admissible n’est toujours pas connue à priori, en particulier pour les
problèmes de programmation linéaire déjà sous forme standard. Certains problèmes
n’admettent pas de solution admissible, donc il est impossible de trouver une base de départ.
Si la solution de base n’est pas admissible, il faut introduire une nouvelle phase (appelée
phase 1 ou phase d’initialisation) au simplexe et l’algorithme du simplexe vient en phase 2
pour la résolution du problème.
Cette introduction d’une phase initiale à l’algorithme du simplexe va permettre de déterminer
une base admissible ou prouver que le problème est impossible.
On va voir comment construire des solutions de base réalisable : c’est la phase d’initialisation
du simplexe.

1.2Variables artificielles
Considérons le programme linéaire suivant :
Max 5x1 + 6x2
S.c -x1 + x2 ≤4
5x1 + 3x2 = 60
x2 ≥ 5
x1 ≥ 0 , x2 ≥ 0

L'introduction des variables d'écart dans le programme linéaire donne

Max 5x1 + 6x2
S.c -x1 + x2 + S1 = 4
5x1 + 3x2 = 60
x2 - S2 = 5
x1≥ 0 , x2≥ 0, S1≥ 0, S2≥ 0
Afin de générer une solution réalisable de base initiale pour la méthode de simplexe, on a
annulé les variables de décision x1 et x2. Ceci nous permet de commencer à partir de
l’origine O. Or, on vérifie bien que l’origine n’est pas une solution réalisable car S2 sera
négatif ce qui est en contradiction avec les conditions de non-négativité.
La question qui se pose est comment nous allons réécrire le programme linéaire de manière
qu’on puisse construire le tableau de simplexe initial à l’origine.
Pour arriver à cette fin, on doit ressortir une astuce mathématique qui se résume à
l’introduction de nouvelles variables, appelées variables artificielles. Pour obtenir donc une
solution de base réalisable ou bien pour détecter l’impossibilité, on introduit un problème de
programmation linéaire auxiliaire pour des variables supplémentaires : les variables
artificielles.
Ces variables n’ont aucune interprétation, comme leur nom l’indique, ils sont conçus
artificiellement pour nous aider à utiliser la procédure de simplexe et à formuler le tableau
initial à partir de l'origine.

Au niveau de chaque contrainte qui pose problème en annulant les variables de décision, on
ajoute une variable artificielle. Si on prend A1 et A2 comme variables artificielles qu’on ajoute
respectivement à la 2e et 3e contrainte on a l’expression suivante des contraintes :
-x1 + x2 + S1 = 4
5x1 + 3x2 + A1 = 60
x2 -S2 + A2 = 5
x1≥ 0, x2≥ 0, S1≥ 0, S2≥ 0 , A1 ≥ 0, A2≥ 0

Ainsi, l’introduction de variables artificielles permet de déterminer simplement une base,

certes artificielle, mais admissible pour amorcer l’algorithme.

Si le problème est réalisable, nous devrions avoir une annulation de toutes les variables
artificielles c’est-à-dire qu’elles doivent être toutes hors base. Deux méthodes peuvent être
considérées : la méthode à deux phases et la méthode du grand M.

2 Méthodes des deux phases

La méthode à deux phases se déroule comme suit:
Phase 1 Trouver une solution réalisable en minimisant la somme des variables artificielles.
Phase 2 Optimiser en revenant à la fonction de coût initial à partir de la solution initiale
trouvée dans la phase 1.
Exemple (programme linéaire précédent):
Phase 1
Le programme linéaire auxiliaire se présente comme suit :
Min A1 + A2
S.c -x1 + x2 + S1 = 4
5x1 + 3x2 + A1 = 60
x2 -S2 + A2 = 5
x1≥ 0, x2≥ 0, S1≥ 0, S2≥ 0 , A1 ≥ 0, A2≥ 0
On retient comme solution de base initiale la base artificielle telle que :
– toutes les variables artificielles sont en base (c’est-à-dire non nulles) ;
– toutes les autres variables des contraintes où figurent des variables artificielles (réelles et
d’´écart) sont hors base (c’est-à-dire nulles).
Donc dans l’exemple la base initiale est constituée des variables A1, A2 et S1.
Ensuite on applique l’algorithme du simplexe jusqu’à ce que toutes les variables artificielles
soient supprimées. Donc le problème auxiliaire est résolu par la méthode du simplexe jusqu’à
obtenir une valeur optimale nulle.
Si le programme linéaire a une solution réalisable on passe à la phase 2.
Phase 2
Appliquer l’algorithme du simplexe pour résoudre le problème à partir de la solution de base
réalisable trouvée en phase 1.
Max 5x1 + 6x2
S.c -x1 + x2 + S1 = 4
5x1 + 3x2 + A1 = 60
x2 -S2 + A2 = 5
x1≥ 0, x2≥ 0, S1≥ 0, S2≥ 0 , A1 ≥ 0, A2≥ 0

3 La méthode du grand M

La méthode du grand M consiste à optimiser en utilisant une fonction objective formée de la

fonction de coût initiale et de la somme, très fortement pénalisée, des variables artificielles.
La pénalité est sous la forme d’un coefficient négatif (dans le cas d’un problème de
maximisation) et de valeur absolue très élevée dans la fonction économique originelle.

Tant que les variables artificielles restent dans la base, la solution demeure non réalisable
réellement pour notre programme. Une manière pour garantir que ces variables artificielles
sortent de la base avant d’atteindre la solution optimale est de leur associer un grand coût –M
dans la fonction objectif. Ainsi, si ces variables restent dans la base ils vont causer une
diminution importante de la valeur de la fonction objectif. Ce qui nous contraint à les faire
sortir le plutôt possible de la base.

La fonction objectif s’écrit donc :

Max z = 5x1 + 6x2 - M A1 - M A2
avec M un très grand nombre (exemple: M ≥1010) .

Le programme linéaire devient :

Max z = 5x1 + 6x2 - M A1 - M A2

S.c -x1 + x2 + S1 = 4
5x1 + 3x2 + A1 = 60
 x2 -S2 + A2 = 5
x1≥ 0, x2≥ 0, S1≥ 0, S2≥ 0 , A1 ≥ 0, A2≥ 0

De même, on applique l’algorithme du simplexe jusqu’à ce que toutes les variables

artificielles soient supprimées et qu’on obtienne une solution de base admissible.
Cette base n’est plus artificielle mais réelle. La procédure doit ensuite être poursuivie jusqu’à
l’obtention de l’optimum, sans tenir compte des colonnes concernant les variables artificielles.

Remarque: cas où le second membre négatif

Le problème qui peut se poser est que l’une des variables du second membre soit négative.
Par exemple supposons que lors de la formulation on trouve une contrainte de ce type :
x1 - x2 ≥ -4
La condition qu’il faut vérifier avant de se lancer dans la réécriture de cette contrainte, en vue
de construire le programme standard, est la non-négativité du second membre.
Ainsi, on doit modifier la contrainte avant de commencer la standardisation et la réécrire
comme suit :
-x1 + x2 ≤ 4
Exercice :
Réécrire convenablement ces contraintes:
(1) x1 + 3x2 - 5x3 = - 20
(2) -x1 + 3x2 ≥ - 5
(3) 5x1 - 2x2 ≤ - 10

4 Problèmes de minimisation et problèmes irréguliers

4.1 Problèmes de minimisation

ll y a deux manières de résoudre un problème de minimisation en utilisant la méthode de
simplexe.
La première méthode nécessite le changement de la règle de choix de la variable entrante.
Dans un problème de maximisation la règle est de choisir comme variable entrante celle qui a
le plus grand effet net positif non nul. Ceci parce que notre objectif est de choisir la variable
qui en entrant dans la base va engendrer un profit supplémentaire et ainsi accroître la valeur
de la fonction objectif. Pour un problème de minimisation, on va utiliser la règle
inverse. C’est-à-dire la variable entrante est celle à laquelle on associe la plus petite valeur
négative non nulle de l’effet net.
Ceci va nous amener aussi à changer notre règle d’arrêt de la procédure de simplexe et de
définir le tableau optimal, comme celui où tous les effets nets
sont positifs ou nuls.
Par exemple supposons qu’on veuille appliquer la méthode de simplexe sur le problème de
suivant:
 Min x1 + x2
Sc 2x1 + x2 ≥ 12
5x1 + 8x2 ≥ 74
x1 + 6x2 ≥ 24
x1 ≥ 0 , x2 ≥ 0
Pour permettre à la méthode de simplexe de démarrer de l’origine, il faut comme on l’a déjà
vu dans le cas de problème de maximisation, introduire les variables artificielles.
Avec les problèmes de maximisation on attribue à ces variables un coefficient
-M dans la fonction objectif pour les contraindre à quitter la base rapidement. Dans le cas de
problèmes de minimisation, on a intérêt à changer le coefficient de ces variables en M (M très
grand) afin d’arriver au même résultat et de les faire sortir de la base.
Avant de construire le tableau de simplexe initial, on réécrit le programme linéaire avec les
variables artificielles.
Min x1 + x2 + MA1 + MA2+ MA3
Sc 2x1 + x2 - S1 + A1 = 12
5x1 + 8x2 - S2 + A2 = 74
x1 + 6x2 - S3 + A3 = 24
x1 , x2 , S1 , S2 , S3 , A1 , A2, A3 ≥ 0
Le tableau suivant résume les étapes de la méthode du simplexe relatif aux problèmes de
maximisation et minimisation :

Etape Maximisation Minimisation

1 Formuler un programme linéaire pour le Formuler un programme linéaire pour le
problème réel. problème réel.
2 Vérifier que le second membre Vérifier que le second membre
du programme linéaire est positif sinon du programme linéaire est positif sinon
modifier les contraintes modifier les contraintes
3 Écrire le programme linéaire sous une Écrire le programme linéaire sous une
forme standard forme standard
4 Construire le premier tableau de simplexe Construire le premier tableau de simplexe
5 Choisir comme variable entrante dans la Choisir comme variable entrante dans la
base celle qui admet le plus grand effet net base celle qui admet le plus petit effet net
positif. négatif.
6 Choisir la variable sortante de la base celle Choisir la variable sortante de la base
qui admet le plus petit ratio supérieur à celle qui admet le plus petit
 zéro. ratio supérieur à zéro.
7 Construire le nouveau tableau en utilisant Construire le nouveau tableau en utilisant
la règle de pivot la règle de pivot
8 Faire le test d’optimalité. Si Faire le test d’optimalité. Si
les effets sont ≤ 0 pour toutes les variables les effets ≥ 0 pour toutes les variables
(hors base) donc la solution obtenue est (hors base) donc la solution obtenue est
optimale. Sinon retourner à l’étape 5. optimale. Sinon retourner à l’étape 5.

La deuxième méthode pour résoudre un problème de minimisation se base sur le résultat

suivant « Résoudre un problème min ctx sujet à un ensemble de contraintes est équivalent à
résoudre un problème max -ctx sujet au même ensemble de contraintes ». Ces deux problèmes
sont équivalents dans la mesure où ils donnent le même vecteur des solutions optimales. La
seule différence est que la valeur de la solution max -ctx est l’opposé de la solution de min
ctx; (i.e. min ctx = - max -ctx).
Donc pour résoudre le programme linéaire relatif à l’exemple, on peut résoudre le problème
de maximisation suivant:
Max - x1 - x2
S.c. 2x1 + x2 ≥ 12
5x1 + 8x2 ≥74
x1 + 6x2 ≥ 24
x1 , x2 ≥ 0
On peut vérifier facilement que la méthode de simplexe appliquée au programme ci-dessus,
engendre le même vecteur de solutions optimales.

4.2 Problèmes irréguliers

4.2.1 Solutions non bornées

On considère l’exemple suivant :

En résolvant graphiquement ce problème on remarque que la solution optimale n’existe pas

puisque l’ensemble convexe des solutions réalisables n’est pas borné et la fonction objectif
peut augmenter dans ce cas sans limite.
Appliquons l’algorithme du simplexe à cet exemple : la solution (x, y) = (0, 0) est admissible.
 e2

Aucun coefficient de la colonne sélectionnée n’est positif donc la colonne C ne donne aucune
valeur positive non infinie, x peut donc augmenter indéfiniment et la fonction objectif Z
également. On dira dans ce cas que la valeur maximale n’existe pas, le problème n’admet pas
de solution optimale.

4.2.2 Solutions multiples

Lorsqu’on utilise la méthode de simplexe, on identifie ce problème lorsqu’un des effets nets
(relatif à une variable hors base) est nul.

Exercice : On se donne le programme linéaire suivant :

Vérifier que ce problème a de multiples solutions.

4.2.3 Solutions impossibles

Le système de contraintes peut n’avoir aucune solution. Généralement, cela provient d’une
mauvaise formulation du problème.
Avec la méthode de simplexe, on reconnaît que le problème est impossible si une ou plusieurs
variables artificielles sont présentes dans la base dans le tableau de simplexe optimal, ce qui
signifie que la solution donnée par ce tableau n’est pas réellement réalisable.
Exercice: Vérifions à l’aide de la méthode de simplexe, que le problème suivant est
réellement impossible :

Max 4 x1 + 3x2
Sc x1 + x2 ≤ 2
3x1 + x2 ≥ 10
x1, x2 ≥ 0

Exercice d'application: Résoudre le problème de M. Zop du chapitre 1