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 methode de simplexe chapitre 3

Chapitre La méthode de simplexe CHAPITRE 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 en version pour étudiant supporte au plus variables et contraintes Dans ce chapitre la méthode de simplexe est présentée pour les problèmes Max ct x s c A x n b et en utilisant le problème de l ? agriculteur X n Max x n x s c x n x n x n x n x n x n x n x n x n 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 n 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 Max ct x s c A x n S n b X n S n n Max s c c x n c x n n n cN xN a x n a x n n n a N xN n S n b a x n a x n n n a N xN n S n b n aM x n aM x n n n aMN xN n S M n bM x n x n n xN n S n S n n S M n Cours de recherche opérationnelle Slim GUERMAZI Chapitre La méthode de simplexe La forme standard du programme linéaire de l'agriculteur est Max x x s c x x S x x S x x S x S x x S S S S n 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 - forment un système de équations et de 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