Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

LA MÉTHODE DU SIMPLEXE EDJA Kouamé B. Table des matières Objectifs 3 Introducti

LA MÉTHODE DU SIMPLEXE EDJA Kouamé B. Table des matières Objectifs 3 Introduction I - programme linéaire sous sa forme standard 4 1. Définition ........................................................................................................................................................ 4 2. Principe ........................................................................................................................................................... 6 3. La méthode des tableaux ................................................................................................................................. 6 4. Récapitulatif ................................................................................................................................................. 11 5. Exercice : ...................................................................................................................................................... 12 Solutions des exercices 13 Bibliographie 14 3 A la fin de ce cours vous serez capables de : Écrire un programme linéaire sous sa forme standard ; Résoudre un programme linéaire par la méthode du simplexe. Objectifs programme linéaire sous sa forme standard 4 1. Définition Pour résoudre un programme linéaire (PL) par la méthode du simplexe, il faut mette le (PL)sous sa forme standard (FS) Dans un (PL) sous sa forme canonique, les contraintes sont toutes des inéquation du type "≤" La mise sous forme standard consiste à introduire des variables supplémentaires (une pour chaque contrainte) de manière à réécrire les inégalités ( ≤) sous la forme d'égalités (=). Chacune de ces variables représente le nombre de ressources non utilisés. On les appelle variables d'écart. On travaille dans un espace de dimension plus grande, mais toutes les contraintes sont des égalités. Donc les manipulations algébriques plus aisées. a. Contraintes de type (≤) : Pour chaque contrainte i de ce type, on rajoute une variable d'écart , tel que est une variable positive ou nulle. Exemple : se transforme en b. Contraintes de type : Pour chaque contrainte i de ce type, on retranche une variable d'excédent , tel que est une variable positive ou nulle. Exemple : se transforme en programme linéaire sous sa forme standard I Remarque Définition 5 Le passage à la forme standard augmente le nombre de variables dans le programme linéaire. Considérons un système d'équations à n variables et m équations où (n ≥ m). Une solution de base pour ce système est obtenue de la manière suivante : a) On pose n - m variables égales à 0. Ces variables sont appelées variables hors base. b) On résout le système pour les m variables restantes. Ces variables sont appelées les variables de base. c) Le vecteur de variables obtenu est appelé solution de base (il contient les variables de base et les variables hors base) Une solution de base est admissible si toutes les variables de la solution de base sont ≥ 0. Considérons le PL suivant passant de sa forme canonique à sa forme standard. On a et ; variables Variables hors base : si alors les variables de base sont : . Une solution admissible ou réalisable de base est donc : . Exemple Variables de base et variables hors base Exemple Principe 6 Toute solution de base pour laquelle toutes les variables sont non négatives, est appelée solution de base admissible. Cette solution de base admissible correspond à un point extrême. Solution de base dégénérée : certaines variables de base sont nulles 2. Principe L'algorithme du simplexe (G. B. Dantzig 1947) est un algorithme itératif permettant de résoudre un problème de programmation linéaire. C'est une procédure algébrique qui sera en mesure de choisir parmi les solutions réalisables ceux qui maximisent la fonction objectif. Pour la méthode de simplexe une solution réalisable de base initiale est demandée. Une telle solution peut être retrouvée en annulant toutes les variables de décision. A partir de ce point la méthode de simplexe va générer successivement des solutions réalisables de base pour notre système d'équations en s'assurant que la valeur de la fonction objectif est en train d'augmenter jusqu'à localiser la solution optimale du problème qui est un point extrême de l'espace des solutions réalisables donc une solution réalisable de base. Ainsi, on peut décrire la méthode de simplexe comme étant une procédure itérative qui passe d'une solution réalisable de base à une autre jusqu'à atteindre la solution optimale. La description mathématique de ce processus fera l'objet de la section suivante. 3. La méthode des tableaux C'est une mise en œuvre manuelle de l'algorithme du simplexe. Nous les différentes étapes à travers un exemple tire du cours de (Bernard Auge - Alexandre Vernhet) [cf. videoplayback.webm] Les variables d'écart introduites au cours de cette transformation représentent les contraintes techniques et commerciales disponibles qu'il convient de saturer. Solutions admissibles étape 1: écrire le programme sous forme standard La méthode des tableaux 7 Disposer les éléments conformément au tableau ci-dessous. Pour cela on choisit le coefficient le plus élevé de la fonction économique. Le coefficient le plus élevé de la fonction économique MAX est 50. Ainsi, il s'agit de la variable y qui rentre dans la base. On fait le rapport : second membres/coefficient de la variable choisie. Et on retient le plus faible. Le second membre ( encadre en vert), on retient la valeur la plus faible (en orange) du rapport du second membre en vert/coefficient de la variable choisie. Ainsi la variable est la variable à enlever de la base. La variable y prendra la place de la variable dans la base. étape 2 : Construire le premier tableau du simplexe correspond à la ( FS) étape 3 : Choisir les variables à introduire dans la base étape 4 : Choisir les variables à enlever de la base La méthode des tableaux 8 Le pivot est égal à 1 ( encadré). c'est l'intersection entre la colonne de la variable entrante et la ligne de la variable sortante ( ) étape 5 :Choix du pivot étape 6 : Multiplier la ligne du pivot parle rapport : 1/valeur du pivot ( ou diviser la ligne du pivot par la valeur du pivot). La méthode des tableaux 9 - - . C'est la règle du rectangle. Cette opération consiste à transformer les des autres lignes en . Les coefficients de la fonction économique sont tous nuls ou négatifs ? ( si oui on est à l'optimum, si non on effectue un nouveau passage). Les coefficients de la fonction économique ne sont pas tous nuls ou négatif (30). Donc on effectue un nouveau passage. choisir la variable à introduire dans la base. Le coefficient de la fonction économique (MAX ) est 30. Ainsi la variable x ( encadré en rouge ) entre dans la base. choisir la variable à enlever de la base. En utilisant le principe ( étape 4), la variable e1 est à enlever de la base. étape 7 : Calculer les valeurs des autres lignes étape 8 : Test d'optimalité Nouveau passage : Récapitulatif 10 - - - Le pivot est égal à 3 Multiplier la ligne du pivot par 1/3 Calculer les autres valeurs des lignes On obtient Les coefficients de la fonction économique ne sont pas tous nuls ou négatifs, fin de l'algorithme du Simplexe. La solution qui rend le optimal le programme est le suivant : - le maximum de la fonction économique est : 36000 euros ( remarquez bien qu'a n'a pas mis le signe négatif !) - les quantités produites correspondantes sont x = 200 et y = 600. - la variable d'écart correspondant à la contrainte de marche X n'est pas saturée ( est toujours dans la base). On aurait donc pu vendre 200 produit X de plus. - Par contre, les variables et sont saturées. Exercice : 11 1. 2. 4. Récapitulatif Dans le cas d'un problème de Maximisation (Max) : lorsque les coefficients de la fonction économique sont tous nuls ou négatifs on est a l'optimum. Dans le cas d'un problème de Minimisation (Min) : lorsque les coefficients de la fonction économique sont tous nuls ou positifs on est a l'optimum. A l'optimum, les valeurs des variables d'écart représentent les marges entre les valeurs disponibles et les valeur techniquement utiles. Schéma de l'algorithme critères d'optimalité Exercice : 12 5. Exercice : I- On considère le programme suivant Question 1 Question 2 Soit le programme (P) suivant : Question 3 Montrer que est un sommet de la région réalisable. Mettre le programme sous forme standard, puis donner la solution de base réalisable associée à . Résoudre (P) en utilisant la méthode du simplexe. [ ] solution n°1 * [ ] p.13 Solutions des exercices 13 Exercice p. 12 > Solution n°1 , et la valeur maximale de est . Solutions des exercices Bibliographie 14 [C. Prins et M. Sevaux] C. Prins et M. Sevaux - Programmation linéaire avec Excel : 55 problèmes d'optimisation modélisés pas à pas et résolus avec Excel, Eyrolles, 2011. [Chvàtal] 1. V. Chvàtal - Linear Programming, W.H.Freeman, New York, 1983. [Guéret, C. Prins et M. Sevaux] 3 C. Guéret, C. Prins et M. Sevaux - Programmation linéaire : 65 problèmes d'optimisation modélisés et résolus avec Visual Xpress, Eyrolles, 2000. [iutbayonne] https://www.iutbayonne.univ-pau.fr/~grau/2A/RO/cadre3.html [techno-science] https://www.techno-science.net/definition/6353.html [Vanderbei] 2. R. J. Vanderbei - Linear Programming, Foundations and Extensions, Springer-Verlag, 2008. Bibliographie uploads/s3/ pl-l2-cours-papier.pdf