Université Sorbonne Paris Nord

Institut Galilée - Ingénieur 2ème année

Optimisation Linéaire (OL) -G4SIOL-

Cours 3 - Algorithme du simplexe (2)

[Link]@[Link]

4 octobre 2020

1/47
Questions
L’algorithme du simplexe Phase II présenté précédemment consiste à passer de base
en base jusqu’à trouver une base correspondant à une solution optimale.

Plusieurs questions se posent alors :

I La validité de l’algorithme :
- est-ce qu’à chaque itération, il est possible d’exprimer la base en fonction des
variables hors-base ?
- est-ce que ces bases sont à chaque fois associées à des solutions réalisables ?
I La terminaison de l’algorithme :
- est-ce que l’algorithme du simplexe se terminer en un nombre fini d’itérations
par une solution optimale ou la détection d’un PL non-borné ?
- comment détecter les PL de domaine de définition vide ?
I Comment initialiser la phase II de l’algorithme par une première base si celle
des variables d’écart n’est pas réalisable ?
I Quelle est la complexité de l’algorithme du simplexe ?
I Et comment prouver formellement tout cela ?

2/47
Visualisation graphique

Visualisation graphique

Complexité

Notations matricielles et écriture en base

Théorèmes d’optimalité et validé du pivot

Dégénérescence et cyclage

Terminaison et validité de l’algorithme du simplexe

3/47
 Visualisation graphique

Visualisation graphique de l’algorithme du simplexe

(3)
x2
Considèrons à nouveau le PL (2)
H

max z = 6x1 + 5x2 I



x1 + x2 ≤ 8 (1)





−2x1 + 3x2 ≤ 6 (2) C

 x1 − x2 ≤ 2 (3)
 D B
x1 ≥ 0 (5)



 E G x1
x2 ≥ 0 (4) O A
F
(1)
Sa forme standard est :
max z = 6x1 + 5x2


x1 + x2 +e1 = 8 (1)




−2x1 + 3x2 +e2 = 6 (2)



x1 − x2 +e3 = 2 (3)
x1 ≥ 0 (5)




x2 ≥ 0 (4)




ei ≥ 0 i ∈ {1, 2, 3}
Etre à l’intersection de 2 droites parmi (1),...,(5) revient à annuler 2 variables parmis
x1 , x2 , x3 , e1 , e2 , e3 : c’est-à-dire à choisir une base ! 4/47
 Visualisation graphique

Visualisation graphique de l’algorithme du simplexe

Pour la base des variables d’écart B = {e1 , e2 , e3 }, on a le dictionnaire :
(3)
x2
(2)
H

e1 = + 8 - 1 x1 - 1 x2 I
e2 = + 6 + 2 x1 - 3 x2
C
e3 = + 2 - 1 x1 + 1 x2
z = + 0 + 6 x1 + 5 x2 D B
E G x1
O A
F
(1)

Cette base correspond à la solution où les variables hors-base x1 , x2 et x3 sont nulles :

c’est le point O (0,0)
qui correspond dans la forme standard au vecteur solution s0 = (0, 0, 8, 6, 2)
de valeur z = 0.

Il n’est pas optimal

(les coûts dans z des variables d’écarts ne sont pas tous négatifs ou nuls).
5/47
 Visualisation graphique

Visualisation graphique de l’algorithme du simplexe

Première itération :
On choisit comme variable entrante x1 (critère de Dantzig car 6>5).

On maintient x2 = 0 et on augmente x1 au maximum possible.

e1 ≥ 0 ⇔ x1 ≤ 8
e2 ≥ 0 ⇔ x1 ≥ −3
e3 ≥ 0 ⇔ x1 ≤ 2
Le plus contraignant est e3 qui va sortir de base.

(3)
Dans le dessin, augmenter x1 en maintenant x2
x2 = 0 : c’est se déplacer sur l’axe des abscisses (2)
à partir du point O(0,0). H

I
En faisant cela :
- on reste du “bon côté” de la droite (2), c’est-
C
à-dire que e2 va rester positif (non contraint).
- on se rapproche de (1) et (3) :
cela fait diminuer e1 et e3 . D B
- la première droite rencontrée est (3) : E G x1
e3 s’annule avant e1 . O A
F
(1) 6/47
 Visualisation graphique

Visualisation graphique de l’algorithme du simplexe

La nouvelle base est B = {x1 , e1 , e2 }

