Convergence

de
l’algorithme du simplexe
 Convergence dans le cas non dégénéré

• Hypothèse de non dégénérescence:

toutes les variables de base sont positives à chaque itération

• Théorème 4.1: Considérons le problème de programmation linéaire sous

forme standard
T
min z = c x
Sujet à Ax = b
x≥0

n m
c, x ∈ R , b ∈ R
A matrice m × n

Sous l’hypothèse de non dégénérescence, l’algorithme du simplexe se

termine en un nombre fini d’itérations.
• Preuve:
En supposant que la matrice A est de plein rang m, chaque solution de base
réalisable doit comporter m variables de base positives (hyp. non
dégénérescence).
Il y a un nombre fini de façons de choisir m colonnes de A parmi les n
pour former des sous matrices m × m :
n  n!
m =
  m ! (n − m)!

Or les bases réalisables constituent un sous ensemble de ces-dernières.

n  n!
Donc   = est une borne supérieure sur le nombre de
m
  m ! (n − m)!
solutions de base réalisables.
• Considérons l’effet de compléter un pivot sur la valeur de la fonction
économique lors d’une itération du simplexe
Division de ligne r

par a rs

br
→ × cs
a rs

Soustraire de
−z
br
z 0 ==−−zz−0 c−s c bs r > −
−−z z0 → − ~ > z− z 0
a rsa rs
puisque c s < 0, a rs > 0, et b r > 0 par hyp. de non dégénérescence
 ~ ~ b rb r
− −z z→ − z− z=0 −= z−−
0 → z 0c−s c s > >−−z z 0
a rsa rs
puisque c s < 0, a rs > 0, et b r > 0 par hyp. de non dégénérescence

Donc ~z~ z0 << zz0 et ainsi la valeur de l’objectif décroît strictement d’une
itération à l’autre.
Par conséquent une même solution de base réalisable ne peut se répéter au
cours de l’application de l’algorithme du simplexe.
Puisque le nombre de ces dernières est borné (fini), il s’ensuit que
l’algorithme du simplexe doit être complété en un nombre fini d’itérations.
Problème où l’algo. du simplexe cycle
 x1 x2 x3 x4 x5 x6 x7 −z
1 1
x5 − 60 − 9 1 0 0 0 0
4 25
1 1
x6 − 90 − 3 0 1 0 0 0
2 50
x7 0 0 1 0 0 0 1 0 1
3 1
−z − 150 − 6 0 0 0 1 0
4 50

x1 x2 x3 x4 x5 x6 x7 −z
4
x1 1 − 240 − 36 4 0 0 0 0
25
3
x6 0 30 − 15 −2 1 0 0 0
50
x7 0 0 1 0 0 0 1 0 1
7
−z 0 − 30 − 33 3 0 0 1 0
50
 x1 x2 x3 x4 x5 x6 x7 −z
4
x1 1 − 240 − 36 4 0 0 0 0
25
3
x6 0 30 − 15 −2 1 0 0 0
50
x7 0 0 1 0 0 0 1 0 1
7
−z 0 − 30 − 33 3 0 0 1 0
50

x1 x2 x3 x4 x5 x6 x7 −z
8
x1 1 0 − 84 − 12 8 0 0 0
25
1 1 1 1
x2 0 1 − − 0 0 0
500 2 15 30
x7 0 0 1 0 0 0 1 0 1
2
−z 0 0 − 18 1 1 0 1 0
25
 x1 x2 x3 x4 x5 x6 x7 −z
8
x1 1 0 − 84 − 12 8 0 0 0
25
1 1 1 1
x2 0 1 − − 0 0 0
500 2 15 30
x7 0 0 1 0 0 0 1 0 1
2
−z 0 0 − 18 1 1 0 1 0
25

x1 x2 x3 x4 x5 x6 x7 −z
25 525 75
x3 0 1 − − 25 0 0 0
8 2 2
1 1 1 1
x2 − 1 0 − 0 0 0
160 40 120 60
25 525 75
x7 − 0 0 − 25 1 0 1
8 2 2
1
−z 0 0 −3 −2 3 0 1 0
4
 x1 x2 x3 x4 x5 x6 x7 −z
