Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?
Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur Graph Search.
Concept
Algorithme du simplexe
Résumé
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. 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. 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.
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 .
Source officielle
À propos de ce résultat
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.