qui correspond à l’annulation de x2 et de e3 , c’est-à-dire le point d’intersection de (3)
et (4) : le point A(2,0).

On écrit le nouveau dictionnaire

e1 = + 6 - 2 x2 + 1 e3
e2 = + 10 - 1 x2 - 2 e3
x1 = + 2 + 1 x2 - 1 e3
z = + 12 + 11 x2 - 6 e3

La solution est s1 = (2, 0, 6, 10, 0) de valeur z = 12

qui n’est pas optimale car le coefficient de x2 n’est pas négatif ou nul.

7/47
 Visualisation graphique

Visualisation graphique de l’algorithme du simplexe

Deuxième itération :
La seule variable entrante possible est x2
On maintient e3 = 0 et on augmente x2 au maximum possible.
e1 ≥ 0 ⇔ x2 ≤ 3
e2 ≥ 0 ⇔ x2 ≤ 10
x1 ≥ 0 ⇔ x2 ≥ −2
Le plus contraignant est e1 qui va sortir de base. (3)
x2
Dans le dessin, augmenter x2 en maintenant (2)
e3 = 0 : c’est se déplacer sur la droite (3) à H
partir du point point A(2,0).
I

En faisant cela :
- on reste du “bon côté” de la droite (4), c’est- C
à-dire que x1 va rester positif (non contraint).
- on se rapproche de (1) et (2) : D B
cela fait diminuer e1 et e2 . E G
- la première droite rencontrée est (1) : x1
O A
e1 s’annule avant e2 . F
(1)
On atteint le point B(5,3).
8/47
 Visualisation graphique

Visualisation graphique de l’algorithme du simplexe

La nouvelle base est B = {x1 , x2 , e2 }

qui correspond à l’annulation de e1 et de e3 , c’est-à-dire le point d’intersection de (1)
et (3) : le point B(5,3).

On écrit le nouveau dictionnaire

x2 = + 3 - 1/ 2 e1 + 1/ 2 e3
e2 = + 7 + 1/ 2 e1 - 5/ 2 e3
x1 = + 5 - 1/ 2 e1 - 1/ 2 e3
z = + 45 - 11/ 2 e1 - 1/ 2 e3

La solution est s2 = (5, 3, 6, 0, 0) de valeur z = 45

qui est optimale car tous les coefficients dans z sont négatifs ou nuls.

9/47
Complexité

Visualisation graphique

Complexité

Notations matricielles et écriture en base

Théorèmes d’optimalité et validé du pivot

Dégénérescence et cyclage

Terminaison et validité de l’algorithme du simplexe

10/47
 Complexité

Complexité
Plaçons-nous sous les 3 hypothèse suivantes :
- l’algorithme est valide
- l’algorihme se termine (pas de cyclage)
- on connaît une base initiale pour démarrer la phase II
quelle est la complexité de la phase II ?

La vision géométrique précédente témoigne du fait qu’une base est associée à un point
extrême du polyèdre de définitions.
L’algorithme du simplexe consiste en fait à passer de base en base réalisable,
c’est-à-à-dire d’un point extrême à un autre.

On a vu qu’un point extrême est l’intersection de n inégalités parmi n + m : ce qui est

un nombre largement exponentiel de points :
contrairement à l’algorithme d’énumération, l’algorithme du simplexe ne considère que
les intersections à l’intérieur du polyèdre de définitions.

Mais combien peut-il y avoir d’intersections dans un polyèdre de définitions d’un PL ?

11/47
 Complexité

Pire-cas
Klee et Minty ont proposé le PL suivant :
Pn
Max 10n−j xj
 j=1
Pi−1 
2 j=1 xj + xi ≤ 100i−1 ∀i ∈ {1, . . . , n}
xj ≥ 0 ∀j ∈ {1, . . . , n}

Ce PL correspond a 2n − 1 points extrêmes : tous explorables l’un après l’autre par

l’algorithme du simplexe. Ce qui prouve qu’il peut falloir au moins 2n − 1 itérations de
l’algorithme du simplexe pour arriver à l’optimum dans un pire-cas.

Ainsi L’algorithme du simplexe est un algorithme de complexité exponentielle au sens

classique de la complexité pire-cas.

Beaucoup de résulats ont permis de déterminer des règles de choix de variables, de

pivot, de prétraitement efficaces permettant d’accélérer l’algorithme.
Néanmoins l’algorithme reste de complexité exponentielle (dans le pire des cas).

