Résolution de programmes linéaires par l’algorithme

du simplexe

Nous avons vu dans le chapitre précédent que la résolution graphique ne peut être un moyen
de résolution de PL que si le nombre de variables de décision est égal à 2. Or, la majorité des
PL formulés sont en réalité complexes et admettent généralement un nombre de variables de
décision important beaucoup plus élevé. La résolution de ces PL est réalisée grâce à
l’algorithme du simplexe proposé par Dantzig en 1947. Cet algorithme a pour objectif
d’explorer les sommets du polyèdre représentant le DSR en commençant par un sommet
pouvant être une base puis en progressant vers les sommets adjacents de façon à toujours
améliorer la valeur de la fonction économique. Cette exploration s’arrête lorsque les sommets
adjacents de la dernière solution ne peuvent pas améliorer la valeur de la fonction objectif.

1. Forme standard d’un PL

Avant de commencer, nous rappelons qu’un PL est une fonction linéaire à

optimiser sous contraintes. Les contraintes sont un système d’inéquations linéaires
permettant, comme on l’a vu dans le chapitre précédent, de définir le DSR. Nous
avons vu également que la solution optimale ne peut être qu’un sommet du DSR
ou un ensemble de points reliant deux sommets du DSR. Cela veut dire que la
solution recherchée ne peut se trouver que sur les contours du DSR.

La forme standard d’un PL permet de transformer le système d’inéquations

linéaires en un système d’équations linéaires en introduisant pour chaque
contrainte, une variable d’écart notée si . Cette variable d’écart si représente soit la

quantité non utilisée de la ressource i pour les contraintes de type «  », soit la

quantité manquante de la ressource i pour les contraintes de type «  ».

Contrainte sous forme générale Contrainte sous forme standard

ai1 x1 + ai 2 x2 + ....... + ain xn  bi ai1 x1 + ai 2 x2 + ....... + ain xn + si = bi

ai1 x1 + ai 2 x2 + ....... + ain xn  bi ai1 x1 + ai 2 x2 + ....... + ain xn − si = bi

Dans la fonction économique, les variables d’écart ont un coefficient économique

de 0 puisqu’elles ne contribuent pas aux bénéfices ou aux coûts.
1/11
 2. Algorithme du simplexe pour les PL avec des contraintes de type ≤

Soit le PL suivant :

MaxZ = 6 x1 + 4 x2
2 x1 + 3x2  120
 (1)
S .C. 4 x1 + 2 x2  100
x , x  0
 1 2

Pour pouvoir appliquer la méthode du simplexe, la première étape consiste à écrire le PL sous
forme standard c'est-à-dire à transformer les inéquations en équations en introduisant deux
nouvelles variables s1 et s2 appelées variables d’écart. La forme standard de ce PL s’écrit :

MaxZ = 6 x1 + 4 x2 + 0s1 + 0s2

2 x1 + 3x2 + s1 + 0s2 = 120
 (2)
S .C. 4 x1 + 2 x2 + 0s1 + s2 = 100
x , x  0
 1 2

Les programmes linéaires (1) et (2) sont équivalents et leur résolution aboutit aux mêmes
solutions optimales.

Rappelons que dans le problème initial, nous recherchons la valeur optimale de 2 variables de
décision (en général n variables). Une variable d’écart a été introduite pour chaque contrainte.
Dans notre exemple, 2 variables d’écart ont été introduites (en général le nombre de variables
d’écart est  m, une variable pour chacune des m contraintes de type  ou ).

Que représentent les variables d’écart si?

Economiquement il s’agit de la quantité de ressource manquante (contrainte de type ) ou de

la quantité de ressource disponible (contrainte de type ≤).

Géométriquement, les quantités si impliquent que les solutions sont recherchées sur les arêtes
du DSR et non pas sur le DSR tout entier.

Dans notre exemple, la forme standard du PL est un système linéaire à 2 équations et 4

