Remerciez-le!

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

Introduction à la Recherche Opérationnelle • PARTIE 1: INTRODUCTION GÉNÉRALE 

Introduction à la Recherche Opérationnelle • PARTIE 1: INTRODUCTION GÉNÉRALE MODÉLISATION PROGRAMMATION LINÉAIRE A.U 2019 - 2020 ANIMÉ PAR : IBRAHIM GUELZIM Cours : Introduction à la Recherche Opérationnelle REFERENCES • Hamdy Taha. OPERATIONS RESEARCH, AN INTRODUCTION. • Hillier / Liberman. INTRODUCTION TO OPERATIONS RESEARCH. • R. Faure. Précis de recherche opérationnelle - Méthodes et exercices d'application. 22/09/2019 08:13 2 Cours : Introduction à la Recherche Opérationnelle PROCÉDURE DU COURS • Présence. • Prises de notes de cours. • Diffusion de l’information: Responsable de la section facebook : Dept Info FSA site web: ibrahimguelzim.atspace.co.uk contact: ibr_guelzim@yahoo.fr Note Finale = Contrôle + Projet (TP langage C) + Examen 22/09/2019 08:13 3 Cours : Introduction à la Recherche Opérationnelle EXEMPLE 01 • Un agent commercial d’une entreprise doit faire 5 voyages d’affaire dans une durée de 5 semaines entre Casablanca et London, de sorte qu'il doit prendre le vol Casa-London les lundis et le retour les mercredis. Un billet régulier aller-retour coûte 4000 Dh, une réduction de 20% est accordée si les dates du billet couvrent un week-end. Un billet aller dans les deux sens coûte 75% du prix régulier. Quel est le prix minimum en dirhams que peut payer cet agent commercial ? 22/09/2019 08:13 4 Cours : Introduction à la Recherche Opérationnelle EXEMPLE 01 ~ • Un agent commercial d’une entreprise doit faire 5 voyages d’affaire dans une durée de 5 semaines entre Casablanca et London, de sorte que: il doit prendre le vol Casa-London les lundis et le retour les mercredis. Un billet régulier aller-retour coûte 4000 Dh, une réduction de 20% est accordée si les dates du billet couvrent un week-end. Un billet aller dans les deux sens coûte 75% du prix régulier. • Quel est le prix minimum en dirhams que peut payer cet agent commercial ? 22/09/2019 08:13 5 Cours : Introduction à la Recherche Opérationnelle EXEMPLE 02 • Ahmed, Kamal, Omar et Ilyas sont du côté droit d’une rivière et souhaitent traverser vers le côté gauche en utilisant un canot (petit bateau). Le canot peut contenir au maximum deux personnes simultanément. Ahmed étant le plus athlétique, peut traverser la rivière en 1 minute. Kamal, Omar et Ilyas prendraient 2, 5 et 10 minutes respectivement. Si deux personnes sont dans le canot, la personne la plus lente impose son temps de passage. Ex : Ahmed et Omar traverseront en 5 min. Sachant que le canot ne peut pas être envoyé vide, quel est le temps minimal pour ces 4 amis afin de traverser vers le côté gauche de la rivière ? 22/09/2019 08:13 6 Cours : Introduction à la Recherche Opérationnelle EXEMPLE 02 ~ • Ahmed, Kamal, Omar et Ilyas sont du côté droit d’une rivière et souhaitent traverser vers le côté gauche en utilisant un canot (petit bateau). • Le canot peut contenir au maximum deux personnes simultanément. • Ahmed étant le plus athlétique, peut traverser la rivière en 1 minute. Kamal, Omar et Ilyas prendraient 2, 5 et 10 minutes respectivement. • Si deux personnes sont dans le canot, la personne la plus lente impose son temps de passage. Ex : Ahmed et Omar traverseront en 5 min. • Sachant que le canot ne peut pas être envoyé vide, quel est le temps minimal pour ces 4 amis afin de traverser vers le côté gauche de la rivière ? 22/09/2019 08:13 7 Cours : Introduction à la Recherche Opérationnelle RÉSUMÉ • Difficulté du bon sense Passer au FORMALISME • Objectif: Trouver une / la meilleure solution (OPTIMAL) SOUS CONTRAINTES 22/09/2019 08:13 8 Cours : Introduction à la Recherche Opérationnelle INTRODUCTION GÉNÉRALE: CONTEXTE 22/09/2019 08:13 9 • Révolution industrielle (الثورة الصناعية) au UK (18ème siècle) • Nouveau style de vie • Progrès: Energie, Transport, Textile, Electricité… • Interactivité des organisations s’est compliquée. • Utilisation d’une approche scientifique dans la gestion des organisations. • Optimisation de l’utilisation des ressources pour l’aide à la décision. • Apparition de la recherche opérationnelle (RO). Cours : Introduction à la Recherche Opérationnelle INTRODUCTION GÉNÉRALE: CONTEXTE 22/09/2019 08:13 10 • Officiellement la RO avait apparu lors de la 2nd guerre mondiale. • à cause du besoin urgent d’allocation des ressources rares pour diverses OPERATIONS militaires dans les armées britannique puis américaine. • L’objectif : adapter les stratégies et les tactiques militaires à l’approche de la science (Mathématiques). • Ces armées ont invité des scientifiques pour faire la recherche sur les opérations militaires. • L’efficacité de la RO dans le domaine militaire a suscité son extension au secteur civil suite au «Boom industriel» qui a suivi la guerre. Cours : Introduction à la Recherche Opérationnelle INTRODUCTION GÉNÉRALE: CONTEXTE 22/09/2019 08:13 11 • La RO doit sa grande évolution durant le 20ème siècle à deux principaux facteurs: – Évolution algorithmique. – Révolution électronique-informatique. • la RO est importante lorsque le bon sens est impuissant: – Problèmes combinatoires : difficulté d’énumérer toutes les combinaisons; – Domaines aléatoires : déterminer parmi les décisions possibles, celle qui possède la plus grande probabilité de succès. – Situations de concurrence (théorie de jeux) : choix d’une stratégie qui dépendra forcément des décisions du (des) concurrent(s). Cours : Introduction à la Recherche Opérationnelle INTRODUCTION GÉNÉRALE: DÉFINITION 22/09/2019 08:13 12 • “Operations Research (O.R.) is the discipline of applying advanced analytical methods to help make better decisions”.[MIT-OR] • La Recherche Opérationnelle (RO) est la discipline de l'application des méthodes analytiques avancées pour aider à prendre de meilleures décisions. • Synonyme : Management science. Cours : Introduction à la Recherche Opérationnelle MODÈLE • Un modèle est une représentation partielle de la réalité: Avant : pour mieux construire (maquette), Après: pour mieux comprendre. • Abstraction de ce qui est intéressant pour un contexte donné • Vue subjective et simplifiée d'un système • Utilité des modèles – Faciliter la compréhension d'un système • Permettre également la communication avec le client • Vision de communication, de documentation – Définir voire simuler le fonctionnement d'un système • Il faut être le plus précis possible dans le contenu des modèles • Vision de développement, de production 22/09/2019 08:13 13 Cours : Introduction à la Recherche Opérationnelle MODÉLISATION: MÉTHODOLOGIE 22/09/2019 08:13 14 1. Définition du problème & Collecte des données : étape primordiale consistant à recueillir minutieusement les données pertinentes sans négliger le moindre détail. "ce sont les détails qui font la différence" 2. Formulation du modèle mathématique: C’est l’étape la plus importante et consiste à traduire les données collectées en modèle mathématique, comprenant aussi les restrictions imposées. 3. Résolution du modèle en cherchant une meilleure solution. On parle d’une solution optimale. Cours : Introduction à la Recherche Opérationnelle MODÉLISATION 22/09/2019 08:13 15 • Définition du problème & Collecte des données – En concertation avec les décideurs. – Pratiquement, la plupart des Pb rencontrés par les équipes de la RO sont initialement décrits d'une manière imprécise et vague. – Étudier méticuleusement le système. – Élaborer une description bien définie du Pb à considérer. – Détermination: • objectifs appropriés, • restrictions rencontrées, • interrelations entre la zone à étudier et autres domaines de l'organisation, • limites de temps pour prendre une décision. – Rappel: Objectif de la RO "Optimiser sous contraintes". Cours : Introduction à la Recherche Opérationnelle MODÉLISATION 22/09/2019 08:13 16 • Définition du problème & Collecte des données – Processus chronophage – Affecte grandement le modèle mathématique (étape suivante) – Affecte la pertinence des conclusions de l'étude. – Rappel: La résolution d’un problème "mal posé" est une tâche ardue ! Cours : Introduction à la Recherche Opérationnelle MODÉLISATION: FORMULATION DU MODÈLE 22/09/2019 08:13 17 • Pierre angulaire de la résolution d’un problème en RO. • Reformulation du Pb sous une forme analytique. • Construire un ensemble de relations mathématiques appelé « modèle mathématique » . • Représenter l'essence du problème. • Modèles mathématiques standards (Ex: PL) utilisation des algorithmes disponibles (cf. chapitres suivants). • Modèles complexes (MÉTAHEURISTIQUES): – Abandonner, éventuellement, la recherche de la solution optimale. – Chercher tout simplement une bonne solution. Cours : Introduction à la Recherche Opérationnelle MODÉLISATION 22/09/2019 08:13 18 • Formulation du modèle: Exemple 1 – Enoncé (Définition du Pb & Collecte des données): "Une entreprise fabrique deux produits A et B dont le marché ne peut absorber respectivement que les quantités 7000 et 10000 par mois. La disponibilité en matière première pour l’entreprise est de 96000 Kg par mois. Pour la production des deux produits, elle a besoin de 7kg de matière première pour une unité de A et 5kg pour une unité de B. Le profit unitaire est respectivement 3 um et 2 um pour A et B. (um : unités monétaires)." Cours : Introduction à la Recherche Opérationnelle MODÉLISATION 22/09/2019 08:13 19 • Questions / Réponses (Q/R): Rappel : RO = "Optimisation sous contraintes". 1. Q: Quel est le problème ? R: Une entreprise fabrique des produits et veut faire des profits (bénéfices, gains…), 2. Q: Quel est l'objectif ? R: Maximiser les gains (ici optimiser ⇔Maximiser) . 3. Q: Quelles sont les difficultés (restrictions): R: - restrictions internes: liées à la capacité de production, - restrictions externes: uploads/Geographie/ 01-cours-ro-intro-pl-19-20.pdf