2.
LA METHODE DU SIMPLEXE
2.1. Algorithme primal Simplexe
On suppose qu’on dispose d’une base réalisable de depart B. Soit I et J
respectivement les ensembles des indices des variables de base et hors base.
Pour un problème de minimisation
1) Tester ĉ.
a) Si ĉ ≥ 0, stop : ”La base B est optimale.”
b) S’il existe k ∈ J tel que ĉk < 0 avec Âk ≤ 0, stop : ”Le problème est
non bornée i.e. la valeur optimale est infinie.”
c) Autrement effectuer un changement de base.
2) Changement de base
a) Test d’entrée : Soit k ∈ J tel que
ĉk = min [ĉj : j ∈ J, ĉj < 0] .
La variable correspondante xk rentre dans la base on l’appelle variable ren-
trante.
b) Test de sortie : Soit l tel que
[ ]
b̂l b̂i
= min : i ∈ I, âik > 0 .
âlk âik
La variable xl sort de la base on l’appelle variable sortante.
c) On considère la nouvelle base réalisable encore notée B dont les en-
sembles des indices de variables de base et hors base sont respectivement
I := I − l + k et J := J − k + l
Aller à 1).
Fin
Remarque Dans le cas d’un probleme de maximisation, il n’est pas
necessaire de transformer le probleme en un probleme de minimisation afin
d’appliquer l’algorithme du simplexe. Il suffit de considérer les modifications
suivantes :
1− a) Si cˆ ≤ 0 stop : ”la base B est optimale.”
1 − b) S’il existe k ∈ J tel que cˆk > 0 avec Aˆk ≤ 0 stop : ”le probl`eme est
non bornée i.e. la valeur optimale est infinie.”
32− a) Test d’entrée : Soit k ∈ J tel que
ĉk = max [ĉj : j ∈ J, ĉj > 0] .
La variable correspondante xk rentre dans la base.
Les autres instructions restent valables.
2.2 Methode des tableaux
C’est une mise en œuvre manuelle de l’algorithme du simplexe.
Soit à résoudre le programme linéaire (P L)
∗
Z
{ = min Z = cx
Ax = b
x ∈ Rn , x ≥ 0
La methode des tableaux consiste a ecrire les tableaux simplexes relatifs
aux differentes bases rencontrees dans la resolution du programme (P L) a
l’aide de l’algorithme du simplexe.
On appelle tableau simplexe complet de (P L) par rapport a la base realisable
B.
xi i ∈ I xj j ∈ J
xi
 b̂
i∈I
ĉ −Ẑ
Dans le tableau simplexe, on appelle pivot l’element qui est a l’intersection
de la colonne de la variable rentrante et de la ligne de la variable sortante.
Dans ce cas la ligne correspondante est dite ligne du pivot et la colonne,
colonne du pivot.
Pour passer d'un tableau à un autre en appliquant l'algorithme simplexe, il faut :
1) Permuter les variables sortante et rentrante.
2) Remplacer le pivot par son inverse
3) Diviser les autres éléments de la ligne du pivot par le pivot
4) Diviser les autres éléments de la colonne du pivot par le pivot et changer
de signe.
5) Pour les autres éléments du tableau, appliquer la règle du rectangle
suivante :
Règle du rectangle
Soit l ∈ I la ligne du pivot et k ∈ J la colonne du pivot.
âik âlj
Pour i ∈ I − l et j ∈ J − k, l’élément âij est remplacé par âij − âlk
.
On note alors
âik âlj
âij := âij −
âlk
Cette règle s’applique à tous les éléments du tableau.
Remarque Si une ligne intersecte la colonne du pivot par un zero, la ligne
reste inchangee.
Si une colonne intersecte la ligne du pivot par un zéro, la colonne reste
inchangée.
Exemple 1
in Z = −3x1 + 2x2
m
2x1 + x2 ≤ 5
x1 − x2 ≤ 1
x1 + 2x2 ≤ 3
x1 , x2 ≥ 0
On écrit le programme sous forme standard. On obtient :
in Z = −3x1 + 2x2
m
2x1 + x2 + x3 = 5
x1 − x2 + x4 = 1
x1 + 2x2 + x5 = 3
xi ≥ 0, i = 1, · · · , 5
On remarque que I = {x3 , x4 , x5 } est une base réalisable évidente. En
outre le programme est déjà sous forme canonique par rapport à cette base.
Les tableaux simplexes sont les suivants.
x1 x2 x4 x2
x3 2 1 5 x3 -2 3 3
x4 1 -1 1 ← x1 1 -1 1
TS1 TS2
x5 1 2 3 x5 -1 3 2 ←
-3 2 0 3 -1 3
↑ ↑
x4 x5
x3 -1 -1 1
x1 2/3 1/3 5/3
TS3
x2 -1/3 1/3 2/3
8/3 1/3 11/3
La condition d’arrêt de l’algorithme est vérifiée, on est donc à l’optimum.
Une solution optimale du problème initial est x∗ = ( 53 , 23 )T et la valeur
optimale est Z ∗ = − 11
3
.
Exemple 2.
max Z = 6x1 + 5x2
x1 + x2 ≤ 8
−2x1 + 3x2 ≤ 6
x1 − x2 ≤ 2
x1 , x2 ≥ 0
On écrit le programme sous forme standard. On obtient :
max Z = 6x1 + 5x2
x1 + x2 + x3 = 8
−2x1 + 3x2 + x4 = 6
x1 − x2 + x5 = 2
xi ≥ 0, i = 1, · · · , 5
On remarque que I = {x3 , x4 , x5 } est une base réalisable évidente. En
outre le programme est déjà sous forme canonique par rapport à cette base.
Les tableaux simplexes sont les suivants.
x1 x2 x5 x2
x3 1 1 8 x3 -1 2 6 ←
x4 -2 3 6 x4 2 1 10
TS1 TS2
x5 1 -1 2 ← x1 1 -1 2
6 5 0 -6 11 -12
↑ ↑
x5 x3
x2 -1/2 1/2 3
x4 2 -1/2 7
TS3
x5 1 1/2 5
-1/2 -11/2 -45
Tous les coefficients de la fonction-objectif sont négatifs ou nuls on est
donc à l’optimum. Une solution optimale du problème initial est x∗ = (5, 3)T
et la valeur optimale est Z ∗ = 45.
Exemple 3
min Z = −3x1 + 5x2
−2x1 + 3x2 ≤ 6
x1 − 4x2 ≤ 4
x1 , x2 ≥ 0
On écrit le programme sous forme standard. On obtient :
Z = −3x1 + 5x2
min
−2x1 + 3x2 + x3 = 6
x1 − 4x2 + x4 = 4
xi ≥ 0, i = 1, · · · , 4
On remarque que I = {x3 , x4 } est une base réalisable évidente. En outre
le programme est déjà sous forme canonique par rapport à cette base. Les
tableaux simplexes sont les suivants.
x1 x2 x4 x2
x3 -2 3 6 x3 2 -5 14
TS1 x4 1 -4 4 ← TS2 x1 1 -4 4
-3 5 0 3 -7 12
↑ ↑
On remarque que la colonne de la variable x2 est toute négative, il n y
a donc pas de pivot. Le programme linéaire est alors non borné ; c’est-à-dire
que la valeur optimale est −∞.
Exemple 4
max Z = 3x1 + 2x2
4x1 + 3x2 ≤ 12
4x1 + x2 ≤ 8
4x1 − x2 ≤ 8
x1 , x2 ≥ 0
On remarque que I = {x3 , x4 , x5 } est une base réalisable évidente. En
outre le programme est déjà sous forme canonique par rapport à cette base.
x1 x2 x4 x2
x3 4 3 12 x3 -1 2 4 ←
x4 4 1 8 ← x1 1/4 1/4 2
TS1 TS2
x5 4 -1 8 x5 -1 0 0
3 2 0 -3/4 5/4 -6
↑ ↑
x4 x3
x2 -1/2 1/2 2
x1 3/8 -1/8 3/2
TS3
x5 -2 1 4
-1/8 -5/8 -17/2
On est à l’optimum. Une solution optimale du problème initial est x∗ =
( 32 , 2)T et la valeur optimale est Z ∗ = 17
2
.