inconnues (en général, il s’agit de systèmes linéaires de m équations à (n+m) inconnues) .

Mathématiquement, il n’est pas possible de résoudre un système linéaire comportant plus

d’inconnues que d’équations. L’astuce imaginée par Dantzig, l’auteur de l’algorithme du
simplexe est de résoudre le PL dans un sous espace linéaire de taille m, m étant le nombre de
contraintes. Pour cela, on choisit parmi les (n+m) variables, m variables qu’on appelle
variables de base. Ces variables sont supposées être > 0. Les n variables restantes sont
appelées variables hors base et sont supposées égales à 0.

2/11
Comment choisir les m variables de base ?

En observant la matrice A des coefficients technologiques, on choisit les variables dont les
coefficients technologiques forment une matrice unité entre eux comme variable de base.

 2 3 1 0
Dans notre exemple, A =   . Les variables de base seront donc s1 et s2 .
 4 2 0 1

Une fois les premières variables de base choisies, la première étape pour résoudre le PL par
l’algorithme du simplexe consiste à écrire le PL sous forme de tableau.

Pour appliquer l'algorithme du simplexe, il est intéressant d'écrire le problème sous forme
d'un tableau appelé tableau du simplexe. Ce tableau se présente sous la forme suivante :

Coefficients économiques (cj)

Variables de décision et d’écart
b=
cj des Variables
Quantités
variables de base A = matrice des coefficients technologiques
des i
de base (VB)
ressources
Ainsi, le premier tableau du simplexe de notre exemple est :

cj 6 4 0 0
cj
VB x1 x2 s1 s2 Quantités

0 s1 2 3 1 0 120
0 s2 4 2 0 1 100

Il s’agit de la solution x1 = x2 = 0 (VHB) ; s1 = 120 et s2 = 100 ; Z = 0 .

Cette première solution n’est pas la solution optimale puisqu’elle consiste à ne rien faire. Les
ressources sont intactes et la fonction objectif nulle.

Pour améliorer cette première solution, il faut faire un changement de base en remplaçant une
des variables de base (variable sortante) par une des variables hors base (variable entrante).
On commence par choisir la variable entrante. Pour cela, il est nécessaire de commencer par
calculer z j la perte de profit unitaire pour chaque variable (VB et VHB). Dans notre exemple,

l’introduction d’une unité de x1 implique la perte de 2 unités de s1 et de 4 unités de s2 .

Comme les coefficients économiques de s1 et de s2 sont nuls, z1 = 0*2 + 0*4 = 0 .

Par la suite, le profit marginal de chaque variable est calculé. Ce profit marginal, noté
 z j = c j − z j , représente le profit généré par l’introduction d’une unité de la variable. La

3/11
variable entrante choisie est celle qui va engendrer le plus grand profit unitaire. Dans cet
exemple, il s’agit de la variable x1 dont le  z j = 6 .

La colonne de x1 est appelée colonne pivot.

cj 6 4 0 0
cj
VB x1 x2 s1 s2 Quantités

0 s1 2 3 1 0 120
0 s2 4 2 0 1 100

zj 0 0 0 0 Z =0

 zj 6 4 0 0

Une fois la variable entrante déterminée, il faut choisir la variable sortante qui sera remplacée
par la variable entrante. Cette variable sortante deviendra une variable hors base, donc une
variable nulle. Dans l’exemple étudié, si on choisit s1 comme variable sortante, cela veut dire

qu’on devra épuiser la ressource 1 en produisant autant de x1 que possible. La ressource 1

 120 
permet de produire 60 unités de x1  = 60  . En revanche, si on choisit s2 comme variable
 2 
 100 
sortante, la ressource 2 ne permet de produire que  = 25  unités de x1 . Ainsi, seules 25
 4 
unités de x1 peuvent être produites. En effet, avec 25 unités de x1 , la ressource 2 est épuisée.

Il n’est plus possible de produire une unité supplémentaire. Donc, on choisit s2 comme

variable sortante.