12/47
 Complexité

Nombre d’itérations constaté

Si l’algorithme du simplexe a une complexité exponentielle pire-cas,
les pire-cas apparaissent peu “en pratique” et un nombre faible d’itérations est
suffisant !

Il est difficile de définir exactement le terme “en pratique” :

- des PL provenant des problèmes d’optimisation réels où les coefficients sont
rationnels
- des coefficients de valeurs éloignées les unes des autres.
- ...
Il est difficile de définir ce “en pratique”... pourtant la réalité quotidienne de
l’utilisation de la PL est claire : aucun PL rencontré dans le quotidien d’un optimiseur
de l’industrie ne demande à l’algorithme du simplexe un temps dépassant quelques
minutes : même pour des PL de 200 000 variables et 200 000 inégalités !

Cette question de la présence faible de pire-cas laisse penser qu’il y existe une
structure combinatoire particulière dans ces PL “utilisé en pratique”.
C’est une question de recherche importante qui passionne à la fois les
algorithméticiens, les combinatoriciens et les géométriciens !
Avec une meilleure connaissance de cette structure polyédrale, on en saurait
davantage sur la fameuse question “P est il-différent de NP ?” (P? = NP).

13/47
 Complexité

Complexité de la Programmation Linéaire

L’algortihme du simplexe n’est pas le seul algorithme capable de résoudre tout
programme linéaire (en variable continue).

La complexité de la Programmation Linéaire se définit comme la complexité du

meilleur algorithme permettant de résoudre tout PL.

Posée explicitement dans les années 1870, la question de la complexité de la

programmation linéaire n’est pas résolue par Georges Dantzig lorsqu’il propose
l’algorithme du simplexe en 1947 car Klee et Minty prouve sa complexité expontielle
en 1970.

En 1979, Leonid Khatchian s’inspire de la méthode des ellipsoïdes connues dans un

autre cadre pour proposer un algorithme polynomial pour la Programmation Linéaire !
La Programmation Linéaire est donc polynomiale !

Mais le degré du polynome de la complexité de la méthode des ellipsoïdes est assez

élevé : cette méthode est très lente en pratique : elle est largement battu par
l’algorithme du simplexe sur les fameux cas pratiques.

En 1984, Narendra Karmarkar propose la méthode des points intérieurs qui est
polynomiale et efficace !
14/47
 Complexité

Résolution et solveurs
Un programme linéaire peut être résolu efficacement :
- par la méthode des points intérieurs (qui est polynomial)
- par l’algorithme du simplexe (qui est pourtant exponentiel).

Quelle méthode choisir ?

Depuis 1947, de nombreux travaux ont permis des implémentations efficaces de ces 2
méthodes : chacune progressant peu à peu.

Il existe de nombreux solveurs de programmation linéaire :

- des solveurs commerciaux Cplex (IBM), Gurobi, Xpress et même Matlab ou Excel...
- des solveurs universitaires : Lp (COIN-OR), Soplex (univesité ZIB)
- des solveurs libres : Glpk (gnu)

Les meilleurs d’entre eux peuvent résoudre des PL jusqu’à 200 000 variables et
200 000 contraintes en quelques minutes.

Remarque : En revanche, lorsque les variables doivent prendre des valeurs discrètes
(par exemple binaires), la Programmation Linéaire en Nombres Entiers (PLNE) est un
problème NP-difficile que les solveurs ont du mal à résoudre en général : la plupart des
PLNE contenant à peine un millier de lignes et colonnes ne peuvent pas être résolus
après plusieurs semaines de calculs.
15/47
 Complexité

Hypothèses

Revenons à l’algorithme du simplexe et à sa preuve.

En effet, cet algorithme est à la base de nombreuses méthodes pour des problèmes
célèbres (flots, affectations...).

Pour montrer la validité et la terminaison de l’algorithme du simplexe, plaçons-nous

sous l’hypothèses suivantes :
- on connaît une base initiale pour démarrer la phase II
- on définira aussi plus tard l’hypothèse de non cyclage
(Ces deux hypothèses seront levées dans le chapitre suivant).

16/47
Notations matricielles et écriture en base

Visualisation graphique

Complexité

Notations matricielles et écriture en base

Théorèmes d’optimalité et validé du pivot

Dégénérescence et cyclage

Terminaison et validité de l’algorithme du simplexe

