Graphes et Recherche Operationnelle ESIAL 2A

Chapitre 2 : Methode du Simplexe

J.-F. Scheid

20122013

Plan du chapitre

Introduction

Progression de lalgorithme du simplexe (phase 2)

Methode des dictionnaires

Finitude du simplexe

Initialisation du simplexe (phase 1)

I. Introduction
On a vu que pour resoudre un PL, il suffit de se restreindre aux solutions
de bases realisables.
Methode du simplexe due `a Dantzig (1947).
Deux phases :
1

Phase 1 Initialisation : Trouver une solution de base realisable

(ou bien detecter limpossibilite).

Phase 2 Progression : On passe dun sommet `a un sommet voisin

pour augmenter la fonction objectif

Remarque : On appelle n-simplexe ou simplement simplexe, lenveloppe

convexe dun ensemble de n + 1 points (n = 1 : un segment, n = 2 : un
triangle, n = 3 : un tetra`edre)
3

II. Lalgorithme du simplexe proprement dit : Phase 2

PL sous forme standard
h
i
maxn F (x) = c> x
xR

Ax = b
x0
On dispose dune base B et dune solution de base realisable x avec (`a une
permutation pr`es des colonnes de A)


xB
A = (AB | AH )
et x =
xH
o`
u AB matrice m m, inversible (variables de base)
AH matrice m (n m) (variables hors-base)

II. Lalgorithme du simplexe proprement dit : Phase 2

PL sous forme standard
h
i
maxn F (x) = c> x
xR

Ax = b
x0
On dispose dune base B et dune solution de base realisable x avec (`a une
permutation pr`es des colonnes de A)


xB
A = (AB | AH )
et x =
xH
o`
u AB matrice m m, inversible (variables de base)
AH matrice m (n m) (variables hors-base)
But : on veut trouver une autre base B et une solution de base realisable
x telles que x est meilleur que x c-`a-d
F (x ) > F (x)
4

Principe de la m
ethode du simplexe : faire rentrer une variable
hors-base dans la nouvelle base (variable entrante) et faire sortir `a la place
une variable de base (variable sortante).

Principe de la m
ethode du simplexe : faire rentrer une variable
hors-base dans la nouvelle base (variable entrante) et faire sortir `a la place
une variable de base (variable sortante).

1) Variable entrante - calcul des co

uts r
eduits
Fonction objectif F exprimee en fonction des variables hors-base.
Ensemble des solutions realisables DR = {x Rn |Ax = b, x 0}.

Proposition (Couts reduits)

Pour tout x DR , on a
F (x) = F (x) + L>
H xH
o`
u
>
> 1
L>
H = cH cB AB AH

est le vecteur des co

uts reduits.
5

D
emonstration.
On a b = Ax = AB xB + AH xH avec AB inversible donc
xB = A1
B (b AH xH ). On obtient donc
>
F (x) = c> x = c>
B xB + cH xH avec c =
1
>
= c>
B AB (b AH xH ) + cH xH

cB
cH

1
>
> 1
= c>
B AB b + (cH cB AB AH )xH
> 1
>
Or xB = A1
B b (car xH = 0) et cB AB b = c x = F (x) donc
> 1
F (x) = F (x) + (c>
H cB AB AH )xH .

Variable entrante
Si les co
uts reduits sont tous negatifs i.e. L>
H 0, il nest alors pas
possible daugmenter la fonction objectif F : lalgorithme se termine
normalement cest-`a-dire quon a trouve une solution de base
realisable x optimale.

Variable entrante
Si les co
uts reduits sont tous negatifs i.e. L>
H 0, il nest alors pas
possible daugmenter la fonction objectif F : lalgorithme se termine
normalement cest-`a-dire quon a trouve une solution de base
realisable x optimale.
Dans le cas contraire (i.e. (LH )i > 0), on a interet `a faire entrer
dans la base, la variable hors-base qui a le co
ut reduit
positif le plus grand possible.

Variable entrante
Si les co
uts reduits sont tous negatifs i.e. L>
H 0, il nest alors pas
possible daugmenter la fonction objectif F : lalgorithme se termine
normalement cest-`a-dire quon a trouve une solution de base
realisable x optimale.
Dans le cas contraire (i.e. (LH )i > 0), on a interet `a faire entrer
dans la base, la variable hors-base qui a le co
ut reduit
positif le plus grand possible.
On note e
/ B lindice de la variable entrante. On choisit e tel que
n
o
(LH )e = max (LH )j , (LH )j > 0
j