En pratique, les étapes pour le choix de la variable sortant de la base sont les suivantes :

1. On fait un ratio test noté RT en divisant les quantités par les coefficients
technologiques de la colonne pivot.

2. Tous les rapports dont le dénominateur est négatif (Solution non réalisable) ou nul
(RT = ) ne sont pas considérés.

3. On choisit la variable qui a le plus petit RT comme variable sortante. Si on peut

choisir entre plusieurs variables, le choix se fait de manière arbitraire. Dans notre
exemple, c'est la variable s2 qui sort de la base.

4. La ligne de la variable sortante est appelée ligne pivot.

5. L’intersection entre la ligne pivot et la colonne pivot est appelée le pivot.

4/11
 cj 6 4 0 0
cj
x1 x2 s1 s2 Quantités RT
VB
0 s1 2 3 1 0 120 120/2=60

0 s2 4 2 0 1 100 100/4=25

zj 0 0 0 0 Z =0

 zj 6 4 0 0

Remarques

1. Les coefficients des variables de base forment toujours une matrice identité d'ordre m
(m contraintes sans compter les contraintes de non-négativité).

2. Pour pouvoir appliquer l'algorithme du simplexe, il est impératif que les seconds
membres des contraintes ne soient pas négatifs. Si un tel cas se présente, il convient de
multiplier les 2 membres de l'inéquation par -1 sans oublier de changer le sens de
l'inégalité qui peut alors se transformer en une inéquation de type  qu'on apprendre à
traiter plus loin.

− x1 + 4 x2  −1  x1 − 4 x2  1

Changement de base

L'intégration d'une nouvelle variable de base implique que tous les coefficients relatifs à cette
variable de base représentent une matrice identité. Il faut donc écrire le système d'une manière
équivalente de telle façon de faire ressortir cette matrice identité (la variable entrante prend
les coefficients technologiques de la variable sortante). Plusieurs méthodes existent pour
effectuer ce changement de base. Nous retenons ici la méthode la plus simple à mettre en
œuvre : La méthode de Gauss-Jordan.

Les étapes de cette méthode sont :

1. Division de la ligne pivot par le pivot : cela garantit que la valeur du pivot soit égale à
1 dans le nouveau tableau du simplexe.

2. Trouver une combinaison linéaire entre chacune des autres lignes du tableau du
simplexe et la ligne pivot de sorte que les valeurs des coefficients de la colonne pivot
dans le nouveau tableau du simplexe soit égales à 0. Soit aij un coefficient
technologique de la variable xj n’appartenant pas à la ligne pivot et apj le coefficient
technologique de la variable xj de la ligne pivot.

3.
5/11
 La nouvelle valeur de aij dans le tableau du simplexe suivant est égale à :

nouveau aij = ancien aij -TLP* apj. Comment déterminer TLP ?

On sait que les valeurs de la colonne pivot dans le nouveau tableau du simplexe (TS)
doivent être égales à 1 pour le pivot et à 0 pour les autres éléments de la colonne pivot.
Soit aip le coefficient technologique de la ligne i pour la colonne pivot et app le pivot.
Le nouveau aip doit être égal à 0.

aip
ancien aip -TLP* app = 0  TLP =
a pp

cj 6 4 0 0
cj
x1 x2 s1 s2 Quantités RT
VB
L1-(LP/2) 0 s1 2 3 1 0 120 120/2=60

LP/4 0 s2 4 2 0 1 100 100/4=25

zj 0 0 0 0 Z =0

 zj 6 4 0 0

LP/2 0 s1 0 2 1 -1/2 70 70/2=35

L2-(LP/4) 6 x1 1 1/2 0 1/4 25 25/0.5=50

zj 6 3 0 3/2 Z=150
 zj 0 1 0 -3/2
4 x2 0 1 1/2 -1/4 35

6 x1 1 0 -1/4 3/8 15/2

zj 6 4 1/2 5/4 Z=185

 zj 0 0 -1/2 -5/4