17/47
 Notations matricielles et écriture en base

Notations matricielles
On présente ici l’algorithme du simplexe sous forme matriciel dans l’objectif de prouver
la validité de l’algorithme.

Considèrons un programme linéaire à n variables et m inégalités non-triviales sous sa

forme canonique
 n
X
Max z= cj xj



 
Max z = cT x



 j=1 

s.c. s.c.
 
n ↔
 X  Ax ≤b
aij xj ≤ bi ∀i ∈ {1, . . . , m}
 
x ≥0

 




 j=1
xj ≥ 0 ∀j ∈ {1, . . . , n}
où
• x ∈ IR n
• c ∈ IR n
• b ∈ IR m
• A est une matrice réelle à m lignes et n colonnes avec :
aij son coefficients de i-ème ligne et j-ème colonne.
On note Aj la j-ème colonne de A.
18/47
 Notations matricielles et écriture en base

Notations matricielles
Ecrivons la forme standard
 n
X
max cj xj



 
Max z = cT x


 j=1 
n
 
s.c.
 
↔
X
 s.c. aij xj +xn+i =bi ∀i ∈ {1, . . . , m}  [A I ]x ≤b
 


 j=1 
x ≥0



 xj ≥0 ∀j ∈ {1, . . . , n}
xn+i ≥ 0 ∀i ∈ {1, . . . , m}

où
• x ∈ IR n+m
• c ∈ IR n+m avec m nouvelles composantes nulles
• b ∈ IR m
• [ A I ] désigne une matrice obtenue en ajoutant à A les n colonnes de la
matrice identité I

19/47
 Notations matricielles et écriture en base

Base candidate

Une base candidate B est un ensemble de m indices de colonnes parmi les n + m

colonnes de la matrice [ A I ].

On note alors B(i) l’indice de la i-ème colonne choisie dans[ A I ].

On va également noter B la matrice associée à la base B, c’est-à-dire les m colonnes

B(i), i ∈ B.
h i
B = AB(1) AB(2) . . . AB(m)

On dit que les colonnes AB(1) , AB(2) . . . AB(m) sont les colonnes de base et les autres
colonnes les colonnes hors-bases.
Cela correspond exactement aux variables de base et hors-base de la version algébrique.

Une remarque importante : la base des variables d’écart correspond à la matrice

identité !

20/47
 Notations matricielles et écriture en base

Base
Ecrivons le PL suivant sous forme standard matricielle.

Min 5x1 +5x2 +3x3

x1 +3x2 +x3 ≤3
−x1 +3x3 ≤2
2x1 −x2 +2x3 ≤4
2x1 +3x2 −x3 ≤2
xi ≥ 0, ∀i ∈ {1, 2, 3}.

3 et m = 4 
n=
5 x1

 5  x2    
1 3 1 1 0 0 0 3
 
 3  x3
   
   −1 0 3 0 1 0 0 
  2 
c= 0 x = x4 [A I ]= b=
    
 2 −1 2 0 0 1 0   4 
0 x5
   
2 3 −1 0 0 0 1 2
   
 0   x6 
0 x7

21/47
 Notations matricielles et écriture en base

Base primale

On dit qu’une base est primale si la matrice B est inversible

i.e. si ses m colonnes sont linéairement indépendentes.

Si B est primale, on va réécrire le PL en utilisant la base B comme “clef” d’écriture.

Posons
I E j = B −1 Aj pour tout j ∈ {1, . . . , n + m}
le vecteur des coordonnées de la colonne Aj selon la base primale B
I E 0 = B −1 b
le vecteur des coordonnées de b sur B.

22/47
 Notations matricielles et écriture en base

Ecriture en base

Donc pour une colonne j ∈ {1, . . . , n + m} donnée, on a

Aj = BE j
ou encore
m
Elj AB(l)
X
Aj =
l=1

Rappelons que AB(l) est la l-ème colonne de B.

On peut donc dire que le réel Elj est la l-ème coordonnée de la colonne Aj sur la base
primale B
et donc que E j est le vecteur des coordonnées de la colonne Aj sur la base primale B.

23/47
 Notations matricielles et écriture en base

Ecriture en base  
1 3 1 1 0 0 0
 −1 0 3 0 1 0 0 
Sur l’exemple où [ A I ] =  
 2 −1 2 0 0 1 0 
2 3 −1 0 0 0 1
la base B = (A7 , A3 , A5 , A6 ) (en respectant cet ordre)
 