25 525 75
x3 0 1 − − 25 0 0 0
8 2 2
1 1 1 1
x2 − 1 0 − 0 0 0
160 40 120 60
25 525 75
x7 − 0 0 − 25 1 0 1
8 2 2
1
−z 0 0 −3 −2 3 0 1 0
4

x1 x2 x3 x4 x5 x6 x7 −z
125
x3 − 10500 1 0 50 − 150 0 0 0
2
1 1 2
x4 − 40 0 1 − 0 0 0
4 3 3
125
x7 − 10500 0 0 − 50 150 1 0 1
2
1
−z − 120 0 0 −1 1 0 1 0
2
 x1 x2 x3 x4 x5 x6 x7 −z
125
x3 − 10500 1 0 50 − 150 0 0 0
2
1 1 2
x4 − 40 0 1 − 0 0 0
4 3 3
125
x7 − 10500 0 0 − 50 150 1 0 1
2
1
−z − 120 0 0 −1 1 0 1 0
2

x1 x2 x3 x4 x5 x6 x7 −z
5 1
x5 − 210 0 1 −3 0 0 0
4 50
1 1 1
x4 − 30 − 1 0 0 0 0
6 150 3
x7 0 0 1 0 0 0 1 0 1
7 1
−z − 330 0 0 −2 0 1 0
4 50
 x1 x2 x3 x4 x5 x6 x7 −z
5 1
x5 − 210 0 1 −3 0 0 0
4 50
1 1 1
x4 − 30 − 1 0 0 0 0
6 150 3
x7 0 0 1 0 0 0 1 0 1
7 1
−z − 330 0 0 −2 0 1 0
4 50

x1 x2 x3 x4 x5 x6 x7 −z
1 1
x5 − 60 − 9 1 0 0 0 0
4 25
1 1
x6 − 90 − 3 0 1 0 0 0
2 50
x7 0 0 1 0 0 0 1 0 1
3 1
−z − 150 − 6 0 0 0 1 0
4 50
 Illustration graphique de la dégénerescence

Min − 3 x − 2 y
Sujet à x + 2y ≤ 26
−x+ y ≤3 s2
x− y ≤ 2 s3
2 x − y ≤ 10
x, y ≥ 0
s1
Min − 3 x − 2 y 8 
Sujet à x + 2y + s1 = 26 6 
−x+ y + s2 =3 8 
x− y + s3 =2 s4 6 
2x − y + s4 = 10 6 
x, y, s1 , s 2 , s3 , s4 ≥ 0 5 
0 
0
Min − 3x − 2 y
Sujet à x + 2y ≤ 26
−x+ y ≤3 s2
x− y ≤ 2 s3
2 x − y ≤ 10
6 x − 5 y ≤ 18
x, y ≥ 0 s1
8 
6 
Min − 3x − 2 y 8 
Sujet à x + 2y + s1 = 26 s4 6 
−x+ y + s2 =3 6 
x− y + s3 =2 5 
2x − y + s4 = 10 s5 0 
6x − 5 y + s5 = 18 0 
0 
x, y, s1 , s 2 , s3 , s 4 , s5 ≥ 0  
 Convergence dans le cas dégénéré

Critères d'entrée et de sortie de Bland:

Critère d'entrée: La variable d'entrée xs est celle ayant le plus petit indice
parmi les variables hors base ayant un coût relatif négatif; i.e.,
{
s = Min j : c j < 0 .
j =1,…, n
}
Critère de sortie: La variable de sortie x jr (x jr dénotant la variable de base
dans la r ième ligne du tableau) est celle ayant le plus petit indice parmi les
variables candidates à sortir de la base; i.e.,
 bl  bi 

jr = Min  jl : als > 0, = Min  : ais > 0  .
l =1,…, m
 als i =1,…, m  ais  
Critère de sortie: La variable de sortie x jr (x jr dénotant la variable de base
dans la r ième ligne du tableau) est celle ayant le plus petit indice parmi les
variables candidates à sortir de la base; i.e.,
 bl  bi 

jr = Min  jl : als > 0, = Min  : ais > 0  .
l =1,…, m
 als i =1,…, m  ais  

Note très importante:

Lorsque
bl  bi 
= Min  : ais > 0 
als i =1,…, m  ais 
est atteint pour plusieurs indices l , alors la variable de base x jr choisi selon
le critère précédent pour devenir variable de sortie devient égale à 0. Par
contre les autres variables x jl où ce Min est atteint restent dans la base
mais deviennent aussi égales à 0.
 x1 x2 x3 x4 x5 x6 x7 −z
1 1
x5 − 60 − 9 1 0 0 0 0
4 25
1 1
x6 − 90 − 3 0 1 0 0 0
2 50
x7 0 0 1 0 0 0 1 0 1
3 1
−z − 150 − 6 0 0 0 1 0
4 50

x1 x2 x3 x4 x5 x6 x7 −z
4
x1 1 − 240 − 36 4 0 0 0 0
25
3
x6 0 30 − 15 −2 1 0 0 0
50
x7 0 0 1 0 0 0 1 0 1
7
−z 0 − 30 − 33 3 0 0 1 0
50
 x1 x2 x3 x4 x5 x6 x7 −z
8
x1 1 0 − 84 − 12 8 0 0 0
25
1 1 1 1
x2 0 1 − − 0 0 0
500 2 15 30
x7 0 0 1 0 0 0 1 0 1
2
−z 0 0 − 18 1 1 0 1 0
25

x1 x2 x3 x4 x5 x6 x7 −z
25 525 75
x3 0 1 − − 25 0 0 0
8 2 2
1 1 1 1
x2 − 1 0 − 0 0 0
160 40 120 60
25 525 75
x7 − 0 0 − 25 1 0 1
8 2 2
1
−z 0 0 −3 −2 3 0 1 0
4
 x1 x2 x3 x4 x5 x6 x7 −z
25 525 75
x3 0 1 − − 25 0 0 0
8 2 2
1 1 1 1
x2 − 1 0 − 0 0 0
160 40 120 60
25 525 75
x7 − 0 0 − 25 1 0 1
8 2 2
1
−z 0 0 −3 −2 3 0 1 0
4

x1 x2 x3 x4 x5 x6 x7 −z
125
x3 − 10500 1 0 50 − 150 0 0 0
2
1 1 2
x4 − 40 0 1 − 0 0 0
4 3 3
125
x7 − 10500 0 0 − 50 150 1 0 1
2
1
−z − 120 0 0 −1 1 0 1 0
2
 x1 x2 x3 x4 x5 x6 x7 −z
125
x3 − 10500 1 0 50 − 150 0 0 0
2
1 1 2
x4 − 40 0 1 − 0 0 0
4 3 3
125
x7 − 10500 0 0 − 50 150 1 0 1
2
1
−z − 120 0 0 −1 1 0 1 0
2

x1 x2 x3 x4 x5 x6 x7 − z
x3 0 0 1 0 0 0 1 0 1
2 1 1 1
x4 0 −2 0 1 − 0
15 5 250 250
100 300 2 1
x1 1 − 168 0 0 − 0
125 125 125 125
175 275 1 1
−z 0 36 0 0 − 1
125 125 125 125
 x1 x2 x3 x4 x5 x6 x7 − z
x3 0 0 1 0 0 0 1 0 1
2 1 1 1
x4 0 −2 0 1 − 0
15 5 250 250
100 300 2 1
x1 1 − 168 0 0 − 0
125 125 125 125
175 275 1 1
−z 0 36 0 0 − 1
125 125 125 125

x1 x2 x3 x4 x5 x6 x7 − z
x3 0 0 1 0 0 0 1 0 1
15 3 3 3
x5 0 − 15 0 1 − 0
2 2 100 100
150 5 5
x1 1 − 180 0 6 0 0
125 125 125
21 1 1 1
−z 0 15 0 0 1
2 10 20 20
Théorème 4.2: En utilisant les critères d'entrée et de sortie de
Bland, l'algorithme du simplexe doit être complété en un
nombre fini d'itérations.

Preuve. (Preuve par contradiction) Supposons qu'au contraire