L’algorithme du simplexe s’arrête lorsque tous les  z j des VHB sont 0. La solution optimale

15 *
est pour cet exemple : x1* = ; x2 = 25; s1* = s2* = 0; Z * = 185
2

Il est à noter que tous les  z j des VB doivent être nuls car leur profit marginal est nul

puisqu’elles sont déjà des VB.

6/11
Exercice

Résoudre le PL suivant :

Max Z = 10 x1 + 12 x2 Max Z = 10 x1 + 12 x2 + 0s1 + 0s2

 x1 + 2 x2  40  x1 + 2 x2 + s1 + 0s2 = 40 1 2 1 0 
  A= 
S .C 3x1 + 2 x2  60 S .C 3x1 + 2 x2 + 0s1 + s2 = 60 3 2 0 1 
x , x  0 x , x  0
 1 2  1 2

Forme standard :

cj 10 12 0 0
cj
x1 x2 s1 s2 Quantités RT
VB
0 s1 1 2 1 0 40 40/2=20

TLP=1 0 s2 3 2 0 1 60 60/2=30

zj 0 0 0 0 0

 zj 10 12 0 0

TLP =1/4 12 x2 1/2 1 1/2 0 20 40

0 s2 2 0 -1 1 20 10

zj 6 12 6 0 240
 zj 4 0 -6 0
12 x2 0 1 3/4 -1/4 15

10 x1 1 0 -1/2 1/2 10

zj 10 12 1/4 2 280

 zj 0 0 -1/4 -2

Problèmes de minimisation :

Les problèmes de minimisation se traitent exactement de la même façon que les problèmes de
maximisations. La seule différence réside dans le fait qu’on doit choisir comme variable
entrante la VHB qui a le plus petit  z j parmi les  z j  0 . L’algorithme s’arrête lorsque tous

les  z j des VHB 0. On peut également choisir de définir  z j = z j − c j . Dans ce cas, la

résolution du PL se fait exactement comme pour une maximisation.

7/11
 3. Algorithme du simplexe pour les PL avec des contraintes de type  ou =

Soit le PL suivant :

MaxZ = 6 x1 + 4 x2
2 x1 + 3 x2  120
4 x + 2 x  100
 1 2

S .C  x1 = 10
 x  30
 2
 x1 , x2  0

La forme standard de ce PL s’écrit :

MaxZ = 6 x1 + 4 x2 + 0 s1 + 0 s2 + 0 s4
2 x1 + 3x2 + s1 + 0 s2 + 0 s4 = 120
4 x + 2 x + 0s + s + 0s = 100
 1 2 1 2 4
(1)
S .C  x1 + 0 x2 + 0s1 + 0s2 + 0s4 = 10
0 x + x + 0s + 0s − s = 30
 1 2 1 2 4

 x1 , x2 , s1 , s2 , s4  0

On remarque que les variables d'écart s1 et s2 sont rajoutées pour les deux premières
contraintes. En ce qui concerne la 4ème contrainte, il est nécessaire de retrancher la variable
d’écart s4 pour transformer l'inéquation en équation. En revanche, il n’est pas nécessaire de
rajouter une variable d’écart pour la 3ème contrainte puisque c’est déjà une égalité.

La matrice des coefficients technologiques A s’écrit :

 x1 x2 s1 s2 s4 
 
2 3 1 0 0 
A = 4 2 0 1 0 
 
1 0 0 0 0 
0 1 0 0 − 1


Existe-t-il une première solution de base pour démarrer le simplexe ?

La réponse est non car on ne trouve pas 4 variables dont les coefficients technologiques
forment une matrice unité entre eux.

La solution consiste à introduire de nouvelles variables qu’on appelle variables artificielles

afin de créer artificiellement une base pour démarrer le simplexe. En règle générale, on
rajoute une variable artificielle dans chaque contrainte de type «  » ou « = ». Ces variables
sont notées ai et n’ont aucune explication économique.