0 1 0 0
 0 3 1 0 
correspond à la matrice B =   0

2 0 1 
1 −1 0 0
C’est une base primale car sa matrice est inversible (q diagonale de produit des termes
diagonaux non nuls).

Essayons de déterminer E 1 “à la main” dans la base B ci-dessus :

On peut remarquer que :
I A1 = A4 − A5 + 2A6 + 2A7 par jeu des vecteurs canoniques A4 , A5 , A6 et A7
I et A3 = A4 + 3A5 + 2A6 − A7 (idem) donc A4 = A3 − 3A5 − 2A6 + A7
I Donc A1 =A3 − 4A 5
 + 3A
7

3
 1 
On a donc E 1 =  −4 .


0
24/47
 Notations matricielles et écriture en base

Ecriture en base

1 i m

Rappel : vecteur canonique εT
i = 0 ... 0 1 0 ... 0

Remarque importante : si B(i) = j alors E j est le vecteur canonique i .

En d’autre terme, si la j-ième colonne de [ A I ] est la i-ième colonne de la base, une
écriture en base B de cette j-ième colonne étant une combinaison linéaire : elle ne
peut être qu’elle-même : or elle est en i-ème position dans la base.

Exemple : Dans l’exemple précédent, on peut faire le même calcul que dans l’exemple
de E 1 pour obtenir E 5 mais on obtiendra
 
0
 0 
E5 =  5 7 3 5 6 5
 1  car A est la 3ème colonne de B = (A , A , A , A ) donc E = ε3 .


25/47
 Notations matricielles et écriture en base

Base et Hors-Base
Pour une base primale B, on considère également les colonnes hors-bases numérotées
N(1), N(2), . . . , N(n).
On a alors les matrices

B = AB(1) AB(2) . . . AB(n) N = AN(1) AN(2) . . . AN(n)

   
et

On note
xB = (xB(1) , xB(2) , . . . , xB(m) ) le vecteur des variables de base.
cB = (cB(1) , cB(2) , . . . , cB(m) ) le vecteur des coûts des variables de base.
xN = (xN(1) , xN(2) , . . . , xN(m) ) le vecteur des variables hors-base.
cN = (cN(1) , cN(2) , . . . , cN(m) ) le vecteur des coûts des variables hors-base.

Le PL s’écrit alors également

Max cB xB + cN xN
BxB + NxN = b
xB ≥ 0
xN ≥ 0

26/47
 Notations matricielles et écriture en base

Ecriture dictionnaire

En multipliant les contraintes par B −1 , on obtient

xB + B −1 NxN = B −1 b

et
xB = B −1 b − B −1 NxN .

En utilisant cela dans le PL, on obtient l’écriture dictionnaire vue dans la section
“algébrique” :
xB = B −1 b − B −1 NxN
avec l’écriture de z selon les variables hors-base

z = cB B −1 b + (cN − cB B −1 N)xN

27/47
 Notations matricielles et écriture en base

Coûts réduits (ou marginaux)

Un des résultats de cette écriture est la définition très importante en économie des
coûts marginaux.
Les coefficients des variables hors-bases dans cette écritures sont appellées coûts
réduits.

c̄N = cN − cB B −1 N

On les appelera aussi “coût marginaux” dans la section Dualité .

Dans l’écriture dictionnaire algébrique de la section précédente, c’est tout simplement

les coûts obtenus dans l’écriture de z selon les variables hors-base.

Remarque : Le coût réduit d’une variable de base est donc 0.

28/47
Théorèmes d’optimalité et validé du pivot

Visualisation graphique

Complexité

Notations matricielles et écriture en base

Théorèmes d’optimalité et validé du pivot

Dégénérescence et cyclage

Terminaison et validité de l’algorithme du simplexe

29/47
 Théorèmes d’optimalité et validé du pivot

Base primale réalisable

Une base primale est dite réalisable si E 0 = B −1 b ≥ 0.

En effet, si B est une base primale réalisable, alors la solution définie par

xB = E 0 et xN = 0

définit une solution réalisable du PL appelée solution de base associée à la BRP B.

Sa valeur objective correspondante est zB = cB E 0 .

Cas particulier important :

Si b ≥ 0, la base des variables d’écart est primale réalisable.
En effet, la matrice B est la matrice identité.
Cela revient à dire que dans une écriture sous forme canonique, si toutes les valeurs
bi ≥ 0, i = 1, . . . , m, alors la base des variables d’écart peut être la base initiale de la
phase II de l’algorithme du simplexe.

