Remerciez-le!

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

Pl l2 cours papier LA MÉTHODE DU SIMPLEXE EDJA Kouamé B CTable des matières Objectifs Introduction I - programme linéaire sous sa forme standard Dé ?nition Principe La méthode des tableaux Récapitulatif Exercice Solutions des exercices Bibliographie CObje

LA MÉTHODE DU SIMPLEXE EDJA Kouamé B CTable des matières Objectifs Introduction I - programme linéaire sous sa forme standard Dé ?nition Principe La méthode des tableaux Récapitulatif Exercice Solutions des exercices Bibliographie CObjectifs A la ?n 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 Cprogramme linéaire sous sa forme standard programme linéaire sous sa forme standard I Dé ?nition 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 Remarque 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 CExemple Dé ?nition Variables de base et variables hors base 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 à 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 ? Exemple 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 CPrincipe Solutions admissibles 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 Principe L'algorithme du simplexe G B Dantzig 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