Aller au contenu

Algorithme du simplexe

Un article de Wikipédia, l'encyclopédie libre.

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.

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 variables réelles,

, 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 (A pour admissible, P pour primal). On écrit le problème sous la forme suivante

.

L'ensemble admissible 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 :
    est une matrice réelle de type et . L'écriture signifie que toutes les variables doivent être positives. Sous cette forme, apparaît comme l'intersection d'un sous-espace affine et de l'orthant positif.
  • On rencontre aussi la forme canonique :
    est une matrice réelle de type , et l'inégalité doit se comprendre composante par composante : , pour . Sous cette forme, apparaît comme l'intersection de demi-espaces de . 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 , peut s'exprimer sous la forme canonique par

De même, un polyèdre convexe représenté par la forme canonique , peut s'exprimer sous la forme standard par

a été décomposé en avec et et les composantes de sont appelées des variables d'écart.

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

.

Il consiste donc à minimiser la fonction linéaire , aussi appelée fonction-coût, sur l'ensemble admissible

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

est surjective,

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

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

Illustration de l'algorithme du simplexe.

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 à 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 ). 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 , on note

On rappelle que est un sommet de si la sous-matrice , formée des colonnes de avec indices dans , est injective ; on a donc nécessairement et on peut bien sûr avoir . On dit d'ailleurs qu'un sommet est dégénéré si et qu'il est non dégénéré si .

On appelle base d'indices un ensemble de indices pris dans tels que la sous-matrice formée des colonnes correspondantes de soit inversible. Si , les composantes avec sont alors dites basiques et celles avec sont dites non basiques. On dit qu'une base d'indices est associée à un sommet si .

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 . 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 de . 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 une base d'indices associée à ce sommet et le complémentaire de dans . Au départ de l'itération, on a donc

où, comme précédemment, (resp. ) désigne la sous-matrice de formée de ses colonnes avec indices dans (resp. ).

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 un point de l'ensemble admissible , qui vérifie donc . Comme est une base d'indices, on peut exprimer les composantes basiques de en fonction de et de ses composantes non basiques  :

On peut également exprimer le coût en fonction de  :

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

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

Proposition — Un sommet de est solution du problème si, et seulement si, il existe une base d'indices associée à telle que le coût réduit .

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

L'ensemble admissible est réduit au singleton . La solution du problème est donc forcément , qui est un sommet dégénéré. Si l'on prend pour base d'indices , le coût réduit est strictement négatif. Ceci signifie que l'on peut faire décroître le critère en augmentant tout en satisfaisant la contrainte d'égalité (c'est le sens du coût réduit). Mais ici on ne peut pas augmenter 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 , le coût réduit 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 est la positivité du coût réduit, calculé en utilisant la base d'indices 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 a une composante strictement négative, disons , cela veut dire que l'on peut faire décroître le coût en augmentant la composante de . On est donc tenté de chercher un nouveau point admissible en faisant un déplacement suivant une direction , c'est-à-dire

telle que la composante non basique de soit

On a noté le -ième vecteur de base de et . Pour que ce déplacement soit acceptable, il faut d'abord que l'on ait , donc , ce qui détermine sa composante basique :

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

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

Proposition — Soient défini comme ci-dessus et . Alors soit est réduit au sommet , soit est une arête de .

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

Si , alors

et comme le coût décroît strictement le long de la direction de descente , le problème n'est pas borné.

Nouvelle base d'indices

Si , on ne peut plus prendre un pas arbitrairement grand. Pour que l'on ait , il faut que , où

Lorsque le sommet est dégénéré (il y a des pour ), ce pas maximal peut être nul (voir ci-après). Soit un indice donnant le ci-dessus. Alors, et on peut faire sortir l'indice de la base d'indices , et y faire entrer l'indice . La nouvelle base d'indices s'écrit

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

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

Progrès ou stagnation

Deux situations peuvent maintenant se présenter.

  • Si , le coût décroît strictement et on peut passer à l'itération suivante avec comme nouveau sommet et comme nouvelle base d'indices.
  • Si (ceci ne peut se produire que si le sommet est dégénéré), il y a un changement de base d'indices sans changer de sommet (le pas est nul). Si l'on ne prend pas quelques précautions, l'algorithme peut cycler (par exemple en faisant entrer dans la base et en faisant sortir à 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 le plus petit indice tel que le coût réduit (voir ci-dessus) et à en faire sortir le plus petit indice , (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 de et d'une base d'indices associée . Une itération calcule un nouveau sommet et une nouvelle base d'indices , à moins qu'il ne soit observé que est solution ou que le problème est non borné.

  1. Coût réduit. On calcule le multiplicateur , solution du système linéaire
    et on en déduit le coût réduit
  2. Optimalité. Si , on s'arrête : est solution du problème .
  3. Direction de descente. Soit un indice tel que , respectant une règle d'anti-cyclage. On définit la direction de descente du critère par
    est le j-ième vecteur de base de .
  4. Problème non borné. Si , on s'arrête car le problème n'est pas borné : lorsque .
  5. Pas maximal. On calcule le pas maximal jusqu'à la frontière de l'ensemble admissible par
    Ce pas peut être nul. On note un des indices donnant le minimum ci-dessus et respectant une règle d'anti-cyclage.
  6. Nouveau sommet. .
  7. Nouvelle base d'indices. .

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 , est réalisable (c'est-à-dire , 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 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 . 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 (si ) ou indique que ce problème n'a pas de point admissible. Dans la phase II, on résout le problème 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 :

est la matrice diagonale définie par si et sinon. On peut utiliser pour cela l'algorithme du simplexe, démarrant en , qui est un sommet de son ensemble admissible

Proposition — Le point 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 . Si , le problème n'est pas réalisable. Si , est un sommet de l'ensemble admissible de .

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

est pris comme dans la technique des deux phases et est une constante choisie « suffisamment grande ». On ne connait pas a priori la valeur qu'il faut donner à pour que le problème soit équivalent au problème , c'est-à-dire pour qu'en une solution du problème on ait . Le raisonnement suivant montre pourquoi ils le seront si est « suffisamment grand ».

On peut en effet voir le problème comme la pénalisation exacte, au moyen de la norme , de la contrainte dans

Ce dernier problème est équivalent à . Dès lors, selon la théorie de la pénalisation exacte, si est supérieur à la norme (norme duale de la norme pour le produit scalaire euclidien) de tout multiplicateur optimal associé à la contrainte dans ce dernier problème, et si , alors toute solution du problème sera telle que et donc sera solution de .

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 à 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

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

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 : est le plus petit nombre d'arêtes reliées à un même sommet du polytope parcouru par le simplexe et est le nombre de sommets. On remarquera que 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ées (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.

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[4].

Cependant, Dantzig propose Fourier et son travail précurseur, en 1823-1830, sur l’algorithmique du simplexe. « De manière assez intéressante, en dépit de sa vaste applicabilité aux problèmes de tous les jours, la programmation linéaire resta inconnue avant 1947. Fourier était conscient de son potentiel dès 1823. » G.B. Dantzig, Linear Programming, Theory and Extensions [5]

Sur les autres projets Wikimedia :

  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. » George 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.
  4. George Dantzig, « Origins of the simplex method », A history of scientific computing,‎ (ISBN 0-201-50814-1, DOI 10.1145/87252.88081, lire en ligne).
  5. lien externe : pour l’historique du problème du simplexe. |url texte= http://www.mathouriste.eu/Fourier/Fourier_pgm_lin.html

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,‎ , p. 385–463 (lire en ligne)