Remerciez-le!

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

1 CHAPITRE 1 La Programmation Linéaire Introduction L’objectif principal de ce

1 CHAPITRE 1 La Programmation Linéaire Introduction L’objectif principal de ce cours est d’acquérir une connaissance approfondie de certaines techniques considérées à l’heure actuelle comme des méthodes de base et permettre à l'étudiant de se familiariser avec les principales techniques décisionnelles et d'optimisation de la recherche opérationnelle. Cette dernière représente l'ensemble des méthodes mathématiques et algorithmiques qui permettent de résoudre un problème donné de la meilleure façon possible La programmation linéaire est lié à des problèmes d’allocations de ressources limitées, de la meilleure façon afin de maximiser un profit ou de minimiser un coût. Elle consiste à chercher l’optimum d’une fonction économique linéaire de plusieurs variables sous certaines contraintes exprimées par des équations (ou inéquations) qui sont linéaires. I) La modélisation en recherche opérationnelle et son application La RO s’intéresse à la compréhension et à la résolution des problèmes de décision se posant dans les organisations et vise à l’amélioration de leur fonctionnement. Ceci en se basant sur des méthodes scientifiques (Mathématiques et informatiques) pour résoudre des problèmes d'optimisation. L’application de la RO touche plusieurs domaines tels que la gestion de production et la gestion de ressources humaines. Elle permet de prendre des décisions optimales concernant nombreux problèmes, afin de maximiser un profit ou de minimiser un coût tout en utilisant la meilleure combinaison des ressources disponibles. Dans le domaine de la production l'application de la RO revient à maximiser le profit selon la disponibilité des ressources suivantes : main d'œuvre, capacité de production, demande du marché, prix de revient du matériau brut. 2 II) Formulation mathématiques d’un programme linéaire (PL) 1. Les conditions de formulation d’un PL Afin de formuler un PL certaines hypothèses doivent être vérifiées1. En effet,  Les variables de décision du problème sont positives  Une fonction linéaire des variables de décision est définie afin de prendre décision. Cette fonction est dite fonction objectif ou fonction économique.  Les contraintes (ou les restrictions) relatives aux variables de décision sont exprimées par un ensemble d’équations linéaires.  Les paramètres du problème ont une valeur connue (en dehors des variables de décisions) 2. Les étapes de formulation d’un PL : La formulation d'un PL nécessite de suivre les étapes suivantes :  IL faut Identifier les variables de décision du problème notées généralement par xi (i= 1,...,n) avec . 0 , , 0 , 0 2 1    N x x x   Identifier les contraintes du problème et les présenter sous forme d' un système d’équations linéaires. ( b x a x a x a N 1N 2 12 1      11 )  Écrire la fonction "objectif" et spécifier si le critère de sélection est à maximiser ou à minimiser. Cette fonction "objectif" est linéaire de type: N N x c x c x c z      2 2 1 1 Ainsi après avoir présenté les différentes étapes, on peut écrire le PL lié au problème en question: Pour un problème de maximisation le système se présente comme suit : x , , x , x b x a x a x a b x a x a x a b x a x a x a c . s x c x c x c Max N N N MN M M N N N N N N 0 0 0 2 1 2 2 1 1 2 2 2 22 1 21 1 1 2 12 1 11 2 2 1 1                         1 Ces hypothèses résument celles qui ont été donné par G. B. Dantzig : La proportionnalité, La non- négativité, l’additivité et la linéarité de la fonction objectif 3 Pour un problème de minimisation le système se présente comme suit x , , x , x b x a x a x a b x a x a x a b x a x a x a c . s x c x c x c in M N N N MN M M N N N N N N 0 0 0 2 1 2 2 1 1 2 2 2 22 1 21 1 1 2 12 1 11 2 2 1 1                         3. Formulation Plusieurs problèmes dans divers domaines peuvent être représentés par des modèles de PL. L’utilisation de ces techniques de modélisation s’est approfondie par la construction des algorithmes et des logiciels capables de résoudre des problèmes avec autant de variables de décision que de contraintes. La formulation d'un PL demande, en général, une certaine connaissance du problème pour pouvoir relever facilement les différentes composantes du problème et donner un programme qui modélise la situation réelle. Dans la suite, on présente des exemples de formulation en programme linéaire qui sont liés à différents problèmes de décision. Exemple 1: usine de fabrication des jouets Une usine fabrique deux types de jouets en bois : des soldats et des trains. Les données de ce problème sont représentées dans le tableau suivant : L'usine dispose par semaine de toutes les matières premières nécessaires à la fabrication et ne dispose que de 100 heures de finition et 80 heures de menuiserie. La Menuiserie Finition 1 soldat 1h de travail 2h de travail 1 train 1h de travail 1h de travail 4 demande des trains et des soldats est illimitée. Sachant que Le prix de vente du jouet de type soldat est de 3 dinars et celui de type train est de 2 dinars, déterminer le plan de production qui maximise le profit de l'usine. On note par : x1= le nombre de soldats produits chaque semaine, x2= le nombre de trains produits chaque semaine. D'après les données, on définie les contraintes suivantes représentent la disponibilité des facteurs de production:  Menuiserie: on dispose de 80 heures de menuiseries, pour fabrique 1 soldat il faut 1 heure et pour un train il faut 1 heure. la contrainte liée à la menuiserie est : 80 2 1   x x  Finition : la finition d’1 soldat nécessite 2 heures de travail, et celle d'1 train nécessite 1 heure, le fabriquant ne dispose que de 100 heures de travail. La contrainte liée à la limitation de la finition est: 100 2 2 1  x x . Il s'agit d'un programme linéaire à deux variables de décision, la fonction objectif est la suivante : . x x z 2 1 2 3   Le problème consiste à maximiser le profit de l'usine, donc le programme linéaire suivant : 0 0 100 2 80 2 3 2 1 2 1 2 1 2 1        x , x x x x x . c . s x x Max Exemple 2 : Problème d’agriculture 2 Un des meilleurs exemples qui explique bien la formulation d'un PL est celui lié au problème de l'agriculteur. Par conséquent, on reprend dans ce qui suit les différentes étapes de sa formulation. 2 Exemple du cours du Prof. Mohamed Saleh Hannachi 5 Cet agriculteur veut allouer 150 hectares de surface irrigable entre la culture de tomates et la culture de piments. Pour cela, il dispose de 480 heures de main d’œuvre et de 440 m3 d’eau. L'hectare de tomates demande 1 heure de main d’œuvre, 4 m3 d’eau et donne un bénéfice net de 100 dinars. Cependant, 1 hectare de piments nécessite 4 heures de main d’œuvre, 2 m3 d’eau et donne un bénéfice net de 200 dinars. De plus, pour des raisons de protection du prix des tomates le bureau du périmètre irrigué ne lui permet pas de cultiver plus de 90 hec de tomates. Quelle est donc la meilleure allocation de ses différentes ressources ? Formulation du problème en un PL : 1ère Étape: On considère  x1 : la surface allouée à la culture des tomates  x2 : la surface allouée à la culture des piments Les variables de décision x1 et x2 sont positives : 0 , 0 2 1   x x . 2ème Étape: Identification des contraintes.  Terrain : la contrainte liée à la limitation de la surface de terrain est 150 2 1  x x  Eau : La contrainte qui exprime les limitations des ressources en eau est 440 2 4 2 1  x x .  Main d’œuvre : La contrainte représentant les limitations des ressources humaines est 480 4 2 1  x x  Les limitations du bureau du périmètre irrigué : La contrainte qui représente cette restriction est . 90 1  x 3ème Étape : La fonction objectif consiste à maximiser le profit apporté par la culture de tomates et de piments. Les contributions respectives des deux variables de décision x1 et x2 sont 100 uploads/Voyage/ chapitres-123.pdf