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 UMMTO/FSECG Département des sciences économiques 2ème Année LMD Module : Math

1 UMMTO/FSECG Département des sciences économiques 2ème Année LMD Module : Mathématiques d’entreprise /Section : « B » Chapirte1 : Formulation d’un programme linéaire (Modélisation) : 1. Introduction L’importance de l’optimisation et la nécessité d’un outil simple pour modéliser des problèmes de décision que soit économique, militaire ou autres on fait de la programmation linéaire un des champs de recherche les plus actifs au milieu du siècle précédent. Les premiers travaux (1947) sont celle de George B. Dantzig et ses associés du département des forces de l’air des Etats Unis d’Amérique. Les problèmes de programmations linéaires sont généralement liés à des problèmes d’allocations de ressources limitées, de la meilleure façon possible, afin de maximiser un profit ou de minimiser un coût. Le terme meilleur fait référence à la possibilité d’avoir un ensemble de décisions possibles qui réalisent la même satisfaction ou le même profit. Ces décisions sont en général le résultat d’un problème mathématique. 2. Les conditions de formulation d’un PL La programmation linéaire comme étant un modèle admet des hypothèses (des conditions) que le décideur doit valider avant de pouvoir les utiliser pour modéliser son problème. Ces hypothèses sont : 1. Les variables de décision du problème sont positives 2. Le critère de sélection de la meilleure décision est décrit par une fonction linéaire de ces variables, c’est à dire, que la fonction ne peut pas contenir par exemple un produit croisé de deux de ces variables. La fonction qui représente le critère de sélection est dite fonction objectif (ou fonction économique). 3. Les restrictions relatives aux variables de décision (exemple: limitations des ressources) peuvent être exprimées par un ensemble d’équations linéaires. Ces équations forment l’ensemble des contraintes. 4. Les paramètres du problème en dehors des variables de décisions ont une valeur connue avec certitude 3. étapes de formulation d’un PL : Généralement il y a trois étapes à suivre pour pouvoir construire le modèle d'un programme linéaire : 1. Identifier les variables du problème à valeur non connues (variable de décision) et les représenter sous forme symbolique (exp. x1, y1 ). 2. Identifier les restrictions (les contraintes) du problème et les exprimer par un système d’équations linéaires. 3. Identifier l’objectif ou le critère de sélection et le représenter sous une forme linéaire en fonction des variables de décision. Spécifier si le critère de sélection est à maximiser ou à minimiser. 2 4. Présentation Théorique Un programme linéaire consiste à trouver le maximum ou le minimum d’une forme linéaire dite fonction objectif en satisfaisant certaines équations et inégalités dites contraintes. En langage mathématique, on décrira de tels modèles de la manière suivante : Soient N variables de décision x1, x2,…, xn, l’hypothèse que les variables de décision sont positives implique que . 0 , , 0 , 0 2 1    N x x x  La fonction objective est une forme linéaire en fonction des variables de décision de type N N x c x c x c z      2 2 1 1 où les coefficients c1,…,cN doivent avoir une valeur bien déterminée (avec certitude) et peuvent être positifs, négatifs ou nuls. Par exemple le coefficient cj peut représenter un profit unitaire lié à la production d’une unité supplémentaire du bien xj, ainsi la valeur de z est le profit total lié à la production des différents biens en quantités égales à . , , , 2 1 N x x x  Supposons que ces variables de décision doivent vérifier un système d’équations linéaires définis par M inégalités M N MN M M N N N N b x a x a x a b x a x a x a b x a x a x a                 2 2 1 1 2 2 2 22 1 21 1 1 2 12 1 11 où les coefficients a1M,…, aMN et b1,…, bM doivent avoir une valeur bien déterminée (avec certitude) et peuvent être positifs, négatifs ou nuls. Le paramètre bi représente la quantité de matière première disponible dont le bien xj utilise une quantité égale à aij xj . En suivant les étapes de formulation ci-dessus, on peut représenter le PL comme suit : 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                   N N N MN M M N N N N N N 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       5. Exemples de formulations Limité au départ aux problèmes industriels et militaires, de nos jours plusieurs problèmes de divers domaines sont représentés ou approximés par des modèles de PL. L’utilisation de ces techniques de modélisation s’est renforcée encore après avoir construit des algorithmes et des logiciels capables de résoudre de plus larges problèmes avec autant de variables de décision que de contraintes. La tâche de formulation demande généralement une certaine expertise et connaissance du problème pour pouvoir relever facilement les différentes composantes du problème et ainsi donner un programme qui modélise au mieux la situation réelle. Dans ce qui suit, on présentera quelques exemples de formulation en programme linéaire liés à différents problèmes de décision : 3 Exemple n°1 : Un fabricant produit 2 types de yaourts `a la fraise A et B `a partir de Fraise, de Lait et de Sucre. Chaque yaourt doit respecter les proportions suivantes de matières premières Les matières premières sont en quantité limitée : 800 kilos de Fraises, 700 kilos de Lait et 300 kilos de sucre. La vente des yaourts A rapportent 4 € par kilo et les yaourts B 5€ Solution : 1. Identification des variables de décision : X1 : la quantité de yaourts A à produire ; X2 : la quantité de yaourts A à produire ; 2. La fonction objective : Max Z= 4 X1 +5X2 3. Les contraints structurelles : 1ère Contrainte : 2X1 +X2≤ 800 2ème contrainte : X1+ 2X2≤700 3ème contrainte : X2≤ 300 4. Les contraintes de positivité : X1≥ ; X2≥0 ; Alors, le programme linéaire peut s’écrire sous la forme mathématique suivante : Max Z= 4 X1 +5X2 2X1 +X2≤ 800 X1+ 2X2≤700 X2≤ 300 X1≥ ; X2≥0 ; Exemple n°2 : Un fleuriste dispose de 50 lys, 80 roses et 80 jonquilles. Il réalise ou bien des bouquets qu’il vend 40 euros comprenant 10 lys, 10 roses et 20 jonquilles, ou bien des bouquets dont il tire un prix de 50 euros qui comprennent 10 lys, 20 roses et 10 jonquilles. Comment le fleuriste doit il former les bouquets pour réaliser une recette maximale ? Yaourts A Yaourt B Fraise 2 1 Lait 1 2 Sucre 0 1 Yaourts A (X1) Yaourts B (X2) Disponibilités de matières premières Fraise 2 1 800 1ère Contrainte Lait 1 2 700 2ème contrainte Sucre 0 1 300 3ème contrainte 4 Exemple n°3 : Un agriculteur souhaite mélanger des engrais de façon à obtenir au minimum 15 unités de potasse, 20 unités de nitrates et 30 unités de phosphates. Il achète deux types d’engrais.  Le type 1 procure 3 unités de potasse, 1 unité de nitrates et 3 unités de phosphates. Il coûte 120 €.  Le type 2 procure 1 unités de potasse, 5 unité de nitrates et 2 unités de phosphates. Il coûte 60 €. Exprimer à l’aide d’un programme linéaire la combinaison d’engrais qui remplira les conditions exigées au moindre coût. Solution : 5. Identification des variables de décision : X1 : la quantité de mélange de type 1 à acheter ; X2 : la quantité de mélange de type 2 à acheter; 6. La fonction objective : Min Z= 120 X1 +60X2 7. Les contraints structurelles 1ère Contrainte : 3X1 +X2 ≥15 2ème contrainte : X1+ 5X2 ≥20 3ème contrainte : 3X1 +2X2≥30 8. Les contraintes de positivité : X1≥ ; X2≥0 ; Alors, le programme linéaire peut s’écrire sous la forme mathématique suivante : Max Z= 120 X1 +60X2 3X1 +X2 ≥15 X1+ 5X2 ≥20 Mélange de type 1 (X1) Mélange de type2 (X2) Les besoins potasse 3 1 15 1ère Contrainte Nitrates 1 5 20 2ème contrainte Phosphates 3 2 30 3ème contrainte 5 3X1 +2X2≥30 X1≥ ; X2≥0 ; Exemple n°4 : Un atelier fabrique des tables et des bureaux.  Chaque table nécessite 2, 5 h pour l’assemblage, 3 h pour le polissage et 1 h pour la mise en caisse.  Chaque bureau exige 1 h pour l’assemblage, 3 h pour le polissage et 2 h pour la mise en caisse. L’entreprise ne peut disposer, chaque semaine, de plus de 10 h pour l’assemblage, de 15 h pour uploads/Voyage/ chapitre-1-1.pdf