Deux cas sont donc à identifier :

- Si b ≥ 0, on peut ainsi initier l’algorithme du simplexe : que l’on appelle Phase II .
- Si b possède des valeurs négatives, la base des variables d’écart n’est pas réalisable :
il faut alors précéder la phase II d’une phase d’initialisation appelée Phase I (voir
section correspondante).
30/47
 Théorèmes d’optimalité et validé du pivot

Cas d’un PL non-borné

Un cas particulier de base mène à prouver qu’un PL est non-borné.

Lemme
Pour une base B donnée, s’il existe une colonne hors-base j de coût réduit srictement
positif et tel que E j = B −1 Aj ≤ 0, alors le PL est non-borné dans la direction
d’optimisation.

Preuve : Pour une telle base B et une telle colonne j, remarquons que la fonction
objectif s’écrit z = cB B −1 b + (cN − cB B −1 N)xN . Soit un réel M > 0, et considérons
la solution x̃ telle que x̃e = M, x̃k = 0 pour tout autre variable hors base k et les
valeurs x̃l des variables de base calculées par l’écriture dictionnaire. Alors on peut
remarquer que x̃ est solution du PL. Ainsi pour tout M > 0, il existe une solution
z > M, ce qui signifie que le PL est non-borné dans la direction d’optimisation. 

Dans l’énoncé algébrique de l’algorithme du simplexe, cela correspond à l’arrêt en cas

de solution infinie.

On dit aussi “oralement” que le PL admet une “solution infinie”.

31/47
 Théorèmes d’optimalité et validé du pivot

Critère d’optimalité
Théorème
Pour une base primale réalisable B et variables hors-base N,
si c̄N ≤ 0, i.e. si tous les coûts réduits sont négatifs ou nuls,
alors la solution de base associée à B est optimale.

Preuve : Considérons une base B ∗ suivant l’hypothèse. Dans cette base B ∗ , la

fonction objective z est écrite en fonction des variables hors-base, c’est-à-dire

z = cB B ∗−1 b + c̄N xN .

Or par hypothèse, c̄N ≤ 0 et par définition xN ≥ 0.

On obtient donc une borne supérieure

z ≤ cB B ∗−1 b

D’autre part, la solution x ∗ correspondante à B ∗ correspond exactement à une

solution de valeur cB B ∗−1 b : cette borne supérieure est donc atteinte pour x ∗ qui est
donc optimale. 

32/47
 Théorèmes d’optimalité et validé du pivot

Pivot
Deux bases B et B 0 sont dites voisines si B 0 est obtenue à partir de B en remplaçant
une colonne B s par une colonne Ae de A,

e si k = e
c’est-à-dire ∀k = 1, . . . , m B 0 (k) =
B(k) sinon

L’opération suivante, dite pivot permet de passer de B à B 0 :

- Repérons une colonne Ae hors-base telle que E e contient des composantes
strictement positive.
- Repérons une ligne s telle que Ese > 0.
- La ligne s sert alors de ligne d’échange

1 1 X Esj
xe = (B −1 b)s − e xB(s) − xj
Ese Es Ese
j∈N\{s}

- Dans les autres lignes (k 6= s), on substitue xe par l’expression précédente

E e Esj
!
Ee Ee
Ekj − k e
X
xB(k) = (B −1 b)k − ke (B −1 b)s − ke xB(s) − xj
Es Es Es
j∈N\{s}

33/47
 Théorèmes d’optimalité et validé du pivot

Pivot

La solution x 0 associée à la base B 0 est alors donnée par :

xN0 = 0
1
xe0 = Ese
(B −1 b)s
0 Eke
xB(k) = (B −1 b)k − Ese
(B −1 b)s pour les colonnes de la base B 0 autre que e.

La question est donc de savoir si la base B 0 est primale et réalisable.

34/47
 Théorèmes d’optimalité et validé du pivot

Pivot
Lemme
Si les deux conditions suivantes sont vérifiées :
i) Esj > 0
Eke
ii) (B −1 b)k − Ese
(B −1 b)s ≥ 0, pour tout k 6= s
Alors la base 0
B obtenu par pivot est primale réalisable.