pour un certain problème, l'algorithme ne soit pas complété en
un nombre fini d'itérations. Or étant donné qu'il existe un nombre
fini de solutions de base réalisables, il s'ensuit que certaines
solutions de base réalisables sont répétées au cours de la
résolution avec l'algorithme du simplexe; i.e., l'algorithme cycle.
Preuve. (Preuve par contradiction) Supposons qu'au contraire
pour un certain problème, l'algorithme ne soit pas complété en
un nombre fini d'itérations. Or étant donné qu'il existe un nombre
fini de solutions de base réalisables, il s'ensuit que certaines
solutions de base réalisables sont répétées au cours de la
résolution avec l'algorithme du simplexe; i.e., l'algorithme cycle.
Considérons une solution de base d'une itération quelconque.
Alors ou bien cette solution réalisable est optimale, ou bien
nous décelons que le problème n'est pas borné inférieurement,
ou bien les critères d'entrée et de sortie de Bland déterminent
de façon unique l'élément du tableau sur lequel le pivot est
complété.
Considérons une solution de base d'une itération quelconque.
Alors ou bien cette solution réalisable est optimale, ou bien
nous décelons que le problème n'est pas borné inférieurement,
ou bien les critères d'entrée et de sortie de Bland déterminent
de façon unique l'élément du tableau sur lequel le pivot est
complété.
Par conséquent si l'algorithme cycle, alors le cycle des solutions
de base réalisables qui sont répétées est unique.
Dénotons par Γ ∈ {1, … , n} l'ensemble des indices des variables
d'entrée au cours des itérations du cycle. Donc si j ∉ Γ, alors x j
demeure une variable de base au cours de toutes les itérations du
cycle ou elle demeure un variable hors base au cours de toutes
les itérations du cycle. En somme son statut ne change pas au
cours des itérations du cycle.
Par conséquent si l'algorithme cycle, alors le cycle des solutions
de base réalisables qui sont répétées est unique.
Dénotons par Γ ∈ {1,… , n} l'ensemble des indices des variables
d'entrée au cours des itérations du cycle. Donc si j ∉ Γ, alors x j
demeure une variable de base au cours de toutes les itérations
cycle ou elle demeure un variable hors base au cours de toutes
les itérations du cycle. En somme son statut ne change pas au
cours de itérations du cycle.
Dénotons également
g = Max { j} ,
j∈Γ

et utilisons l'indice supérieur ′ pour désigner les éléments du

tableau du simplexe à l'itération où xg devient variable d'entrée.
Dénotons également
g = Max { j} ,
j∈Γ

et utilisons l'indice supérieur ′ pour désigner les éléments du

tableau du simplexe à l'itération où xg devient variable d'entrée.
x1 x2 … xg … xn − z
′ a12
a11 ′ … a1′g … a1′n 0 b1′
′ a22
a21 ′ … a2′ g … a2′ n 0 b2′
⋮ ⋮ ⋮ ⋮ ⋮ ⋮
am′ 1 am′ 2 … amg
′ … amn
′ 0 bm′
c1′ c2′ … c′g … cn′ 1 − z′

Dénotons par hT ∈ R n +1 la dernière ligne du tableau:

hT =  c1′ c2′ … c′g … cn′ 1  .
 x1 x2 … xg … xn − z
′ a12
a11 ′ … a1′g … a1′n 0 b1′
′ a22
a21 ′ … a2′ g … a2′ n 0 b2′
⋮ ⋮ ⋮ ⋮ ⋮ ⋮
am′ 1 am′ 2 … amg
′ … amn
′ 0 bm′
c1′ c2′ … c′g … cn′ 1 − z′
Dénotons par hT ∈ R n +1 la dernière ligne du tableau:
hT =  c1′ c2′ … c′g … cn′ 1  .
Puisque xg est la variable d'entrée, il découle du critère d'entrée
que toutes les variables ayant un indice plus petit que g ont un
coût relatif plus grand ou égal à 0. De plus puisque g = Max { j}
j∈Γ

alors
hg = c′g < 0 et h j = c′j ≥ 0 ∀j ∈ Γ, j ≠ g . (4.1)
 x1 x2 … xg … xn − z
′ a12
a11 ′ … a1′g … a1′n 0 b1′  0
 
′ a22
a21 ′ … a2′ g … a2′ n 0 b2′  0
⋮ ⋮ ⋮ ⋮ ⋮ ⋮  A ⋮
 
am′ 1 am′ 2 … amg
′ … amn
′ 0 bm′  0
c1′ c2′ … c′g … cn′ 1 − z ′
c c … c … c 1
1 2 g n

