Worldlex Wiki En optimisation mathématique , l'algorithme du simplexe de Dantzig (ou méthode du simplexe ) est un algorithme de programmation linéaire .
Le nom de l'algorithme est dérivé du concept de simplexe et a été proposé par T.S. Motzkin . Les simplexes ne sont pas utilisés directement dans la méthode, mais on peut l'interpréter comme opérant sur des cônes simpliciaux , lesquels deviennent des simplexes stricts sous l'effet d'une contrainte supplémentaire. Les cônes simpliciaux en question sont les coins (c'est-à-dire les voisinages des sommets) d'un objet géométrique appelé polytope . La forme de ce polytope est définie par les contraintes appliquées à la fonction objectif.
Pendant la Seconde Guerre mondiale, George Dantzig travaillait sur des méthodes de planification pour l'US Army Air Force, utilisant une calculatrice de bureau . En 1946, un collègue le mit au défi de mécaniser le processus de planification afin de le dissuader d'accepter un autre emploi. Dantzig formula le problème sous forme d'inégalités linéaires, s'inspirant des travaux de Wassily Leontief . Cependant, à cette époque, il n'intégra pas d'objectif à sa formulation. Sans objectif, un grand nombre de solutions sont envisageables. Par conséquent, pour trouver la « meilleure » solution réalisable, il est nécessaire d'utiliser des « règles de base » définies par l'armée, décrivant comment les objectifs peuvent être atteints, plutôt que de spécifier un objectif en soi. L'intuition fondamentale de Dantzig fut de comprendre que la plupart de ces règles de base peuvent être traduites en une fonction objectif linéaire à maximiser. Le développement de la méthode du simplexe fut progressif et s'étala sur environ un an.Après que Dantzig eut intégré une fonction objectif à sa formulation au milieu de l'année 1947, le problème devint mathématiquement plus facile à traiter. Dantzig réalisa alors que l'un des problèmes non résolus qu'il avait pris pour un devoir dans le cours de son professeur Jerzy Neyman (et qu'il avait effectivement résolu par la suite) s'appliquait à la recherche d'un algorithme pour les programmes linéaires. Ce problème consistait à déterminer l'existence de multiplicateurs de Lagrange pour des programmes linéaires généraux sur un continuum de variables, chacune bornée entre zéro et un, et satisfaisant des contraintes linéaires exprimées sous forme d' intégrales de Lebesgue . Dantzig publia plus tard son « devoir » comme thèse de doctorat. La géométrie des colonnes utilisée dans cette thèse lui apporta une intuition qui le convainquit de l'efficacité de la méthode du simplexe.
Aperçu
L'algorithme du simplexe opère sur des programmes linéaires sous forme canonique
- maximiser
- sous réserve de et
avec les coefficients de la fonction objectif, est la transposée de la matrice avec un point comme marqueur , et sont les variables du problème, est une matrice p × n , et . Il existe un processus simple pour convertir tout programme linéaire en un programme sous forme standard, donc l'utilisation de cette forme de programmes linéaires n'entraîne aucune perte de généralité.
En termes géométriques, la région admissible définie par toutes les valeurs de telles que et est un polytope convexe (éventuellement non borné) . Un point extrême ou sommet de ce polytope est appelé solution admissible de base (SAB).
On peut démontrer que, pour un programme linéaire sous forme standard, si la fonction objectif atteint sa valeur maximale sur la région admissible, alors elle atteint cette valeur en (au moins) un des points extrêmes. Ceci ramène le problème à un calcul fini puisqu'il existe un nombre fini de points extrêmes, mais ce nombre est excessivement grand pour tous les programmes linéaires, sauf les plus petits.
On peut également démontrer que, si un point extrême n'est pas un maximum de la fonction objectif, alors il existe une arête contenant ce point telle que la valeur de la fonction objectif augmente strictement le long de cette arête lorsqu'on s'éloigne du point. Si l'arête est finie, elle se connecte à un autre point extrême où la fonction objectif a une valeur supérieure ; sinon, la fonction objectif n'est pas bornée supérieurement sur l'arête et le programme linéaire n'admet pas de solution. L'algorithme du simplexe exploite cette observation en parcourant les arêtes du polytope jusqu'aux points extrêmes dont les valeurs de la fonction objectif augmentent progressivement. Ce processus se poursuit jusqu'à ce que la valeur maximale soit atteinte ou qu'une arête non bornée soit visitée (ce qui indique que le problème n'a pas de solution). L'algorithme se termine toujours car le nombre de sommets du polytope est fini ; de plus, comme les sauts entre les sommets se font toujours dans la même direction (celle de la fonction objectif), on s'attend à ce que le nombre de sommets visités soit faible.
La résolution d'un programme linéaire s'effectue en deux étapes. La première, appelée Phase I, consiste à déterminer un point extrême initial. Selon la nature du programme, ce point peut être trivial, mais en général, il peut être déterminé en appliquant l'algorithme du simplexe à une version modifiée du programme initial. Les résultats possibles de la Phase I sont soit la découverte d'une solution de base admissible, soit l'absence de solution admissible. Dans ce dernier cas, le programme linéaire est dit infaisable . La seconde étape, Phase II, consiste à appliquer l'algorithme du simplexe en utilisant comme point de départ la solution de base admissible trouvée lors de la Phase I. Les résultats possibles de la Phase II sont soit une solution de base admissible optimale, soit une arête infinie sur laquelle la fonction objectif est non bornée supérieurement.
Forme standard
La transformation d'un programme linéaire en un programme sous forme standard peut être réalisée comme suit. Premièrement, pour chaque variable ayant une borne inférieure différente de 0, une nouvelle variable est introduite, représentant la différence entre la variable et sa borne. La variable initiale peut ensuite être éliminée par substitution. Par exemple, étant donné la contrainte
une nouvelle variable, , est introduite avec
La seconde équation peut être utilisée pour éliminer du programme linéaire. De cette manière, toutes les contraintes de borne inférieure peuvent être remplacées par des contraintes de non-négativité.
Deuxièmement, pour chaque contrainte d'inégalité restante, une nouvelle variable, appelée variable d'écart , est introduite afin de transformer la contrainte en une contrainte d'égalité. Cette variable représente la différence entre les deux membres de l'inégalité et est supposée non négative. Par exemple, les inégalités
sont remplacés par
Il est beaucoup plus facile d'effectuer des manipulations algébriques sur les inégalités de cette forme. Dans les inégalités où apparaît ≥, comme la seconde, certains auteurs désignent la variable introduite comme une
L'équation peut être utilisée pour éliminer du programme linéaire.
Une fois ce processus terminé, la région admissible se présentera sous la forme suivante :
Il est également utile de supposer que le rang de est égal au nombre de lignes. Cela ne provoque aucune perte de généralité, car sinon soit le système comporte des équations redondantes qui peuvent être supprimées, soit le système est incompatible et le programme linéaire n'a pas de solution.
Tableau simplex
Un programme linéaire sous forme standard peut être représenté comme un tableau de la forme
La première ligne définit la fonction objectif et les lignes suivantes spécifient les contraintes. Le zéro de la première colonne représente le vecteur nul de même dimension que le vecteur (les conventions exactes de présentation varient selon les auteurs). Si les colonnes de peuvent être réorganisées de manière à contenir la matrice identité d'ordre (le nombre de lignes de ), alors le tableau est dit sous forme canonique . Les variables correspondant aux colonnes de la matrice identité sont appelées variables de base, tandis que les autres variables sont appelées variables hors base ou variables libres . Si les valeurs des variables hors base sont nulles, les valeurs des variables de base sont facilement obtenues comme éléments de et cette solution est une solution de base réalisable. L'interprétation algébrique est que les coefficients de l'équation linéaire représentée par chaque ligne sont soit , soit d'autres nombres. Chaque ligne aura une colonne avec la valeur , des colonnes avec les coefficients , et les colonnes restantes avec d'autres coefficients (ces autres variables représentent nos variables hors base). En attribuant la valeur zéro aux variables non basiques, nous garantissons dans chaque ligne que la valeur de la variable représentée par un « a » dans sa colonne est égale à la valeur de cette ligne.
Réciproquement, étant donné une solution de base réalisable, les colonnes correspondant aux variables non nulles peuvent être développées en une matrice non singulière . Si le tableau correspondant est multiplié par l'inverse de , alors le résultat est un tableau sous forme canonique.
Laisser
soit un tableau sous forme canonique, où . Des transformations d'addition de lignes supplémentaires peuvent être appliquées pour supprimer les coefficients
Opérations de pivot
L'opération géométrique de passage d'une solution de base admissible à une solution de base admissible adjacente est implémentée comme une opération de pivot . Premièrement, un élément pivot non nul est sélectionné dans une colonne non basique. La ligne contenant cet élément est multipliée par son inverse pour le transformer en 1, puis des multiples de cette ligne sont ajoutés aux autres lignes pour transformer les autres éléments de la colonne en 0. Ainsi, si l'élément pivot se trouve dans une ligne r , la colonne devient la r -ième colonne de la matrice identité. La variable associée à cette colonne devient alors une variable de base, remplaçant celle qui correspondait à la r -ième colonne de la matrice identité avant l'opération. En pratique, la variable correspondant à la colonne pivot entre dans l'ensemble des variables de base et est appelée variable entrante , tandis que la variable remplacée quitte cet ensemble et est appelée variable sortante . Le tableau reste sous forme canonique, mais l'ensemble des variables de base a été modifié d'un élément.
Algorithme
Soit un programme linéaire représenté par un tableau canonique. L'algorithme du simplexe procède par opérations de pivot successives, chacune fournissant une solution de base admissible améliorée ; le choix de l'élément pivot à chaque étape est largement déterminé par la condition que ce pivot améliore la solution.
Les sections suivantes expliquent comment trouver le maximum de la fonction objectif. Si l'on souhaite plutôt trouver le minimum, l'algorithme peut être modifié en supprimant toutes les références à la fonction objectif.
Saisie de la sélection de variables
Puisque la variable d'entrée augmente généralement de 0 à une valeur positive, la valeur de la fonction objectif augmente (et se rapproche du maximum) si sa dérivée (c'est-à-dire ses coefficients ) par rapport à cette variable est positive. Il convient donc de choisir une colonne pivot dont l'élément correspondant dans la ligne de la fonction objectif est négatif. (Si l'on souhaite minimiser la fonction objectif, on choisira au contraire une colonne dont l'élément correspondant dans la ligne de la fonction objectif est positif.)
Il y a généralement plus d'une colonne avec une entrée négative dans la ligne objectif, et le choix de celle à ajouter à l'ensemble des variables de base est guidé par l'une des nombreuses règles de choix de variables entrantes telles que l'algorithme Devex .
Si aucune des valeurs de la ligne objectif n'est négative, aucun choix de variable d'entrée ne peut être effectué et la solution est en fait maximale. On constate aisément qu'elle est maximale puisque la ligne objectif correspond alors à une équation de la forme suivante :
Sélection de variables de sortie
Une fois la colonne pivot sélectionnée, le choix de la ligne pivot est largement déterminé par l'exigence de faisabilité de la solution. Dans un premier temps, seules les valeurs positives de la colonne pivot sont prises en compte, car seules celles-ci imposent des limites à la valeur de la variable d'entrée. En l'absence de valeurs positives dans la colonne pivot, la variable d'entrée peut prendre n'importe quelle valeur non négative, la solution restant réalisable. Dans ce cas, la fonction objectif n'est pas bornée supérieurement et ne présente pas de maximum.
Ensuite, il faut sélectionner la ligne pivot de sorte que la variable entrante (et donc l'amélioration de la fonction objectif) ait une valeur maximale, tout en veillant à ce que toutes les autres variables de base restent non négatives. Si la colonne pivot est c , alors ceci est réalisé si la ligne pivot r est choisie de sorte que…
est le minimum sur tous les r tels que > 0. C'est ce qu'on appelle le test du ratio minimum . S'il y a plus d'une ligne pour laquelle le minimum est atteint, une règle de choix de variable de suppression peut être utilisée pour effectuer la détermination.
Exemple
Trouver un tableau canonique initial
En général, un programme linéaire n'est pas donné sous forme canonique et un tableau canonique équivalent doit être trouvé avant d'appliquer l'algorithme du simplexe. Ceci peut être réalisé par l'introduction de variables artificielles . Les colonnes de la matrice identité sont ajoutées comme vecteurs colonnes pour ces variables. Si la valeur b d'une équation de contrainte est négative, l'équation est inversée avant l'ajout des colonnes de la matrice identité. Ceci ne modifie ni l'ensemble des solutions admissibles ni la solution optimale, et garantit que les variables d'écart constituent une solution admissible initiale. Le nouveau tableau est sous forme canonique, mais n'est pas équivalent au problème initial. Une nouvelle fonction objectif, égale à la somme des variables artificielles, est donc introduite et l'algorithme du simplexe est appliqué pour trouver le minimum ; le programme linéaire modifié est appelé problème de la phase I.
L'algorithme du simplexe appliqué au problème de la Phase I doit converger vers une valeur minimale pour la nouvelle fonction objectif, car, étant la somme de variables non négatives, sa valeur est minorée par 0. Si le minimum est nul, les variables artificielles peuvent être éliminées du tableau canonique résultant, ce qui produit un tableau canonique équivalent au problème initial. L'algorithme du simplexe peut alors être appliqué pour trouver la solution ; cette étape est appelée Phase II . Si le minimum est positif, alors il n'existe aucune solution admissible pour le problème de la Phase I lorsque toutes les variables artificielles sont nulles. Cela implique que la région admissible du problème initial est vide, et donc que le problème initial n'a pas de solution.
Exemple
Considérons le programme linéaire
- Maximiser
- Sous réserve de
Il diffère de l'exemple précédent par la présence de contraintes d'égalité au lieu d'inégalité. La solution précédente viole la première contrainte. Ce nouveau problème est représenté par le tableau (non canonique)
Introduisons les variables artificielles u et v et la fonction objectif W = u + v , ce qui donne un nouveau tableau.
L'équation définissant la fonction objectif initiale est conservée en prévision de la phase II.
Par construction, u et v sont toutes deux des variables de base puisqu'elles font partie de la matrice identité initiale. Cependant, la fonction objectif W suppose actuellement que u et v sont toutes deux nulles. Afin d'ajuster la fonction objectif pour qu'elle prenne la valeur correcte où u = 10 et v = 15, ajoutez les troisième et quatrième lignes à la première ligne.
Sélectionnez la colonne 5 comme colonne pivot, la ligne pivot doit donc être la ligne 4, et le tableau mis à jour est
Sélectionnez maintenant la colonne 3 comme colonne pivot, la ligne 3 devant être la ligne pivot, pour obtenir
Les variables artificielles sont désormais nulles et peuvent être supprimées, ce qui donne un tableau canonique équivalent au problème initial :
Cette valeur est, par chance, déjà optimale et donc la valeur optimale pour le programme linéaire d'origine est 130/7. Cette valeur est « pire » que 20, ce qui est prévisible pour un problème plus contraint.
Sujets avancés
Mise en œuvre
Dans les problèmes de programmation linéaire de grande taille, A est généralement une matrice creuse et, lorsque la sparsité résultante de B est exploitée tout en préservant son inversibilité, l'algorithme du simplexe modifié est beaucoup plus efficace que la méthode du simplexe standard. Les solveurs commerciaux du simplexe sont basés sur cet algorithme modifié.
Dégénérescence : calage et cyclisme
Si les valeurs de toutes les variables de base sont strictement positives, un pivot doit nécessairement améliorer la valeur de la fonction objectif. Dans ce cas, aucun ensemble de variables de base n'apparaît deux fois et l'algorithme du simplexe doit s'arrêter après un nombre fini d'itérations. Les solutions de base réalisables où au moins une des variables de base est nulle sont dites dégénérées et peuvent donner lieu à des pivots qui n'améliorent pas la valeur de la fonction objectif. Il n'y a alors aucun changement dans la solution elle-même, seulement un changement d'ensemble de variables de base. Lorsque plusieurs pivots de ce type se succèdent, il n'y a aucune amélioration ; dans les grandes applications industrielles, la dégénérescence est fréquente et ce « blocage » est notable. Pire encore, il est possible que le même ensemble de variables de base apparaisse deux fois, auquel cas les règles de pivotage déterministes de l'algorithme du simplexe produisent une boucle infinie, ou « cycle ». Bien que la dégénérescence soit la règle en pratique et le blocage fréquent, les cycles sont rares. Un exemple de cycle pratique est présenté dans l'ouvrage de Padberg . La règle de Bland empêche les cycles et garantit ainsi que l'algorithme du simplexe se termine toujours. Un autre algorithme de pivotement, l' algorithme de croisement, ne présente jamais de cycle sur les programmes linéaires.
Les règles de pivot basées sur l'historique, telles que la règle de Zadeh et la règle de Cunningham, tentent également de contourner le problème de la stagnation et de la cyclage en gardant une trace de la fréquence d'utilisation de certaines variables, puis en privilégiant les variables les moins utilisées.
Efficacité dans le pire des cas
La méthode du simplexe est remarquablement efficace en pratique et a constitué une amélioration significative par rapport aux méthodes antérieures telles que l'élimination de Fourier-Motzkin . Cependant, en 1972, Klee et Minty ont donné un exemple, le cube de Klee-Minty , démontrant que la complexité dans le pire des cas de la méthode du simplexe, telle que formulée par Dantzig, est exponentielle . Depuis lors, pour presque chaque variante de la méthode, il a été démontré qu'il existe une famille de programmes linéaires pour lesquels ses performances sont médiocres. L'existence d'une variante à complexité polynomiale reste une question ouverte , bien que des règles de pivot sous-exponentielles soient connues.
En 2014, il a été démontré qu'une variante particulière de la méthode du simplexe est NP-difficiles . À peu près au même moment, il a été montré qu'il existe une règle de pivot artificielle dont le calcul de la sortie est PSPACE-complet . En 2015, ce résultat a été renforcé pour démontrer que le calcul de la sortie de la règle de pivot de Dantzig est également PSPACE-complet .
L'efficacité dans la pratique
L'analyse et la quantification de l'efficacité pratique de l'algorithme du simplexe, malgré sa complexité exponentielle dans le pire des cas, ont conduit au développement d'autres mesures de complexité. L'algorithme du simplexe présente une complexité polynomiale en moyenne pour diverses distributions de probabilité , ses performances moyennes précises dépendant du choix de la distribution de probabilité des matrices aléatoires . Une autre approche pour étudier les « phénomènes typiques » utilise la théorie des catégories de Baire en topologie générale , et montre que la plupart des matrices (topologiquement parlant) peuvent être résolues par l'algorithme du simplexe en un nombre polynomial d'étapes.stabilité structurelle ), ou deviennent-ils traitables ? Ce domaine de recherche, appelé analyse lissée , a été introduit spécifiquement pour étudier la méthode du simplexe. En effet, le temps d'exécution de cette méthode sur des données d'entrée bruitées est polynomial en fonction du nombre de variables et de l'amplitude des perturbations.
Autres algorithmes
D'autres algorithmes de résolution de problèmes de programmation linéaire sont décrits dans l' article consacré à la programmation linéaire . L'algorithme de croisement est un autre algorithme de pivotage par échange de base . Il existe des algorithmes polynomiaux pour la programmation linéaire utilisant des méthodes de points intérieurs : parmi ceux-ci figurent l'algorithme ellipsoïdal de Khachiyan , l'algorithme projectif de Karmarkar et les algorithmes de suivi de chemin . La méthode Big-M est une stratégie alternative pour résoudre un programme linéaire, utilisant un simplexe monophasé. Cohen et al. représentent une branche d'algorithmes appliquant des algorithmes de multiplication matricielle rapides aux programmes linéaires.