Chapitre 2

La programmation linéaire - Méthode du

simplexe

2.1 Introduction
L’algorithme du simplexe fut proposé en 1947 par G. B. Dantzig comme méthode de résolution générale
des programmes linéaires. La solution optimale est approchée par étapes ou itérations successives. Chaque
étape correspond au calcul de la valeur économique d’une solution. Comme il existe une infinité de solutions
admissibles, la méthode propose de n’explorer qu’un nombre limité de solutions parmi lesquelles se trouve
à coup sûr la solution optimale.

2.2 La méthode du simplexe

La méthode du simplexe repose sur le théorème fondamental suivant :

Théorème 2.2.1
– 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.

2.2.1 Programme linéaire standard

Exemple 2.2.1 On se donne le problème suivant :


 x1 ≥ 0, x2 ≥ 0

5x1 − x2 ≤ 3

 x + 4x2 ≤ 4
 1
Z(x1 , x2 ) = 2x1 + 3x2 à optimiser,

31
32 CHAPITRE 2. LA PROGRAMMATION LINÉAIRE - MÉTHODE DU SIMPLEXE

programme linéaire exprimé sous sa forme canonique.

On introduit des variables auxiliaires positives ou nulles appelées variables d’écart de la façon suivante :
{
5x1 − x2 + e1 = 3
5x1 − x2 ≤ 3 ⇔
e1 ≥ 0
{
x1 + 4x2 + e2 = 4
x1 + 4x2 ≤ 4 ⇔
e2 ≥ 0

Le programme linéaire peut se réécrire alors :



 x1 ≥ 0, x2 ≥ 0, e1 ≥ 0, e2 ≥ 0

5x1 − x2 + e1 = 3

 x + 4x2 + e2 = 4
 1
Z(x1 , x2 ) = 2x1 + 3x2 à optimiser.

Le programme est écrit sous sa forme standard et les variables e1 et e2 sont des variables d’écart.

Exemple 2.2.2 On se donne le programme linéaire ci-dessous :



 x1 ≥ 0, x2 ≥ 0, x3 ≥ 0



 x 1 + x2 ≤ 1

x1 + 2x2 + 3x3 ≤ 5

 x 2 − 4x3 ≤ 2



 x + x2 + x3 = 5
 1
Z(x1 , x2 , x3 ) = 2x1 + x2 + x3 à optimiser.

On remplace les 3 inégalités par 3 égalités en introduisant 3 variables d’écart e1 , e2 et e3 . Le programme

linéaire standard est alors


 x1 ≥ 0, x2 ≥ 0, x3 ≥ 0, e1 ≥ 0, e2 ≥ 0, e3 ≥ 0



 x 1 + x 2 + e1 = 1

x1 + 2x2 + 3x3 + e2 = 5
 x2 − 4x3 + e3 = 2




 x + x2 + x3 = 5
 1
Z(x1 , x2 , x3 ) = 2x1 + x2 + x3 à optimiser.

Cas général
Soit un programme linéaire à n variables. On remplace chaque inégalité

a1 x1 + a2 x2 + . . . + an xn ≤ b1

par l’égalité

a1 x1 + a2 x2 + . . . + an xn + e1 = b1 avec e1 ≥ 0

et

a1 x1 + a2 x2 + . . . + an xn ≥ b1

par

a1 x1 + a2 x2 + . . . + an xn − e1 = b1 avec e1 ≥ 0

On obtient alors le programme linéaire standard qu’on cherche à résoudre.

2.2. LA MÉTHODE DU SIMPLEXE 33

2.2.2 L’algorithme du simplexe

Exemple 2.2.3 (solution unique)
1. Enoncé
Un ébéniste fabrique des bureaux sous forme standard ou luxe. Des études de marché ont montré que
pour l’année à venir, les possibilités de vente s’élèvent à 300 unités pour le modèle luxe et à 400 unités
pour le modèle standard. L’approvisionnement en bois est suffisant pour fabriquer annuellement 500
bureaux quel que soit le type. Par ailleurs, le temps de fabrication d’un modèle luxe est le double
de celui d’un bureau de modèle standard. La capacité annuelle de fabrication est telle que, si tous
les bureaux fabriqués étaient de type standard, on pourrait en fabriquer 700 au maximum. La vente
d’un bureau sous le modèle luxe conduit à une marge unitaire sur coût variable égale à 7, celle d’un
bureau de type standard égale à 5. On se propose de rechercher le programme annuel de fabrication
conduisant au profit global maximum.

2. Mise en équation
Soit x1 le nombre de bureaux de type luxe, x2 le nombre de bureaux de type standard. Le programme
linéaire est


 x1 ≥ 0, x2 ≥ 0

 x1 ≤ 300



x2 ≤ 400

 x1 + x2 ≤ 500



 2x1 + x2 ≤ 700

Z(x1 , x2 ) = 7x1 + 5x2 à maximiser
3. Domaine des solutions réalisables

4. Forme standard
On introduit les variables d’écart xi avec i ∈ {3, 4, 5, 6} positives ou nulles.


 x1 + x3 = 300


 x2 + x4 = 400
x1 + x2 + x5 = 500


 2x1 + x2 + x6 = 700


Z(x1 , x2 ) = 7x1 + 5x2 à maximiser
5. Variables hors-base, variable dans la base
Une solution de base est avant tout une solution admissible ; elle satisfait l’ensemble des contraintes
et conditions de signe. Toute solution de base comporte deux catégories de variables.
– Des variables ayant une valeur prédéterminée nulle : ces variables nulles sont dites variables hors-
base (ou variables exclues). Il y a au moins autant de variables hors-base que le problème comporte
de variables réelles.
– Des variables ayant une valeur non nulle : ce sont les variables dans la base (ou variables retenues).
Leur nombre est au plus équivalent au nombre de variables d’écart.
De façon générale, si un problème comprend m contraintes et n variables réelles, pour qu’une solution
soit solution de base il faut et il suffit
34 CHAPITRE 2. LA PROGRAMMATION LINÉAIRE - MÉTHODE DU SIMPLEXE

– qu’elle soit solution admissible,

– qu’elle admette au moins n variables hors base et au plus m variables dans la base.
Pour amorcer l’algorithme du simplexe, il est nécessaire de connaı̂tre une solution de base.

La solution de base de départ de l’ébéniste consiste à ne rien produire : x1 = x2 = 0. Ces va-

riables x1 , x2 qui sont nulles sont hors-base. Dans ce cas, x3 = 300, x4 = 400, x5 = 500, x6 = 700.
Les variables x3 , x4 , x5 , x6 non nulles sont dans la base. La valeur de la fonction économique est
Z(0, 0) = 7 × 0 + 5 × 0 = 0.

Notation :

VDB VHB
x3 x1
x4 x2
x5
x6

Tableau initial :

PP
PP VHB
PP x3 x4 x5 x6
VDB PP
P x1 x2 cste
• • • •
x3 1 0 1 0 0 0 300 x1 + x3 = 300
x4 0 1 0 1 0 0 400 x2 + x4 = 400
x5 1 1 0 0 1 0 500 x1 + x2 + x5 = 500
x6 2 1 0 0 0 1 700 2x1 + x2 + x6 = 700
Z 7 5 0 0 0 0 0 Z = 7x1 + 5x2

6. Première itération
La solution de base de départ consiste à ne rien produire soit x1 = x2 = 0. On étudie ensuite, à partir
de cette solution, jusqu’à quel niveau on peut porter x1 ou x2 conformément aux contraintes de façon
à accroı̂tre au maximum le profit. Il se pose le problème du choix de la variable x1 ou x2 qui va passer
de la valeur 0 à une valeur strictement positive. La variable choisie sera appelée variable entrante.
• Critère de sélection de la variable entrante :
Cette sélection doit s’accompagner d’une augmentation de la fonction économique
Z(x1 , x2 ) = 7x1 + 5x2
La sélection portera sur x1 qui par unité rapporte le plus. Cette règle est appelée règle du plus
grand gain marginal :

Le critère de sélection de Dantzig de la variable entrante consiste, dans la fonction économique exprimée
exclusivement en fonction des variables hors-base, à sélectionner la variable affectée du coefficient
strictement positif le plus élevé.

• On exprime ensuite x3 , x4 , x5 , x6 et Z
 en fonction des variables hors-base x1 et x2

 x3 = 300 − x1


 x4 = 400 − x2
x5 = 500 − x1 − x2



 x = 700 − 2x1 − x2
 6
Z = 7x1 + 5x2
La variable x2 reste hors-base donc nulle, la variable x1 entre en base. On reporte x2 = 0 dans ce
système, on obtient :
2.2. LA MÉTHODE DU SIMPLEXE 35



 x3 = 300 − x1


 x4 = 400
x5 = 500 − x1



 x = 700 − 2x1
 6
Z = 7x1
On cherche jusqu’à quel niveau il est possible de porter x1 , de façon compatible avec les contraintes
x3 ≥ 0, x4 ≥ 0, x5 ≥ 0, x6 ≥ 0. Les contraintes de positivité donnent
x1 ≤ 300, x1 ≤ 500, x1 ≤ 350.
La valeur maximale prise par x1 est donc 300. On remplace x1 par 300 dans le système et on obtient
x3 = 0, x4 = 400, x5 = 200, x6 = 100 et Z(300, 0) = 2100.
La variable x3 est devenue nulle, elle est sortie de la base, x3 est appelée variable sortante. Les
variables x1 et x3 ont permuté.

On exprime le programme standard en fonction des nouvelles variables hors-base x2 , x3 :

  

 x1 + x3 = 300 
 x1 = 300 − x3 
 x1 + x3 = 300

 
 

 x2 + x4 = 400  x4 = 400 − x2  x2 + x4 = 400
x1 + x2 + x5 = 500 ⇔ x5 = 500 − (300 − x3 ) − x2 ⇔ x2 − x3 + x5 = 200

 
 


 2x 1 + x2 + x 6 = 700 
 x = 700 − 2(300 − x ) − x 
 x − 2x3 + x6 = 100
  6 3 2
 2
Z = 7x1 + 5x2 Z = 7(300 − x3 ) + 5x2 Z = 5x2 − 7x3 + 2100
On exprime ce nouveau programme à l’aide d’un second tableau. Pour l’obtenir, on remplace impérativement
dans le premier tableau la variable x3 par la variable x1 (x1 et x3 ont permuté) et ceci dans la colonne
“variables dans la base”.
PP
PP VHB
PP x1 x4 x5 x6
VDB PP
P x2 x3 cste
• • • •
x1 1 0 1 0 0 0 300 x1 + x3 = 300
x4 0 1 0 1 0 0 400 x2 + x4 = 400
x5 0 1 −1 0 1 0 200 x2 − x3 + x5 = 200
x6 0 1 −2 0 0 1 100 x2 − 2x3 + x6 = 100
Z 0 5 −7 0 0 0 −2100 Z = 5x2 − 7x3 + 2100

On a pris la colonne des variables dans la base du premier tableau et on y a remplacé x3 par x1 .
Pour la fonction économique Z, le coefficient constant 2100 est affecté impérativement du signe “−”
et on place −2100.

7. Deuxième itération
• Sélection de la variable entrante :
Z = 5x2 − 7x3 + 2100
On sélectionne x2 ; en effet, toute augmentation de x3 à partir de la valeur 0 provoquerait une
diminution de la fonction économique Z.
• Sélection de la variable sortante : la variable x3 reste hors-base donc nulle, on remplace x3 par 0 dans
le système précédent, on obtient x1 = 300, x4 = 400−x2 ≥ 0, x5 = 200−x2 ≥ 0 et x6 = 100−x2 ≥ 0.
Les contraintes de positivité imposent
36 CHAPITRE 2. LA PROGRAMMATION LINÉAIRE - MÉTHODE DU SIMPLEXE

x2 ≤ 400, x2 ≤ 200 et x2 ≤ 100.

Jusqu’à quel niveau peut-on porter x2 ? La valeur maximale prise par x2 est 100. Dans ce cas,
x1 = 300, x4 = 300, x5 = 100 et x6 = 0.
La variable sortante est x6 .

Les variables hors-base sont alors x3 et x6 , les variables dans la base sont x1 , x2 , x4 et x5 . Cette
itération conduit au sommet B(300, 100). Pour cette solution, la fonction économique prend la valeur
2600.

x2 et x6 ont permuté. On exprime les variables dans la base en fonction des nouvelles variables hors-base
x3 et x6
 

 x1 + x3 = 300 
 x1 = 300 − x3

 

 2x + x 4 = 400  x2 = 700 − 2(300 − x3 ) − x6 = 100 + 2x3 − x6
x1 + x2 + x5 = 500 ⇔ x4 = 400 − (100 + 2x3 − x6 )

 


 2x1 + x 2 + x6 = 700 
 x = 500 − (300 − x3 ) − (100 + 2x3 − x6 )
  5
Z = 7x1 + 5x2 Z = 7(300 − x3 ) + 5(100 + 2x3 − x6 )
Le programme linéaire se réécrit finalement :


 x1 + x3 = 300


 x2 − 2x3 + x6 = 100
2x3 + x4 − x6 = 300



 x + x5 − x6 = 100
 3
Z = 2600 + 3x3 − 5x6

PP
PP VHB
PP x1 x2 x4 x5
VDB PP
P x3 x6 cste
• • • •
x1 1 0 1 0 0 0 300 x1 + x3 = 300
x4 0 0 2 1 0 −1 300 2x3 + x4 − x6 = 300
x5 0 0 1 0 1 −1 100 x3 + x5 − x6 = 100
x2 0 1 −2 0 0 1 100 x2 − 2x3 + x6 = 100
Z 0 0 3 0 0 −5 −2600 Z = 3x3 − 5x6 + 2600

On a pris la colonne des variables dans la base du second tableau et on y a remplacé x6 par x2 (ces
deux variables permutent).
Pour la fonction économique Z, le coefficient constant 2600 est affecté du signe “−” et on place −2600.

8. Troisième itération
• Sélection de la variable entrante :
Z = 3x3 − 5x6 + 2600
x3 sera la variable entrante car toute augmentation de x6 entraı̂ne une diminution de la fonction
économique Z.
• Sélection de la variable sortante : on exprime les variables dans la base en fonction des variables
hors-base x3 et x6 .
2.2. LA MÉTHODE DU SIMPLEXE 37



 x1 = 300 − x3

x2 = 100 + 2x3 − x6

 x = 300 − 2x3 + x6
 4
x5 = 100 − x3 + x6
La variable x6 reste hors-base donc nulle, on remplace x6 par 0. On obtient x1 = 300 − x3 ≥ 0,
x2 = 100 + 2x3 ≥ 0, x4 = 300 − 2x3 ≥ 0 et x5 = 100 − x3 ≥ 0. Les contraintes de positivité donnent
x3 ≤ 300, x3 ≥ −50, x3 ≤ 150 et x3 ≤ 100.
La valeur maximale prise par x3 est 100. Pour x3 = 100, on obtient
x1 = 200, x2 = 300, x4 = 100 et x5 = 0.
La variable qui sort de la base est x5 .

Cette itération conduit au sommet C(200, 300). La valeur de la fonction économique est Z = 2900.

Les variables x3 et x5 ont permuté.

On exprime les variables dans la base en fonction des variables hors-base x5 et x6 .

 

 x3 = 100 − x5 + x6 
 x3 + x5 − x6 = 100

 

 x1 = 300 − (100 − x5 + x6 ) = 200 + x5 − x6  x1 − x5 + x6 = 200
x2 = 100 + 2(100 − x5 + x6 ) = 300 − 2x5 + x6 ⇔ x2 + 2x5 − x6 = 300

 


 x = 300 − 2(100 − x + x ) = 100 + 2x − x 
 x − 2x5 + x6 = 100
 4 5 6 5 6
 4
Z = 2600 + 3(100 − x5 + x6 ) = 2900 − 3x5 − 2x6 Z = 2900 − 3x5 − 2x6
On obtient le tableau :
PP
PP VHB
PP x1 x2 x3 x4
VDB PP
P x5 x6 cste
• • • •
x1 1 0 0 0 −1 1 200 x1 − x5 + x6 = 200
x4 0 0 0 1 −2 1 100 x4 − 2x5 + x6 = 100
x3 0 0 1 0 1 −1 100 x3 + x5 − x6 = 100
x2 0 1 0 0 2 −1 300 x2 + 2x5 − x6 = 300
Z 0 0 0 0 −3 −2 −2900 Z = 2900 − 3x5 − 2x6

On a pris la colonne des variables dans la base du troisième tableau et on y a remplacé x5 par x3 .
Pour la fonction économique Z, le coefficient constant 2900 est affecté du signe “−” et on place −2900.
38 CHAPITRE 2. LA PROGRAMMATION LINÉAIRE - MÉTHODE DU SIMPLEXE

Conclusion :
Z = 2900 − 3x5 − 2x6 ,
x5 et x6 sont hors-base donc nulles, toute augmentation de x5 ou x6 entraı̂ne une diminution de Z. Il n’est
plus possible d’améliorer la fonction économique, la solution (x1 = 200, x2 = 300) est la solution optimale.
On interprète les résultats de la manière suivante :
. x1 = 200 bureaux de modèle luxe,
. x2 = 300 bureaux de modèle standard,
. x3 = 100, il reste une possibilité de fabriquer 100 bureaux de modèle luxe,
. x4 = 100, il reste une possibilité de fabriquer 100 bureaux de modèle standard,
. x5 = 0, tout le bois disponible est utilisé,
. x6 = 0, tout le temps disponible est utilisé.

Z est maximum pour x1 = 200, x2 = 300 et vaut 2900.

Disposition pratique des tableaux :

Afin de systématiser et de simplifier les calculs, ceux-ci peuvent être présentés sous forme de tableaux. Un
tableau correspond à une solution de base et une itération représente une modification du tableau.

– Tableau initial
PP
PP VHB
PP x3 x4 x5 x6
VDB PP
P x1 x2 cste
• • • •
x3 1 0 1 0 0 0 300
x4 0 1 0 1 0 0 400
x5 1 1 0 0 1 0 500
x6 2 1 0 0 0 1 700
Z 7 5 0 0 0 0 0

x1 = x2 = 0 représente le sommet origine et Z = 0. On a de plus, x3 = 300, x4 = 400, x5 = 500 et

x6 = 700.
On sélectionne dans la fonction économique la variable affectée du coefficient strictement positif le
plus grand. La variable x1 entre en base. Quelle est la variable sortante ?
On considère la colonne C obtenue en divisant les coefficients constants par la colonne des coefficients
de la variable x1 qui entre en base.

x1 constante C
300
x3 1 300 = 300
1
400
x4 0 400 = +∞
0
500
x5 1 500 = 500
1
700
x6 2 700 = 350
2

On sélectionne dans cette colonne le plus petit nombre strictement positif 300. La variable x3 sort
de la base. Les deux variables x1 et x3 ont permuté. Le pivot est situé à l’intersection de la colonne
variable entrante et de la ligne variable sortante et est égal à 1.
2.2. LA MÉTHODE DU SIMPLEXE 39

– Deuxième tableau :
Impérativement dans la colonne des variables dans la base du tableau initial, on remplace la variable
x3 qui sort de la base par la variable x1 qui entre en base, on recopie les autres variables d’où la
disposition du second tableau
PP
PP VHB
PP x1 x4 x5 x6
VDB PP
P x2 x3 cste
• • • •
x1
x4
x5
x6
Z
Comment remplit-on le tableau ?
On recopie la ligne Lp du pivot (avec un pivot a = 1) dans la ligne Lx1 :

Lp 1 0 1 0 0 0 300
On doit exprimer le programme en fonction des nouvelles variables hors-base x2 et x3 .
. Pour la ligne Lx4 ,
x2 + x4 = 400.
x4 s’exprime bien en fonction de x2 et x3 . On recopie cette ligne.
. Pour la ligne Lx5 ,
x1 + x2 + x5 = 500.
Par une combinaison linéaire de la ligne Lx5 et de la ligne pivot Lp , on élimine la variable x1 qui
est entrée en base :

Lx5 1 1 0 0 1 0 500
Lp 1 0 1 0 0 0 300
Lx5 − Lp 0 1 −1 0 1 0 200

On recopie ensuite cette nouvelle ligne Lx5 :

x2 − x3 + x5 = 200
. Pour la ligne Lx6

Lx6 2 1 0 0 0 1 700
Lp 1 0 1 0 0 0 300
Lx6 − 2Lp 0 1 −2 0 0 1 100

On recopie cette nouvelle ligne Lx6 :

x2 − 2x3 + x6 = 100
. Pour la ligne de la fonction économique LZ
LZ 7 5 0 0 0 0 0
Lp 1 0 1 0 0 0 300
LZ − 7Lp 0 5 −7 0 0 0 −2100
d’où la fonction économique exprimée en fonction des variables hors-base :
40 CHAPITRE 2. LA PROGRAMMATION LINÉAIRE - MÉTHODE DU SIMPLEXE

Z = 5x2 − 7x3 + 2100

On obtient donc le second tableau :

PP
PP VHB
PP x1 x4 x5 x6
VDB PP
P x2 x3 cste
• • • •
x1 1 0 1 0 0 0 300
x4 0 1 0 1 0 0 400
x5 0 1 −1 0 1 0 200
x6 0 1 −2 0 0 1 100
Z 0 5 −7 0 0 0 −2100

On a x2 = x3 = 0. Comme x1 = 300, on atteint le sommet A(300, 0) et Z = 2900. On a de plus,

x4 = 400, x5 = 200, x6 = 100.

– Troisième tableau :
Z = 5x2 − 7x3 + 2100,
la variable entrante est x2 (une augmentation de x3 entraı̂ne une dimimution de Z). Déterminons la
variable sortante : la colonne C est donnée par :
x2 constante C
300
x1 0 300 = +∞
0
400
x4 1 400 = 400
1
200
x5 1 200 = 200
1
100
x6 1 100 = 100
1
On sélectionne dans cette colonne C le coefficient strictement positif le plus petit c’est-à-dire 100, la
variable x6 sort de la base. Les variables x2 et x6 ont permuté. Le pivot est situé à l’intersection de la
colonne variable entrante et de la ligne variable sortante. Ce pivot vaut 1.

On remplit le troisième tableau : dans la colonne des variables dans la base du deuxième tableau,
on remplace la variable x6 qui sort de la base par la variable x2 qui entre en base. On recopie la ligne
pivot avec le pivot de 1 :
Lp : 1.x2 − 2.x3 + 1.x6 = 100
PP
PP VHB
PP x1 x2 x4 x5
VDB PP
P x3 x6 cste
• • • •
x1
x4
x5
x2 0 1 −2 0 0 1 100
Z

Par des combinaisons avec la ligne pivot, on exprime le système en fonction des variables hors-base x3
2.2. LA MÉTHODE DU SIMPLEXE 41

et x6 c’est-à-dire qu’on élimine la variable x2 qui est entrée en base :

. pour la ligne Lx4 :
Lx4 0 1 0 1 0 0 400
Lp 0 1 −2 0 0 1 100
Lx4 − Lp 0 0 2 1 0 −1 300
. pour la ligne Lx5 :
Lx5 0 1 −1 0 1 0 200
Lp 0 1 −2 0 0 1 100
Lx5 − Lp 0 0 1 0 1 −1 100
. pour la ligne LZ :
LZ 0 5 −7 0 0 0 −2100
Lp 0 1 −2 0 0 1 100
LZ − 5Lp 0 0 3 0 0 −5 −2600

Une fois le tableau rempli, on obtient :

PP
PP VHB
PP x1 x2 x4 x5
VDB PP
P x3 x6 cste
• • • •
x1 1 0 1 0 0 0 300
x4 0 0 2 1 0 −1 300
x5 0 0 1 0 1 −1 100
x2 0 1 −2 0 0 1 100
Z 0 0 3 0 0 −5 −2600

On a x3 = x6 = 0. Comme x1 = 300 et x2 = 100, on est passé du sommet A(300, 0) au sommet

B(300, 100). On a de plus x4 = 300, x5 = 100 et Z vaut 2600.

– Quatrième tableau :
Z = 3x3 − 5x6 + 2600
La variable entrante est x3 (toute augmentation de x6 entraı̂ne une diminution de Z). Déterminons la
variable sortante : la colonne C est donnée par
x3 constante C
300
x1 1 300
= 300
1
300
x4 2 300 = 150
2
100
x5 1 100 = 100
1
100
x2 −2 100 = −50
−2
On sélectionne dans cette colonne C le coefficient strictement positif le plus petit c’est-à-dire 100, la
variable x5 sort de la base. Les variables x3 et x5 ont permuté. Le pivot est 1, il est situé à l’intersection
de la colonne x3 et de la ligne x5 . On remplit le quatrième tableau : dans la colonne des variables dans
la base du troisième tableau, on remplace la variable x5 qui sort de base par la variable x3 qui entre
en base. On recopie la ligne pivot avec un pivot de 1 :
42 CHAPITRE 2. LA PROGRAMMATION LINÉAIRE - MÉTHODE DU SIMPLEXE

Lp : x3 + x5 − x6 = 100
PP
PP VHB
PP x1 x2 x3 x4
VDB PP
P x5 x6 cste
• • • •
x1
x4
x3 0 0 1 0 1 −1 100
x2
Z
Par des combinaisons avec la ligne pivot, on exprime le système en fonction des variables hors-base x5
et x6 c’est-à-dire qu’on élimine la variable x3 qui est entrée en base :
. pour la ligne Lx1 :

Lx1 1 0 1 0 0 0 300
Lp 0 0 1 0 1 −1 100
Lx1 − Lp 1 0 0 0 −1 1 200
. pour la ligne Lx4 :

Lx4 0 0 2 1 0 −1 300
Lp 0 0 1 0 1 −1 100
Lx4 − 2Lp 0 0 0 1 −2 1 100
. pour la ligne Lx2 :

Lx2 0 1 −2 0 0 1 100
Lp 0 0 1 0 1 −1 100
Lx2 + 2Lp 0 1 0 0 2 −1 300
. pour la ligne LZ :

LZ 0 0 3 0 0 −5 −2600
Lp 0 0 1 0 1 −1 100
LZ − 3Lp 0 0 0 0 −3 −2 −2900
On peut ensuite remplir le quatrième tableau :
PP
PP VHB
PP x1 x2 x3 x4
VDB PP
P x5 x6 cste
• • • •
x1 1 0 0 0 −1 1 200
x4 0 0 0 1 −2 1 100
x3 0 0 1 0 1 −1 100
x2 0 1 0 0 2 −1 300
Z 0 0 0 0 −3 −2 −2900
2.2. LA MÉTHODE DU SIMPLEXE 43

Conclusion, la fonction économique s’écrit Z = 2900 − 3x5 − 2x6 où x5 et x6 sont les variables hors-base donc
nulles. Toute augmentation de x5 et x6 conduit à une diminution de Z. Donc x1 = 200, x2 = 300, x3 = 100,
x4 = 100 et Z = 2900. La fonction économique atteint son maximum au point C(200, 300) et vaut 2900.

Exemple 2.2.4 (solution unique)

On considère le programme linéaire suivant


 x1 ≥ 0, x2 ≥ 0, x3 ≥ 0


 x1 + 3x2 + 2x3 ≤ 40
3x1 + 2x2 + x3 ≤ 45


 x1 + x2 + 4x3 ≤ 38


Z(x1 , x2 , x3 ) = 10x1 + 14x2 + 12x3 à maximiser

1. Programme standard :


 x1 ≥ 0, x2 ≥ 0, x3 ≥ 0, x4 ≥ 0, x5 ≥ 0, x6 ≥ 0


 x1 + 3x2 + 2x3 + x4 = 40
3x1 + 2x2 + x3 + x5 = 45



 x + x2 + 4x3 + x6 = 38
 1
Z(x1 , x2 , x3 ) = 10x1 + 14x2 + 12x3 à maximiser
La solution de base de départ du programme correspond au sommet 0, c’est la solution nulle qui
consiste à ne rien produire : x1 = x2 = x3 = 0 et Z(0, 0, 0) = 0. Les variables x1 , x2 , x3 sont hors-base
donc nulles, les autres variables x4 , x5 , x6 sont dans la base.
2. Tableau initial :
PP
PP VHB
PP x4 x5 x6
VDB PP
P x1 x2 x3 cste
• • •
x4 1 3 2 1 0 0 40 x1 + 3x2 + 2x3 + x4 = 40
x5 3 2 1 0 1 0 45 3x1 + 2x2 + x3 + x5 = 45
x6 1 1 4 0 0 1 38 x1 + x2 + 4x3 + x6 = 38
Z 10 14 12 0 0 0 0 Z = 10x1 + 14x2 + 12x3

• Choix de la variable entrante : on sélectionne la variable affectée du coefficient strictement positif le

plus grand dans la fonction économique, la variable x2 entre en base.
• Choix de la variable sortante : on détermine la colonne C :

x2 constante C
40
x4 3 40 ≃ 13, 33
3
45
x5 2 45 = 22, 5
2
38
x6 1 38 = 38
1
On sélectionne le coefficient strictement positif le plus petit dans la colonne C, la variable x4 sort
de la base.
44 CHAPITRE 2. LA PROGRAMMATION LINÉAIRE - MÉTHODE DU SIMPLEXE

• Le pivot : il est situé à l’intersection de la colonne variable qui entre en base et de la ligne variable
qui sort de la base, ce pivot est 3. Afin d’obtenir un pivot de 1, on divise tous les coefficients de la
ligne pivot par ce pivot 3. On obtient la nouvelle ligne pivot :
1 2 1 40
Lp : x1 + x2 + x3 + x4 =
3 3 3 3
soit
1 2 40
Lp 1 1 0 0
3 3 3

3. Deuxième tableau :

PP
PP VHB
PP x2 x5 x6
VDB PP
P x1 x3 x4 cste
• • •
1 2 1 40
x2 1 0 0
3 3 3 3
x5
x6
Z

• On recopie la ligne du pivot avec le pivot de 1.

• Pour remplir ce second tableau, par des combinaisons avec la ligne pivot, on élimine la variable x2
qui est entrée en base :

. pour la ligne Lx5 :

Lx5 3 2 1 0 1 0 45
1 2 1 40
Lp 1 0 0
3 3 3 3
7 1 2 55
Lx5 − 2Lp 0 − − 1 0
3 3 3 3
. pour la ligne Lx6 :

L x6 1 1 4 0 0 1 38
1 2 1 40
Lp 1 0 0
3 3 3 3
2 10 1 74
Lx6 − Lp 0 − 0 1
3 3 3 3
. pour la ligne LZ :
LZ 10 14 12 0 0 0 0
1 2 1 40
Lp 1 0 0
3 3 3 3
16 8 14 560
LZ − 14Lp 0 − 0 0 −
3 3 3 3

Le deuxième tableau s’écrit alors :

2.2. LA MÉTHODE DU SIMPLEXE 45

PP
PP VHB
PP x2 x5 x6
VDB PP
P x1 x3 x4 cste
• • •
1 2 1 40
x2 1 0 0
3 3 3 3
7 1 2 55
x5 0 − − 1 0
3 3 3 3
2 10 1 74
x6 0 − 0 1
3 3 3 3
16 8 14 560
Z 0 − 0 0 −
3 3 3 3

On a par conséquent
16 8 14 560
Z= x1 + x3 − x4 +
3 3 3 3

4. Troisième tableau :
16
• La variable entrante est x1 ; en effet, est le coefficient strictement positif le plus grand dans la
3
fonction économique.
• La variable sortante est déterminée à l’aide de la colonne C :

x1 constante C
1 40 40 1
x2 / = 40
3 3 3 3
7 55 55 7 55
x5 / =
3 3 3 3 7
2 74 74 2
x6 / = 37
3 3 3 3
55
On choisit le coefficient strictement positif le plus petit dans la colonne C soit , la variable x5
7
sort de la base.
7
• Le pivot est , situé à l’intersection de la colonne variable qui entre en base et de la ligne variable
3
7
qui sort de la base. Pour obtenir un pivot de 1, on divise la ligne pivot par ce pivot , on obtient
3
1 2 3 55
Lp = x1 − x3 − x4 + x5 =
7 7 7 7
soit
1 2 3 55
Lp 1 0 − − 0
7 7 7 7

• On exprime le système en fonction des nouvelles variables hors-base x3 et x4 et on élimine x1 qui

est entrée en base.
. Pour la ligne Lx2 :
1 2 1 40
Lx2 1 0 0
3 3 3 3
1 2 3 55
Lp 1 0 − − 0
7 7 7 7
5 3 1 75
Lx2 − 13 Lp 0 1 − 0
7 7 7 7
46 CHAPITRE 2. LA PROGRAMMATION LINÉAIRE - MÉTHODE DU SIMPLEXE

. Pour la ligne Lx6 :

2 10 1 74
Lx6 0 − 0 1
3 3 3 3
1 2 3 55
Lp 1 0 − − 0
7 7 7 7
24 1 2 136
Lx6 − 23 Lp 0 0 − − 1
7 7 7 7
. Pour la ligne LZ :
16 8 14 560
LZ 0 − 0 0 −
3 3 3 3
1 2 3 55
Lp 1 0 − − 0
7 7 7 7
24 22 16 1600
LZ − 16
3 Lp 0 0 − − 0 −
7 7 7 7
On peut maintenant remplir le troisième tableau :
PP
PP VHB
PP x1 x2 x6
VDB PP
P x3 x4 x5 cste
• • •
5 3 1 75
x2 0 1 − 0
7 7 7 7
1 2 3 55
x1 1 0 − − 0
7 7 7 7
24 1 2 136
x6 0 0 − − 1
7 7 7 7
24 22 16 1600
Z 0 0 − − 0 −
7 7 7 7

5. Quatrième tableau :
24 22 16 1600
Z= x3 − x4 − x5 +
7 7 7 7
24
• Variable entrante : on sélectionne le coefficient , la variable x3 entre en base.
7
• Variable sortante :
x3 Constante C
5 75 75 5
x2 / = 15
7 7 7 7
1 55 55 1
x1 − / − = −55
7 7 7 7
24 136 136 24 17
x6 / =
7 7 7 7 3
La variable x6 sort de base.
24
• Le pivot est , on divise la ligne pivot par ce pivot et on obtient la nouvelle ligne pivot :
7
1 1 7 17
Lp : x3 − x4 − x5 + x6 =
24 12 24 3
1 1 7 17
Lp 0 0 1 − −
24 12 24 3
2.2. LA MÉTHODE DU SIMPLEXE 47

Dans la colonne variables dans la base du troisième tableau, on remplace la variable x6 par la variable
x3 et on y recopie la nouvelle ligne pivot
PP
PP VHB
PP x1 x2 x3
VDB PP
P x4 x5 x6 cste
• • •
x2
x1
1 1 7 17
x3 0 0 1 − −
24 12 24 3
Z
On exprime le système en fonction des variables hors-base x4 , x5 et x6 . On élimine la variable x3
qui est entrée en base :
. pour la ligne Lx2 :
5 3 1 75
Lx2 0 1 − 0
7 7 7 7
1 1 7 17
Lp 0 0 1 − −
24 12 24 3
11 1 5 20
Lx2 − 57 Lp 0 1 0 − −
24 12 24 3
. pour la ligne Lx1 :
1 2 3 55
Lx1 1 0 − − 0
7 7 7 7
1 1 7 17
Lp 0 0 1 − −
24 12 24 3
7 5 1 26
Lx1 + 17 Lp 1 0 0 −
24 12 24 3
. pour la ligne LZ :

24 22 16 1600
LZ 0 0 − − 0 −
7 7 7 7
1 1 7 17
Lp 0 0 1 − −
24 12 24 3
LZ − 24
7 Lp 0 0 0 −3 −2 −1 −248

Le quatrième tableau est finalement donné par :

PP
PP VHB
PP x1 x2 x3
VDB PP
P x4 x5 x6 cste
• • •
11 1 5 20
x2 0 1 0 − −
24 12 24 3
7 5 1 26
x1 1 0 0 −
24 12 24 3
1 1 7 17
x3 0 0 1 − −
24 12 24 3
Z 0 0 0 −3 −2 −1 −248
48 CHAPITRE 2. LA PROGRAMMATION LINÉAIRE - MÉTHODE DU SIMPLEXE

6. Conclusion :
Z = −3x4 − 2x5 − x6 + 248
Les trois variables x4 , x5 et x6 sont affectées de coefficients négatifs, toute augmentation de x4 , x5 ou
x6 diminuerait la valeur de Z. Il n’est plus possible d’améliorer la fonction économique.
20 26 17
Z est maximum pour x4 = 0, x5 = 0, x6 = 0, x1 = , x2 = , x3 = , atteint son maximum au
( ) 3 3 3
point 20 , 26 17
3 3 3, et vaut Z( 20 26 17
,
3 3 3, ) = 248. De plus, comme x 4 = 0, x5 = 0 et x6 = 0, les trois
matières premières sont utilisées en totalité.