Voir la source de Algorithme du simplexe

{{Confusion|texte=Ne pas confondre avec la [[méthode de Nelder-Mead]] qui s'applique aux problèmes d'optimisation non linéaires.}}

L{{'}}'''[[algorithme]] du [[simplexe]]''' est un algorithme de résolution des problèmes d'[[optimisation linéaire]]. Il a été introduit par [[George Dantzig]] à partir de 1947. C'est probablement le premier algorithme permettant de [[Optimisation (mathématiques)#Minimisation|minimiser]] une fonction sur un ensemble défini par des inégalités<ref>{{Citation étrangère|langue=en|Curiously, up to 1947 when I first proposed that a model based on linear inequalities be used for planning activities of large-scale enterprises, linear inequality theory had produced only 40 or so papers, in contrast to linear equation theory and the related subjects of linear algebra and approximation, which had produced a vast literature.}} George Dantzig (1990).</ref>. De ce fait, il a beaucoup contribué au démarrage de l'optimisation numérique. L'algorithme du simplexe a longtemps été la méthode la plus utilisée pour résoudre les problèmes d'[[optimisation linéaire]]. Depuis les années 1985-90, il est concurrencé par les [[méthodes de points intérieurs]], mais garde une place de choix dans certaines circonstances (en particulier si l'on a une idée des contraintes d'inégalité actives en la solution).

Le nom de l'algorithme est dérivé de la notion de [[simplexe]] et a été suggéré par [[Theodore Motzkin|Motzkin]]<ref>Murty (1983), commentaire 2.2.</ref>. En réalité, l'algorithme n'utilise pas de simplexes, mais certaines interprétations de l'ensemble admissible du problème renvoient au concept de simplexe.

'''Connaissances supposées''' : l'[[algèbre linéaire]], le [[Différentielle|calcul différentiel]], le vocabulaire de l'[[Optimisation (mathématiques)|optimisation mathématique]].

== Le problème à résoudre ==

Les problèmes d'[[optimisation linéaire]] que l'algorithme du simplexe résout consistent à minimiser une fonction linéaire de <math>n</math> variables réelles,
<center>
<math>
x=(x_1,\ldots,x_n)\in\R^n\mapsto c^\top x:=\sum_{i=1}^n\,c_ix_i,
</math>
</center>
où <math>c=(c_1,\ldots,c_n)\in\R^n</math>, sur un ensemble défini au moyen de contraintes affines (ou linéaires) d'égalité et d'inégalité. L'''ensemble admissible'' du problème est donc un [[Ensemble convexe|polyèdre convexe]], que nous noterons <math>{\mathcal A}_P</math> (A pour admissible, P pour primal). On écrit le problème sous la forme suivante
<center>
<math>
\left\{\begin{array}{l}
{\inf}_x\;c^\top x\\
x\in{\mathcal A}_P
\end{array}\right.
</math>.
</center>
L'ensemble admissible <math>{\mathcal A}_P</math> peut être défini de manières variées.
* La forme la plus couramment utilisée pour présenter et étudier les algorithmes, qui est celle supposée par l'algorithme du simplexe révisé, est la ''forme standard'' :<center>{{Saut|10px}}<math>{\mathcal A}_P=\{x\in\R^n:Ax=b,~x\geqslant0\},</math>{{Saut|10px}}</center>où <math>A\in\R^{m\times n}</math> est une [[Matrice (mathématiques)|matrice]] réelle de type <math>m\times n</math> et <math>b\in\R^m</math>. L'écriture <math>x\geqslant0</math> signifie que toutes les variables <math>x_i</math> doivent être positives. Sous cette forme, <math>{\mathcal A}_P</math> apparaît comme l'intersection d'un [[Espace affine|sous-espace affine]] et de l'[[orthant|orthant positif]].
* On rencontre aussi la ''forme canonique'' :<center>{{Saut|10px}}<math>{\mathcal A}_P=\{x\in\R^n:Ax\leqslant b\},</math>{{Saut|10px}}</center>où <math>A\in\R^{m\times n}</math> est une [[Matrice (mathématiques)|matrice]] réelle de type <math>m\times n</math>, <math>b\in\R^m</math> et l'inégalité <math>Ax\leqslant b</math> doit se comprendre composante par composante : <math>(Ax-b)_i\leqslant0</math>, pour <math>i\in[\![1,m]\!]\equiv\{1,\ldots,m\}</math>. Sous cette forme, <math>{\mathcal A}_P</math> apparaît comme l'intersection de <math>m</math> demi-espaces de <math>\R^n</math>. C'est souvent la forme utilisée pour illustrer le comportement de l'algorithme du simplexe.
Ces deux manières de représenter un [[Ensemble convexe|polyèdre convexe]] sont équivalentes dans le sens où l'on peut passer d'une expression à l'autre. Ainsi, un polyèdre convexe représenté par la forme standard <math>\{x\in\R^n:Ax=b,~x\geqslant0\}</math>, peut s'exprimer sous la forme canonique par
<center>
<math>
\{x\in\R^n:Ax\leqslant b,~-Ax\leqslant-b,~-x\leqslant0\}.
</math>
</center>
De même, un polyèdre convexe représenté par la forme canonique <math>\{x\in\R^n:Ax\leqslant b\}</math>, peut s'exprimer sous la forme standard par
<center>
<math>
\{(u,v,s)\in\R^n\times\R^n\times\R^m:Au-Av+s=b,~u\geqslant0,~v\geqslant0,~s\geqslant0\},
</math>
</center>
où <math>x</math> a été décomposé en <math>u-v</math> avec <math>u\geqslant0</math> et <math>v\geqslant0</math> et les composantes de <math>s</math> sont appelées des ''variables d'écart''.

== L'algorithme du simplexe primal ==

=== Vue d'ensemble ===

La version de l'algorithme du simplexe que nous présentons dans cette section est celle connue sous le nom d''''algorithme du simplexe révisé'''. On suppose que le problème à résoudre est écrit sous la forme standard
<center>
<math>
(P_L)\qquad
\left\{\begin{array}{l}
{\inf}_x\;c^\top x\\
Ax=b\\
x\geqslant0
\end{array}\right.
</math>.
</center>
Il consiste donc à minimiser la fonction linéaire <math>x\in\R^n\mapsto c^{\top}x</math>, aussi appelée ''fonction-coût'', sur l{{'}}''ensemble admissible''
<center>
<math>
{\mathcal A}_P:=\{x\in\R^n:Ax=b,~x\geqslant0\}.
</math>
</center>
Cet ensemble est un [[polyèdre convexe]], que l'on supposera non vide. On supposera également que
<center>
<math>A</math> est [[Surjection|surjective]],
</center>
c'est-à-dire que ses colonnes sont [[Indépendance linéaire|linéairement indépendantes]].

On peut [[Optimisation linéaire#Existence de solution|montrer]] que lorsque le problème <math>(P_L)</math> a une solution, il a une solution sur un [[Optimisation linéaire#sommet|sommet]] du polyèdre convexe <math>{\mathcal A}_P</math>. On sait comment calculer tous ces sommets, qui sont en nombre fini, si bien que le problème de résoudre <math>(P_L)</math> pourrait être de sélectionner le sommet qui donne à la fonction à minimiser sa plus petite valeur. Cependant, le nombre fini de sommets est en général très grand et dépend souvent exponentiellement des dimensions <math>n</math> et <math>m</math> du problème, si bien que cette approche ne pourrait être utilisée que pour résoudre des problèmes de petite dimension. L'algorithme du simplexe va rechercher une solution parmi les sommets de <math>{\mathcal A}_P</math>, mais en n'en calculant qu'une partie d'entre eux, en éliminant séquentiellement les sommets donnant à la fonction-coût une valeur supérieure à celle obtenue à l'itéré courant.

[[Image:Simplex description.png|thumb|right|Illustration de l'algorithme du simplexe.]]
L'algorithme du simplexe est géométriquement très simple : chaque itération consiste à passer d'un [[Optimisation linéaire#sommet|sommet]] ([[Points et parties remarquables de la frontière d'un convexe#face|face]] de dimension 0) du polyèdre convexe <math>{\mathcal A}_P</math> à un sommet adjacent en suivant une arête ([[Points et parties remarquables de la frontière d'un convexe#face|face]] de dimension 1) particulière de ce polyèdre, de manière à faire décroître la fonction-coût. S'il n'y a pas de sommet le long de l'arête sélectionnée (parce que cette arête a une longueur infinie), le problème sera non borné (la valeur minimale de la fonction-coût sera <math>-\infty</math>). Il est bien de garder cette idée générale à l'esprit car la description algébrique d'une itération est relativement longue et doit prendre en compte quelques cas particuliers (problème non borné et pas nul) qui distraient.

=== Quelques définitions ===

Si <math>x\in\R^n_+</math>, on note
<center>
<math>
I^+ (x) := \{i: x_i > 0 \}
\quad\mbox{et}\quad
I^0(x): = \{i: x_i = 0\}.
</math>
</center>
On rappelle que <math>x\in {\mathcal A}_P</math> est un [[Optimisation linéaire#sommet|sommet]] de <math>{\mathcal A}_P</math> si la sous-matrice <math>A_{\bullet I^+(x)}</math>, formée des colonnes de <math>A</math> avec indices dans <math>I^+(x)</math>, est injective ; on a donc nécessairement <math>|I^+(x)|\leqslant m</math> et on peut bien sûr avoir <math>|I^+(x)|<m</math>. On dit d'ailleurs qu'un sommet <math>x\in {\mathcal A}_P</math> est '''dégénéré''' si <math>|I^+(x)|<m</math> et qu'il est '''non dégénéré''' si <math>|I^+(x)|=m</math>.

On appelle '''base d'indices''' un ensemble <math>B</math> de <math>m</math> indices pris dans <math>[\![1,n]\!]</math> tels que la sous-matrice <math>A_{\bullet B}</math> formée des <math>m</math> colonnes correspondantes de <math>A</math> soit inversible. Si <math>x\in\R^n</math>, les composantes <math>x_i</math> avec <math>i\in B</math> sont alors dites '''basiques''' et celles avec <math>i\notin B</math> sont dites '''non basiques'''. On dit qu'une base d'indices <math>B</math> est '''associée''' à un sommet <math>x\in {\mathcal A}_P</math> si <math>I^+(x)\subset B</math>.

L'optimisation linéaire a son propre jargon, que l'on doit reconnaître si l'on veut comprendre les ouvrages et articles écrits par les spécialistes de la discipline, en particulier les contributions fondatrices. Certains termes, chargés d'histoire, apportent pourtant d'inutiles complications et confusions ; nous les éviterons. Il en va ainsi de ''solution'' pour désigner un point (pour nous, une solution sera une ''[[Optimisation (mathématiques)#Minimisation|solution]]'' du problème d'optimisation linéaire), de ''solution admissible'' pour désigner un ''[[Optimisation (mathématiques)#Minimisation|point admissible]]'' ou encore de ''solution basique admissible'' pour désigner un ''[[Optimisation linéaire#Sommet|sommet]]'' de <math>{\mathcal A}_P</math>. Nous nous sommes permis de simplifier cette terminologie compliquée et de l'accorder avec celle utilisée en analyse convexe et en optimisation non linéaire.

{| class="wikitable" align="center" style="text-align:center; width:90%;"
|-
! scope=col | Jargon de l'optimisation linéaire
! scope=col | Terminologie adoptée
|-
| base
| base d'indices
|-
| solution
| point
|-
| solution admissible
| point admissible
|-
| solution basique
| -
|-
| solution basique admissible
| sommet
|-
| solution admissible optimale
| solution
|-
| solution basique admissible optimale
| solution-sommet
|}

=== Description raisonnée de l'algorithme ===

Une itération de l'algorithme démarre donc en un sommet <math>\hat{x}</math> de <math>{\mathcal A}_P</math>. Le calcul d'un tel sommet n'est pas une opération triviale, mais nous verrons [[#Démarrage de l'algorithme|plus loin]] comment on peut la réaliser. On note <math>B</math> une base d'indices associée à ce sommet et <math>N</math> le complémentaire de <math>B</math> dans <math>[\![1,n]\!]</math>. Au départ de l'itération, on a donc
<center>
<math>
\hat{x}_B \geqslant 0, \quad \hat{x}_N = 0 \quad\mbox{et}\quad
A_{\bullet B} \hat{x}_B = b  \quad
\mbox{(donc}~ \hat{x}_B = A_{\bullet B}^{-1} b),
</math>
</center>
où, comme précédemment, <math>A_{\bullet B}</math> (resp. <math>A_{\bullet N}</math>) désigne la sous-matrice de <math>A</math> formée de ses colonnes avec indices dans <math>B</math> (resp. <math>N</math>).

L'algorithme du simplexe génère en réalité une suite de bases d'indices plutôt qu'une suite de sommets. Il y a une distinction entre les deux notions lorsque le sommet est dégénéré, auquel cas il peut y avoir plusieurs bases d'indices correspondant à un même sommet. Si l'algorithme du simplexe visite un sommet dégénéré, il est possible qu'il ne change pas de sommet à l'itération suivante, mais il changera alors de base d'indices. Cependant, décrire l'algorithme en matière de bases d'indices fait perdre l'aspect géométrique de l'algorithme, qu'il nous semble précieux de conserver. Dès lors, nous considérerons que l'itéré de l'algorithme est un sommet, mais que certaines itérations font un déplacement nul.

'''Reconnaître l'optimalité'''

Soit <math>x</math> un point de l'ensemble admissible <math>{\mathcal A}_P</math>, qui vérifie donc <math>Ax = b</math>. Comme <math>B</math> est une base d'indices, on peut exprimer les composantes basiques <math>x_B</math> de <math>x</math> en fonction de <math>b</math> et de ses composantes non basiques <math>x_N</math> :
<center>
<math>
x_B = A_{\bullet B}^{-1} (b - A_{\bullet N} x_N).
</math>
</center>
On peut également exprimer le coût <math>c^\top x</math> en fonction de <math>x_N</math> :
<center>
<math>
c^\top  x = c^\top_B A_{\bullet B}^{-1} (b - A_{\bullet N} x_N) + c^\top_N x_N.
</math>
</center>
Son gradient par rapport à <math>x_N</math> est appelé le ''[[coût réduit]]''. Il s'écrit
<center>
<math>
r = c_N - A^\top_N A_{\bullet B}^{-\top} c_B.
</math>
</center>
Dans l'algorithme du simplexe, ce coût réduit sert, d'une part, à détecter l'optimalité éventuelle de l'itéré courant <math>\hat{x}</math> et, d'autre part, à sélectionner une arête de <math>{\mathcal A}_P</math> le long de laquelle la fonction-coût décroît lorsque <math>\hat{x}</math> n'est pas optimal.

{{Théorème|nom=Proposition|Un sommet <math>\hat{x}</math> de <math>{\mathcal A}_P</math> est solution du problème <math>(P_L)</math> si, et seulement si, il existe une base d'indices <math>B\subset[\![1,n]\!]</math> associée à <math>\hat{x}</math> telle que le coût réduit <math>r\geqslant0</math>.}}

Si un sommet optimal est dégénéré, il peut y avoir un coût réduit <math>r\ngeqslant0</math> pour une base d'indices arbitraire associée à ce sommet, comme le montre l'exemple suivant :
<center>
<math>
\left\{\begin{array}{l}
\min\,2x_1+x_2\\
x_1+x_2=0\\
x\geqslant0.
\end{array}\right.
</math>
</center>
L'ensemble admissible est réduit au singleton <math>\{(0,0)\}</math>. La solution du problème est donc forcément <math>\hat{x}=(0,0)</math>, qui est un sommet dégénéré. Si l'on prend pour base d'indices <math>B=\{1\}</math>, le coût réduit <math>r=-1</math> est strictement négatif. Ceci signifie que l'on peut faire décroître le critère en augmentant <math>x_N=x_2</math> tout en satisfaisant la contrainte d'égalité (c'est le sens du coût réduit). Mais ici on ne peut pas augmenter <math>x_2</math> sans sortir de l'ensemble admissible (ce ne serait pas le cas si le sommet était non dégénéré). À l'inverse, si l'on prend pour base d'indices <math>B=\{2\}</math>, le coût réduit <math>r=1</math> est positif, ce qui est annoncé par la proposition (il n'y a pas d'autre base d'indices).

La technique utilisée par l'algorithme du simplexe pour détecter l'optimalité éventuelle du sommet courant <math>\hat{x}</math> est la positivité du coût réduit, calculé en utilisant la base d'indices <math>B</math> courante. Il s'agit d'un critère essentiellement primal (il ne fait pas intervenir de multiplicateur ou variable duale). Lorsque l'itéré courant est un sommet-solution ''non dégénéré'', il n'y a qu'une seule base d'indices associée à ce sommet, si bien que le coût réduit est positif et l'algorithme s'interrompt. À l'inverse, lorsque l'itéré courant est un sommet-solution ''dégénéré'', il se peut que la base d'indices courante ne permette pas d'avoir un coût réduit positif. Il est donc important que l'algorithme dispose d'un mécanisme lui permettant de changer de base d'indices si cela est nécessaire jusqu'à en trouver une permettant d'avoir un coût réduit positif (comme dans l'exemple ci-dessus). Un mécanisme permettant d'obtenir la convergence de l'algorithme du simplexe (c'est-à-dire d'éviter son cyclage) est appelé ''règle d'anti-cyclage'' ; les principales règles d'anti-cyclage seront vues [[#Règles d'anti-cyclage|ci-dessous]].

'''Déplacement le long d'une arête'''

Si <math>r</math> a une composante strictement négative, disons <math>r_j<0</math>, cela veut dire que l'on peut faire décroître le coût en augmentant la composante <math>j</math> de <math>\hat{x}_N</math>. On est donc tenté de chercher un nouveau point admissible en faisant un déplacement suivant une direction <math>d</math>, c'est-à-dire
<center>
<math>
x(\alpha) = \hat{x} + \alpha d,
</math>
</center>
telle que la composante non basique de <math>d</math> soit
<center>
<math>
d_N=e^j_N.
</math>
</center>
On a noté <math>e^j</math> le <math>j</math>-ième [[vecteur de base]] de <math>\R^n</math> et <math>e^j_N=(e^j)_N</math>. Pour que ce déplacement <math>d=(d_B,d_N)</math> soit acceptable, il faut d'abord que l'on ait <math>Ax(\alpha)=b</math>, donc <math>Ad=0</math>, ce qui détermine sa composante basique :
<center>
<math>
d_B = - A_{\bullet B}^{-1} A_{\bullet N} e^j_N.
</math>
</center>

''Sur le choix de l'indice <math>j</math>''. Remarquons que le coût décroît bien le long de <math>d</math> puisque l'on a
<center>
<math>
c^{\top} d=r_j<0.
</math>
</center>
Si <math>r</math> a plusieurs composantes strictement négatives, il semble donc raisonnable de choisir l'indice <math>j</math> parmi ceux donnant la composante de <math>r</math> la plus négative. C'est ce que l'on appelle la '''règle du coût réduit minimal'''. Cette règle ne garantit cependant pas l'efficacité globale de l'algorithme qui est principalement liée au nombre total d'itérations, c'est-à-dire au nombre de sommets visités (aspect global), ce qui ne peut se déduire d'un calcul de dérivée (aspect local). D'autres règles existent (comme celles introduites par les règles d'anti-cyclage décrites à la section [[#Règles d'anti-cyclage|Règles d'anti-cyclage]]) et les algorithmes du simplexe diffèrent en particulier par l'heuristique adoptée à cette étape.

Il est intéressant d'observer que le déplacement porté par la direction <math>d</math> se fait le long d'une arête de <math>{\mathcal A}_P</math>.

{{Théorème|nom=Proposition|Soient <math>d</math> défini comme ci-dessus et <math>D:=\{\hat{x}+\alpha d\in {\mathcal A}_P:\alpha\geqslant 0\}</math>. Alors soit <math>D</math> est réduit au sommet <math>\{\hat{x}\}</math>, soit <math>D</math> est une arête de <math>{\mathcal A}_P</math>.}}

'''Détection d'un problème non borné'''

Si <math>d_B \geqslant 0</math>, alors
<center>
<math>
\forall\, \alpha > 0:\qquad x(\alpha) \geqslant 0,
</math>
</center>
et comme le coût <math>c^{\top}x(\alpha) = c^{\top}\hat{x} + \alpha c^{\top}d</math> décroît strictement le long de la direction de descente <math>d</math>, le problème n'est pas borné.

'''Nouvelle base d'indices'''

Si <math>d_B \ngeqslant 0</math>, on ne peut plus prendre un pas arbitrairement grand. Pour que l'on ait <math>x(\alpha)_B\geqslant 0</math>, il faut que <math>\alpha\leqslant\hat{\alpha}</math>, où
<center>
<math>
\hat{\alpha} = \min  \left\{ - \frac{\hat{x}_i }{ d_i}: i \in B,~ d_i < 0 \right\}.
</math>
</center>
Lorsque le sommet <math>\hat{x}</math> est dégénéré (il y a des <math>\hat{x}_i=0</math> pour <math>i \in B</math>), ce pas maximal <math>\hat{\alpha}</math> peut être nul (voir ci-après). Soit <math>k</math> un indice donnant le <math>\min</math> ci-dessus. Alors, <math>\hat{x}_k+\hat{\alpha} d_k=0</math> et on peut faire sortir l'indice <math>k</math> de la base d'indices <math>B</math>, et y faire entrer l'indice <math>j</math>. La nouvelle base d'indices s'écrit
<center>
<math>
B_+ = \left(B \cup \{j\}\right) \setminus \{k\}.
</math>
</center>

{{Théorème|nom=Proposition|L'ensemble <math>B_+</math> est une base d'indices.}}

L'opération de mise à jour de la base d'indices <math>B</math> en <math>B_+</math>, qui consiste à lui adjoindre l'indice <math>j</math> et à lui ôter l'indice <math>k</math>, est parfois appelée '''pivotage''' et la règle déterminant le choix des indices <math>j</math> et <math>k</math> est alors appelée '''règle de pivotage'''.

'''Progrès ou stagnation'''

Deux situations peuvent maintenant se présenter.
* Si <math>\hat{\alpha} > 0</math>, le coût décroît strictement et on peut passer à l'itération suivante avec <math>\hat{x}_+:=\hat{x}+\hat{\alpha} d</math> comme nouveau sommet et <math>B_+</math> comme nouvelle base d'indices.
* Si <math>\hat{\alpha} = 0</math> (ceci ne peut se produire que si le sommet <math>\hat{x}</math> est dégénéré), il y a un changement de base d'indices sans changer de sommet (le pas <math>\hat{\alpha}</math> est nul). Si l'on ne prend pas quelques précautions, l'algorithme peut cycler (par exemple en faisant entrer <math>k</math> dans la base et en faisant sortir <math>j</math> à l'itération suivante). On a mis au point des règles d'anti-cyclage pour faire face à cette situation. Certaines d'entre elles sont présentées dans la section suivante.

=== Règles d'anti-cyclage ===

Nous énonçons ci-dessous quelques règles d'anti-cyclage et renvoyons le lecteur aux articles qui les introduisent pour une démonstration de leur propriété d'anti-cyclage. Ces articles sont souvent difficiles à comprendre, si l'on n'est pas familier avec le jargon développé par les spécialistes de l'algorithme du simplexe, en particulier avec la description de l'algorithme sous forme de tableau.

==== Règle des petites perturbations ====
{{…}}

==== Règle lexicographique ====
{{…}}

==== Règle des plus petits indices de Bland ====

La {{Lien|trad=Bland's rule|lang=en|fr=règle de Bland|texte=règle de Bland}}<ref>R. G. Bland (1977), ''{{Langue|en|New Finite Pivoting Rules for the Simplex Method}}'', ''{{Langue|en|Mathematics of Operations Research}}'', 2, 103–107.</ref> consiste à faire entrer dans la base <math>B_+</math> le plus petit indice <math>j\in N</math> tel que le coût réduit <math>r_j<0</math> (voir [[#Déplacement le long d'une arête|ci-dessus]]) et à en faire sortir le plus petit indice <math>k\in\operatorname{arg\,min}\{-\hat{x}_i/d_i: i \in B</math>, <math>d_i < 0\}</math> (voir [[#Nouvelle base d'indices|ci-dessus]]).

=== Énoncé et convergence de l'algorithme ===

On peut résumer l'algorithme décrit ci-dessus comme suit.

{{Théorème|Algorithme du simplexe révisé|On suppose au départ que l'on dispose d'un sommet <math>\hat{x}</math> de <math>{\mathcal A}_P</math> et d'une base d'indices associée <math>B</math>. Une itération calcule un nouveau sommet <math>\hat{x}_+</math> et une nouvelle base d'indices <math>B_+</math>, à moins qu'il ne soit observé que <math>\hat{x}</math> est solution ou que le problème est non borné.
# ''Coût réduit''. On calcule le multiplicateur <math>y\in\R^m</math>, solution du système linéaire<center><math>A_{\bullet B}^\top y=c_B</math></center> et on en déduit le coût réduit<center><math>r=c_N-A_{\bullet N}^\top y.</math></center>
# ''Optimalité''. Si <math>r\geqslant0</math>, on s'arrête : <math>\hat{x}</math> est solution du problème <math>(P_L)</math>.
# ''Direction de descente''. Soit <math>j</math> un indice tel que <math>r_j<0</math>, respectant une [[#Règles d'anti-cyclage|règle d'anti-cyclage]]. On définit la direction de descente <math>d\in{\mathcal N}(A)</math> du critère <math>x\mapsto c^\top x</math> par<center><math>d_B=-A_{\bullet B}^{-1}A_{\bullet N} e^j_N \quad\mbox{et}\quad d_N=e^j_N,</math></center>où <math>e^j</math> est le j-ième [[vecteur de base]] de <math>\R^{|N|}</math>.
# ''Problème non borné''. Si <math>d_B\geqslant0</math>, on s'arrête car le problème <math>(P_L)</math> n'est pas borné : <math>c^\top(\hat{x}+\alpha d)\to-\infty</math> lorsque <math>\alpha\to\infty</math>.
# ''Pas maximal''. On calcule le pas maximal <math>\hat{\alpha}</math> jusqu'à la frontière de l'ensemble admissible <math>{\mathcal A}_P</math> par<center><math>\hat{\alpha} := \min\, \left\{ - \frac{\hat{x}_i}{ d_i}: i \in B,~ d_i < 0 \right\}.</math></center>Ce pas peut être nul. On note <math>k</math> un des indices donnant le minimum ci-dessus et respectant une [[#Règles d'anti-cyclage|règle d'anti-cyclage]].
# ''Nouveau sommet''. <math>\hat{x}_+=\hat{x}+\hat{\alpha} d</math>.
# ''Nouvelle base d'indices''. <math>B_+=(B\cup\{j\})\setminus\{k\}</math>.}}

On a le résultat de convergence finie suivant.

{{Théorème|Convergence de l'algorithme du simplexe révisé|Si le problème d'optimisation linéaire, écrit sous la forme standard <math>(P_L)</math>, est réalisable (c'est-à-dire <math>{\mathcal A}_P\ne\varnothing)</math>, l'algorithme du simplexe révisé décrit ci-dessus termine après un nombre fini d'étapes, soit en déterminant que le problème <math>(P_L)</math> est non borné, soit en en trouvant une solution-sommet.}}

=== Démarrage de l'algorithme ===

Pour utiliser l'algorithme du simplexe, il faut disposer d'un itéré initial qui est un sommet de l'ensemble admissible <math>{\mathcal A}_P:=\{x\in\R^n:Ax=b,~x\geqslant0\}</math>. Nous présentons dans cette section plusieurs manières de faire face à cette exigence.

==== Technique des deux phases ====

Comme son nom l'indique, la technique des deux phases décompose la résolution d'un problème d'optimisation linéaire en deux étapes. La phase/étape I consiste à résoudre un problème d'optimisation linéaire auxiliaire, dont on connait un sommet, par l'algorithme du simplexe. La solution de ce problème auxiliaire fournit un sommet du problème <math>(P_L)</math> (si <math>{\mathcal A}_P\ne\varnothing</math>) ou indique que ce problème n'a pas de point admissible. Dans la phase II, on résout le problème <math>(P_L)</math> par l'algorithme du simplexe, à partir du sommet obtenu dans la première phase.

La phase I consiste à résoudre le problème d'optimisation linéaire auxiliaire suivant :
<center>
<math>
\left\{\begin{array}{l}
\textstyle
\min\, \sum_{i=1}^m z_i \\
A x + D z = b \\
x \geqslant 0, \quad z \geqslant 0,
\end{array}\right.
</math>
</center>
où <math>D</math> est la matrice diagonale définie par <math>D_{ii}=1</math> si <math>b_i \geqslant 0</math> et <math>D_{ii}=-1</math> sinon. On peut utiliser pour cela l'algorithme du simplexe, démarrant en <math>(0,D b)</math>, qui est un sommet de son ensemble admissible

{{Théorème|nom=Proposition|Le point <math>(0,D b)</math> est un sommet de l'ensemble admissible du problème ci-dessus, lequel a toujours une solution. Si ce problème est résolu par l'algorithme du simplexe en partant de ce point, il obtient pour solution un point <math>(\hat{x},\hat{z})</math>. Si <math>\hat{z}\ne0</math>, le problème <math>(P_L)</math> n'est pas réalisable. Si <math>\hat{z}=0</math>, <math>\hat{x}</math> est un sommet de l'ensemble admissible de <math>(P_L)</math>.}}

==== Technique du grand M ====

Cette technique combine les phases I et II de manière à ne devoir résoudre qu'un seul problème d'optimisation linéaire, à savoir le problème
<center>
<math>
(P_{L,M})\qquad
\left\{ \begin{array}{l}
\textstyle
\min\, c^\top x+M\,\sum_{i=1}^m z_i \\
A x + D z = b \\
x \geqslant 0, \quad z \geqslant 0,
\end{array}\right.
</math>
</center>
où <math>D</math> est pris comme dans la [[#Technique des deux phases|technique des deux phases]] et <math>M>0</math> est une constante choisie « suffisamment grande ». On ne connait pas ''a priori'' la valeur qu'il faut donner à <math>M</math> pour que le problème <math>(P_{L,M})</math> soit équivalent au problème <math>(P_L)</math>, c'est-à-dire pour qu'en une solution <math>(\hat{x},\hat{z})</math> du problème <math>(P_{L,M})</math> on ait <math>\hat{z}=0</math>. Le raisonnement suivant montre pourquoi ils le seront si <math>M</math> est « suffisamment grand ».

On peut en effet voir le problème <math>(P_{L,M})</math> comme la [[Pénalisation (optimisation)#Pénalisation exacte|pénalisation exacte]], au moyen de la norme <math>\ell_1</math>, de la contrainte <math>z=0</math> dans
<center>
<math>
\left\{\begin{array}{l}
\min\, c^\top x\\
A x + D z = b \\
z = 0\\
x \geqslant 0, \quad z \geqslant 0.
\end{array}\right.
</math>
</center>
Ce dernier problème est équivalent à <math>(P_L)</math>. Dès lors, selon la théorie de la [[Pénalisation (optimisation)#Pénalisation exacte|pénalisation exacte]], si <math>M</math> est supérieur à la norme <math>\ell_\infty</math> (norme duale de la norme <math>\ell_1</math> pour le produit scalaire euclidien) de tout multiplicateur optimal associé à la contrainte <math>z=0</math> dans ce dernier problème, et si <math>{\mathcal A}_P\ne\varnothing</math>, alors toute solution <math>(\hat{x},\hat{z})</math> du problème <math>(P_{L,M})</math> sera telle que <math>\hat{z}=0</math> et donc <math>\hat{x}</math> sera solution de <math>(P_L)</math>.

== L'algorithme du simplexe dual ==
{{…}}

== Autre version de l'algorithme ==

En termes géométriques, l'ensemble des inégalités linéaires définit un [[polytope]] dans l'espace à <math>n</math> dimensions (polygone en 2 dimensions et polyèdre en 3 dimensions) et il s'agit de trouver le sommet optimal pour la fonction de coût donnée. En effet, la fonction que l'on cherche à minimiser étant linéaire sur le polytope, elle y est en particulier concave. Or une fonction concave et minorée sur un polytope admet un minimum en un des sommets du polytope. La recherche d'un point de minimum peut donc se restreindre aux sommets du polytope (qui peuvent être très nombreux néanmoins).

L'idée de l'algorithme consiste à partir d'un sommet quelconque du polytope et, à chaque itération, d'aller à un sommet adjacent s'il est possible d'en trouver un meilleur pour la fonction objectif. S'il n'y en a pas, l'algorithme s'arrête en concluant que le sommet courant est optimal. En général, il y a plusieurs sommets adjacents au sommet courant qui sont meilleurs pour l'objectif. Il faut en sélectionner un seul, la règle de sélection est appelée '''règle de pivotage'''.

Le polytope est donné par ''f'' contraintes linéaires : une matrice ''A'' de taille (''f'', ''n'') et un vecteur ''b'' de taille ''f''. On cherche à trouver
:<math>\min_{x\in\mathbb{R}^n,\, Ax\leq b}\; \varphi(x) </math>
avec <math> \varphi </math> une forme linéaire. Un sommet du polytope se définit comme un sous-ensemble ''I'' ⊂ {1, …, ''f''} tel que
* Card ''I'' = ''n''
* la matrice carrée extraite ''A''<sub>''I''</sub> est inversible
* le point ''x''<sub>''I''</sub> = ''A''<sub>''I''</sub><sup>−1</sup>''b''<sub>''I''</sub> vérifie ''A'' ''x''<sub>''I''</sub> ≤ ''b''

La colonne ''j'' de ''A''<sub>''I''</sub><sup>−1</sup> est le déplacement qui ajoute 1 à la ''I''<sub>''j''</sub>-ème forme linéaire de ''A'', en gardant les formes ''I''<sub>''k''</sub>, ''k'' ≠ ''j'', constantes. C'est un déplacement sur une arête du polytope. Une version de l'algorithme peut alors s'écrire comme suit :
* Trouver un sommet ''I'' ⊂ {1, …, ''f''}
* ''n'' arêtes arrivent à ''I''. Calculer la matrice ''A''<sub>''I''</sub><sup>−1</sup>. Pour ''k''=1 à ''n'', regarder le signe de φ.Col<sub>''k''</sub>[''A''<sub>''I''</sub><sup>−1</sup>].
** Si ce signe est négatif ou nul pour tout ''k'', Terminer. φ a son minimum en ce sommet ''I'', sous les contraintes ''A'' ''x'' ≤ ''b''.
** Si ce signe est strictement positif pour un ''k'', soit ''u'' = Col<sub>''k''</sub>[''A''<sub>''I''</sub><sup>−1</sup>] et aller au point suivant.
* Chercher le sommet le plus proche sur la demi-droite ''x''<sub>''I''</sub> + '''R'''<sup>*</sup><sub>+</sub>''u''. Pour tout ''h'' ∈ {1, …, ''f''} \ ''I'', quand ''A''<sub>''h''</sub>''u'' ≠ 0, calculer <math>\lambda_h = \frac{b_h-A_h x_I}{A_h u}\in\mathbb{R}</math>.
** S'il y a un ''h'' avec λ<sub>''h''</sub> > 0, prendre le plus petit de ces λ<sub>''h''</sub> > 0. Assigner {''h''} ∪ ''I'' \ {''k''} à ''I'' et aller au point précédent.
** Sinon terminer. Cette arête du polytope est infinie ; en la suivant on trouve <math>\min_{x\in\mathbb{R}^n,\, Ax\leq b}\; \varphi(x) = -\infty</math>.

== Complexité ==

Il a été montré pour les principales règles de pivotage employées que l'algorithme du simplexe pouvait prendre un [[complexité en temps|temps de calcul]] exponentiel. En particulier, on ne sait pas s'il existe une règle de pivotage qui assurerait que l'algorithme se termine après un nombre polynomial d'étapes.

On peut montrer que le nombre d'itérations de l'algorithme est majoré par :
<math> \frac{N-2}{\nu-1} </math>
où <math>\nu</math> est le plus petit nombre d'arêtes reliées à un même sommet du polytope parcouru par le simplexe et <math>N</math> est le nombre de sommets. On remarquera que <math>\nu</math> est minoré par la dimension de l'espace dans lequel vit le polytope.

Néanmoins, l'algorithme du simplexe est très efficace en pratique et il est implémenté dans tous les solveurs d'optimisation linéaire.

Une analyse un peu différente, l'[[analyse lisse d'algorithme|analyse lisse]] permet d'expliquer l'efficacité du simplexe en pratique, en calculant des performances sur des entrées légèrement perturbées {{harv|Spielman|Teng|2004}}.

== Autres méthodes de résolution d'un problème d'optimisation linéaire ==

On trouve d'autres algorithmes de résolution de problèmes d'optimisation linéaire : l'{{Lien|trad=Criss-cross algorithm|lang=en|fr=algorithme en croix|texte=algorithme en croix}}, la méthode du gradient projeté, la méthode du lagrangien augmenté, la [[méthode de l'ellipsoïde]], les méthodes affines, les [[méthodes de points intérieurs]], etc.

== Histoire ==

L'algorithme du simplexe est le plus souvent attribué à [[George Dantzig]] qui l'a découvert en 1947. Des techniques similaires avaient été découvertes par d'autres mathématiciens précédemment, mais sans parvenir à attirer l'attention<ref>
{{article
|url texte= http://www.dtic.mil/dtic/tr/fulltext/u2/a182708.pdf
|titre = Origins of the simplex method
|auteur = George Dantzig
|date = mai 1987
|périodique = A history of scientific computing
|doi = 10.1145/87252.88081
|isbn = 0-201-50814-1}}.</ref>.

== Annexes ==

=== Notes ===

{{références|colonnes=2}}

=== Articles connexes ===

* [[Méthode de Nelder-Mead]]
* [[Optimisation linéaire]]

=== Liens externes ===

* {{en}} [http://www.egwald.com/operationsresearch/lpsimplex.php Simplex Algorithm]. Illustration détaillée de l'exécution de l'algorithme (version « tableau »).
* {{pdf}} [http://litis.univ-lehavre.fr/~balev/Teaching/OR/simplex.pdf Exemple de l'algorithme du Simplexe]. L’algorithme du simplexe appliqué de manière très didactique à un exemple (version « tableau »).
* [http://www.phpsimplex.com/simplex/simplex.htm?l=fr PHPSimplex: Outil en ligne pour résoudre les problèmes d'optimisation linéaire] développé par Daniel Izquierdo et Juan José Ruiz, Université de Málaga (UMA, Espagne).
* J. Ch. Gilbert, ''[http://www-rocq.inria.fr/~gilbert/ensta/optim.html Éléments d'Optimisation Différentiable — Théorie et Algorithmes]'', syllabus de cours à l'[[École nationale supérieure de techniques avancées|ENSTA ParisTech]], Paris.

=== Bibliographie ===

* {{en}} G.B. Dantzig (1990). Origins of the simplex method. In G. Nash, éditeur, ''A History of Scientific Computing'', ACM Press Hist. Ser., pages 141–151. ACM Press, Reading, MA, États-Unis.
* {{en}} K.G. Murty (1983). ''Linear programming''. John Wiley & Sons Inc., New York. {{ISBN|0-471-09725-X}}. MR 720547.
* {{en}} M. Padberg (1999). ''Linear Optimization and Extensions'', deuxième édition, Springer-Verlag.
* {{article 
 | nom1=Spielman 
 | prénom1=Daniel A.
 | lien auteur1 = Daniel Spielman
 | nom2=Teng
 | prénom2=Shang-Hua
 | lien auteur2 = Shang-Hua Teng
 | titre=Smoothed analysis of algorithms: Why the simplex algorithm usually takes polynomial time
 | url=http://www.cs.duke.edu/courses/spring07/cps296.2/papers/p385-a_spielman.pdf
 | année=2004
 | journal=Journal of the ACM
 | volume=51
 | numéro=3
 | pages=385–463}}
{{Palette|Convexité|Informatique théorique}}{{Portail|informatique théorique}}

[[Catégorie:Algorithme numérique|Simplexe]]
[[Catégorie:Algorithme d'optimisation|Simplexe]]
[[Catégorie:Algorithmique et convexité|Simplexe]]