TD Partie-1 [PDF]

Zitiervorschau

Cours de Recherche Opérationnelle

Mme LEBBAR

TD de Recherche Opérationnelle

Partie Programmation Linéaire : Modélisation/Résolution Graphique, Méthode du Simplexe et Dualité Exercice 1 : Modélisation La compagnie AlphaInvest s'est vue attribuer la tâche de préparer un portefeuille d'investissements pour une société industrielle. Les fonds disponibles représentent un montant de 2500000 DH. L'analyste financier de la compagnie a retenu 6 possibilités d'investissements réparties dans l'industrie du pétrole, de l'électronique et pharmaceutique. Les diverses sociétés dans lesquelles on désire investir et les rendements anticipés sont résumés ci-après : Sociétés Sami PluriPetr MicroElec BetaElec Biomed Adwiya

Secteur d'activités Pétrole Pétrole Electronique Electronique Pharmaceutique Pharmaceutique

Rendement anticipé (%) 9.35 8.00 10.90 7.80 9.60 8.50

Les contraintes suivantes ont été émises :
Les investissements dans le secteur pharmaceutique devraient représenter au moins 30% des investissements dans le secteur électronique.
Aucun secteur d'activité ne devrait se voir allouer plus de 55% des fonds disponibles.
Bien que la société MicroElec présente un rendement anticipé élevé, on veut limiter le montant investi dans cette société, à cause de son risque élevé, à 60% des investissements dans le secteur électronique.
On a demandé aussi à AlphaInvest d'investir au moins 150000 Dh dans l'industrie pétrolière. L'objectif de l'analyste financier est de maximiser le rendement anticipé. Formuler le modèle de programmation linéaire qui permettrait à l'analyste financier de lui suggérer une stratégie de placement tout en respectant les contraintes mentionnées : 1. Donner les variables de décision du programme linéaire. 2. Ecrire les contraintes du programme linéaire. 3. Ecrire la fonction objectif de maximisation de rendement. 4. Le décideur peut éventuellement ne pas investir dans le secteur pharmaceutique, s’il décide d’y investir la quantité maximale est toujours de 55% des fonds : changer le modèle pour prendre en compte cette nouvelle contrainte de choix. Exercice 2 : Modélisation d’un Problème de mélanges Un importateur d’huiles essentielles dispose d’un marché supposé illimité pour vendre ses produits. Il peut importer trois qualités d’huiles (H1, H2 H3) en quantités maximales notées : d1 d2 ,d3 et aux prix respectifs P1, P2 P3. A partir de ces trois huiles, il effectue deux mélanges : un premier mélange A vendu avec le label « super » et un deuxième mélange B vendu avec le label « standard », qu’il vend aux prix respectifs : PA = 540 Dh et PB = 480 Dh par litre. Les donnés des trois huiles sont les suivantes : Quantités maximales : d1 = 2000, d2 = 2500, d3 = 1200 (en litres) Prix d’achat : P1 = 550, P2 = 450, P3 = 300 (Dh par litre)

Cours de Recherche Opérationnelle

Mme LEBBAR

Le mélange A doit contenir au moins 65% de l’huile H1 et au plus 25% de H3. Le mélange B doit contenir au moins 35% de l’huile H1 et au plus 25% de H2. Pour des raisons commerciales, la quantité totale de B ne doit pas dépasser la quantité totale de A. Ecrire le PL qui correspond au problème de l’importateur : il s’agit de décider les quantités respectives à fabriquer de chacun des produits A et B afin de maximiser les profits. 1. Donner les variables de décision du programme linéaire. 2. Ecrire les contraintes du programme linéaire 3. Ecrire la fonction objectif de maximisation de profit Exercice 3 : Résolution Un artisan chocolatier décide de confectionner des confiseries au chocolat. En réserves, il lui reste 90 kg de cacao, 40 kg de noisettes et 70 l de lait. Il a deux spécialités : le produit Extra et le produit Sublime. Une unité du produit Extra nécessite 1 kg de cacao, 1 kg de noisettes et 2 l de lait. Une unité du produit Sublime nécessite 3 kg de cacao, 1 kg de noisettes et 1 l de lait. Il fera un profit de 400 DH en vendant un produit Extra, et de 600 DH en vendant un produit Sublime. Combien de produits Extra et Sublime doit-il fabriquer pour faire le plus grand bénéfice possible ?

