Remerciez-le!

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

Unive rsité Moha m e d pre m ie r Fa culté pluridisciplina ire Na dor Programma

Unive rsité Moha m e d pre m ie r Fa culté pluridisciplina ire Na dor Programmation linéaire Présenté par: Encadré par: EL OSROUTI MOHAMMED MR.SAADI ZOUGAGH SOUFYANE DALALI ABDELMAJID Anne é unive rsita ire :2015/2016 L’objectif de cet éxposé est de: Apprendre comment modéliser un problème linéaire. Savoir résoudre un problème simple d'optimisation linéaire sous contraintes. plan I. Introduction II. Historique et évolution de Programmation linéaire V. Notions de base 1) Modélisation 2) Les étapes de modélisation ) -les variables de decision ) -Les contraintes ) -La fonction objectif(économique) IV. Les différentes méthodes pour resoudre un probleme lineaire 1) Méthode des facteurs rares 2) Méthode graphique 3) Méthode simplexe V. Développement de méthode graphique )Principe de méthode graphique )exemple VI. Application VIII.Conclusion I. INTRODUCTION: Une partie importante de problèmes de décision que rencontrent les dirigeants dans la pratique sont sans aucun doute les problèmes d’optimisation linéaire ou programmes linéaires. La résolution d’un problème de la programmation linéaire ne pose incontestablement aucune difficulté car il y a des méthodes pratiques pour le résoudre ,plus cela on peut utiliser des logiciels très efficaces pour la résolution tel que MATLAB , EXCEL SOLVER ,LINDO ,…etc. II. Historique et évolution de Programmation linéaire ) Les premiers mathématiciens qui se sont occupés de problèmes, que l’on ne nommait pas encore à l’époque « programmes linéaires » (P.L.), sont : LAPLACE (1749-1827) et le baron FOURIER. ) le russe KANTOROVITCH en 1939 a imaginé une méthode inspirée des multiplicateurs de LAGRANGE, classiques en mécanique, pour résoudre des « programmes de transport ». )La contribution décisive a été l’invention de l’algorithme du SIMPLEXE, développé à partir de 1947 notamment par G.B. DANTZIG et le mathématicien VON NEUMANN ) Au milieu des années 80, l’indien KARMARKAR a proposé une nouvelle méthode créée aux Bell Laboratories qui permettait de résoudre de très gros problèmes linéaires, par une démarche « intérieure » au polyèdre des solutions admissibles. Définition de programmation linéaire(PL):  Selon William J. BAUMAUL, la programmation linéaire est une technique mathématique d'optimisation (maximisation ou minimisation) de fonction à objectif linéaire sous des contraintes ayant la forme d'inéquations linéaires. Elle vise à sélectionner parmi différentes actions celle qui atteindra le plus probablement l'objectif visé.  Robert DORFMAN et Paul Samuelson, ajoutent que la programmation linéaire est une méthode de détermination du meilleur plan d'action pour réaliser des objectifs donnés dans une situation où les ressources sont limitées. C'est donc une méthode de résolution du problème économique, soit dans le cadre d'une économie globale, soit dans celui du secteur public, soit dans une entreprise particulière . III. Notions de base 1) Modélisation La modélisation d’un problème linéaire consiste a identifier:  les variables. Les différentes contraintes auquelles sont soumises ces variables. L’objectif visé(optimisation). 1) Les étapes de modélisation ) -La détermination des variables de décision les variables x1,x2,….. Xn sont appelées des variables de décision ou variables réelles du problème.  -La détermination des contraintes : La contrainte peut être assimilée à un obstacle.tel que les limitations techniques scientifiques, économiques, les lois de la nature, les délais, etc. exemple: x1+2x2 ≤ 10 2x1+x2 ≤ 5 domaine des contraintes 3x1+2x2 ≤ 12 avec: x1 ≥ 0 ;x2 ≥ 0 La détermination de la fonction objectif (économique) La fonction objectif (économique) est une fonction qui permet de determiner l’optimum (max de profit /min des Coût) . Le but du problème d'optimisation est alors de minimiser ou de maximiser cette fonction jusqu'à l'optimum, par différents procédés comme la méthode graphique. La fonction objectif est une forme linéaire en fonction des variables de décision de type: Max(ou min)z = c1 x1 + c 2 x 2 +....+cN xN où les coefficients c1,…,cN doivent avoir une valeur bien déterminée et peuvent être positifs, négatifs ou nuls. IV. Les differentes méthodes pour résoudre un problème linéaire Il existe plusieurs méthodes pour la résolution d’un problème linéaire . Dans notre éxposé on va s’interesser juste au trois méthodes tel que: Les méthodes pour la résolution d’un problème linéaire la méthode des facteurs rares La méthode simplexe La méthode graphique 1) Méthode des facteurs rares Définition du facteur rare: Un facteur rare est un moyen de production (matiére premiére , main d’oeuvre , heure machine)dans la quelle on est limité . Exemple: On a une entreprise qui fabrique deux produit A et B a l’aide d’une seul machine . Alors pour fabriquer A il faut 2H de machine et pour fabriquer B il faut 3 heure . La machine ne peut tourner plus de 100 heure . Donc pour choisir entre ces deux produits sous contrainte de capacité, les décideurs doivent privilégier le produit pour lequel la marge par unité de facteur rare est maximale 2) Méthode graphique l'utilisation de cette méthode est restreinte aux (PL) ayant un nombre de variables au plus égal à 3. Il existe 2 façon pour résoudre un PL a partir de la méthode graphique:  la méthode d’énumeration des sommets  la méthode des droits paralléles 3) Méthode simplexe 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. C'est la méthode de simplexe. Une application de cette procédure à permis de résoudre des programmes avec un peu plus de quelques milliers de variables. Le programme Lindo supporte au plus 200 variables et 100 contraintes. 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(MIN) Z=10X+20Y 2X+3Y ≤ 50 S/C : X+4Y ≤ 60 X+Y ≤ 100 MAX(MIN) Z=10X+20Y 2X+3Y+e1=50 S/C: X+4Y+e2=60 X+Y+e3=100 V. Développement de méthode graphique Principe de méthode graphique : le principe de cette méthode se base sur la représentation des données(contraintes + fonction objectif)d’une maniére graphiquement. Les 3 étapes de Résolution Graphique : Représentation graphique des contraintes et de la région réalisable Représentation de la fonction objectif Détermination le point optimum 1 2 3 • la méthode d’énumeration des sommets: Dans la méthode d’énumeration des sommets,on se bornera seulement à : + représenter graphiquement les droites – limites (équations provenant des inéquations de départ) . + délimiter la frontière de l'enveloppe polygonale, c'est à dire à construire le domaine d'acceptabilité . + remplacer successivement les coordonnées de chaque sommet du polygone dans la fonction économique afin d'obtenir la combinaison optimale cherchée(minimum ou maximum). • méthode des droits paralléles: En général, pour chercher le minimum, on optera pour le point le plus voisin de l'origine, alors que pour le maximum ce sera le point le plus éloigné. On pourra utiliser, à la place de l'énumération de tous les points du polygone d'acceptabilité, le procédé qui consiste à déplacer la droite de la fonction économique parallèlement à son inclinaison à l'origine et en chacun des sommets du domaine d'acceptabilité. Pour le coût, on retiendra la droite la plus voisine de l'origine et pour le maximum, la plus éloignée. Le premier sommet sera le minimum et le dernier atteint le maximum cherché. MAX (ou MIN): c1X1 + c2X2 + … + cnXn a11X1 + a12X2 + … + a1nXn ≤ b1 S.C a21X1 + a22X2 + … + a2nXn ≤ b2 ……………………………….. am1X1 + am2X2 + … + amnXn = bm x1≥ 0 , x2 ≥ 0 , ........., xn ≥0 Forme générale d’un problème linéaire: On va maximiser la fonction suivante: Max(z) = 1200 x1 + 1000 x2 sous les contraintes économiques 3 x1 + 4 x2 ≤ 160 6 x1 + 3 x2 ≤ 180 et les contraintes de signe x1 ≥ 0 ; x2 ≥ 0 Un problème linéaire peut être résolu de manière graphique en suivant le processus en trois étapes : Exemple: 6X1 + 3X2= 180 60 50 40 30 20 10 3 X1 + 4X2 =160 0 10 20 30 40 50 60 70 X1 Région des solutions admissibl es 1200X1+1000X2 =0 Point optimal 1)Représentation graphique des contraintes et de la région réalisable 2)Représentation de la fonction objectif 3) Détermination le point optimum VI. Application: Une entreprise fabrique 2 produits X et Y. Pour sa conception, chaque produit fini nécessite 3 produits intermédiaires A, B et C. Pour fabriquer un produit X, on a besoin de 2 produits A, de 2 produits B et de 1 produit C. De même, pour fabriquer un produit Y, on a besoin de 4 produits A, de 1 produit B et de 3 produits C. En outre, l’entreprise dispose d’une quantité limitée de produits A, B et C. Elle a 92 produits A, 60 produits B et 45 produits C. Sachant que le prix de revient de X est 20 DH et que celui de Y est de 40 DH . T.A.F: combien de produits X et Y faut-il fabriquer pour maximiser le profit ? Solution: Il faut formaliser le probléme sous forme d’un programme linéaire. soient: x:la quantité de X produit uploads/Histoire/ corrcetion.pdf