S1 PL [PDF]

Zitiervorschau

ESPRIT 2018/2019

Programmation linéaire Série N:1

UP-MATH/UE-RO Si… Sami

Exercice 1 Un conseiller …nancier doit choisir pour ses clients (club d’investissement) un certain nombre d’actions dans lesquelles investir. Ses clients souhaitent investir 100 000 DT dans 6 actions di¤érentes. Le conseiller leur indique le retour d’investissement (taux de retour) qu’ils peuvent espérer pour une période de six mois. Le tableau suivant donne pour chaque action son nom, sa catégorie (T : technologique, N : non technologique) et le taux de retour espéré. N 1 2 3 4 5 6

Nom Dash Associates (UK) Ilog France (F) France Telecom (F) General Motors (USA) Elf (F) BNP (F)

Catégorie T T T N N N

Retour 5.3 % 6.2 % 5.1 % 4.9 % 6.5 % 3.4 %

Les clients …xent certaines contraintes au conseiller. Ils veulent investir au moins 5000 DT et au plus 40 000 DT dans chaque action. Le club d’investissement désire investir au minimum la moitié de leur capital dans des actions françaises et au plus 30 % dans des valeurs technologiques. Donner le programme linéaire qui permet de répartir le capital investi de façon optimale. Exercice 2 Une ra¢nerie fabrique deux qualités d’essence (A et B) en mélangeant dans certaines proportions deux produits semi-…nis (P1 et P2). Les indices d’octane et les quantités disponibles par jour pour ces deux produits sont indiqués dans le tableau suivant : Indice d’octane Nombre de barils par jours P1 71 3900 P2 99 5000 L’indice d’octane de l’essence A doit être d’au moins 96 et celui de l’essence B d’au moins 85. La ra¢nerie vend toute sa production de A et B aux prix respectifs de 3,75 $ et 2,75 $ par baril. Les excédents éventuels de P1 sont revendus au prix de 1,25 $ par baril à une fabrique de goudron et ceux de P2 sont revendus à un terrain d’aviation au prix de 2,25 $ par baril. On notera x1 et x2 (resp. x1 et x2 ) le nombre de barils de P1 et de P2 utilisés pour fabriquer A (resp. B). 1- Calculer, en fonction de x1 et x2 , l’indice d’octane de A. 2- Ecrire le programme correspondant à l’optimisation du pro…t de la ra¢nerie. Exercice 3 Une usine de pièces électroniques produit trois types de produits P1, P2 et P3. Les prix unitaires et les contraintes de production sont les suivantes : Produit Prix unitaire (TND) P1 25 P2 75 P3 110 1

Contrainte 1 : La production d’une unité du produit P1 nécessite deux heures de main d’œuvre. Contrainte 2 : La production d’une unité du produit P2 nécessite trois heures de main d’œuvre en plus de deux unités du produit P1 Contrainte 3 : La production d’une unité du produit P3 nécessite quatre heures de main d’œuvre en plus d’une unité du produit P2 Contrainte 4 : L’usine dispose de 40 heures de main d’œuvre par semaine. Donner le programme linéaire qui permet à l’usine de déterminer le nombre optimal de produits (P1, P2, P3) à produire a…n de maximiser son chi¤re d’a¤aire. Exercice 4 : Un gestionnaire de fonds en bourse veut investir 1 million de dollars dans une combinaison d’obligations, actions, dépôts à terme, épargne, immobilier et or. Les valeurs estimées des facteurs de risque et les augmentations prévues des valeurs de l’investissement sont présentées dans le tableau suivant : Type d’investissement Obligation Action Dépôt à terme Immobilier Or

Taux de risque (%) Taux de croissance (%) 3 0 10 7 2 0 5 7 20 11

Par exemple, la valeur de l’immobilier devrait augmenter de 7% par an. D’autre part, les actions sont prévues d’augmenter de 7%. L’objectif est de déterminer la meilleure stratégie d’investissement a…n de maximiser le montant généré tout en respectant les restrictions suivantes : ² Au moins 30% du montant total investi doit correspondre à des obligations, pas plus de 10% à des actions et au moins 10% à des dépôts à terme. ² Jusqu’à 50% de l’argent total investi dans l’immobilier peut être emprunté sous forme d’hypothèque à un taux d’intérêt de 6%. Le montant emprunté ne dépasse pas 150 000 $. ² Le taux de risque moyen de l’investissement est au maximum égal à 4.5%. ² Le montant d’argent investi en « Or » ne peut pas dépasser 100 000 $ ou encore 8% du Montant total disponible. Exercice 5 : Un …nancier dispose d’un capital de 20 milles dinars, qu’il peut placer dans deux types d’investissements A et B. Le type A est disponible tous les ans et rapporte un intêret de 6% par an. Le type B nécessite un placement de deux ans et rapporte un intêret de 10%. Déterminer un plan d’invesstisement pour le …nancier sachant qu’il désire récupérer tout son capital après trois années tout en le maximisant. Exercice 6 : Une compagnie produit deux types d’engrais M1 et M2, qui doivent faire l’objet d’un traitement dans les trois ateliers de la compagnie. Le tableau suivant a¢che les données relatives au problème de production du mois prochain. 2

Durée du traitement (en heures / tonne) Atelier Engrais M1 Engrais M2 Temps disp (en heures) A1 4 6 250 A2 2 5 180 A3 3 3 180 Pro…t (mille DT / tonne) 4 6.5 1- Formuler le programme linéaire (P) qui permet de maximiser le pro…t de la compagnie, et écrire les deux premiers tableaux simplexe associés au problème (P). 3- À une itération donnée, on obtient le tableau suivant ( : la quantité d’engrais Mi) :  ? ? ?

 1 ? 3 

1 ? ? ? ?

2 0 1 0 ?

1 2 3 0.625 -0.75 ? -0.250 0.5 ? -1.125 0.75 ? ? ? ?

 21.25 27.50 33.75 Z=?

a- Compléter ce tableau et dire s’il correspond à la solution optimale. b- Indiquer les ateliers qui sont utilisés à pleine capacité. Exercice 7 : Résoudre le programme linéaire suivant, en utilisant la méthode du simplex :   = 21 + 2  8: 1 · 3 > > < 2 · 6 ¡1 + 2 ¸ 2 > > :  ¸ 0 Exercice 8 : On considère le programme linéaire (P) suivant: max  = 21 + 2  8 1 · 5 > > < 31 + 2 · 25 1 + 52 ¸ 5 > > : 1 ¸ 0 2 ¸ 0

1- Résoudre graphiquement le programme linéaire (P). 2- En utilisant l’algorithme du simplexe, déterminer une SBR initiale SBR0 du problème (P). 3- D’après le graphique, quel est le point extrême qui correspond à SBR0  4- Dresser le tableau du Simplexe qui correspond à SBR0  5- Quelle est la variable entrante qui permet d’obtenir la solution optimale en une seule itération.

3