ce quon note par

n
o
e = argmax (LH )j , (LH )j > 0
j

Remarque. Si on traite dun probl`eme de minimisation cest-`a-dire avec

min F (x),
alors la variable entrante xe est determinee par lindice
n
o
e = argmin (LH )j , (LH )j < 0
j

2) Variable sortante
Une fois lindice e choisi, il faut determiner la variable qui doit quitter la
base. En maintenant la relation Ax = b avec x 0, on augmente la
variable entrante xe jusqu`a annuler une des variables de base. Cette
variable sera alors la variable sortante.

2) Variable sortante
Une fois lindice e choisi, il faut determiner la variable qui doit quitter la
base. En maintenant la relation Ax = b avec x 0, on augmente la
variable entrante xe jusqu`a annuler une des variables de base. Cette
variable sera alors la variable sortante.
Ax = b AB xB + Ae xe = b

o`
u Ae designe la e-i`eme colonne de A

2) Variable sortante
Une fois lindice e choisi, il faut determiner la variable qui doit quitter la
base. En maintenant la relation Ax = b avec x 0, on augmente la
variable entrante xe jusqu`a annuler une des variables de base. Cette
variable sera alors la variable sortante.
Ax = b AB xB + Ae xe = b

o`
u Ae designe la e-i`eme colonne de A

e
xB = A1
B (b A xe )

2) Variable sortante
Une fois lindice e choisi, il faut determiner la variable qui doit quitter la
base. En maintenant la relation Ax = b avec x 0, on augmente la
variable entrante xe jusqu`a annuler une des variables de base. Cette
variable sera alors la variable sortante.
Ax = b AB xB + Ae xe = b

o`
u Ae designe la e-i`eme colonne de A

e
xB = A1
B (b A xe )
e
xB = xB A1
B A xe

2) Variable sortante
Une fois lindice e choisi, il faut determiner la variable qui doit quitter la
base. En maintenant la relation Ax = b avec x 0, on augmente la
variable entrante xe jusqu`a annuler une des variables de base. Cette
variable sera alors la variable sortante.
Ax = b AB xB + Ae xe = b

o`
u Ae designe la e-i`eme colonne de A

e
xB = A1
B (b A xe )
e
xB = xB A1
B A xe

xB = xB zxe
avec
e
m
z = A1
B A R .

On doit avoir : xB = xB zxe 0

10

On doit avoir : xB = xB zxe 0

Si z 0, on peut augmenter xe autant quon veut, on aura toujours
la positivite de la variable de base xB . La fonction objectif nest pas
majoree sur DR (max F = +) arret de lalgorithme.

10

On doit avoir : xB = xB zxe 0

Si z 0, on peut augmenter xe autant quon veut, on aura toujours
la positivite de la variable de base xB . La fonction objectif nest pas
majoree sur DR (max F = +) arret de lalgorithme.
Sinon (i.e. il existe zi > 0), pour avoir la positivite (xB )i zi xe 0
pour tout i, on choisit la variable sortante xs pour laquelle le rapport
(xB )i /zi pour i = 1, , m avec zi > 0, est le plus petit possible :

10

On doit avoir : xB = xB zxe 0

Si z 0, on peut augmenter xe autant quon veut, on aura toujours
la positivite de la variable de base xB . La fonction objectif nest pas
majoree sur DR (max F = +) arret de lalgorithme.
Sinon (i.e. il existe zi > 0), pour avoir la positivite (xB )i zi xe 0
pour tout i, on choisit la variable sortante xs pour laquelle le rapport
(xB )i /zi pour i = 1, , m avec zi > 0, est le plus petit possible :
Variable sortante (indice) :
s = argmin
i

n (x )
o
B i
, zi > 0
zi

On a, dans ce cas, xs = 0 et xB 0.
10

Remarque. La valeur de la variable entrante est donnee par

xe = min
i

n (x )
o
B i
, zi > 0
zi

11

Methode du simplexe en phase 2 (progression)

1

Calcul des variables de base realisables :

Etant donne A = (AB | AH ), on calcule xB = AB1 b 0.
Calcul des co
uts reduits :
>
> 1
L>
H = cH cB AB AH

F (x) = F (x) + L>

H xH

Si LH 0 alors xB est une solution optimale ( arret de lalgo.).

12

Methode du simplexe en phase 2 (progression)

1

Calcul des variables de base realisables :

Etant donne A = (AB | AH ), on calcule xB = AB1 b 0.
Calcul des co
uts reduits :
>
> 1
L>
H = cH cB AB AH

F (x) = F (x) + L>

H xH

Si LH 0 alors xB est une solution optimale ( arret de lalgo.).

2

n
o
variable entrante : e = argmaxj (LH )j , (LH )j > 0

12

Methode du simplexe en phase 2 (progression)

1

Calcul des variables de base realisables :

Etant donne A = (AB | AH ), on calcule xB = AB1 b 0.
Calcul des co
uts reduits :
>
> 1
L>
H = cH cB AB AH

F (x) = F (x) + L>

H xH

Si LH 0 alors xB est une solution optimale ( arret de lalgo.).

2

n
o
variable entrante : e = argmaxj (LH )j , (LH )j > 0
variable sortante : Calcul de z = A1
Ae puis
n (xB )
o
B i
, zi > 0 .
s = argmini
zi

12

Methode du simplexe en phase 2 (progression)

1

Calcul des variables de base realisables :

Etant donne A = (AB | AH ), on calcule xB = AB1 b 0.
Calcul des co
uts reduits :
>
> 1
L>
H = cH cB AB AH

F (x) = F (x) + L>

H xH

Si LH 0 alors xB est une solution optimale ( arret de lalgo.).

2

n
o
variable entrante : e = argmaxj (LH )j , (LH )j > 0
variable sortante : Calcul de z = A1
Ae puis
n (xB )
o
B i
, zi > 0 .
s = argmini
zi
e et une nouvelle matrice A e dans
On obtient une nouvelle base B
B
e
laquelle la colonne A remplace la colonne As . Calcul de A1
e et
B
retour en 1.

12

III. Methode des dictionnaires

PL sous forme standard

>
max
 x F (x) = c x
Ax = b
x0

Principe: on exprime les variables de base xB ainsi que F en fonction des

variables hors-base xH . On obtient un syst`eme lineaire quon appelle
dictionnaire.

