Remerciez-le!

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

Chapitre 2 : La méthode de simplexe Cours de recherche opérationnelle Slim GUER

Chapitre 2 : La méthode de simplexe Cours de recherche opérationnelle Slim GUERMAZI 19 CHAPITRE 3 La Méthode de Simplexe I. Introduction On a présenté dans le chapitre précédent une procédure graphique pour résoudre un programme linéaire à deux variables. Par contre, dans la plupart des problèmes réels, on a plus que deux variables à déterminer. Une procédure algébrique pour résoudre les programmes linéaires avec plus que deux variables fera l’objet de ce chapitre. C'est la méthode de simplexe. Une implémentation de cette procédure à permis de résoudre des programmes avec un peu plus de quelques milliers de variables. Le programme Lindo qu’on présentera dans le chapitre 7 (en version pour étudiant) supporte au plus 200 variables et 100 contraintes. Dans ce chapitre la méthode de simplexe est présentée pour les problèmes 0 .   X b x A c s x c Max t et en utilisant le problème de l’agriculteur : 0 2 , 0 1 90 1 480 2 4 1 440 2 2 1 4 150 2 1 . . 2 200 1 100           x x x x x x x x x c s x x Max II. Mise sous forme standard La mise sous forme standard consiste à introduire des variables supplémentaires (une pour chaque contrainte) de manière a 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 variable d'écart. La forme standard s'écrit donc : 0 , 0 .     S X b S x A c s x c Max t  0 , , 0 , 0 0 , , 0 , 0 . 2 1 2 1 2 2 1 1 2 2 2 2 22 1 21 1 1 1 2 12 1 11 2 2 1 1                         M N M M N MN M M N N N N N N S S S x x x b S x a x a x a b S x a x a x a b S x a x a x a c s x c x c x c Max        Chapitre 2 : La méthode de simplexe Cours de recherche opérationnelle Slim GUERMAZI 20 La forme standard du programme linéaire de l'agriculteur est : Max 100x1 + 200x2 (3.1) s. c x1 + x2 + S1 = 150 (3.2) 4x1 + 2x2 + S2 = 440 (3.3) x1 + 4x2 + S3 = 480 (3.4) x1 + S4 = 90 (3.5) x1, x2, S1, S2, S3, S4 0 (3.6) L'impact de ces variables d'écart sur la fonction objectif est nulle. Ceci explique le fait que leur existence soit tout simplement liée à une mise en forme du programme linéaire initial. Ces variables d'écart peuvent prendre des valeurs nonnegatives. Le fait de donner la valeur des variables d'écart a l'optimum donne une idée du nombre des ressources non utilisées. III. Revue algébrique de la méthode du simplexe La question qui se pose : que demande-t-on d’une procédure algébrique ? En premier lieu, on note que les contraintes du problème (3.2)-(3.5), forment un système de 4 équations et de 6 variables. Or il y a un nombre infini de solutions de ce système d’équations. Donc une procédure algébrique, pour la résolution d’un programme linéaire doit être capable de retrouver les solutions des systèmes d’équations où il y a plus de variables que de contraintes. En deuxième lieu, ce ne sont pas toutes les solutions qui vérifient (3.2)-(3.5) qui sont des solutions du programme linéaire ; ils doivent en plus satisfaire les contraintes de nonnégativité. Ainsi une procédure algébrique doit être capable d’éliminer, de l’ensemble des solutions qui satisfait (3.2)-(3.1) celles qui n’arrivent pas à satisfaire les contraintes de nonnégativité. Finalement, une procédure algébrique pour résoudre les programmes linéaires doit être en mesure de choisir parmi les solutions réalisables ceux qui maximisent la fonction objectif. La méthode de simplexe est une procédure algébrique qui tient compte de ces trois considérations. Pour illustrer cette procédure, supposons que x2 = 0 et S1 = 0. Notre système devient x1 = 150 x1 = 150 x1 + S2 = 440 S2 = 340 4x1 + S3 = 480 S3 = -120 x1 + S4 = 90 S4 = -60 Chapitre 2 : La méthode de simplexe Cours de recherche opérationnelle Slim GUERMAZI 21 Les variables x1, S2, S3 et S4 (non nulles) sont dites variables de base et les variables S1, x2, (nulles) sont dites variables hors base. Généralement, si on a un programme linéaire standard constitué de n variables et m contraintes (n  m) alors une solution de base (extrême) est obtenue, en annulant (n-m) variables et en résolvant les m contraintes pour déterminer les valeurs des autres m variables. On note qu’une solution de base n’est pas toujours réalisable. C’est le cas de la solution qu’on vient de retrouver. Une solution réalisable de base serait celle où x1 = x2 = 0, ainsi on a : S1 = 150 S2= 440 S3 = 480 S4 = 90 Cette solution correspond à un point extrême de l’ensemble des solutions réalisables qui est l’origine O. 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. Ce qui correspond dans notre exemple au point d’origine O. 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. IV. La méthode des tableaux La méthode de simplexe commence par l'identification d'une solution réalisable de base et ensuite, elle essaye de trouver d'autres solutions réalisables de base jusqu’à atteindre à la solution optimale. Ainsi, on doit, tout d’abord, retrouver cette solution réalisable de base. Chapitre 2 : La méthode de simplexe Cours de recherche opérationnelle Slim GUERMAZI 22 Généralement si le programme linéaire satisfait ces deux propriétés : P1/ Parmi les variables du problème standard, il y a m variables qui apparaissent avec un coefficient non nul dans chaques contraintes (dans notre exemple : S1, S2, S3 et S4). P2/ Les valeurs du second membre des contraintes (les composants du vecteur b) sont positives. Alors une solution réalisable de base est obtenue en annulant les (n-m) variables de décision et la valeur des variables d'écart est directement donnée par le second membre. La deuxième propriété assure la satisfaction des contraintes de nonnégativité des variables d'écart. Dans notre exemple, la forme standard du programme linéaire vérifie ces deux propriétés. a. Tableau de simplexe initial Après avoir mis le programme linéaire sous une forme qui vérifie les deux propriétés P1 et P2, l’étape suivante est de tracer le tableau de simplexe initial. Le modèle général des tableaux de simplexe est : Pour notre exemple le tableau de simplexe initial est le suivant : 100 200 0 0 0 0 x1 x2 S1 S2 S3 S4 0 S1 150 1 1 1 0 0 0 0 S2 440 4 2 0 1 0 0 0 S3 480 1 4 0 0 1 0 0 S4 90 1 0 0 0 0 1 cj coefficient correspond aux variables Toutes les variables A = (aij)i,j matrice des coefficients des contraintes du programme standard Qi Valeur des variabl es de base VB varia bles de base Ci coefficie nts des variable s de base Chapitre 2 : La méthode de simplexe Cours de recherche opérationnelle Slim GUERMAZI 23 On remarque qu’on a placé en première ligne les contributions unitaires de toutes les variables de décision x1,..., S4 dans la fonction objectif. Dans la troisième ligne, on retrouve la première contrainte x1 + x2 + S1 = 150. La valeur 150 représente ici la valeur de S1 relative à la solution réalisable de base initiale. Dans la première colonne on trouve les contributions nulles des variables d'écart qui forment la solution de base initiale. Exemple : Question : Quelles sont les contraintes et la fonction objectif du programme linéaire décrit par le tableau de simplexe suivant : 6 7 0 0 x1 x2 S1 S2 0 S1 150 4 2 1 0 0 S2 440 1 5 0 1 Réponse : Les contraintes du programme sont : 4 x1 + 2x2 + S1 = 50 x1 + 5x2 + S2 = 40 uploads/Voyage/ la-methode-de-simplexe-chapitre-3.pdf