Chapitre 7: programmation linéaire
III- Algorithme du simplexe (Méthode des tableaux)
1- Définitions.
Lorsqu’on considère un programme linéaire ayant plus de deux variables, la résolution graphique devient
difficile, mais les propriétés restent les mêmes.
L’algorithme du simplex (G. B. Dantzig 1947) est un algorithme récursif qui permet théoriquement de
résoudre un problème de programmation linéaire d’un nombre quelconque de variables.
Il existe de nombreuses variantes de cet algorithme, comme l’algorithme du simplexe sous forme
algébrique, l’algorithme du simplexe sous forme matricielle et l’algorithme du simplexe sous forme des
tableaux, dans ce cours, nous utiliserons la variante tabulaire.
2- La méthode du simplexe
La méthode du simplexe repose sur les étapes fondamentales suivantes :
– Si un programme linéaire admet une solution possible finie, alors il admet au moins une solution de base.
– Si ce programme linéaire admet une solution optimale, il admet au moins une solution de base optimale
(ce qui signifie qu’une solution de base au moins est optimale).
La solution optimale étant une solution de base, l’algorithme du simplexe consiste à :
1. déterminer une solution de base,
2. faire subir un test d’optimalité à cette solution de base pour déterminer s’il s’agit ou non de la solution
optimale,
– s’il s’agit de la solution optimale, le problème est terminé,
– s’il ne s’agit pas de la solution optimale, on passe à l’étape 3,
3. changer de solution de base puis reprendre la procédure au 1. Jusqu’ à l’obtention de la solution optimale.
Chaque changement de solution de base constitue une itération.
Afin de réaliser les opérations successives de l’algorithme du simplexe, il convient de mettre le programme
sous une forme standard.
3- Algorithme du simplexe en tableaux
L’algorithme du simplexe comporte 4 étapes dont les 3 dernières sont répétées à chaque itération. La
méthode des tableaux du simplexe permet d’appliquer toutes les étapes de l’algorithme du simplexe sous
forme d’une séquence de tableaux représentés par la figure suivant :
B b x1 x2 ... xn xn+1xn+2 ... xn+
m
xn+1 b1 a11 a12 ... a1n 1 0 ... 0
xn+2 b2 a21 a22 ... a2n 0 1 ... 0
... 0
. . . . . . . .
xn+ bm am1 am2 ... amn 0 0 ... 1
m
z −zB c1 c2 ... cn 0 0 ... 0
Étape 1 :
Dans le cas où toutes les contraintes initiales d’un programme linéaire se présentent sous forme de
contraintes d’inégalités du type "inférieur ou égal" avec un membre de droite positif, on réécrit d’abord le
programme sous forme standard en ajoutant des variables d’écart. Puis on met les variables de décisions
(variables originales) hors base et les variables d’écart en base. On indique en section suivante comment
construire le tableau initial dans le cas d’un programme linéaire quelconque.
Étape 2 :
Si les coefficients cj sont tous ≤ 0, alors STOP : la solution de la base actuelle est optimale. Sinon, choisir la
variable hors base dont le coefficient dans la dernière ligne est positif et le plus grand possible. Soit xr la
variable entrante.
Soit xr telle que cr ≥ cj , pour tout cj ≥ 0
On colore la colonne correspondante qui est appelée colonne pivot. Il en résulte le tableau suivant :
B b x1 ... xr ... xn xn+1xn+2 ... xn+
m
xn+1 b1 a11 ... a1r ... a1n 1 0 ... 0
xn+2 b2 a21 ... a2r ... a2n 0 1 ... 0
... 0
. . . . . . . . .
xn+ bm am ... amr ... am 0 0 ... 1
m 1 n
z −zB c1 ... cr ... cn 0 0 ... 0
Étape 3 :
Choisir comme variable sortante la première variable de base à s’annuler. Pour cela, on calcule le minimum
du rapport du second membre bi sur le coefficient air de la variable entrante dans la même ligne lorsque air >
0. Soit ℓ la ligne où le minimum se produit :
La variable sortante est celle qui correspond à la ligne où le minimum se produit.
Soit xs la variable sortante.
On colore la ligne correspondante qui est appelée ligne pivot. Il en résulte le tableau suivant :
Le pivot est le nombre qui se trouve à l’intersection de la colonne pivot et la ligne pivot.
Dans la section gauche du nouveau tableau, on remplace la variable sortante xs par la variable entrante xr.
Étape 4 :
Cette étape permet de construire un nouveau tableau de simplexe à partir du tableau précédent. Elle
comprend trois opérations :
• Ligne de pivot : pour obtenir la ligne du pivot transformée, il suffit de diviser tous ses éléments par
le pivot.
• Colonne de pivot : pour obtenir la colonne du pivot transformée, il suffit de remplacer tous ses
éléments par 0 sauf la place du pivot.
• Ailleurs : pour obtenir la transformée des autres nombres, il suffit d’appliquer la règle du rectangle
Si a est l’élément de l’ancien tableau (bi, aij (i ≠s, j ≠r), −zB, cj) dont on cherche la transformée a′, asr est le
pivot et b, c les éléments permettant de construire un rectangle à partir de a et asr,
Alors a′, la transformée de a, s’obtient en retranchant à a le produit b×c divisé par le pivot asr
Remarque :
Toute ligne possédant un zéro dans la colonne du pivot reste inchangée; de même, toute colonne possédant
un zéro dans la ligne du pivot reste inchangée.
4- Illustration de l’algorithme
Exemple On se donne le programme linéaire exprimé sous sa forme canonique suivant :
Max Z =300x1+500x2
SC : x1 ≤4
2x2 ≤12
3x1+2x2 ≤18
x1 ≥0, x2 ≥ 0
Le programme linéaire peut se réécrire alors sous sa forme standard on introduit des variables auxiliaires
positives ou nulles appelées variables d'écart de la façon suivante :
Max Z =300x1+500x2
SC : x1+x3 =4
2x2 +x4 =12
3x1+2x2+x5=18
x1, x2, x3, x4, x5 ≥ 0
On exprime le problème sous forme matricielle, où:
Nous allons maintenant voir commet effectuer les procédures de l’algorithme du simplexe en utilisant les
tableaux.
4.1 Tableau initial
On construit un tableau initial du simplexe, qui se compose du vecteur b, de la matrice A, et d’une ligne
[0, c] situés sous les précédents où 0 correspond à la valeur de z à l’origine (lorsque x1 = x2 = 0) :
On a ajouté au-dessus du tableau le nom des variables pour voir à quelle variable correspond chaque colonne
du tableau. Plusieurs caractéristiques d’un tableau simplex sont à remarquer
• Tout d’abord, on peut lire directement sur le tableau les valeurs des variables de base.
Si x1 = x2 = 0, on obtient x3 = 4, x4 = 12 et x5 = 18. Soit xB = b.
• Dans la dernière ligne, on trouve un coefficient égal à 0 pour chaque variable de base
(La fonction z est exprimée en fonction des seules variables hors base).
• La matrice carrée correspondant aux variables de base est la matrice identité.
• Enfin, le premier coefficient de la dernière ligne donne l’opposé de la valeur de z
4.2 Pivot et changement de base
Pour augmenter la valeur de z, on examine une nouvelle solution de base.
Pour l’obtenir, on doit introduire une nouvelle variable dans la base et exclure une des variables qui y
figurait précédemment. On appelle changent de base le processus qui consiste à choisir la variable
entrante et la variable sortante.
Choix de la variable entrante
Dans la dernière ligne, le coefficient dont la valeur est la plus élevée détermine la variable à entrer dans la
base. Donc la variable entrante est x2.
On indique ceci dans le tableau en colorant la colonne de la variable entrante que l’on appelle la colonne
pivot.
variable entrante
B b x1 x2 x3 x4 x5
x3 4 1 0 1 0 0
x4 12 0 2 0 1 0
x5 18 3 2 0 0 1
z 0 300 500 0 0 0
Colonne pivot
Choix de la variable sortante
On choisit la variable sortante comme étant la variable de base qui s’annule la première. Cela revient à
calculer le minimum du rapport du coefficient du membre de droite de chaque contrainte sur le coefficient
correspondant de la colonne pivot lorsque ce dernier est strictement positif.
Min 12/2 et 18/2 = 6
Dans le cas où le coefficient dans la colonne entrante est négatif ou nul, la ligne n’entre pas en compte
dans le calcul du minimum. Illustrons ceci sur un exemple. Supposons que le coefficient de x2 dans la
première contrainte soit −1 à la place de 0.
L’équation correspondante se récrit de manière équivalente comme suit :
x1=4+x2
Quelle que soit la valeur de x2 ≥ 0, la variable de base x1 reste positive.
La variable sortante est alors la variable de base dont la valeur se lit dans la ligne où le minimum se produit
: ici, il s’agit de la deuxième ligne et donc de la variable x4.
On encadre alors la ligne où le minimum se produit. Cette ligne reçoit le nom de ligne pivot :
On appelle nombre pivot ou pivot le coefficient situé à l’intersection de la colonne pivot et de la ligne
pivot.
C’est donc le centre de la croix ainsi formée par la ligne et la colonne pivot.
4.3 Pivotage et tableaux simplexe
Le pivotage est le processus qui consiste à amener la colonne de la variable sortante en lieu et place de la
variable entrante. Le pivot nous permettra de transformer le tableau actuel en un deuxième tableau
correspondant à la nouvelle base. Ceci peut
1. Transformation de la ligne pivot : pour obtenir la ligne du pivot transformée, il suffit de diviser
tous ses éléments par le pivot.
2. Transformation de la colonne pivot : après avoir ramené par division le pivot à 1, tous les éléments
situés au-dessus et au-dessous du pivot deviennent zéro.
B b x1 x2 x3 x4 x5 B b x1 x2 x3 x4 x5
x3 4 1 0 1 0 0 x3 4 1 0 1 0 0
x4 1 x2 1
6 0 1 0 0 6 0 1 0 2 0
2
x5 18 3 2 0 0 1 x5 18 3 0 0 0 1
z 0 300 500 0 0 0 z 0 300 0 0 0 0
3. Transformation des autres cases du tableau : la transformée des autres nombres, il suffit d’appliquer la
règle dite du rectangle :
b×c
a′ = a −
pivot
• a′ est la valeur modifiée du coefficient a qui est considéré
• b est l’élément situé sur la même ligne que a, mais dans la colonne du pivot
• c est l’élément situé dans la même colonne que a, mais sur la ligne du pivot
B b x2 xj
b a
x4 2 c
z
Dans le tableau à modifier, le pivot et les coefficients a, b et c forment les coins d’un rectangle. D’où le
nom de la méthode.
Remarquons que la règle du rectangle implique :
• Si une ligne contient un 0 à l’intersection avec la colonne du pivot, cette ligne ne sera pas modifiée.
• Si une colonne contient un 0 à l’intersection avec la ligne du pivot, cette colonne ne sera pas
modifiée.
En appliquant ces opérations au tableau initial, on obtient le deuxième tableau :
B b x1 x2 x3 x4 x5
x3 4 1 0 1 0 0
1
x2 6 0 1 0 0
2
x5 6 3 0 0 −1 1
z −3000 300 0 0 −250 0
On peut lire directement sur ce tableau la deuxième solution de base réalisable.
En posant x1 = x4 = 0, nous conservons une matrice identité qui donne :
x2 = 6, x3 = 4 et x5 = 6.
Le premier coefficient de la dernière ligne (ici, -3000) donne l’opposé de la valeur z dans la deuxième
solution de base réalisable :
Deuxième solution de base : xB2 = (0, 6, 4, 0, 6)
Valeur de la fonction z en xB2 : z2 = 3000
4.4 Deuxième itération
Le maximum de la fonction z est atteint lorsqu’il n’y a plus de coefficients positifs dans la dernière ligne.
On poursuit les changements de base et les pivotages, conformément aux règles exposées ci-dessus, jusqu’à
ce qu’on y parvienne.
• Comme il ne reste plus comme coefficient positif (dans la dernière ligne) que 300, on introduit x1
dans la base. La colonne de x1 devient la colonne pivot.
• La division de la colonne des seconds membres par la colonne pivot révèle que le plus faible rapport
correspond à la ligne x5. C’est x5 qui quitte la base. Alors le nombre 3 devient le nouveau pivot.
Le dernier pas de la deuxième itération consiste à déterminer la nouvelle solution de base au moyen du
pivotage :
1. Transformation de la ligne et la colonne pivot : Divisons la ligne pivot par 3, puis annuler tous les
éléments de la colonne pivot sauf le pivot qui est remplacé par1.
2. Transformation des autres cases du tableau : Nous utilisons la règle du rectangle pour transformer le
reste des coefficients. Le résultat est le suivant :
On peut lire directement sur ce tableau la troisième solution de base réalisable et la valeur de la fonction
objective z dans cette solution :
Troisième solution de base : xB3 = (2, 6, 2, 0, 0)
Valeur de la fonction z en xB3 : z3 = 3600
Comme il n’y a plus de coefficients positifs sur la dernière ligne, la solution courante est optimale. Ainsi :
(x1*, x2*) = (2, 6) et z* = 3600
5- Algorithme de simplexe à l’aide des variables artificielles
En regardant la forme canonique d’un PL, nous remarquons dans les contraintes l’existence des
inégalités d’infériorités ‘ ≤ ’ et des variables de décisions non négatives.
Souvent, on commence l’algorithme de simplexe au sommet x = (0, 0, …,0) qui appartient à l’espace
de solution réalisable. Si la forme canonique n’est pas respectée et s’il existe une contrainte de
supériorité ‘ ≥ ’ on remarque ce qui suit :
En premier temps, pour atteindre la forme standard on ajoute des variables d’écart non négatives.
Puisqu’on a une inégalité ‘ ≥ ’, ces variables d’écart sont d’un signe négatif.
Ex : si le PL contient des contraintes de cette forme :
x1 + 3x2 ≥ 4
x2 =2
x1, x2 ≥ 0
Devient : x1+3x2-t1 = 4 (x1, x2, t1 ≥ 0)
Si on souhaite initier l’algorithme de simplexe à l’origine (x1=0, x2=0) on aura :
– t1 = 4 c.à.d. t1 = –4 donc, contradiction avec la contrainte de non négativité de t1.
Et : x2=0, aussi contradiction avec la contrainte x2=2 !!!.
Conclusion : le point origine X = (0,0,…,0) ne peut pas appartenir à l’espace de solution réalisable,
d’où le lancement de l’algorithme avec une solution artificielle.
Résultat : introduction aux équation(s) semblables, des variable(s) dites artificielle(s) pour contourner le
problème.
Pour résoudre le nouveau PL, deux méthodes étroitement liées sont les pluscitées dans la littérature :
les Méthodes du grand M et le simplexe en 2-Phases.
6- Méthodes du grand M : (appelées aussi M-Méthodes)
Après avoir inséré les variables artificielles dans la partie des contraintes, il faut modifier la fonction
objective de la manière suivante :
Etant donnée une valeur M très grande (M → +∞), on ajoute à la fonction objectif les variables artificielles
avec des coefficients -M si le PL est un problème de maximisation et avec des coefficients M si le PL est
un problème de minimisation et on résout le nouveau PL
Exemple :
Max Z = 4x1 + 5x2
Sc : 2x1 + 2x2 ≥ 8
x2 = 3
-9x1 - 3x2 ≥ -27 9x1+3x2 ≤ 27
x1, x2 ≥ 0
Au début, il faut vérifier la non négativité du second membre,
Après insertion des variables d’écart et des variables artificielles, le PL devient :
Max Z = 4x1 + 5x2 - MA1 - MA2
Sc :
2x1 + 2x2 – x3 + A1 = 8
x2 + A2 = 3
9x1 + 3x2 +x4 = 24
x1 , x2 , x3 , x4, A1 , A2 ≥ 0
Le tableau initial de simplexe devient (après remplacement des expressions des Ai dans la fonction
objectif) :
Itération 0
Max Ci 4 5 0 0 -M -M
CB B b x1 x2 x3 x4 A1 A2
-M A1 8 2 2 -1 0 1 0
-M A2 3 0 1 0 0 0 1
0 x4 27 9 3 0 1 0 0
Zi 11M -2M -3M M 0 -M -M
Ci-Zi 4+2M 5+3M -M 0 0 0
On remarque que pour cette itération, il y a 2 coefficients positif de variable hors base, d’où l’itération
actuelle n’est pas finale et la solution atteinte n’est pas optimale :
B0={0,0,0,27,8,3} et ZB0=11M
Puisqu’on est face à un problème de maximisation, on choisit le coefficient positif qui a la plus grande
valeur : 5+3M (puisque M est très grand)
Itération 1
Max Ci 4 5 0 0 -M -M
CB B b x1 x2 x3 x4 A1 A2
-M A1 2 2 0 -1 0 1
5 x2
3 0 1 0 0 0
0 x4 18 9 0 0 1 0
Zi 15-2M -2M 5 M 0 -M
Ci-Zi 4+2M 0 -M 0 0
On remarque que pour cette itération, il y a un coefficient positif de variable hors base, d’où l’itération
actuelle n’est pas finale et la solution atteinte n’est pas optimale :
B1={0,3,0,18,2,0} et ZB1=15-2M
Donc, on passe à une autre itération, on choisit le coefficient positif qui a la plus grande valeur : 4+2M .
Itération 2
Max Ci 4 5 0 0 -M -M
CB B b x1 x2 x3 x4 A1 A2
4 x1 1 1 0 -1/2 0
5 x2 3 0 1 0 0
0 x4 9 0 0 9/2 1
Zi 19 4 5 -2 0
Ci-Zi 0 0 2 0
On remarque que pour cette itération, il y a un coefficient positif de variable hors base, d’où l’itération
actuelle n’est pas finale et la solution atteinte n’est pas optimale :
B2={1,3,0,9,0,0} et ZB2=19
Remarque : B2={1,3,0,9,0,0}, est la première solution de base réalisable, puisque toutes les variables
artificielles sont devenues hors base.
Donc, on passe à une autre itération, on choisit le coefficient positif qui a la plus grande valeur : 2.
Itération 3
Max Ci 4 5 0 0 -M -M
CB B b x1 x2 x3 x4 A1 A2
4 x1 2 1 0 0 1/9
5 x2 3 0 1 0 0
0 x3 2 0 0 1 2/9
Zi 23 4 5 0 4/9
Ci-Zi 0 0 0 -4/9
Comme il n’y a plus de coefficients positifs sur la dernière ligne, la solution courante est optimale.
B3={2,3,2,0,0,0} et ZB3=23
* * *
Ainsi : (x1 , x2 ) = (2, 3) et z = 23
7- Cas particuliers
• Solutions multiples : lorsque le simplexe s’arrête et que des variables hors base ont pour valeur 0
dans la ligne Z, cela signifie qu’il y a une infinie de solution. Dans ce cas, une itération
supplémentaire donnera une seconde solution optimale. Toute combinaison convexe de ces 2
solutions optimales est aussi une solution optimale. Géométriquement, cela signifie que la fonction
objective est parallèle à l’une des contraintes.
• Solution non bornée : Un PL est dit non borné si son optimum est infini. On reconnait un tel modèle
lorsqu’à une itération donnée, le vecteur colonne de la variable qui rentre en base est négatif ou nul.
En pratique, cette situation peut signifier une omission d’une contrainte vitale lors de la formulation
du problème.
• Pas de solution (solution non réalisable) : avec la méthode du grand M, il est possible que la
région réalisable soit vide. Dans ce cas, lors du calcul du grand M certaines variables artificielles ont
une valeur non nulle. Alors si au moins une variable artificielle apparait dans la solution de base, le
PL correspondant n’a pas de solution.
• Choix de la variable entrante (coefficients égaux): lorsqu’il y a un choix parmi les variables
entrantes (même valeur), pour un problème de maximisation, on traite les deux possibilités et on
considère le minimum ration le plus grand.
• Choix de la variable sortante (ratios égaux): lorsqu’il y a un choix parmi les variables sortantes
(même valeur), on calcule pour chaque cas la somme Si des coefficients de la ligne pivot, puis in
dive Si par le coefficient de la colonne pivot, pour un problème de maximisation on choisit en
priorité la plus grande valeur (Si / pivot)
• Solution dégénérée : si la solution optimale possède des variables de base nulles, alors elle est dite
dégénérée, c’est le cas quand il y a plus de variables de base qu’il y a de contraintes.