Preuve : Remarquons que, par les hypothèses i) et ii), la solution x 0 associée à la base
B est bien positive ou nulle. Donc x 0 limitée aux variables initiales vérifient bien le PL.
Donc si B 0 est primale, B 0 est réalisable.
Pour prouver que B 0 est primale, c’est-à-dire que B 0 est inversible, nous allons prouver
que B 0 x = b admet une unique solution. On peut déjà remarquer que la restriction xB0
de x 0 à B est solution de B 0 x = b, donc ce système admet bien une solution. Soit x̃B
une solution de B 0 x = b. Posons alors x̃N = 0. Considérons alors le système

BxB + NxN = b et xN = 0.

Par l’écriture dictionnaire vue plus haut, on peut constater que ce système mène à une
unique solution, qui est précisemment xB0 . Donc ce système et par conséquent B 0 x = b
ont une unique solution. 
35/47
 Théorèmes d’optimalité et validé du pivot

Validité du pivot

On peut alors énoncer le résultat fondamental pour l’algorithme du simplexe.

Théorème
Si on peut choisir :
- une colonne entrante e de coût réduit c̄e > 0
- une colonne sortante s telle que

Eke −1
 
1 −1 −1
(B b)s = min (B b)k − (B b)s
Ese Ese

Alors B 0 est une base primale réalisable et zB 0 ≥ zB .

0
Si de plus, B 0 est telle que B −1 b ne possède aucune composante nulle,
alors zB 0 > zB .

36/47
 Théorèmes d’optimalité et validé du pivot

Validité du pivot

Preuve : En choisissant une des colonnes e et s ainsi définie, par le théorème

précédent, la base B 0 obtenue par pivot est une primale réalisable. En effet, en prenant
le min de toutes les formules ii), on vérifie bien les hypothèses du théorème précédent.
Posons zB (resp. zB 0 ) la valeur associée à B (resp. B 0 ). Or on a par pivot

zB 0 = zB + (ce − cB B ∗−1 Ae )xe0

1
Donc zB 0 = zB + (B −1 b)s (ce − cB B ∗−1 Ae ).
Ese
1
Or par hypothèse, Ese
(B −1 b)s ≥ 0 et (ce − cB B ∗−1 Ae ) > 0. Donc zB 0 ≥ zB .
1 −1
Si de plus Ese
(B b)s 0, on a zB 0 > zB . 

37/47
 Théorèmes d’optimalité et validé du pivot

Schéma de l’algorithme
On obtient alors l’algorithme :

Schéma de l’algorithme du simplexe Phase II :

Initialisation par une base réalisable B
si b ≥ : Pour i = 1, . . . , m, B(i) ← n + i
sinon utiliser la phase I (voir cours suivant)
Répéter
Calculer x solution de base associée à B
Calculer N matrice des variables hors-base pour B
Si (cN − cB B −1 N) ≤ 0 alors Retourner(x)
Choix d’une colonne Ae de N telle que ce − cB B −1 Ae > 0
Si E e = B −1 Ae ≤ 0 alors Retourner (“PL non-borné”)
Calculer s tel que

Eke −1
 
1 −1 −1
(B b)s = min (B b)k − (B b)s
Ese Ese

B(s) ← e
Fin Répéter
38/47
Dégénérescence et cyclage

Visualisation graphique

Complexité

Notations matricielles et écriture en base

Théorèmes d’optimalité et validé du pivot

Dégénérescence et cyclage

Terminaison et validité de l’algorithme du simplexe

39/47
 Dégénérescence et cyclage

Choix d’une variable sortante et dégénérescence

On remarque que lorsqu’à une itération passant de la matrice B à la matrice B 0 ,

0
s’il y a annulation d’un coefficient de B −1 b,
- plusieurs choix sont possibles pour la variable sortante
- la valeur de la fonction objective z reste inchangée

On appelle une base dégénérée une base B

telle que B −1 b possède au moins une composante nulle.

40/47
 Dégénérescence et cyclage

Pivot dégénéré
Ajoutons une inégalité au PL de l’exemple (3)
x2
(2)

max z = 6x1 + 5x2



x1 + x2 ≤ 8 (1)


(4)


−2x1 + 3x2 ≤ 6 (2)



x1 − x2 ≤ 2 (3)
x1 − 2x2 ≤ 2 (4)

x1


A

x1 ≥ 0 (Ox2 )