13

III. Methode des dictionnaires

PL sous forme standard

>
max
 x F (x) = c x
Ax = b
x0

Principe: on exprime les variables de base xB ainsi que F en fonction des

variables hors-base xH . On obtient un syst`eme lineaire quon appelle
dictionnaire.
Exemple du probl`eme de production.
Forme standard (variables decart e1 , e2 , e3 )
max
F (x1 , x2 ) = 6x1 + 4x2
3x1 + 9x2 + e1 = 81

4x1 + 5x2 + e2 = 55
2x + x2 + e3 = 20

1
x1 , x2 0, e1 , e2 , e3 0
13

? Etape 1.
Solution de base realisable initiale :
x1 = 0, x2 = 0, e1 = 81, e2 = 55, e3 = 20 avec F = 0.
Dictionnaire: On exprime les variables de base e1 , e2 , e3 en fonction
des variables hors-base x1 , x2 .
e1 = 81 3x1 9x2
e2 = 55 4x1 5x2
e3 = 20 2x1 x2
F = 6x1 + 4x2

14

? Etape 1.
Solution de base realisable initiale :
x1 = 0, x2 = 0, e1 = 81, e2 = 55, e3 = 20 avec F = 0.
Dictionnaire: On exprime les variables de base e1 , e2 , e3 en fonction
des variables hors-base x1 , x2 .
e1 = 81 3x1 9x2
e2 = 55 4x1 5x2
e3 = 20 2x1 x2
F = 6x1 + 4x2
Variable entrante xe : max>0 {6, 4} = 6 xe = x1 .

14

? Etape 1.
Solution de base realisable initiale :
x1 = 0, x2 = 0, e1 = 81, e2 = 55, e3 = 20 avec F = 0.
Dictionnaire: On exprime les variables de base e1 , e2 , e3 en fonction
des variables hors-base x1 , x2 .
e1 = 81 3x1 9x2
e2 = 55 4x1 5x2
e3 = 20 2x1 x2
F = 6x1 + 4x2
Variable entrante xe : max>0 {6, 4} = 6 xe = x1 .
Variable sortante xs : on maintient e1 0, e2 0, e3 0
81 55 20
x1 = min{ , , } = 10 xs = e3 .
>0
3 4 2