1. Ecrire le programme linéaire : a. Déterminer les variables de décision b. Ecrire les contraintes de disponibilité des matières c. Donner l’expression du profit 2. Résoudre le PL ainsi écrit par la méthode graphique : a. Faire le graphique b. Donner la solution optimale ainsi que le profit maximal qui lui correspond 3. Résoudre le même PL par la méthode simplexe des tableaux 4. A partir du dernier tableau : a. Définissez la notion de ressource abondante b. A-t-on une ressource abondante ? si oui laquelle ? c. Quel est le profit unitaire espéré, associé aux noisettes ? Exercice 4 : Modélisation d’une production à partir de lots Une grande entreprise propose à un sous-traitant de fabriquer trois produits P1 P2 et P3. Elle s’engage à acheter au sous-traitant tout ce qu’il produira dans la limite de 100 unités de P1, 150 unités de P2 et 200 unités de P3 à un prix unitaire unique de 1500Dh. Ces produits sont fabriqués à partir de trois matières premières A, B et C : les différentes quantités nécessaires par produit sont comme suit : Produits / Matière A B C P1 3 5 2 P2 4 2 3 P3 1 2 5 Par exemple pour fabriquer une unité de P1 il faut 3 unités de A, 5 unités de B et 2 de C. Le soustraitant ne peut acheter la matière que par lots. Deux types de lots sont disponibles. Les compositions ainsi que les prix d’achat sont : Lots / Matière

A

B

C

Lot1 Lot2

3 2

2 3

3 3

Le sous-traitant voudrait maximiser sa marge.

Prix d’achat unitaire (en dh) 600 700

Cours de Recherche Opérationnelle

Mme LEBBAR

1- Ecrire le modèle linéaire du sous-traitant qui consiste à fabriquer la commande de l’entreprise tout en maximisant sa marge : donner les variables de décision, la fonction objectif ainsi que les contraintes. 2- En supposant que le sous-traitant devrait choisir le type de lot à acheter : soit que des lots de type 1 ou que des lots de type 2 ; modéliser cette nouvelle contrainte.

Exercice 5 : Modélisation et Résolution Simplexe Un restaurateur dispose de 880 oursins et de 720 huîtres. Il propose à sa clientèle deux types d’assiette : assiette à 300 DH (4 oursins, 1 huître), assiette à 200 DH (2 oursins, 3 huîtres). Selon la capacité en nombre de tables de son restaurant il ne pourra pas vendre plus que 400 assiettes. Combien d’assiettes de chaque catégorie doit-il vendre pour maximiser sa recette : 1. 2. 3. 4.

Ecrire le programme linéaire du restaurateur Résoudre le PL ainsi écrit par la méthode graphique Résoudre le même PL par la méthode simplexe des tableaux A partir du dernier tableau : a. A-t-on des ressources abondantes ? si oui lesquelles ? b. Quel est le profit unitaire espéré, associé aux ressources rares (s’il y’en a) ? 5. Ecrire le programme dual associé à ce problème et donner la signification de ces variables ainsi que l’interprétation économique de sa fonction objectif. 6. Résoudre le Pl Dual à l’aide du théorème des écarts complémentaires

Exercice 6 : Modélisation linéaire

Un jeune couple, Jawad et Leila souhaite se partager les tâches suivantes : Courses, Cuisine, Nettoyage et Entretien. Ils ont évalué les temps nécessaires (en heure par semaine) pour la réalisation de chacune de ces tâches. Leur temps respectifs sont résumés dans le tableau suivant. Il est évident que chacun admet un temps différent : Jawad prépare une omelette en moins de temps que mettra Leila pour un couscous. Courses

Cuisine

Nettoyage

Entretien

Leila

3.2

7.4

4.1

2.5

Jawad

3.9

6.8

4.5

2.7

Ils voudront avoir chacun la responsabilité de deux tâches et minimiser le temps total consacré aux quatre tâches. Il s’agit donc de choisir les tâches que devront effectuer chacun tout en minimisant le temps total. 1- Formuler ce problème comme un programme linéaire : a. Définir les variables de décision b. Ecrire la fonction objectif : minimiser le temps total c. Ecrire les différentes contraintes 2- Montrer qu’on peut n’utiliser que 4 variables et écrire le PL correspondant.

Cours de Recherche Opérationnelle

Mme LEBBAR

Exercice 7 : Problème du transport (modélisation sans résolution) On propose le problème de transport de marchandise entre les dépôts D1 D2 et D3 vers les magasins A, B C D et E. Les données de transport : les coûts unitaires de transport les demandes ainsi que les disponibilités sont résumés comme suit : Le coût de transport

A

B

C

D

E

Total disponibilités

D1

8

5

3

2

6

220

D2

4

2

3

5

8

440

D3

5

4

2

6

7

340

Total des demandes

150

200

300

250

100

Ecrire le programme linéaire qui décide le plan de transport entre les différents dépôts vers les cinq magasins au moindre coût. 1. Donner les variables de décision du programme linéaire. 2. Ecrire les contraintes du programme linéaire et la fonction objectif. Exercice 8 : Modélisation de contraintes logiques On suppose le problème de choix d’investissement parmi 7 types d’actions différentes {1, 2 ,…, 7}. Utilisez des variables binaires pour modéliser les contraintes suivantes : i) Vous ne pouvez investir dans les 7 types ensembles. ii) Vous devez choisir au moins un type. iii) L’investissement de type 1 ne peut être choisi si le type 3 est choisi. iv) L’investissement 4 ne peut être choisi que si le type 2 est choisi aussi. v) Vous devez choisir les type 1 et 5 ensemble ou aucun des deux. vi) Vous devez choisir soit au moins un type parmi (1 2 3) soit au moins deux types parmi (2 4 5 6)