[PDF] TP n°4 : Exercices pratiques de Recherche Opérationnelle

Université Paris Dauphine DE1 Département MIDO Outils en Informatique Initiation à la Recherche Opérationnelle avec Excel 1 TP n°4 : Exercices pratiques de Recherche Opérationnelle Exercice 1: Visite touristique John Doe, chercheur américain, va à Paris pour présenter un article lors d'une conférence. C'est la première fois qu'il vient dans la capitale française. Il arrive un lundi et, étant un chercheur très impliqué, il compte passer toute la semaine à la conférence. Cependant, celle-ci se termine le vendredi, et Monsieur Doe ne repart que le dimanche en fin de soirée pour avoir l'opportunité de visiter la ville pendant le week-end. Il se donne alors 12h sur les deux jours pour visiter pleinement Paris avec un budget de 60 euros maximum. En faisant une recherche sur internet, il trouve alors qu'il peut être intéressant de visiter : La Tour Eiffel (TE), Le Musée du louvre (ML), l'Arc de triomphe (AT), le Musée d'Orsay (MO), le Jardin des tuileries (JT), les Catacombes (CA), le Centre Pompidou (CP), la Cathédrale Notre Dame de Paris (CN), la Basilique du Sacré-Coeur (BS), la Sainte Chapelle (SC), La Place de la Concorde (PC), la Tour Montparnasse (TM) et l'Avenue des Champs-Elysées (AC). Pour chacun de ces lieux, il a pu réunir les informations suivantes dont il tiendra compte pour faire ses choix : la durée en heures de sa visite, l'appréciation globale des internautes (donnée sous forme de notes allant de * à ***** et le tarif à débourser pour une visite. Monsieur Doe a pu également déterminer les distances (en kms de marche à pied) entre deux sites :