14

? Etape 1.
Solution de base realisable initiale :
x1 = 0, x2 = 0, e1 = 81, e2 = 55, e3 = 20 avec F = 0.
Dictionnaire: On exprime les variables de base e1 , e2 , e3 en fonction
des variables hors-base x1 , x2 .
e1 = 81 3x1 9x2
e2 = 55 4x1 5x2
e3 = 20 2x1 x2
F = 6x1 + 4x2
Variable entrante xe : max>0 {6, 4} = 6 xe = x1 .
Variable sortante xs : on maintient e1 0, e2 0, e3 0
81 55 20
x1 = min{ , , } = 10 xs = e3 .
>0
3 4 2
Nouvelle Solution de base realisable :
x1 = 10, x2 = 0, e1 = 51, e2 = 15, e3 = 0 avec F = 60.
14

? Etape 2.
Dictionnaire: On exprime la nouvelle variable de base x1 en fonction
de x2 et e3 (nouvelle variable hors-base). On utilise la 3`eme equation
du dictionnaire de letape 1 et on substitue x1 dans les autres
relations.
x1 = 10 21 x2 21 e3
e1 = 81 3(10 12 x2 12 e3 ) 9x2
e2 = 55 4(10 12 x2 12 e3 ) 5x2
F = 6(10 12 x2 12 e3 ) + 4x2

15

On obtient ainsi le dictionnaire (etape 2)

x1 = 10 12 x2 21 e3
e1 = 51

15
2 x2

+ 32 e3

e2 = 15 3x2 + 2e3
F = 60 + x2 3e3

16

On obtient ainsi le dictionnaire (etape 2)

x1 = 10 12 x2 21 e3
e1 = 51

15
2 x2

+ 32 e3

e2 = 15 3x2 + 2e3
F = 60 + x2 3e3
Variable entrante xe : max{1, 3} = 1 xe = x2 .
>0

16

On obtient ainsi le dictionnaire (etape 2)

x1 = 10 12 x2 21 e3
e1 = 51

15
2 x2

+ 32 e3

e2 = 15 3x2 + 2e3
F = 60 + x2 3e3
Variable entrante xe : max{1, 3} = 1 xe = x2 .
>0

Variable sortante xs : on maintient x1 0, e1 0, e2 0

10 51 15
x2 = min{
,
, } = 5 xs = e2 .
>0 1/2 15/2 3

16

On obtient ainsi le dictionnaire (etape 2)

x1 = 10 12 x2 21 e3
e1 = 51

15
2 x2

+ 32 e3

e2 = 15 3x2 + 2e3
F = 60 + x2 3e3
Variable entrante xe : max{1, 3} = 1 xe = x2 .
>0

Variable sortante xs : on maintient x1 0, e1 0, e2 0

10 51 15
x2 = min{
,
, } = 5 xs = e2 .
>0 1/2 15/2 3
Nouvelle Solution de base realisable (etape 2) :
15
27
x1 = , x2 = 5, e1 = , e2 = 0, e3 = 0 avec F = 65.
2
2
16

? Etape 3.
Dictionnaire: On exprime la nouvelle variable de base x2 en fonction
des variables hors-base e2 et e3 . On utilise la 3`eme equation du
dictionnaire de letape 2 et on substitue x2 dans les autres relations.
x2 = 5 13 e2 + 32 e3
x1 =
e1 =

15
2
27
2

+ 16 e2 56 e3
+ 52 e2 72 e3

F = 65 13 e2 37 e3

17

? Etape 3.
Dictionnaire: On exprime la nouvelle variable de base x2 en fonction
des variables hors-base e2 et e3 . On utilise la 3`eme equation du
dictionnaire de letape 2 et on substitue x2 dans les autres relations.
x2 = 5 13 e2 + 32 e3
x1 =
e1 =

15
2
27
2

+ 16 e2 56 e3
+ 52 e2 72 e3

F = 65 13 e2 37 e3
Tous les co
uts reduits sont 0 donc on ne peut plus augmenter F :
loptimum est atteint et la solution optimale est
x1 =

27
15
, x2 = 5, e1 = , e2 = 0, e3 = 0 avec max F = 65.
2
2
17

IV. Finitude du simplexe

A chaque etape de lalgorithme du simplexe (en phase 2), il y a des cas
remarquables qui conduisent tous `a larret de lalgorithme.