x2 ≥ 0 (Ox1 ) (1)
La droite (4) correspondant à la nouvelle inégalité :
- passe comme (1) et (Ox1 ) par le point A(2,0)
- ne coupe aucun point de l’espace de définition.

Si on note e4 sa variable d’écart, on voit que, dans les 3 cas de bases :

- B1 = {x1 , e2 , e3 , e4 }, hors-base : {x2 , e1 }
- B2 = {x1 , e1 , e2 , e3 }, hors-base : {x2 , e4 }
- B3 = {x1 , x2 , e1 , e3 }, hors-base : {e1 , e4 }
l’annulation des variables hors-base correspond au même point A(2,0) et à la même
solution s1 = (2, 0, 6, 10, 0) et donc à la même valeur z = 12.
41/47
 Dégénérescence et cyclage

Pivot dégénéré

Une itération du simplexe sur une des trois bases peut mener à passer sur une autre de
ces bases : l’itération sera dite dégénérée et le coût de z n’augmentera pas : on parle
d’itération “à vide”.

Souvent, après avoir explorer un lot de bases dégénérées correspondant à une même
solution, l’algorithme se poursuit avec une solution différente sur un nouveau point.

Il peut se produire un cyclage où l’on revient à la base d’origine et ainsi à l’infini !

Heureusement, plusieurs améliorations ont été mises au point pour éviter ce problème
du cyclage (voir chapitre suivant).

42/47
Terminaison et validité de l’algorithme du simplexe

Visualisation graphique

Complexité

Notations matricielles et écriture en base

Théorèmes d’optimalité et validé du pivot

Dégénérescence et cyclage

Terminaison et validité de l’algorithme du simplexe

43/47
 Terminaison et validité de l’algorithme du simplexe

Terminaison

Les deux hypothèses faites au-début de cette preuve peuvent alors se réécrire :
- hypothèse d’initialisation : b ≥ 0
- non-dégénérescence : chaque base B rencontré possède au moins une
composante de B −1 b non nulle

Remarque essentielle : Le nombre de bases primales réalisables est fini (car majoré
par le nombre de combinaisons de m colonnes parmi n + m colonnes).

44/47
 Terminaison et validité de l’algorithme du simplexe

Terminaison

Théorème
Sous les hypothèse précédentes, l’algorithme Phase II se termine.

Preuve : La boucle Répéter de l’algorithme consiste à passer de base en base.

Or si aucune base n’est dégénérée, à chaque itération la valeur de la fonction objective
augmente strictement.
Ainsi, l’algorithme parcourt uniquement des bases distinctes.
n
Or il existe un nombre fini de bases possibles (borné par Cm+n ).
Donc la boucle Répéter crée une suite finie de bases distinctes de valeurs z croissante.
Donc la boucle Répéter a un nombre fini d’itérations. 

45/47
 Terminaison et validité de l’algorithme du simplexe

Validité
Théorème
Sous les hypothèse précédentes, l’algorithme Phase II est valide.

Preuve : Notons B ∗ la dernière base de la boule Répéter (il en existe une car
l’algorithme se termine).
Trois cas sont possibles :
- soit pour B ∗ , le coût réduit est négatif ou nul pour chaque colonne et la base
rencontrée est donc optimale par le théorème du critère d’optimalité.
- soit pour B ∗ le coût réduit c̄e d’une des colonnes est positif avec une colonne
E e = B −1 Ae ≤ 0, dans ce cas, on prouve que le PL est non-borné par le
théorème correspondant.
- soit pour B ∗ le coût réduit c̄e d’une des colonnes est positif avec une colonne
E e = B −1 Ae possédant un coefficient strictement positif. Dans c cas, par le
théorème de validité du pivot et sous l’hypothèse qu’aucune des bases n’est
dégénérée : on peut réaliser une opération de pivot qui produit une base de
solution associée strictement supérieure à z ∗ . Ce qui contredit l’existence de ce
cas.
Ainsi, l’algorithme se termine soit en prouvant que le PL est non-borné, soit en
fournissant une base optimale. 
46/47
 Terminaison et validité de l’algorithme du simplexe

Prochain cours

Dans le cours suivant, pour terminer à la fois la preuve et obtenir un algorithme

complet, on s’intéressera aux deux cas :

Initialisation : utilisation de la phase I d’initialisation de l’algorithme du simplexe.

Dégénérescence : si au cours de l’algorithme une base est dégénérée, l’algorithme

doit prendre en compte la présence de cyclage.

47/47