Remerciez-le!

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

Chap3 doc 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é

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 ? b et en utilisant le problème de l ? agriculteur X ? Max x x s c x x ? x x ? x x ? x ? x ? x ? 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 Max c x c x n cN xN s c a x a x n a N xN S b Max ct x a x a x n a N xN S b Û s c A x S ? b X ? S ? n aM x aM x n aMN xN S M bM x ? x ? n xN ? S ? S ? n S M ? 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 ? 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 deuxième lieu ce ne sont pas toutes les solutions qui vérifient - 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