18

IV. Finitude du simplexe

A chaque etape de lalgorithme du simplexe (en phase 2), il y a des cas
remarquables qui conduisent tous `a larret de lalgorithme.
1

Si les co
uts reduits LH < 0, alors la solution de base realisable
courante est lunique optimum.

optimum unique
1111111111111111111111111111111111
0000000000000000000000000000000000
0000000000000000000000000000000000
1111111111111111111111111111111111
0000000000000000000000000000000000
1111111111111111111111111111111111
F(x)
0000000000000000000000000000000000
1111111111111111111111111111111111
0000000000000000000000000000000000
1111111111111111111111111111111111
0000000000000000000000000000000000
1111111111111111111111111111111111
0000000000000000000000000000000000
1111111111111111111111111111111111
0000000000000000000000000000000000
1111111111111111111111111111111111
0000000000000000000000000000000000
1111111111111111111111111111111111
0000000000000000000000000000000000
1111111111111111111111111111111111
0000000000000000000000000000000000
1111111111111111111111111111111111
DR
0000000000000000000000000000000000
1111111111111111111111111111111111
0000000000000000000000000000000000
1111111111111111111111111111111111
0000000000000000000000000000000000
1111111111111111111111111111111111
0000000000000000000000000000000000
1111111111111111111111111111111111
0000000000000000000000000000000000
1111111111111111111111111111111111
0000000000000000000000000000000000
1111111111111111111111111111111111
0000000000000000000000000000000000
1111111111111111111111111111111111
0000000000000000000000000000000000
1111111111111111111111111111111111
0000000000000000000000000000000000
1111111111111111111111111111111111
0000000000000000000000000000000000
1111111111111111111111111111111111
0000000000000000000000000000000000
1111111111111111111111111111111111

= Fmax

18

Si les co
uts reduits LH 0, alors il y a deux cas remarquables :
i) si (LH )e = 0 et xe > 0, alors loptimum nest pas unique.

optimums
1111111111111111111111111111111111
0000000000000000000000000000000000
0000000000000000000000000000000000
1111111111111111111111111111111111
0000000000000000000000000000000000
1111111111111111111111111111111111
0000000000000000000000000000000000
1111111111111111111111111111111111
0000000000000000000000000000000000
1111111111111111111111111111111111
0000000000000000000000000000000000
1111111111111111111111111111111111
0000000000000000000000000000000000
1111111111111111111111111111111111
0000000000000000000000000000000000
1111111111111111111111111111111111
0000000000000000000000000000000000
1111111111111111111111111111111111
0000000000000000000000000000000000
1111111111111111111111111111111111
0000000000000000000000000000000000
1111111111111111111111111111111111
DR
0000000000000000000000000000000000
1111111111111111111111111111111111
0000000000000000000000000000000000
1111111111111111111111111111111111
0000000000000000000000000000000000
1111111111111111111111111111111111
0000000000000000000000000000000000
1111111111111111111111111111111111
0000000000000000000000000000000000
1111111111111111111111111111111111
0000000000000000000000000000000000
1111111111111111111111111111111111
0000000000000000000000000000000000
1111111111111111111111111111111111
0000000000000000000000000000000000
1111111111111111111111111111111111
0000000000000000000000000000000000
1111111111111111111111111111111111
0000000000000000000000000000000000
1111111111111111111111111111111111
0000000000000000000000000000000000
1111111111111111111111111111111111

F(x) = Fmax

19

ii) si (LH )e = 0 et xe = 0, alors loptimum est unique (a priori). Dans ce

cas, la base est dite d
eg
en
er
ee cest-`a-dire quil existe une variable
de base nulle.
optimum unique dgnr
1111111111111111111111111111111111
0000000000000000000000000000000000
0000000000000000000000000000000000
1111111111111111111111111111111111
0000000000000000000000000000000000
1111111111111111111111111111111111
0000000000000000000000000000000000
1111111111111111111111111111111111
0000000000000000000000000000000000
1111111111111111111111111111111111
0000000000000000000000000000000000
1111111111111111111111111111111111
0000000000000000000000000000000000
1111111111111111111111111111111111
F(x)
0000000000000000000000000000000000
1111111111111111111111111111111111
0000000000000000000000000000000000
1111111111111111111111111111111111
0000000000000000000000000000000000
1111111111111111111111111111111111
0000000000000000000000000000000000
1111111111111111111111111111111111
DR
0000000000000000000000000000000000
1111111111111111111111111111111111
0000000000000000000000000000000000
1111111111111111111111111111111111
0000000000000000000000000000000000
1111111111111111111111111111111111
0000000000000000000000000000000000
1111111111111111111111111111111111
0000000000000000000000000000000000
1111111111111111111111111111111111
0000000000000000000000000000000000
1111111111111111111111111111111111
0000000000000000000000000000000000
1111111111111111111111111111111111
0000000000000000000000000000000000
1111111111111111111111111111111111
0000000000000000000000000000000000
1111111111111111111111111111111111
0000000000000000000000000000000000
1111111111111111111111111111111111
0000000000000000000000000000000000
1111111111111111111111111111111111

