Algorithme du simplexe
Source: Wikipédia sous licence CC-BY-SA 3.0.
La liste des auteurs de cet article est disponible ici.

L'algorithme du simplexe de George Dantzig est une technique à la fois fondamentale et très populaire pour les problèmes de programmation linéaire. Ainsi, étant donné un ensemble d'inégalités linéaires sur n variables réelles, l'algorithme permet de trouver la solution optimale pour une fonction objectif, qui est elle aussi linéaire (l'algorithme fonctionne encore quand la fonction est croissante en chacune de n variables).

En termes géométriques, l'ensemble (En théorie des ensembles, un ensemble désigne intuitivement une collection d’objets (les éléments de l'ensemble), « une...) des inégalités linéaires définit un polyèdre (Traditionnellement, un polyèdre est une forme géométrique à 3 dimensions ayant des faces planes qui se rencontrent le long d'arêtes droites. Le mot polyèdre...) dans l'espace à n dimensions (Dans le sens commun, la notion de dimension renvoie à la taille ; les dimensions d'une pièce sont sa longueur, sa largeur et sa profondeur/son épaisseur, ou bien son diamètre si c'est une pièce de révolution.) et il s'agit de trouver le sommet optimal pour la fonction de coût donnée (Dans les technologies de l'information, une donnée est une description élémentaire, souvent codée, d'une chose, d'une transaction, d'un...). L'idée de l'algorithme consiste à partir d'un sommet quelconque du polyèdre 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.

Il a été montré pour les principales règles de pivotage employées que l'algorithme du simplexe pouvait prendre un temps (Le temps est un concept développé par l'être humain pour appréhender le changement dans le monde.) 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 (La notion de nombre en linguistique est traitée à l’article « Nombre grammatical ».) polynomial d'étapes.

Néanmoins, l'algorithme du simplexe est très efficace en pratique et il est implémenté dans tous les solveurs de programmes linéaires. Il existe entre autres un algorithme basé sur la méthode de l'ellipsoïde (En mathématiques, un ellipsoïde est une surface du second degré de l'espace euclidien à trois dimensions. Il fait donc partie des quadriques, avec pour caractéristique principale de ne pas...), qui résout ces problèmes en un temps polynomial, mais qui est en pratique souvent moins performant que l'algorithme du simplexe.

Page générée en 0.077 seconde(s) - site hébergé chez Amen
Ce site fait l'objet d'une déclaration à la CNIL sous le numéro de dossier 1037632
Ce site est édité par Techno-Science.net - A propos - Informations légales
Partenaire: HD-Numérique