Université Paris Dauphine DE1 Département MIDO Outils en Informatique Initiation à la Recherche Opérationnelle avec Excel 2 1. On suppose que Monsieur Doe souhaite visiter le maximum de sites, quelle(s) liste(s) de lieux lui conseilleriez-vous ? Quelle est son appréciation globale (la moyenne des appréciations des sites retenus) ? 2. Pourriez-vous proposer à Monsieur Doe une lis te de lieux à visiter avec une appréciation globale supérieure à **** ? 3. En réalité M. Doe a des préférences et les exprime de la manière suivante : a. Si deux sites se trouvent géographiquement très proches (dans un rayon de 1 km de marche à pied), il préférera visiter ces deux sites au lieu d'en visiter un seul. b. S'il visite la cathédrale Notre Dame ou la Sainte Chapelle, alors il ne visitera pas la Basilique du Sacré-Coeur. c. Il souhaite visiter à tout prix la Tour Eiffel et un musée. En tenant compte de ses préférences, proposez lui à nouveau une liste de sites touristiques à visiter Exercice 2 : Ge stion de planning (énonc é tiré du livre " Excel 2000 Les fonctions intégrées » éditions ENI) Nous sommes le 01/06/2016. Vous êtes chargé(e) de l'organisation d'un salon professionnel qui débute le 13/06/2016 . Vot re travail de pré paration vous a permis de déc omposer l'ensemble de ces préparatifs en tâches. Ces tâches sont liées par des contraintes d'antériorité présentées dans le tableau ci-dessous. Indice Tâche Durée (en jours) Contraintes d'antériorité 1 Définition des besoins 1 2 Edition plaquettes 2 1

Université Paris Dauphine DE1 Département MIDO Outils en Informatique Initiation à la Recherche Opérationnelle avec Excel 3 3 Préparation du matériel 5 1 4 Transport du matériel 3 3 5 Installation du stand 3 2,4 Vous souhaitez mener à bien ce travail le plus rapidement possible. 1) Saisir les données du problème dans une feuille EXCEL. 2) Saisir dans la même feuille le programme li néaire associé. Dét erminer la solution optimale. 3) A l'aide de fonctions logiques (SI, OU,...), r éaliser dans la même fe uille la représentation graphique de votre solution (sous la forme d'un dia gramme appelé diagramme de GANTT comme ci-dessous). (Ce diagramme doit être construit automatiquement à partir de la solution optimale fournie par le solveur). 4) Tout sera-t-il terminé le 12/06/2016 matin ? 5) Il est possible de comm encer l'installation du stand (tâche 5) après deux jours seulement de transport de matérie l. Ecrire la contrainte ass ociée. M odifier votre programme linéaire et ré-optimiser afin de remettre à jour le diagramme de GANTT. Est-ce maintenant possible de terminer le 12/06/2016 matin ? 6) L'édition de plaquettes a pris du retard et passe de 2 à 5 jours. Modifier le programme et ré-optimiser. Quelles sont les conséquences sur le planning ? Exercice 3 : Un problème mu ltipériode de production (énoncé tiré du livre " La recherche opérationnelle 3eme édition» de Y. Norbert, R. Ouellet et R. Parent, Gaëtan morin editeur, 2003) Pendant les 6 prochains mois, Pastiss imo, qui fabrique une large ga mme de pâtes alimentaires, va fournir en sacs de 1 kg les spaghettis que le supermarché HYPERBIEN vend sous sa marque. A chaque fin de mois, Pastissimo mettra 4 tonnes de spaghettis ensachés à la disposition de HYPERBIEN au prix de 1,28 euros le sac de 1 kg. Pour fabriquer ces spaghettis, il faut du blé dur et de l'eau. Pastissimo s'approvisionne en blé dur en début de chaque mois auprès de l'entreprise Les grands moulins du Sud. Le prix des achats et les quantités minimales et maximales de blé dur qu'il est possible d'acheter sont présentés dans le tableau ci-dessous :

Université Paris Dauphine DE1 Département MIDO Outils en Informatique Initiation à la Recherche Opérationnelle avec Excel 4 Mois Prix (en euros/tonne) Minimum (en tonne) Maximum (en tonne) 1 1000 4 6 2 975 3 4 3 1000 5 7 4 980 2 3 5 1020 4 7 6 1025 5 6 Pastissimo possède un entrepôt et un magasin. Dans le premier, elle conserve le blé jusqu'à son utilisation ; dans le second, elle emmagasine les spaghettis jusqu'à leur livraison. Au début du premier mois, Pastissimo disposera dans son entrepôt de 2 tonnes de blé et désire y retrouver le même tonnage à la fin des 6 mois. Elle peut entreposer à un coût mensuel de 20 euros la tonne les surplus de blé qui ne serviront pas à produire des spaghettis. La capacité maximale de cet entrepôt est de 3 tonnes de blé. Pastissimo dispose également d'une capacité maximale de 1 tonne de sacs de spaghettis dans son magasin à un coût de 25 euros la tonne. Les capacités de production de Pastissimo et les coûts de production sont présentés dans le tableau ci-dessous : Mois Capacité de production (en tonne) Coûts (en euros/tonne) 1 6 160 2 5 150 3 4 150 4 4 160 5 4 175 6 3 165 Pastissimo cherche à définir sa politique de production, d'achat de blé et de stockage pendant les 6 mois à ve nir de façon à minim iser ce s coûts. Pour cela, i l vous faut modéli ser le problème sous la forme d'un programme linéaire et utiliser le solveur. 1) Saisir les données dans une feuille Excel. 2) Choisir les variables de décision sachant qu'il faut décider des quantités à produire chaque mois, des quantités de blé à acheter en début de chaque mois, des quantités de blé à entreposer chaque mois (lorsqu'elles ne sont pas utilisées pour la production du mois), et enfin des quantités de spaghettis à entreposer chaque mois. 3) Ecrire les contraintes. Certaines contraintes lient les périodes entre elles et assurent l'équilibre entre les quantités achetées, les quantités produites et les quantités stockées sur les 6 mois. 4) Ecrire la fonction objectif. Montrer qu'il est équivalent pour Pastissimo de maximiser ses gains ou de minimiser ses coûts. 5) Ecrire le modèle sous sa forme tableau dans une autre feuille Excel. 6) Résoudre le modèle et interpréter les résultats. Exercice 4 : Un problème de production sur une période La société MENUESCA est une menuiserie implantée dans le Jura, spécialisée, entre autre, dans la fabrication d'escaliers. En particulier, elle a deux produits phare : l'un appelé Chorus

Université Paris Dauphine DE1 Département MIDO Outils en Informatique Initiation à la Recherche Opérationnelle avec Excel 5 correspond à un escalier haut de gamme et l'autre, appelé Allegro correspond à un produit plus standard. L'escalier Chorus se vend 4875 euros, alors que l'escalier Allegro se vend au prix unitaire de 2700 euros. La fabrication d'un escalier Chorus nécessite l'équivalent de 9 heures de main d'oeuvre, utilise les machines à bois durant 14 heures et il faut 20 m2 de bois pour le réaliser. La fabrication d'un escalier Allegro nécessite l'équivalent de 5 heures de main d'oeuvre, utilise les machines à bois durant 8 heures et il faut 10 m2 de bois pour le réaliser. Chaque mois, MENUESCA peut acheter et stocker au plus 16000 m2 de bois, au prix unitaire de 54 euros/m2. MENUESCA emploie 36 personnes qui travaillent 160 heures par mois (les salaires sont considérés comme un coût fixe, ils ne dépendent pas de la production). Si nécessaire, elle peut faire appel à une main d'oeuvre intérimaire dont le coût horaire facturé est de 69 euros. Chaque mois, la société dispose pour la production de ces 2 escaliers, en tout de 9500 heures sur les machines à bois . En l'absence de promotion quelconque , MENUESCA peut vendre jusqu'à 200 escaliers Chorus et 240 modèles Allegro chaque mois. Si en plus, on mène une campagne de publicité dans la presse spécialisée et grand public, alors on peut augmenter la demande. Après étude, il semble que pour 600 euros investis dans la publici té par type d'escalier, la demande augmente de 45 unités pour l'escalier Chorus et de 60 unités pour l'escalier Allegro. Ce raisonnement marginal n'est valable qu'en deçà d'un certain seuil : par conséquent, le budget maximum que l'on conseille MENUESCA de consacrer à la publicité est de 6154 euros. La société MENUESCA souhaite évidemment trouver la production mensuelle à réaliser pour ces deux modèles d'escalier, et déterminer avec quels moyens de product ion (heures intérimaires utilisées, quantité de bois acheté et budgets de promotion) elle peut la réaliser au mieux afin de maximiser ses bénéfices (hors charges fixes des locaux et employés). 1. Ecrire le programme linéaire que doit résoudre MENUESCA. 2. Résoudre le programme linéaire en supposant que la publicité n'est pas possible. Quelle est la solution optimale? Quelles sont les contraintes saturées et donc limitantes? 3. A priori est-il intéressant de faire appel à la publicité pour les deux escaliers? 4. Modifier et résoudre le programme précédent pour qu'il intègre la possibilité de faire appel à la publicité. Les résultats sont-ils en accord avec ceux de la question 3? 5. Refaire la résolution mais en imposant que le nombre d'escaliers produits de chaque type soit à valeur entière.