Dénotons par hT ∈ R n +1 la dernière ligne du tableau:

hT =  c1′ c2′ … c′g … cn′ 1  .
Puisque le tableau précédent a été obtenu du tableau original
à l'aide d'une suite de pivots, il s'ensuit que le vecteur hT est
une combinaison linéaire des lignes de cette matrice et qu'il
appartient donc à l'espace engendré par les lignes de cette
dernière.
Puisque xg est variable d'entrée à une certaine itération du cycle,
elle doit être variable de sortie à une autre itération du cycle.
Utilisons l'indice supérieur ′′ pour désigner le tableau du simplexe
associé à cette itération.
Dénotons par
x j1 ,… , x jr ,… x jm où x jr = xg
les variables de base à cette itération. Dénotons également par xs
la variable d'entrée identifiée avec le critère de Bland. Ainsi
′′ est l'élément de pivot.
ars
 x1 … x jr … xs … x j … x jm … xn − z
1

x j1 ′′ … 0… a1′′s …1 … 0 … a1′′n 0
a11 b1′′
⋮ ⋮
x jr ar′′1 … 1… ars′′ … 0 … 0 … arn
′′ 0 br′′
⋮ ⋮
x jm am′′ 1 … 0… ams
′′ … 0 … 1 … amn
′′ 0 bm′′
−z c1′′ … 0… cs′′ … 0 … 0 … cn′′ 1 − z ′′
Définissons un vecteur v ∈ R n+1 à partir des éléments dans la
colonne de la variable d'entrée xs dans le tableau précédent:
v ji = ais′′ i = 1,… , m
Par rapport au tableau illustré plus
vs = −1
haut le vecteur v prend la forme
vn +1 = cs ′′
v =0 autres indices j v T
= [ 0… ars ′′ … 0 cs′′]
′′ … − 1… a1′′s … ams
j
 x1 … x jr … xs … x j … x jm … xn − z
1

x j1 ′′ … 0… a1′′s …1 … 0 … a1′′n 0 b1′′

a11
⋮ [0… ars′′ … − 1… a1′′s … ams
′′ … 0 cs′′] ⋮
x jr ar′′1 … 1… ars′′ … 0 … 0 … arn
′′ 0 br′′
⋮ [0… ars′′ … − 1… a1′′s … ′′ … 0 cs′′ ] ⋮
ams
x jm am′′ 1 … 0… ams
′′ … 0 … 1 … amn
′′ 0 bm′′
−z c1′′ … 0… cs′′ … 0 … 0 … cn′′ 1 − z ′′
[0… ars′′ … − 1… a1′′s … ams
′′ … 0 cs′′]

Le produit scalaire du vecteur v avec chaque ligne du tableau

précédent est égal à 0. Ainsi v est perpendiculaire a chaque
vecteur ligne du tableau. Par rapport au tableau illustré plus
haut le vecteur v prend la forme
v T = [ 0… ars ′′ … 0 cs′′]
′′ … − 1… a1′′s … ams
 x1 … x jr … xs … x j … x jm … xn − z
1

x j1 ′′ … 0… a1′′s …1 … 0 … a1′′n 0
a11 b1′′  0
⋮ ⋮  
 0
x jr ar′′1 … 1… ars′′ … 0 … 0 … arn
′′ 0 br′′  A ⋮
⋮ ⋮  
 0
