Algorithme du simplexe

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher
Page d'aide sur l'homonymie 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 minimiser une fonction sur un ensemble défini par des inégalités[1]. 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 Motzkin[2]. 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 calcul différentiel, le vocabulaire de l'optimisation mathématique.

Le problème à résoudre[modifier | modifier le code]

Les problèmes d'optimisation linéaire que l'algorithme du simplexe résout consistent à minimiser une fonction linéaire de n variables réelles,


x=(x_1,\ldots,x_n)\in\R^n\mapsto c^\top x:=\sum_{i=1}^n\,c_ix_i,

c=(c_1,\ldots,c_n)\in\R^n, 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 polyèdre convexe, que nous noterons {\mathcal A}_P (A pour admissible, P pour primal). On écrit le problème sous la forme suivante


\left\{\begin{array}{l}
{\inf}_x\;c^\top x\\
x\in{\mathcal A}_P.
\end{array}\right.

L'ensemble admissible {\mathcal A}_P 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 :
    {\mathcal A}_P=\{x\in\R^n:Ax=b,~x\geqslant0\},
    A\in\R^{m\times n} est une matrice réelle de type m\times n et b\in\R^m. L'écriture x\geqslant0 signifie que toutes les variables x_i doivent être positives. Sous cette forme, {\mathcal A}_P apparaît comme l'intersection d'un sous-espace affine et de l'orthant positif (en).
  • On rencontre aussi la forme canonique :
    {\mathcal A}_P=\{x\in\R^n:Ax\leqslant b\},
    A\in\R^{m\times n} est une matrice réelle de type m\times n, b\in\R^m et l'inégalité Ax\leqslant b doit se comprendre composante par composante : (Ax-b)_i\leqslant0, pour i\in[\![1,m]\!]\equiv\{1,\ldots,m\}. Sous cette forme, {\mathcal A}_P apparaît comme l'intersection de m demi-espaces de \R^n. C'est souvent la forme utilisée pour illustrer le comportement de l'algorithme du simplexe.

Ces deux manières de représenter un 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 \{x\in\R^n:Ax=b,~x\geqslant0\}, peut s'exprimer sous la forme canonique par


\{x\in\R^n:Ax\leqslant b,~-Ax\leqslant-b,~-x\leqslant0\}.

De même, un polyèdre convexe représenté par la forme canonique \{x\in\R^n:Ax\leqslant b\}, peut s'exprimer sous la forme standard par


\{(u,v,s)\in\R^n\times\R^n\times\R^m:Au-Av+s=b,~u\geqslant0,~v\geqslant0,~s\geqslant0\},

x a été décomposé en u-v avec u\geqslant0 et v\geqslant0 et les composantes de s sont appelées des variables d'écart.

L'algorithme du simplexe primal[modifier | modifier le code]

Vue d'ensemble[modifier | modifier le code]

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


(P_L)\qquad
\left\{\begin{array}{l}
{\inf}_x\;c^\top x\\
Ax=b\\
x\geqslant0.
\end{array}\right.

Il consiste donc à minimiser la fonction linéaire x\in\R^n\mapsto c^{\top}x, aussi appelée fonction-coût, sur l'ensemble admissible


{\mathcal A}_P:=\{x\in\R^n:Ax=b,~x\geqslant0\}.

Cet ensemble est un polyèdre convexe, que l'on supposera non vide. On supposera également que

A est surjective,

c'est-à-dire que ses lignes sont linéairement indépendantes.

On peut montrer que lorsque le problème (P_L) a une solution, il a une solution sur un sommet du polyèdre convexe {\mathcal A}_P. On sait comment calculer tous ces sommets, qui sont en nombre fini, si bien que le problème de résoudre (P_L) 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 n et m 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 {\mathcal A}_P, 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.

Simplex description.png

L'algorithme du simplexe est géométriquement très simple : chaque itération consiste à passer d'un sommet (face de dimension 0) du polyèdre convexe {\mathcal A}_P à un sommet adjacent en suivant une arête (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 -\infty). 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[modifier | modifier le code]

Si x\in\R^n_+, on note


I^+ (x) := \{i: x_i > 0 \}
\quad\mbox{et}\quad
I^0(x): = \{i: x_i = 0\}.

On rappelle que x\in {\mathcal A}_P est un sommet de {\mathcal A}_P si la sous-matrice A_{\bullet I^+(x)}, formée des colonnes de A avec indices dans I^+(x), est injective ; on a donc nécessairement |I^+(x)|\leqslant m et on peut bien sûr avoir |I^+(x)|<m. On dit d'ailleurs qu'un sommet x\in {\mathcal A}_P est dégénéré si |I^+(x)|<m et qu'il est non dégénéré si |I^+(x)|=m.

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

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 solution du problème d'optimisation linéaire), de solution admissible pour désigner un point admissible ou encore de solution basique admissible pour désigner un sommet de {\mathcal A}_P. 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.

Jargon de l'optimisation linéaire 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[modifier | modifier le code]

Une itération de l'algorithme démarre donc en un sommet \hat{x} de {\mathcal A}_P. Le calcul d'un tel sommet n'est pas une opération triviale, mais nous verrons plus loin comment on peut la réaliser. On note B une base d'indices associée à ce sommet et N le complémentaire de B dans [\![1,n]\!]. Au départ de l'itération, on a donc


\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),

où, comme précédemment, A_{\bullet B} (resp. A_{\bullet N}) désigne la sous-matrice de A formée de ses colonnes avec indices dans B (resp. N).

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 termes de bases d'indices fait perdre l'aspect géométrique de l'algorithme, qui 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 x un point de l'ensemble admissible {\mathcal A}_P, qui vérifie donc Ax = b. Comme B est une base d'indices, on peut exprimer les composantes basiques x_B de x en fonction de b et de ses composantes non basiques x_N :


x_B = A_{\bullet B}^{-1} (b - A_{\bullet N} x_N).

On peut également exprimer le coût c^\top x en fonction de x_N :


c^\top  x = c^\top_B A_{\bullet B}^{-1} (b - A_{\bullet N} x_N) + c^\top_N x_N.

Son gradient par rapport à x_N est appelé le coût réduit. Il s'écrit


r = c_N - A^\top_N A_{\bullet B}^{-\top} c_B.

Dans l'algorithme du simplexe, ce coût réduit sert, d'une part, à détecter l'optimalité éventuelle de l'itéré courant \hat{x} et, d'autre part, à sélectionner une arête de {\mathcal A}_P le long de laquelle la fonction-coût décroît lorsque \hat{x} n'est pas optimal.

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

Si un sommet optimal est dégénéré, il peut y avoir un coût réduit r\ngeqslant0 pour une base d'indices arbitraire associée à ce sommet, comme le montre l'exemple suivant :


\left\{\begin{array}{l}
\min\,2x_1+x_2\\
x_1+x_2=0\\
x\geqslant0.
\end{array}\right.

L'ensemble admissible est réduit au singleton \{(0,0)\}. La solution du problème est donc forcément \hat{x}=(0,0), qui est un sommet dégénéré. Si l'on prend pour base d'indices B=\{1\}, le coût réduit r=-1 est strictement négatif. Ceci signifie que l'on peut faire décroître le critère en augmentant x_N=x_2 tout en satisfaisant la contrainte d'égalité (c'est le sens du coût réduit). Mais ici on ne peut pas augmenter x_2 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 B=\{2\}, le coût réduit r=1 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 \hat{x} est la positivité du coût réduit, calculé en utilisant la base d'indices B 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 ci-dessous.

Déplacement le long d'une arête

Si r a une composante strictement négative, disons r_j<0, cela veut dire que l'on peut faire décroître le coût en augmentant la composante j de \hat{x}_N. On est donc tenté de chercher un nouveau point admissible en faisant un déplacement suivant une direction d, c'est-à-dire


x(\alpha) = \hat{x} + \alpha d,

telle que la composante non basique de d soit


d_N=e^j_N.

On a noté e^j le j-ième vecteur de base de \R^n et e^j_N=(e^j)_N. Pour que ce déplacement d=(d_B,d_N) soit acceptable, il faut d'abord que l'on ait Ax(\alpha)=b, donc Ad=0, ce qui détermine sa composante basique :


d_B = - A_{\bullet B}^{-1} A_{\bullet N} e^j_N.

Sur le choix de l'indice j. Remarquons que le coût décroît bien le long de d puisque l'on a


c^{\top} d=r_j<0.

Si r a plusieurs composantes strictement négatives, il semble donc raisonnable de choisir l'indice j parmi ceux donnant la composante de r 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) 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 d se fait le long d'une arête de {\mathcal A}_P.

Proposition — Soient d défini comme ci-dessus et D:=\{\hat{x}+\alpha d\in {\mathcal A}_P:\alpha\geqslant 0\}. Alors soit D est réduit au sommet \{\hat{x}\}, soit D est une arête de {\mathcal A}_P.

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

Si d_B \geqslant 0, alors


\forall\, \alpha > 0:\qquad x(\alpha) \geqslant 0,

et comme le coût c^{\top}x(\alpha) = c^{\top}\hat{x} + \alpha c^{\top}d décroît strictement le long de la direction de descente d, le problème n'est pas borné.

Nouvelle base d'indices

Si d_B \ngeqslant 0, on ne peut plus prendre un pas arbitrairement grand. Pour que l'on ait x(\alpha)_B\geqslant 0, il faut que \alpha\leqslant\hat{\alpha}, où


\hat{\alpha} = \min  \left\{ - \frac{\hat{x}_i }{ d_i}: i \in B,~ d_i < 0 \right\}.

Lorsque le sommet \hat{x} est dégénéré (il y a des \hat{x}_i=0 pour i \in B), ce pas maximal \hat{\alpha} peut être nul (voir ci-après). Soit k un indice donnant le \min ci-dessus. Alors, \hat{x}_k+\hat{\alpha} d_k=0 et on peut faire sortir l'indice k de la base d'indices B, et y faire entrer l'indice j. La nouvelle base d'indices s'écrit


B_+ = \left(B \cup \{j\}\right) \setminus \{k\}.

Proposition — L'ensemble B_+ est une base d'indices.

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

Progrès ou stagnation

Deux situations peuvent maintenant se présenter.

  • Si \hat{\alpha} > 0, le coût décroît strictement et on peut passer à l'itération suivante avec \hat{x}_+:=\hat{x}+\hat{\alpha} d comme nouveau sommet et B_+ comme nouvelle base d'indices.
  • Si \hat{\alpha} = 0 (ceci ne peut se produire que si le sommet \hat{x} est dégénéré), il y a un changement de base d'indices sans changer de sommet (le pas \hat{\alpha} est nul). Si l'on ne prend pas quelques précautions, l'algorithme peut cycler (par exemple en faisant entrer k dans la base et en faisant sortir j à 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[modifier | modifier le code]

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[modifier | modifier le code]

Règle lexicographique[modifier | modifier le code]

Règle des plus petits indices de Bland[modifier | modifier le code]

La règle de Bland (en)[3] consiste à faire entrer dans la base B_+ le plus petit indice j\in N tel que le coût réduit r_j<0 (voir ci-dessus) et à en faire sortir le plus petit indice k\in\operatorname{arg\,min}\{-\hat{x}_i/d_i: i \in B, d_i < 0\} (voir ci-dessus).

Énoncé et convergence de l'algorithme[modifier | modifier le code]

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

Algorithme du simplexe révisé — On suppose au départ que l'on dispose d'un sommet \hat{x} de {\mathcal A}_P et d'une base d'indices associée B. Une itération calcule un nouveau sommet \hat{x}_+ et une nouvelle base d'indices B_+, à moins qu'il ne soit observé que \hat{x} est solution ou que le problème est non borné.

  1. Coût réduit. On calcule le multiplicateur y\in\R^m, solution du système linéaire
    A_{\bullet B}^\top y=c_B
    et on en déduit le coût réduit
    r=c_N-A_{\bullet N}^\top y.
  2. Optimalité. Si r\geqslant0, on s'arrête : \hat{x} est solution du problème (P_L).
  3. Direction de descente. Soit j un indice tel que r_j<0, respectant une règle d'anti-cyclage. On définit la direction de descente d\in{\mathcal N}(A) du critère x\mapsto c^\top x par
    d_B=-A_{\bullet B}^{-1}A_{\bullet N} e^j_N \quad\mbox{et}\quad d_N=e^j_N,
    e^j est le j-ième vecteur de base de \R^{|N|}.
  4. Problème non borné. Si d_B\geqslant0, on s'arrête car le problème (P_L) n'est pas borné : c^\top(\hat{x}+\alpha d)\to-\infty lorsque \alpha\to\infty.
  5. Pas maximal. On calcule le pas maximal \hat{\alpha} jusqu'à la frontière de l'ensemble admissible {\mathcal A}_P par
    \hat{\alpha} := \min\, \left\{ - \frac{\hat{x}_i}{ d_i}: i \in B,~ d_i < 0 \right\}.
    Ce pas peut être nul. On note k un des indices donnant le minimum ci-dessus et respectant une règle d'anti-cyclage.
  6. Nouveau sommet. \hat{x}_+=\hat{x}+\hat{\alpha} d.
  7. Nouvelle base d'indices. B_+=(B\cup\{j\})\setminus\{k\}.

On a le résultat de convergence finie suivant.

Convergence de l'algorithme du simplexe révisé — Si le problème d'optimisation linéaire, écrit sous la forme standard (P_L), est réalisable (c'est-à-dire {\mathcal A}_P\ne\varnothing), 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 (P_L) est non borné, soit en en trouvant une solution-sommet.

Démarrage de l'algorithme[modifier | modifier le code]

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

Technique des deux phases[modifier | modifier le code]

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 (P_L) (si {\mathcal A}_P\ne\varnothing) ou indique que ce problème n'a pas de point admissible. Dans la phase II, on résout le problème (P_L) 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 suivant :


\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.

D est la matrice diagonale définie par D_{ii}=1 si b_i \geqslant 0 et D_{ii}=-1 sinon. On peut utiliser pour cela l'algorithme du simplexe, démarrant en (0,D b), qui est un sommet de son ensemble admissible

Proposition — Le point (0,D b) 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 (\hat{x},\hat{z}). Si \hat{z}\ne0, le problème (P_L) n'est pas réalisable. Si \hat{z}=0, \hat{x} est un sommet de l'ensemble admissible de (P_L).

Technique du grand M[modifier | modifier le code]

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


(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.

D est pris comme dans la technique des deux phases et M>0 est une constante choisie « suffisamment grande ». On ne connait pas a priori la valeur qu'il faut donner à M pour que le problème (P_{L,M}) soit équivalent au problème (P_L), c'est-à-dire pour qu'en une solution (\hat{x},\hat{z}) du problème (P_{L,M}) on ait \hat{z}=0. Le raisonnement suivant montre pourquoi ils le seront si M est « suffisamment grand ».

On peut en effet voir le problème (P_{L,M}) comme la pénalisation exacte, au moyen de la norme \ell_1, de la contrainte z=0 dans


\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.

Ce dernier problème est équivalent à (P_L). Dès lors, selon la théorie de la pénalisation exacte, si M est supérieur à la norme \ell_\infty (norme duale de la norme \ell_1 pour le produit scalaire euclidien) de tout multiplicateur optimal associé à la contrainte z=0 dans ce dernier problème, et si {\mathcal A}_P\ne\varnothing, alors toute solution (\hat{x},\hat{z}) du problème (P_{L,M}) sera telle que \hat{z}=0 et donc \hat{x} sera solution de (P_L).

L'algorithme du simplexe dual[modifier | modifier le code]

Autre version de l'algorithme[modifier | modifier le code]

En termes géométriques, l'ensemble des inégalités linéaires définit un polytope dans l'espace à n 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

\min_{x\in\mathbb{R}^n,\, Ax\leq b}\; \varphi(x)

avec φ 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 AI est inversible
  • le point xI = AI-1bI vérifie A xIb

La colonne j de AI-1 est le déplacement qui ajoute 1 à la Ij-ème forme linéaire de A, en gardant les formes Ik, kj, 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 AI-1. Pour k=1 à n, regarder le signe de φ.Colk[AI-1].
    • Si ce signe est négatif ou nul pour tout k, Terminer. φ a son minimum en ce sommet I, sous les contraintes A xb.
    • Si ce signe est strictement positif pour un k, soit u = Colk[AI-1] et aller au point suivant.
  • Chercher le sommet le plus proche sur la demi-droite xI + R*+u. Pour tout h ∈ {1, …, f} \ I, quand Ahu ≠ 0, calculer \lambda_h = \frac{b_h-A_h x_I}{A_h u}\in\mathbb{R}.
    • S'il y a un h avec λh > 0, prendre le plus petit de ces λh > 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 \min_{x\in\mathbb{R}^n,\, Ax\leq b}\; \varphi(x) = -\infty.

Complexité[modifier | modifier le code]

Il a été montré pour les principales règles de pivotage employées que l'algorithme du simplexe pouvait prendre un 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 :  \frac{N-2}{\nu-1} \nu est le plus petit nombre d'arêtes reliées à un même sommet du polytope parcouru par le simplexe et N est le nombre de sommets. On remarquera que \nu 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 permet d'expliquer l'efficacité du simplexe en pratique, en calculant des performances sur des entrées légèrement perturbée (Spielman et Teng 2004).

Autres méthodes de résolution d'un problème d'optimisation linéaire[modifier | modifier le code]

On trouve d'autres algorithmes de résolution de problèmes d'optimisation linéaire : l'algorithme en croix (en), 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.

Annexes[modifier | modifier le code]

Notes[modifier | modifier le code]

  1. 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. Dantzig (1990).
  2. Murty (1983), commentaire 2.2.
  3. R.G. Bland (1977). New finite pivoting rules for the simplex method. Mathematics of Operations Research, 2, 103–107.

Articles connexes[modifier | modifier le code]

Liens externes[modifier | modifier le code]

Bibliographie[modifier | modifier le code]

  • (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.
  • Daniel A. Spielman et Shang-Hua Teng, « Smoothed analysis of algorithms: Why the simplex algorithm usually takes polynomial time », Journal of the ACM, vol. 51, no 3,‎ 2004, p. 385–463 (lire en ligne)