8/11
Quel va être le coefficient économique de ces variables artificielles ?

On attribue aux variables artificielles un coefficient très pénalisant. Cela veut dire que pour
les problèmes de maximisation, le coefficient économique sera un très grand nombre négatif
qu’on notera -M alors que pour les problèmes de minimisation on choisira un très grand
nombre positif noté +M. Le PL s’écrit

On obtient le système de contraintes suivant :

MaxZ = 6 x1 + 4 x2 + 0 s1 + 0 s2 + 0 s4 − Ma3 − Ma4

2 x1 + 3 x2 + s1 + 0 s2 + 0 s4 + 0a3 + 0a4 = 120
4 x + 2 x + 0 s + s + 0 s + 0a + 0a = 100
 1 2 1 2 4 3 4
(2)
S .C  x1 + 0 x2 + 0 s1 + 0 s2 + 0 s4 + a3 + 0a4 = 10
0 x + x + 0 s + 0 s − s + 0a + a = 30
 1 2 1 2 4 3 4

 x1 , x2 , s1 , s2 , s4  0

 x1 x2 s1 s2 s4 a3 a4 
 
2 3 1 0 0 0 0
A = 4 2 0 1 0 0 0
 
1 0 0 0 0 1 0
0 1 0 0 − 1 0 1 


On obtient ainsi une première solution de base réalisable avec x1 = x2 = s4 = 0, s1 = 120, s2 =

100, a1 = 10 et a2 = 30 (s1, s2, a1 et a2 sont les premières variables de base)

Les solutions réalisables du système (2) sont également des solutions réalisables pour le
système (1) à condition que a1 = a2 = 0. Il faut donc faire en sorte que ces variables
artificielles sortent de la base très rapidement.

9/11
Résolution du PL

cj 6 4 0 0 0 -M -M
cj
x1 x2 s1 s2 s4 a3 a4 Quantités RT
VB
TLP=2 s1 60
0 2 3 1 0 0 0 0 120
TLP=4 s2 25
0 4 2 0 1 0 0 0 100

-M a3 1 0 0 0 0 1 0 10 10

-M a4 0 1 0 0 -1 0 1 30 

zj -M -M 0 0 M -M -M
-40M
 zj 6+M 4+M 0 0 -M 0 0
TLP=3 s1 100/3
0 0 3 1 0 0 0 100
TLP=2 s2 30
0 0 2 0 1 0 0 60

6 x1 1 0 0 0 0 0 10 

-M a4 0 1 0 0 -1 1 30 30

zj 6 -M 0 0 M -M 60-30M
 zj 0 4+M 0 0 -M 0
TLP=3/2 s1 10/3
0 0 0 1 0 3 10

0 s2 0 0 0 1 2 0 0

6 x1 1 0 0 0 0 10 
TLP=- NR
1/2 4 x2 0 1 0 0 -1 30

zj 6 4 0 0 -4 180
 zj 0 0 0 0 4

0 s1 0 0 1 3/2 0 10

0 s4 0 0 0 1/2 1 0

6 x1 1 0 0 0 0 10

4 x2 0 1 0 1/2 0 30
zj 6 4 0 2 0 180
 zj 0 0 0 -2 0

La solution optimale est un cas particulier appelé solution dégénérée. Ainsi, une solution est
dire dégénérée lorsqu’une des VB est nulle.

10/11
4. Cas particuliers

a. Cas particulier 1

Min C = x1 + x2
 x1 + x2  5
−2 x + x  2
 1 2
S .C. 
 x1  6
 x1 , x2  0

b. Cas particulier 2

Max Z = 2 x1 + x2
 1
− 2 x1 + x2  10

 x2  25

S .C.  x2  5
− x + x  6
 1 2
 x1 , x2  0


c. Cas particulier 3

Max Z = x1 + x2
− x1 + x2 = 3
x  1

S .C.  1
 x1 + x2  6
 x1 , x2  0

11/11