Lalgorithme 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 George Dantzig (1990).. 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 MotzkinMurty (1983), commentaire 2.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.

Relevant de l'optimisation mathématique, l'algorithme du simplexe fait appel à des notions d'algèbre linéaire et de calcul différentiel.

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

où , 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 :où 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 :où 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

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

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 . Il consiste donc à minimiser la fonction linéaire , aussi appelée fonction-coût, sur lensemble 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.

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

Si , on note

Par propriété, 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 . Un sommet est dit « dégénéré » si et il est « non dégénéré » si .

Une « base d'indices » est 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 ». Une base d'indices est dite « associée » à un sommet si .

La littérature scientifique en optimisation linéaire utilise un jargon ayant évolué depuis les contributions fondatrices. Certains termes peuvent porter à confusion. Il en va ainsi de « solution » pour désigner un point (par la suite,ce terme désignera 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 . Par suite, la terminologie sera conforme à 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

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.

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 .

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

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.