x jm am′′ 1 … 0… ams
′′ … 0 … 1 … amn
′′ 0 bm′′ c c … c … c 1
1 2 g n
−z c1′′ … 0… cs′′ … 0 … 0 … cn′′ 1 − z ′′
Puisque le tableau précédent a été obtenu du tableau original
à l'aide d'une suite de pivots, il s'ensuit que le vecteur v est
perpendiculaire aux lignes de cette matrice et qu'il est
donc orthogonal à l'espace engendré par les lignes de cette
dernière. Donc il s'ensuit que
hT v = 0.
hT =  c1′ c2′ … c′g … cn′ 1  v ji = ais′′ i = 1,… , m
vs = −1
Donc il s'ensuit que
n +1 vn+1 = cs′′
hT v = ∑ hl vl = 0.
l =1 vj = 0 autres indices j
Notons d'abord que
hn +1vn +1 = 1 ⋅ cs′′ < 0.
Par conséquent, il doit exister au moins un indice j (1 ≤ j ≤ n )
tel que h j v j > 0.
Or
si h j ≠ 0, alors x j est une variable hors base dans le tableau d'indice
supérieur ′
si v j ≠ 0, alors x j est une variable de base dans le tableau d'indice
supérieur ′′, ou j = s.
hT =  c1′ c2′ … c′g … cn′ 1  v ji = ais′′ i = 1,… , m
vs = −1
Donc il s'ensuit que vn+1 = cs′′
hT v = 0. vj = 0 autres indices j
Or
si h j ≠ 0, alors x j est une variable hors base dans le tableau d'indice
supérieur ′
si v j ≠ 0, alors x j est une variable de base dans le tableau d'indice
supérieur ′′, ou j = s.
Donc l'indice j doit appartenir à Γ et alors
j ≤ g.
Mais puisque
hg = c′g < 0 et ′′ > 0,
vg = ars
il s'ensuit que j < g.
hT =  c1′ c2′ … c′g … cn′ 1  v ji = ais′′ i = 1,… , m
vs = −1
Donc il s'ensuit que vn+1 = cs′′
hT v = 0. vj = 0 autres indices j
Mais puisque
hg = c′g < 0 et ′′ > 0,
vg = ars
il s'ensuit que j < g.
Il découle donc de (4.1)
hg = c′g < 0 et h j = c′j ≥ 0 ∀j ∈ Γ, j ≠ g. (4.1)
que hj > 0
et ainsi v j > 0.
Donc x j est une variable de base dans le tableau d'indice supérieur ′′.
 hT =  c1′ c2′ … c′g … cn′ 1  v ji = ais′′ i = 1,… , m
vs = −1
Donc il s'ensuit que vn+1 = cs′′
hT v = 0. vj = 0 autres indices j
v j > 0.
Donc x j est une variable de base dans le tableau d'indice supérieur ′′.
Soit j = j p tel que a′′ps = v j > 0.
 Au cours des itérations du cycle, chaque variable conserve la
même valeur.
En effet, si à une itération du cycle une variable d'entrée
augmentait d'une valeur positive, alors la valeur de la fonction
économique diminuerait strictement et alors l'algorithme ne
pourrait cycler.
En particulier,
xj = 0 ∀j ∈ Γ
au cours de toutes les itérations du cycle.
Par conséquent x j p = b′′p =0.
En somme, nous venons d'établir les deux faits suivants:
Donc x j est une variable de base dans le tableau d'indice supérieur ′′.
Soit j = j p <g tel que a′′ps = v j > 0.
et que x j p = b′′p = 0.
x1 … x jr … xs … x j … x jm … xn − z
1

x j1 ′′ … 0… a1′′s …1 … 0 … a1′′n 0
a11 b1′′ Ainsi cette variable x j p
⋮ ⋮
aurait dû être variable
x jr ar′′1 … 1… ars′′ … 0 … 0 … arn
′′ 0 br′′
de sortie à l'itération ′′
⋮ ⋮
selon le critère de
x j p a′′p1 … 1… a′′ps … 0 … 0 … a′′pn 0 b0′′p
sortie de Bland.
⋮ ⋮
x jm am′′ 1 … 0… ams
′′ … 0 … 1 … amn
′′ 0 bm′′
−z c1′′ … 0… cs′′ … 0 … 0 … cn′′ 1 − z′′
En somme, nous venons d'établir les deux faits suivants:
Donc x j est une variable de base dans le tableau d'indice supérieur ′′.
Soit j = j p <g tel que a′′ps = v j > 0.
et que x j p = b′′p = 0.
Ainsi cette variable x j p aurait dû être variable de sortie à
l'itération ′′ selon le critère de sortie de Bland.
Ceci est une contradiction au fait que nous ayons retenu
plutôt xg comme variable de sortie.
Donc en utilisant les critères d'entrée et de sortie de Bland,
l'algorithme du simplexe ne peut cycler. La décroissance stricte
de la valeur de la fonction économique au cours des itérations
où il n'y a pas dégénérescence nous assure que l'algorithme
du simplexe doit être complété en un nombre fini d'itérations. □