= Fmax

20

ii) si (LH )e = 0 et xe = 0, alors loptimum est unique (a priori). Dans ce

cas, la base est dite d
eg
en
er
ee cest-`a-dire quil existe une variable
de base nulle.
optimum unique dgnr
1111111111111111111111111111111111
0000000000000000000000000000000000
0000000000000000000000000000000000
1111111111111111111111111111111111
0000000000000000000000000000000000
1111111111111111111111111111111111
0000000000000000000000000000000000
1111111111111111111111111111111111
0000000000000000000000000000000000
1111111111111111111111111111111111
0000000000000000000000000000000000
1111111111111111111111111111111111
0000000000000000000000000000000000
1111111111111111111111111111111111
F(x)
0000000000000000000000000000000000
1111111111111111111111111111111111
0000000000000000000000000000000000
1111111111111111111111111111111111
0000000000000000000000000000000000
1111111111111111111111111111111111
0000000000000000000000000000000000
1111111111111111111111111111111111
DR
0000000000000000000000000000000000
1111111111111111111111111111111111
0000000000000000000000000000000000
1111111111111111111111111111111111
0000000000000000000000000000000000
1111111111111111111111111111111111
0000000000000000000000000000000000
1111111111111111111111111111111111
0000000000000000000000000000000000
1111111111111111111111111111111111
0000000000000000000000000000000000
1111111111111111111111111111111111
0000000000000000000000000000000000
1111111111111111111111111111111111
0000000000000000000000000000000000
1111111111111111111111111111111111
0000000000000000000000000000000000
1111111111111111111111111111111111
0000000000000000000000000000000000
1111111111111111111111111111111111
0000000000000000000000000000000000
1111111111111111111111111111111111

= Fmax

Si (LH )e > 0 et xe est non borne alors la fonction objectif

F nest pas majoree.
20

Finitude du simplexe
Une solution de base realisable est dite d
eg
en
er
ee si au moins une des
variables de base est nulle.

Theor`eme
Si au cours de lalgorithme du simplexe, aucune base rencontree nest
degeneree, alors lalgorithme se termine en un nombre fini diterations.

21

Finitude du simplexe
Une solution de base realisable est dite d
eg
en
er
ee si au moins une des
variables de base est nulle.

Theor`eme
Si au cours de lalgorithme du simplexe, aucune base rencontree nest
degeneree, alors lalgorithme se termine en un nombre fini diterations.
Demonstration. A une iteration donnee de lalgorithme :
soit on detecte une fonction objectif non majoree ( arret de lalgo.),
soit elle est strictement croissante car Feopt Fopt = (LH ) xe > 0
e

puisque (LH )e > 0 et xe > 0 (par hypoth`ese, aucune base rencontree

nest degeneree).
Par consequent, on ne rencontre jamais une base dej`a rencontree `a une
iteration precedente. Le nombre de solution de base realisable etant fini
( Cnm ), lalgorithme sarrete necessairement en un nombre fini
diterations.

21

Remarque: Sil existe une base degeneree, alors on peut rencontrer un

eventuel cyclage de lalgorithme : on retrouve une base dej`a rencontree et
on boucle indefiniment. Pour traiter les cas de degenerescence, on peut
appliquer la r`egle de Bland (1977) qui assure larret de lalgorithme en un
nombre fini diterations.

