Remerciez-le!

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

UNIVERSITE SAAD DAHLAB DE BLIDA Cours de Programmation Linéaire donné par le Dr

UNIVERSITE SAAD DAHLAB DE BLIDA Cours de Programmation Linéaire donné par le Dr. Ali DERBALA Cours 01: Modélisation d'un programme linéaire noté P.L. 1 LA PROGRAMMATION LINEAIRE La première révolution industrielle avait remplacé la force musculaire de l'homme par celle des machines. La seconde voyait la machine se commander elle-même. Les ordinateurs se sont introduits dans les entreprises et les pouvoirs publics firent surgir des problèmes de grande envergure auxquels les directions n'étaient pas préparées. La caractéristique essentielle de la Recherche Opérationnelle est le recours à la méthode scientifique. Le chercheur de la R.O. construit une représentation qu'il appelle un "modèle mathématique". Il peut manipuler les modèles et les étudier plus facilement que le système réel. Les modèles sont parfois très difficiles à construire et peuvent prendre la forme d'expressions mathématiques fort compliquées. Lorsqu'ils mettent leur modèle en formule, les chercheurs doivent énoncer formellement quelles sont les variables, l'objectif, les paramètres. La programmation linéaire est une technique mathématique permettant de déterminer la meilleure solution d’un problème dont les données et les inconnues satisfont à une série d’équations et d’inéquations linéaires. La programmation linéaire a été formulée par Dantzig en 1947 et connaît un développement rapide par suite de son application directe à la gestion scientifique des entreprises. Le facteur expliquant l’essor de la P.L est la construction d’ordinateurs puissants qui ont permis de traiter les problèmes concrets de taille très grande. On l’applique surtout en gestion et en économie appliquée. On peut citer les domaines d’application de la programmation linéaire qui sont : les transports, les banques, les industries lourdes et légères, l’agriculture, les chaînes commerciales, la sidérurgie, et même le domaine des applications militaires. Les méthodes de résolution sont la méthode du simplexe, méthode duale du simplexe, méthodes des potentiels, méthode lexicographique et des méthodes récentes appelées méthodes des points intérieurs. Le but de cette partie du recueil n’est pas de donner les méthodes de résolution de la programmation linéaire mais de la présenter à l’aide des exemples concrets et faciles. UNIVERSITE SAAD DAHLAB DE BLIDA Cours de Programmation Linéaire donné par le Dr. Ali DERBALA Cours 01: Modélisation d'un programme linéaire noté P.L. 2 Cours 01 : Modélisation d'un programme linéaire noté PL UNIVERSITE SAAD DAHLAB DE BLIDA Cours de Programmation Linéaire donné par le Dr. Ali DERBALA Cours 01: Modélisation d'un programme linéaire noté P.L. 3 Exemples concrets de problèmes qui se modélisent par la programmation linéaire. 01. Un problème de restauration. Un restaurateur peut offrir deux types de plats indifféremment. Des assiettes à 80 DA, contenant 05 sardines, 2 merlans et 01 rouget. Des assiettes à 120 DA, contenant 03 sardines, 03 merlans et 03 rougets. Il dispose de 30 sardines, 24 merlans et 18 rougets. Comment doit-il disposer pour réaliser la recette maximale ? Réponse 01. Soit x et y respectivement le nombre d’assiettes de type 1 et du type 2 à offrir. Le problème est de maximiser la fonction 80 x + 120 y sous les contraintes: 5 x + 3 y ≤ 30 2 x + 3 y ≤ 24 x + 3 y ≤ 18 x ≥ 0 et y ≥ 0. 02. Préparation de Gâteaux. Un boulanger a la possibilité de faire trois types de gâteaux G1, G2 et G3. Il utilise à cet effet de la farine (E1), du beurre (E2), des œufs (E3), du sucre (E4) et de la levure (E5). Les quantités aij de l’éléments Ei intervenant dans l’élaboration du gâteau Gj sont données dans le tableau ci dessous : G1 G2 G3 E1 1 1 2 E2 1 2 1 E3 2 1 1 E4 1 2 0 E5 1 2 2 Le boulanger dispose de 20 unités de E1, 10 de E2, 20 de E3, 20 de E4 et 10 de E5. Les bénéfices unitaires valent respectivement 2 pour G1 , 5 pour G2 et 7 pour G3 . Ecrire le programme linéaire qui détermine le nombre de gâteaux à confectionner de façon à maximiser le bénéfice total. UNIVERSITE SAAD DAHLAB DE BLIDA Cours de Programmation Linéaire donné par le Dr. Ali DERBALA Cours 01: Modélisation d'un programme linéaire noté P.L. 4 Réponse 2. Si on note xj le nombre de gâteaux de type Gj, j = 1, 2, 3. Le problème s’écrit : Maxz = 2 x1 + 5 x2 + 7 x3 x1 + x2 + 2 x3 ≤ 20 x1 + 2 x2 + x3 ≤ 10 2 x1 + x2 + x3 ≤ 20 x1 + 2 x2 ≤ 20 x1 + 2 x2 + 2x3 ≤ 10 x1 ≥ 0, x2 ≥ 0, x3 ≥ 0. 03. Problème de découpe. Une usine a reçu des plaques de métal d’une largeur de 200 cm et d’une longueur de 500 cm. Il faut en fabriquer au moins 30 plaques de largeur de 110 cm , 40 plaques de largeur de 75 cm et 15 plaques de largeur de 60 cm. Donner le modèle mathématique pour que les déchets soient les plus petits possibles . Réponse 3. Une plaque de 200 cm de largeur peut être découpée de cinq façons : 1. une plaque de 75 cm et deux plaques de 60 cm. Les déchets seront de 05 cm. 2. une plaque de 110 cm et une plaque de 75 cm. Les déchets seront de 15 cm. 3. une plaque de 110 cm et une plaque de 60 cm. Les déchets seront de 30 cm. trois plaques de 60 cm. Les déchets seront de 20 cm. deux plaques de 75 cm. Les déchets seront de 50 cm. Soit xi : le nombre de plaques à découper par la façon i, le problème s’écrit : Min z = 5 x1 + 15 x2 + 30 x3 + 20 x4 + 50 x5 x2 + x3 ≥ 30 x1 + x2 + x5 ≥ 40 2 x1 + x3 + 3 x4 ≥ 15. x1 ≥ 0, …, x5 ≥ 0. 04. Un problème de transport. Une entreprise stocke un produit dans trois dépôts A1, A2 et A3. Les quantités stockées sont respectivement a1, a2 et a3. Les dépôts doivent alimenter quatre magasins de vente B1, B2 , B3 et B4. La quantité du produit nécessaire au point de vente Bi est bi ( i = 1,…, 4 ). Comment l’entreprise doit-elle répartir les stocks entre les points de vente ou quelle quantité le dépôt Ai doit-il livrer au point de vente Bj ? UNIVERSITE SAAD DAHLAB DE BLIDA Cours de Programmation Linéaire donné par le Dr. Ali DERBALA Cours 01: Modélisation d'un programme linéaire noté P.L. 5 Réponse 4. Le problème de transport est un problème particulier de la programmation linéaire. Sa formulation mathématiques est : Minz = cij xij j n i m = − ∑ = ∑ 1 1 1 ai bj j n i m ≥ = − ∑ = ∑ 1 1 1 . Cette équation traduit que la demande doit être satisfaite. xij j n = − ∑ 1 1 ≤ ai , i = 1, …, m. xij i m = ∑ 1 = bj, j = 1, …, n - 1. xij ≥ 0, i = 1,…, m et j = 1,…, n – 1. ai ≥ 0, i = 1,…, m, bj ≥ 0, j = 1,…, n – 1, cij ≥ 0, i = 1,…, m et j = 1,…, n – 1. 05. Un problème de répartition de ressources. Une entreprise peut produire différents biens. Chaque bien est repéré par un indice « j ». Pour réaliser sa production, elle utilise des matières premières, des machines, de la main d’œuvre, c’est à dire des ressources mesurées en unités appropriées. Ces ressources, ou facteurs de production, sont disponibles en quantité limitée ; soit bi la quantité disponible de la ressource « i ». On sait par ailleurs, quelle quantité aij la production d’une unité du bien « j » nécessite une ressource « i ». Supposons que la production soit à rendement constant, c’est à dire que la production de xj unités du bien « j » exige aij xj unités de la ressource « i ». Ecrire un programme de production de l’entreprise sous forme de programme linéaire. Réponse 05. Il s’écrit, Max z = c jx j j n = ∑ 1 aijx j j n bi = ∑ ≤ 1 i = 1,…, m. xj ≥ 0, j = 1,…, n. UNIVERSITE SAAD DAHLAB DE BLIDA Cours de Programmation Linéaire donné par le Dr. Ali DERBALA Cours 01: Modélisation d'un programme linéaire noté P.L. 6 06. Une usine fabrique trois sortes de pièces ( p1, p2, p3 ) à l’aide de deux machines ( m1, m2 ). Chaque pièce en cours de fabrication doit passer successivement sur les deux machines dans un ordre indifférent et pendant les temps suivants ( en minutes ) Temps d’usinage (minutes par pièce) Machines P1 P2 P3 M1 M2 2 6 4 12 3 3 La machine m1 est disponible 8 heures, la machine m2 est disponible 10 uploads/Industriel/ universite-saad-dahlab-de-blida.pdf