Embed Size (px)
Citation preview
3. Convergence
de
l’algorithme du simplexe
• 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 colonnes de parmi les pour former des sous matrices :
!
! ( )!
m A nm m
nnm m n m
Or les bases réalisables constituent un sous ensemble de ces-dernières. !
Donc est une borne supérieure sur le nombre de ! ( )!
solutions de base réalisables.
nnm m n m
• 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 rsa
→ scrs
r
a
b
Soustraire de
encedégénérescnondehyp.par0et,0,0puisque
~0000
rrss
rs
rs
bac
za
bczzz
z
za
bczzz
rs
rs ~
Donc 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.
00~ zz
encedégénérescnondehyp.par0et,0,0puisque
~0000
rrss
rs
rs
bac
za
bczzz za
bczzz
rs
rs ~
zz ~
Problème où l’algo. du simplexe cycle
1 2 3 4 5 6 7
5
6
7
1 160 9 1 0 0 0 0
4 251 1
90 3 0 1 0 0 02 500 0 1 0 0 0 1 0 13 1
150 6 0 0 0 1 04 50
x x x x x x x z
x
x
x
z
1 2 3 4 5 6 7
1
6
7
41 240 36 4 0 0 0 0
253
0 30 15 2 1 0 0 050
0 0 1 0 0 0 1 0 17
0 30 33 3 0 0 1 050
x x x x x x x z
x
x
x
z
1 2 3 4 5 6 7
1
6
7
41 240 36 4 0 0 0 0
253
0 30 15 2 1 0 0 050
0 0 1 0 0 0 1 0 17
0 30 33 3 0 0 1 050
x x x x x x x z
x
x
x
z
1 2 3 4 5 6 7
1
2
7
81 0 84 12 8 0 0 0
251 1 1 1
0 1 0 0 0500 2 15 30
0 0 1 0 0 0 1 0 12
0 0 18 1 1 0 1 025
x x x x x x x z
x
x
x
z
1 2 3 4 5 6 7
1
2
7
81 0 84 12 8 0 0 0
251 1 1 1
0 1 0 0 0500 2 15 30
0 0 1 0 0 0 1 0 12
0 0 18 1 1 0 1 025
x x x x x x x z
x
x
x
z
1 2 3 4 5 6 7
3
2
7
25 525 750 1 25 0 0 0
8 2 21 1 1 1
1 0 0 0 0160 40 120 6025 525 75
0 0 25 1 0 18 2 21
0 0 3 2 3 0 1 04
x x x x x x x z
x
x
x
z
1 2 3 4 5 6 7
3
2
7
25 525 750 1 25 0 0 0
8 2 21 1 1 1
1 0 0 0 0160 40 120 6025 525 75
0 0 25 1 0 18 2 21
0 0 3 2 3 0 1 04
x x x x x x x z
x
x
x
z
1 2 3 4 5 6 7
3
4
7
12510500 1 0 50 150 0 0 0
21 1 2
40 0 1 0 0 04 3 3
12510500 0 0 50 150 1 0 1
21
120 0 0 1 1 0 1 02
x x x x x x x z
x
x
x
z
1 2 3 4 5 6 7
3
4
7
12510500 1 0 50 150 0 0 0
21 1 2
40 0 1 0 0 04 3 3
12510500 0 0 50 150 1 0 1
21
120 0 0 1 1 0 1 02
x x x x x x x z
x
x
x
z
1 2 3 4 5 6 7
5
4
7
5 1210 0 1 3 0 0 0
4 501 1 1
30 1 0 0 0 06 150 30 0 1 0 0 0 1 0 17 1
330 0 0 2 0 1 04 50
x x x x x x x z
x
x
x
z
1 2 3 4 5 6 7
5
4
7
5 1210 0 1 3 0 0 0
4 501 1 1
30 1 0 0 0 06 150 30 0 1 0 0 0 1 0 17 1
330 0 0 2 0 1 04 50
x x x x x x x z
x
x
x
z
1 2 3 4 5 6 7
5
6
7
1 160 9 1 0 0 0 0
4 251 1
90 3 0 1 0 0 02 500 0 1 0 0 0 1 0 13 1
150 6 0 0 0 1 04 50
x x x x x x x z
x
x
x
z
Illustration graphique de la dégénerescence
0,,,,,10223 262y àSujet
23 Min
0,1022
3 262y àSujet
23 Min
4321
4
3
2
1
ssssyxsyx
syxsyx
sxyx
yxyxyxyx
xyx
1s
2s
4s
3s
005668
86
1s
2s
4s
3s
0,,,,,,185610223 262y àSujet
23 Min
0,1856
1022
3 262y àSujet
23 Min
54321
5
4
3
2
1
sssssyxsyx
syxsyx
syxsx
yx
yxyx
yxyx
yxx
yx
5s
0005668
86
Convergence dans le cas dégénéré
1, ,
La variable d'entrée est celle ayant le plus petit indice parmi les variables hors ba
Critères d'entré
se ayant un coûtCritère
relatif
e et de
négati
sor
f; id'e
.e.
tie
, ntrée:
de Bland:
Min :
s
j n
x
s j c
0 .
La variable de sortie ( dénotant la variable de base
dans la ligne du tableau) est celle ayant le plus petit indice parmi les variables
Critère
candida
de sortie:
tes à sortir de la bas
j
j jr rième
x x
r
1, , 1, ,
e; i.e.,
Min : 0, Min : 0 .l ir l ls is
l m i mls is
b bj j a a
a a
La variable de sortie ( dénotant la variable de base
dans la ligne du tableau) est celle ayant le plus petit indice parmi les variables candidates à sortir de la base;
Critère de sort :
ie
i
j jr rième
x x
r
1, , 1, ,
1, ,
.e.,
Min : 0, Min : 0 .
LorsquNote
e
Min : 0
est atteint pour plusieurs indices , alors la variable de
très importante:
b
l ir l ls is
l m i mls is
l iis
i mls is
b bj j a a
a a
b ba
a al
ase choisi selon le critère précédent pour devenir variable de sortie devient égale à 0. Par contre les autres variables où ce Min est atteint r
mais
estent dans la base
deviennent aussi égales à
jr
jl
x
x
0.
1 2 3 4 5 6 7
5
6
7
1 160 9 1 0 0 0 0
4 251 1
90 3 0 1 0 0 02 500 0 1 0 0 0 1 0 13 1
150 6 0 0 0 1 04 50
x x x x x x x z
x
x
x
z
1 2 3 4 5 6 7
1
6
7
41 240 36 4 0 0 0 0
253
0 30 15 2 1 0 0 050
0 0 1 0 0 0 1 0 17
0 30 33 3 0 0 1 050
x x x x x x x z
x
x
x
z
1 2 3 4 5 6 7
1
6
7
41 240 36 4 0 0 0 0
253
0 30 15 2 1 0 0 050
0 0 1 0 0 0 1 0 17
0 30 33 3 0 0 1 050
x x x x x x x z
x
x
x
z
1 2 3 4 5 6 7
1
2
7
81 0 84 12 8 0 0 0
251 1 1 1
0 1 0 0 0500 2 15 30
0 0 1 0 0 0 1 0 12
0 0 18 1 1 0 1 025
x x x x x x x z
x
x
x
z
1 2 3 4 5 6 7
1
2
7
81 0 84 12 8 0 0 0
251 1 1 1
0 1 0 0 0500 2 15 30
0 0 1 0 0 0 1 0 12
0 0 18 1 1 0 1 025
x x x x x x x z
x
x
x
z
1 2 3 4 5 6 7
3
2
7
25 525 750 1 25 0 0 0
8 2 21 1 1 1
1 0 0 0 0160 40 120 6025 525 75
0 0 25 1 0 18 2 21
0 0 3 2 3 0 1 04
x x x x x x x z
x
x
x
z
1 2 3 4 5 6 7
3
2
7
25 525 750 1 25 0 0 0
8 2 21 1 1 1
1 0 0 0 0160 40 120 6025 525 75
0 0 25 1 0 18 2 21
0 0 3 2 3 0 1 04
x x x x x x x z
x
x
x
z
1 2 3 4 5 6 7
3
4
7
12510500 1 0 50 150 0 0 0
21 1 2
40 0 1 0 0 04 3 3
12510500 0 0 50 150 1 0 1
21
120 0 0 1 1 0 1 02
x x x x x x x z
x
x
x
z
1 2 3 4 5 6 7
3
4
7
12510500 1 0 50 150 0 0 0
21 1 2
40 0 1 0 0 04 3 3
12510500 0 0 50 150 1 0 1
21
120 0 0 1 1 0 1 02
x x x x x x x z
x
x
x
z
1 2 3 4 5 6 7
3
4
1
0 0 1 0 0 0 1 0 12 1 1 1
0 2 0 1 015 5 250 250100 300 2 1
1 168 0 0 0125 125 125 125175 275 1 1
0 36 0 0 1125 125 125 125
x x x x x x x zx
x
x
z
1 2 3 4 5 6 7
3
4
1
0 0 1 0 0 0 1 0 12 1 1 1
0 2 0 1 015 5 250 250100 300 2 1
1 168 0 0 0125 125 125 125175 275 1 1
0 36 0 0 1125 125 125 125
x x x x x x x zx
x
x
z
1 2 3 4 5 6 7
3
5
1
0 0 1 0 0 0 1 0 115 3 3 3
0 15 0 1 02 2 100 100
150 5 51 180 0 6 0 0
125 125 12521 1 1 1
0 15 0 0 12 10 20 20
x x x x x x x zx
x
x
z
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 par contradiction)
Théorèm
Suppos
e 4
onsPreuve. qu'
.2:
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 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
Pre
d
uve.
e 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, , l'ensemble des indices des variables
d'entrée au cours des itérations du cycle. Donc si , alors
demeure une variable de base au cours de toutes les itérations du
cycle ou ell
j
n
j x
e 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, , l'ensemble des indices des variables
d'entrée au cours des itérations du cycle. Donc si , alors
demeure une variable de base au cours de toutes les itérations
cycle ou elle d
j
n
j x
emeure 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
Max ,
et utilisons l'indice supérieur pour désigner les éléments du
tableau du simplexe à l'itération où devient variable d'entrée.
j
g
g j
x
Dénotons également
Max ,
et utilisons l'indice supérieur pour désigner les éléments du
tableau du simplexe à l'itération où devient variable d'entrée.
j
g
g j
x
1 2
11 12 1 1 1
21 22 2 2 2
1 2
1 2
0
0
0
1
g n
g n
g n
m m mg mn m
g n
x x x x z
a a a a b
a a a a b
a a a a b
c c c c z
2
1
T1
TDénotons par la dernière ligne du tableau:
= 1 .
n
g nh c c
h
c
R
c
1 2
11 12 1 1 1
21 22 2 2 2
1 2
1 2
0
0
0
1
g n
g n
g n
m m mg mn m
g n
x x x x z
a a a a b
a a a a b
a a a a b
c c c c z
2
1
T1
TDénotons par la dernière ligne du tableau:
= 1 .
n
g nh c c
h
c
R
c
Puisque 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 ont un
coût relatif plus grand ou égal à 0. De plus puisque Max
alors
g
j
x
g
g j
0 et 0 , . (2.1)g g j jh c h c j j g
1 2
11 12 1 1 1
21 22 2 2 2
1 2
1 2
0
0
0
1
g n
g n
g n
m m mg mn m
g n
x x x x z
a a a a b
a a a a b
a a a a b
c c c c z
2
1
T1
TDénotons par la dernière ligne du tableau:
.= 1g
n
nh c c c
h R
c
Puisque le tableau précédent a été obtenu du tableau original
1 2
0
0
0
1g n
A
c c c c
Tà l'aide d'une suite de pivots, il s'ensuit que le vecteur 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.
h
Puisque 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
a
gx
1
ssocié à cette itération.
Dénotons par
, , , où
les variables de base à cette itération. Dénotons également par
la variable d'entrée identifiée avec le critère de Bland. Ainsi
est l'
r m rj j j j g
s
rs
x x x x x
x
a
élément de pivot.
1
1
1
11 1 1 1
1
1
1
0 1 0 0
1 0 0 0
0 0 1 0
0 0 0 1
r j m
r
m
j s j n
j s n
j r rs rn r
j m ms mn m
s n
x x x x x x z
x a a a b
x a a a b
x a a a b
z c c c z
1
1
Définissons un vecteur à partir des éléments dans la
colonne de la variable d'entrée dans le tableau précédent:
1, ,
1
0 autres indices
i
n
s
j is
s
n s
j
v R
x
v a i m
v
v c
v j
T1
Par rapport au tableau illustré plus
haut le vecteur prend la forme
0 1 0rs s ms s
v
v a a a c
1
1
1
11 1 1 1
1
1
1
0 1 0 0
1 0 0 0
0 0 1 0
0 0 0 1
r j m
r
m
j s j n
j s n
j r rs rn r
j m ms mn m
s n
x x x x x x z
x a a a b
x a a a b
x a a a b
z c c c z
10 1 0rs s ms sa a a c
T1
Par rapport au tableau illustré plus
haut le vecteur prend la forme
0 1 0rs s ms s
v
v a a a c
Le produit scalaire du vecteur avec chaque ligne du tableau
précédent est égal à 0. Ainsi est perpendiculaire a chaque
vecteur ligne du tableau.
v
v
10 1 0rs s ms sa a a c
10 1 0rs s ms sa a a c
1
1
1
11 1 1 1
1
1
1
0 1 0 0
1 0 0 0
0 0 1 0
0 0 0 1
r j m
r
m
j s j n
j s n
j r rs rn r
j m ms mn m
s n
x x x x x x z
x a a a b
x a a a b
x a a a b
z c c c z
1 2
0
0
0
1g n
A
c c c c
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 est
perpendiculaire aux lignes de cette matrice et qu'il est
donc orthogonal à l'espace engendré par les lignes de cette
dernière.
v
T
Donc il s'ensuit que
0.h v
T
1 2= 1g nh c c c c
1T
1
Donc il s'ensuit que
0.n
l ll
h v h v
1
1, ,
1
0 autres indices
ij is
s
n s
j
v a i m
v
v c
v j
1 1
Notons d'abord que
1 0.
Par conséquent, il doit exister au moins un indice 1
tel que 0.
Or
si 0, alors est une variable hors base dans le tableau d'ind
n n s
j j
j j
h v c
j j n
h v
h x
ice
supérieur
si 0, alors est une variable de base dans le tableau d'indice
supérieur , ou .
j jv x
j s
T
1 2= 1g nh c c c c
T
Donc il s'ensuit que
0.h v 1
1, ,
1
0 autres indices
ij is
s
n s
j
v a i m
v
v c
v j
Or
si 0, alors est une variable hors base dans le tableau d'indice
supérieur
si 0, alors est une variable de base dans le tableau d'indice
supérieur , ou .
j j
j j
h x
v x
j s
Donc l'indice doit appartenir à et alors
.
j
j g
Mais puisque
0 et 0,
il s'ensuit que .
g g g rsh c v a
j g
T
1 2= 1g nh c c c c
T
Donc il s'ensuit que
0.h v 1
1, ,
1
0 autres indices
ij is
s
n s
j
v a i m
v
v c
v j
Mais puisque
0 et 0,
il s'ensuit que .
g g g rsh c v a
j g
Il découle donc de (2.1)
que 0
et ainsi 0.
j
j
h
v
0 et 0 , . (2.1)g g j jh c h c j j g
Donc est une variable de base dans le tableau d'indice supérieur .jx
T
1 2= 1g nh c c c c
T
Donc il s'ensuit que
0.h v 1
1, ,
1
0 autres indices
ij is
s
n s
j
v a i m
v
v c
v j
0.jv Donc est une variable de base dans le tableau d'indice supérieur .jx
Soit tel que 0.p ps jj j a v
Donc est une variable de base dans le tableau d'indice supérieur .
Soit <g tel que 0.
j
p ps j
x
j j a v
1
1
1
11 1 1 1
1
1
1
1
0 1 0 0
1 0 0 0
1 0 0 0
0 0 1 0
0 0 0 1
r j m
r
p
m
j s j n
j s n
j r rs rn r
j p ps pn p
j m ms mn m
s n
x x x x x x z
x a a a b
x a a a b
x a a a b
x a a a b
z c c c z
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,
0
au cours de toutes les itérations du cycle.
jx j
Par conséquent =0. pj px b
Donc est une variable de base dans le tableau d'indice supérieur .
Soit <g tel que 0.
j
p ps j
x
j j a v
et que 0. pj px b
En somme, nous venons d'établir les deux faits suivants:
1
1
1
11 1 1 1
1
1
1
1
0 1 0 0
1 0 0 0
1 0 0 0
0 0 1 0
0 0 0 1
r j m
r
p
m
j s j n
j s n
j r rs rn r
j p ps pn p
j m ms mn m
s n
x x x x x x z
x a a a b
x a a a b
x a a a b
x a a a b
z c c c z
Ainsi cette variable
aurait dû être variable
de sortie à l'itération
selon le critère de
sortie de Bland.
pjx
0
Donc est une variable de base dans le tableau d'indice supérieur .
Soit <g tel que 0.
j
p ps j
x
j j a v
En somme, nous venons d'établir les deux faits suivants:
et que 0. pj px b
Ainsi cette variable 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 comme variable de sor
pj
g
x
x
tie.
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.