R`egle de Bland
Lorsque plusieurs variables sont susceptibles dentrer ou de sortir de la
base, on choisit toujours celle qui a lindice le plus petit.

22

V. Initialisation du simplexe (phase 1)

1) Introduction
Pour un PL sous forme canonique pure avec les contraintes
Ax b, x 0,
on peut determiner facilement une solution de base realisable dans le cas
o`
u b 0. En effet, sous forme standard les contraintes deviennent
Ax + e = b, avec x, e 0 o`
u e sont les variables decarts.
Une solution de base realisable evidente dans ce cas, est
x = 0,

e = b 0.

23

V. Initialisation du simplexe (phase 1)

1) Introduction
Pour un PL sous forme canonique pure avec les contraintes
Ax b, x 0,
on peut determiner facilement une solution de base realisable dans le cas
o`
u b 0. En effet, sous forme standard les contraintes deviennent
Ax + e = b, avec x, e 0 o`
u e sont les variables decarts.
Une solution de base realisable evidente dans ce cas, est
x = 0,

e = b 0.

Mais pour un PL sous forme standard, il ny a pas toujours de solution de

base realisable evidente.
Construction des solutions de base realisable = phase dinitialisation du
simplexe (phase 1).
23

2) Variables auxiliaires
PL sous forme standard

(PL)

h
i

F (x) = c> x
max
x
Ax = b

x0

On ne suppose pas que la matrice A Mmn est de rang plein, ni quil

existe bien des solutions realisables.

24

2) Variables auxiliaires
PL sous forme standard

(PL)

h
i

F (x) = c> x
max
x
Ax = b

x0

On ne suppose pas que la matrice A Mmn est de rang plein, ni quil

existe bien des solutions realisables.
Pour obtenir une solution de base realisable ou bien pour detecter
limpossibilite, on introduit un probl`eme de programmation lineaire
auxiliaire pour des variables supplementaires appelees variables
artificielles.

24

Programme auxiliaire
Le programme auxiliaire associe `a (PL) secrit

m
X

min
ai

(x,a) i=1
(PLA)
Ax + a = b

x0

a0
o`
u a = (a1 , , am ) sont appelees variables artificielles.

25

On a la propriete (evidente) suivante.

Proposition
Un (PL) admet une solution realisable si et seulement si le probl`eme
auxiliaire (PLA) admet une solution de base optimale avec a = 0.

26

On a la propriete (evidente) suivante.

Proposition
Un (PL) admet une solution realisable si et seulement si le probl`eme
auxiliaire (PLA) admet une solution de base optimale avec a = 0.
D
etermination dune solution de base r
ealisable via le probl`
eme
auxiliaire : On applique lalgorithme du simplexe au probl`eme auxiliaire
(PLA). A la fin du simplexe, le co
ut minimal est nul sinon on a detecte
limpossibilite pour (PL) (i.e. DR = ). Si tout sest deroule normalement
(co
ut nul), on cherche `a eliminer de la base toutes les variables artificielles.
Deux cas possibles :
1

On a reussi `a faire sortir toutes les variables artificielles. On passe `a la

phase 2 du simplexe.

Sil reste des variables artificielles dans la base (base degeneree) alors
les lignes associees `a ces variables sont des contraintes redondantes
quon elimine.
26

Resume de la phase dinitialisation du simplexe (phase 1)

On note Faux la valeur de la fonction objectif du probl`eme auxiliaire (PLA)
m
X
`a la fin du simplexe, cest-`a-dire Faux = min
ai .
(x,a)

i=1

Si Faux = 0 et @aj XB o`
u XB designe lensemble des variables de
base pour (PLA), alors fin normale de la phase 1. On passe `a la phase
2 du simplexe.

Si Faux = 0 et aj XB avec aj = 0, alors on supprime les lignes et

colonnes associees aux aj et on passe `a la phase 2.

Si Faux > 0 alors pas de solution realisable (DR = ).

27

Complexit
e du simplexe.
Complexite = nombre diteration dans le simplexe (phase2).
On peut construire des exemples avec une complexite exponentielle
en O(2n ) iterations (Klee-Minty, 1972).
Mais dans la pratique la complexite du simplexe crot peu avec le
nombre n de variables. En pratique, le nombre diterations est
proportionnel au nombre m de contraintes (de m `a 3m iterations).
Si on tient compte de la resolution des syst`emes lineaires avec une
formule de mise `a jour de linverse (Shermann-Morrison), on a O(m2 )
operations pour linverse.

28