Remerciez-le!

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

28/03/2016 1 Cours Recherche Opérationnelle Appliquée Optimisation dans les gra

28/03/2016 1 Cours Recherche Opérationnelle Appliquée Optimisation dans les graphes Masters Professionnels 1 Partie 1 Objectif du cours L’objectif du cours est de fournir aux participants les outils nécessaires pour: - l’optimisation des ressources par l’utilisation des théories de la recherche opérationnelle, - Modélisation mathématique des problèmes, - Résolution des programmes linéaires. Ce cours vise à mettre l’accent sur l’activité de modélisation dans diverses domaines: Production, ventes, médecine, distribution, agriculture, … et plus secondairement sur les techniques de résolution mathématiques (automatisables). 2 28/03/2016 2 • Présence et participation  20% • Mini-projet en Groupe  20% (Groupes de 4 participants maximum) • Examen individuel  60% 3 Evaluation du module Plan du cours 4 Chapitre 1 : Introduction à la Recherche Opérationnelle - Présentation générale - Compétences et domaines concernés - Structures concernées dans l’entreprise - Exemples de problèmes classiques - Domaines d’applications 28/03/2016 3 - Définition - Utilité - Vocabulaire: Arrête, chemin et circuit - Représentation graphique - Représentation matricielle - Représentation par table de liste - Coloration des graphes 5 Chapitre 2 : Optimisation par les graphes Plan du cours - Présentation générale - Compétences et domaines concernés - Structures concernées dans l’entreprise - Exemples de problème classiques de la programmation linéaire 6 Chapitre 3 : Optimisation par la programmation linéaire (Modélisation) Plan du cours 28/03/2016 4 7 Chapitre 4 : Résolution des programmes linéaires - Résolution graphique - Algorithme du simplexe - Résolution par des outils informatiques: - Solveur - Modeleur Plan du cours Plan du cours 8 Chapitre 1 : Introduction à la Recherche Opérationnelle - Présentation générale - Compétences et domaines concernés - Structures concernées dans l’entreprise - Exemples de problèmes classiques - Domaines d’applications - Les enjeux de la RO 28/03/2016 5 • La recherche opérationnelle est l’ensemble des méthodes et des techniques adaptées à la résolution de problèmes concrets apparaissant dans des secteurs tels que: - la guerre (origine militaire du terme), - l’industrie, - les services, - autres. Présentation générale 9 10 Discipline des méthodes scientifiques pour aider à mieux décider Présentation générale 28/03/2016 6 11 • Objectif de la « RO » : faire de la recherche scientifique « opérationnelle » – utilisable sur « le terrain des opérations » – à l’aide des outils de l’informatique. • Mettre au point des méthodes, les implémenter au sein d’outils (logiciels) pour trouver des résultats ensuite confrontés à la réalité (et repris jusqu’à satisfaction du demandeur). Présentation générale "Optimiser sous contraintes" • La recherche opérationnelle permet de: - Prévoir, - Expliquer, - et agir. • Les compétences et domaines concernés: - Mathématiques, - Physiques, - Informatique (modélisation). - Connaissances spécifiques par secteur. Les Compétences et domaines concernés 12 28/03/2016 7 • La recherche opérationnelle concerne le monde de l’entreprise: - Production, - Logistique, - Commerce, - RH, - Finance, - … 13 Les Compétences et domaines concernés 14 Les Compétences et domaines concernés Tous les problèmes de décision ou d'optimisation présentent des enjeux industriels et économiques très importants: production, écologie... 28/03/2016 8 - Disposer efficacement les radars pour la défense aérienne:  Comment répartir les moyens humains au niveau des radars ?,  Comment assurer la continuité du service malgré les défaillances? - Implantation optimale d’antennes pour téléphones cellulaire. Exemples de problèmes classiques de RO 15 - Ordonnancement optimal d’une suite des tâches : connaissance des dates de fin à poser, les temps de réglage, … - Réalisation optimale d’un plan de transport. - Calcul d’un itinéraire optimale entre 2 villes, … 16 Exemples de problèmes classiques de RO 28/03/2016 9 17 Ordonnancement de chantier Ordonnancement de chantier Domaines d’applications 18 Ordonnancement d'atelier Ordonnancement d'atelier Ordonnancer les passages sur les machines Domaines d’applications 28/03/2016 10 19 • Suivi de production • Respect des délais • Gain de temps • Respect du client • Meilleure compétitivité • Organisation du travail • résistance aux aléas • … Gestion de la production, des stocks et de la maintenance Domaines d’applications 20 • Optimisation des tournées de véhicules, distribution • Relations fournisseurs / clients • Organisation des centres. Transport, logistique Domaines d’applications 28/03/2016 11 21 • Le ramassage scolaire Transport, logistique Domaines d’applications 22 Calcul d’itinéraires • Précalculs d’itinéraires stockables impossible • Approximation de la longueur des chemins Domaines d’applications 28/03/2016 12 23 • Ressources critiques = blocs opératoires. • Objectifs : satisfaire les patients, minimiser les coûts – Planification de l’utilisation des blocs opératoires – Planification des horaires du personnel (infirmières, etc.) – Gestion de la Supply Chain hospitalière (stérilisation, …) Gestion des ressources hospitalières Domaines d’applications 24 • Objectif: – couvrir un territoire à moindre coût • Déterminer – Le nombre de satellites à lancer – Leurs orbites Constellation de satellites Domaines d’applications 28/03/2016 13 25 Finance Domaines d’applications développement durable Domaines d’applications 26 28/03/2016 14 27 Développement en Afrique • Favoriser une culture scientifique dans la prise de décision • Intervention de la RO à tous les niveaux – Gouvernements – Administrations publiques – Industries – ONG • Domaines abordés : – Gestion des ressources en eau, – industries manufacturières – transport (approvisionnement) – finance – énergie – environnement – urgence humanitaire – … Domaines d’applications Energie Design et planification des centrales Localisation des sites Organisation de la production Politique des prix ….. Domaines d’applications 28 28/03/2016 15 29 Les progrès – avancées théoriques sur les algorithmes de programmation linéaire – avancées théoriques sur les algorithmes de programmation linéaire en nombres entiers – enfin, ordinateurs plus rapides. • 1 an de calcul, en 1980 = quelques secondes en 2008 ! • Progression d’un facteur 1 000 000 000 ! Les enjeux de la RO 30 • Entreprises – Améliorer la compétitivité des entreprises – Préserver des emplois – Accéder à l’innovation • Domaine Politique – Meilleures décisions stratégiques • Environnement – Meilleure gestion des ressources • Santé… rationaliser et optimiser Les enjeux de la RO 28/03/2016 16 31 Apports • Exemples: – gain annuel de $3 millions pour une entreprise américaine de réparation de véhicules (Interfaces vol. 36 (5), oct. 2006, pp. 407-419). – réduction du délai de production de 20% et du retard de livraison de 50% pour l’entreprise Caterpillar’s Building Construction (Interfaces vol. 36 (4), juil. 2006, pp. 283-295). – gains de 5% sur la production et la distribution de gaz carbonique par Air Liquide (mise en œuvre d’un outil de SupplyChain par Eurodecision). – Etc. Les enjeux de la RO 32 Entreprises très concernées par la RO • SNCF • Air France • Gaz de France • EDF • Air Liquide • Orange • Bouygues • CNES • Powernext • … + Eurodécision Artélys Rostudel … Et les PME ?? Les enjeux de la RO 28/03/2016 17 33 • Discipline en pleine révolution – Résolution de problèmes qu’on n’imaginait pas il y a 20 ans ! – Domaines d’application en pleine expansion. Les enjeux de la RO 34 Le Monde Informatique n°1110, 14 avril 2006, page 34, Anne-Marie Rouzeré Les enjeux de la RO 28/03/2016 18 - Définition - Utilité - Vocabulaire: Arrête, chemin et circuit - Représentation graphique - Représentation matricielle - Représentation par table de liste - Coloration des graphes 35 Chapitre 2 : Optimisation par les graphes Plan du cours • Un graphe est un couple (E, Γ) ou E est un ensemble de sommets et Γ une relation linéaire sur E . Les graphes Définition: 36 28/03/2016 19 Les graphes Exemple de représentation graphique: B A C D 37 Exemple de formalisme mathématique: G = (A, B, C,D), ((A,B), (B,A), (D,B), (B,C) 38 Les graphes 28/03/2016 20 Utilité des graphes: 1. Puissance d’expression: CLARTE 2. Modélisation de nombreuses situations:  Réseaux routiers,  Projets, Nomenclatures, … 39 Les graphes Vocabulaires et définitions: Arc Arète Chemin B A V A est l’origine de l’Arc B est l’extrémité de l’Arc V est une valeur attaché à l’Arc Circuit 40 Les graphes 28/03/2016 21 Vocabulaires et définitions: Arc Arète Chemin y x Circuit Γ - Même notion que l’arc mais sans le sens. - (x, y) est une arête si x Γ y ou y Γ x. - Les flèches n’apparaissent plus. 41 Les graphes Vocabulaires et définitions: Arc Arète Chemin y x Circuit Γ - (x0, x1, x2, x3, … xp), ensemble de sommets de G est un chemin si: - x0 Γ x1 , x1 Γ x2, x2 Γ x3, …………………xp-1 Γ xP - xi Γ xj signifie « arête ente xi et xj) 42 Les graphes 28/03/2016 22 Vocabulaires et définitions: Arc Arète Chemin Circuit - Chemin hamiltonien: C’est le Chemin qui passe par tous les points du graphe. 43 Exemple : Chemin ADEBC Les graphes Origine du problème: Arc Arète Chemin Circuit Euler, l'un des plus grands mathématiciens, aimait à faire une promenade dans sa bonne ville de Koenigsberg. Il affectionnait tout particulièrement de parcourir les 7 ponts qui enjambent la rivière. 44 - Chemin eulérien: Les graphes 28/03/2016 23 Origine du problème: Arc Arète Chemin Circuit L'âge venant, il se demanda si sans sacrifier à sa promenade, il pouvait en raccourcir la longueur en ne uploads/Ingenierie_Lourd/ cours-module-recherche-operationnelle-fst-settat-masters-partie-1.pdf