Remerciez-le!

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

Doctorant Sous la supervision de Abdourahmane GUEYE Pr Salimata GUEYE DIAGNE 77

Doctorant Sous la supervision de Abdourahmane GUEYE Pr Salimata GUEYE DIAGNE 77 509 95 64 gueyeabou17@gmail.com Chef de l’équipe de Recherche en Mathématiques de la Décision / Recherche Opérationnelle Recherche Opérationnelle Optimisation appliquée en ingénierie Optimisation appliquée en ingénierie civil 1 A. GUEYE gueyeabou17@gmail.com Introduction à la Recherche Opérationnelle 1 – Définitions et Historique 2 - Modélisation de PSC Programmation Linéaire 1 – Modélisation et Formulation de PL 2 – Résolution Graphique 3 – Méthode du Simplexe Initiation à la Théorie des Graphes 1 – Vocabulaire et Exemples 2 – Représentation 3 – Méthode de Résolution par la TG Optimisation des flux 1 – Formulation 2 – Recherche de flot maximal 3 – Algorithme de Ford-Fulkerson Problème d’Ordonnancement 1 – Méthode d’Ordonnancement 2 – Diagrammes de Gantt – Méthodes PMP et PERT 3 – Réduction de la durée d’un projet Programme du cours Optimisation appliquée en ingénierie civil 2 Abdourahmane GUEYE Chapitre 1 Chapitre 2 Chapitre 3 Chapitre 4 Chapitre 5 Objectifs Modéliser et résoudre des problèmes d’optimisation, Ordonnancer pour minimiser de la durée totale de réalisation des travaux d’un projet . Donner un plan de distribution de charge dans un réseau . Analyse et Interprétation des résultats d’une simulation. Pré-requis Notion d’Algèbre Linéaire - Résolution de Système d’inéquation à 2 variables – Relation Binaire. Volume Horaire 40 h Cours 28h - Travaux Dirigés 12 h Mode d’évaluation 1 Test de connaissance par chapitre 1 Devoir surveillé 1 Examen Documentation  Livre Blanc de la RO par la ROADEF.  M. Minoux Graphe et Hypergraphe (DJVIEWER).  Claudio Benedetti Gestion Opérationnelle Présentation du cours 2 1 3 4 5 Optimisation appliquée en ingénierie civil 3 Abdourahmane GUEYE Doctorant Sous la supervision du Abdourahmane GUEYE Pr Salimata GUEYE DIAGNE gueyeabou17@gmail.com 77 509 95 64 Chef de l’équipe de Recherche en Mathématiques de la Décision / Recherche Opérationnelle Doctorant Sous la supervision du Abdourahmane GUEYE Pr Salimata GUEYE DIAGNE gueyeabou17@gmail.com 77 509 95 64 Chef de l’équipe de Recherche en Mathématiques de la Décision / Recherche Opérationnelle Chapitre 1 Introduction à la Recherche Opérationnelle Optimisation appliquée en ingénierie civil 1 Abdourahmane GUEYE Introduction 1 - Définition 2 – Historique 3 – Grands Problèmes - Success Stories Problèmes de Satisfaction de Contraintes 1 – Caractéristique et Typologie des Contraintes 2 – Formulation d’un CSP 3 – Solution d’un CSP CSP avancée 1 – CSP sur-contraint - MaxCSP - VCSP 2 – CSP sous-contraint CSOP Travaux Dirigées 1 – Problème de coloriage 2 – SEND + MORE = MONEY 3 – Partage de Machine 4 – Problème d’Einstein Plan 2 1 3 4 Optimisation appliquée en ingénierie civil 2 Abdourahmane GUEYE 1 – Définitions Qu’est ce que la RO Recherche Opérationnelle « RO » traduction littérale de « Operationel Research » Terme employer pour la première fois par Sir Robert Watson Watt pour désigner : « Recherche scientifique du rendement optimal d’une opération militaire » La RO est la discipline des méthodes scientifique ( Maths – Info – Gestion ) pour résoudre de maniéré efficiente des problèmes opérationnels et organiques. Porté d’une étude en Recherche Opérationnelle Porté Stratégique : problèmes d’organisation (réseaux de distribution), de structuration (choix d’équipements, dimensionnement de flottes) la conduite des opérations au sens économique (choix d’implantations, décisions d’investissement) ... Porté Opérationnelle : gestion de flux et fonctionnement des réseaux de distribution, ordonnancement de tâches dans les chantiers, mise en œuvre d’outils de production, plans de maintenance ... Porté Technique : Elaboration et l’évaluation d’éléments ( optimisation de composants ) ... Introduction Optimisation appliquée en ingénierie civil 3 Abdourahmane GUEYE Le mot « opérations » un terme uniquement militaire s’est imposé de lui-même, et cela, en raison de l’analogie entre les applications : dans les milieux militaires et civils, la recherche opérationnelle est utilisée dans le même but et emploie des méthodes et des techniques identiques caractérisées par les mêmes mots-clés : Modélisation : Ecriture d’un problème sous une formulation mathématique, Optimisation : Résolution efficiente d’un problème. 2 – Historique À partir de 1940, les Anglo-Saxons demandaient en permanence à des groupes composés de scientifiques et de militaires de préparer certaines grandes décisions. Face à la menace d’invasion de la Grande Bretagne 7 000 scientifiques et ingénieurs volontaires s’associèrent sous l’égide de la Royal Society. Grâce à des chefs militaires d’une largeur de vue exceptionnelle et aux succès initiaux de la RO dans la bataille d’Angleterre, l’idée de « faire des mathématiques pour les états-majors » s’instaura définitivement selon les mots de Sir Watson-Watt, Introduction Optimisation appliquée en ingénierie civil 4 Abdourahmane GUEYE En 1936 un groupe de jeunes scientifiques dirigé par Sir Robert Watson Watt fut chargé de recherches sur l’efficacité du radar. Etudier comment la technologie radar peut d’intercepter les avions ennemis. Préconisa la création d’un système de commande au sol des interceptions qui en 1941. améliora l’implantation des radars et permit de doubler la probabilité d’interception. En août 1940 le Pr Blackett, ancien officier de Marine ( prix Nobel de physique en 1948 ) se vue confié par le général Pile, commandant en chef de la DCA anglaise une série de recherches sur la défense aérienne, en liaison avec l’aviation. Introduction Optimisation appliquée en ingénierie civil 5 Abdourahmane GUEYE Sir Watson-Watt Premier directeur d’un centre de recherche sur les radars dans le manoir de Bawdsey (Suffolk). Le Pr Blackett constitua le « Blackett Circus » avec 3 physiologues, 5 physiciens et mathématiciens, un astronome, un topographe et un officier. Pr Blackett, ancien officier de Marine ( prix Nobel de physique en 1948 ) Après étude statistique des tirs, Blackett diminua le tir de DCA sur éléments fixes de 20000 à 4000 du fait que les avions ennemis ne changeaient de cap pendant le tir qu’une fois sur quatre. Etudiant la corrélation entre les erreurs de pointage radar et la nature du terrain, il détermina la taille idéale des treillis métalliques constituant ces systèmes de détection. « Army Operational Research Group » disposa de huit sections pour les problèmes de défense aérienne, radar, transmissions, infanterie, artillerie, appui aérien, armement, mines, obstacles et armes spéciales. Introduction Optimisation appliquée en ingénierie civil 6 Abdourahmane GUEYE 3 – Les grands classe de problèmes Les problèmes d’affectation Maximiser la rentabilité par une répartir des ressources limitées entre des tâches à réaliser. Les problèmes d’ordonnancement Etablir l’ordre d’exécution des tâches afin de produire le maximum de produits et de réduire le temps total de production. Les problèmes de file d’attente Déterminer le nombre minimum de guichets qu’il convient de mettre en place afin de limiter au maximum l’attente des clients. Introduction Optimisation appliquée en ingénierie civil 7 Abdourahmane GUEYE 3 – Les grands classe de problèmes Le problème du Sac à dos Déterminer quels sont, parmi plusieurs éléments, ceux qui respectent les dimensions offertes par une capacité fixe. Les éléments ont des propriétés différentes du point de vue de l’utilisation de la capacité et de leur valeur. Exemple – le personnel d’une entreprise est réparti idéalement entre certaines tâches parmi un ensemble. La sélection des tâches à accomplir doit tenir compte de leur rentabilité mais aussi du nombre de personnes à y consacrer ; – la surface utile d’une usine est occupée par des équipes spécialisées. Quelles équipes faut-il choisir sachant qu’elles n’utilisent pas toutes la même surface et qu’elles n’ont pas toutes la même utilité ? – la surface d’un jardin doit être répartie entre plusieurs types de plantation. Quelle surface faut il consacrer à la culture de chaque légume sachant qu’ils n’ont pas le même rendement énergétique, ni le même prix à la vente. Introduction Optimisation appliquée en ingénierie civil 8 Abdourahmane GUEYE 3 – Les grands classe de problèmes Les problèmes de tournées Comment visiter un ensemble de lieux si on ne peut passer qu’une seule fois sur chaque lieux avant de revenir à son point de départ ? Trajet Minimal : Problèmes NP-complets très difficiles à résoudre Voyageur de commerce : (n-1)!/2 chemins possibles ! Si un ordinateur est capable d'évaluer 1 milliard de chemins / s. 16 villes : 653.109 chemins = 653s = 0,18h. 17 villes : 10461.109 chemins = 10461s = 2,9h. 18 villes : 177843.109 chemins = 177843 s = 49 h = 2,05 j 25 villes : 3,10.1023 = 3,10.1014s = 86 milliards d'heures = 9,8 millions d'années !!! Introduction Optimisation appliquée en ingénierie civil 9 Abdourahmane GUEYE 3 – Les grands classe de problèmes Les problèmes de flux Considérons un réseau routier urbain. Il relie différentes parties de la ville : les quartiers d’habitation, les zones industrielles, les zones commerciales, etc. Il s’ensuit que la circulation routière privilégie certains axes quand d’autres sont moins empruntés. Il faut alors adapter la largeur des axes afin d’éviter les embouteillages, tout en restant dans des limites acceptables pour le contribuable. Il s’agit d’un problème de flux qui peut se mettre sous la forme d’un graphe (le réseau urbain) dont chaque arc a des capacités propres (nombre de véhicule maximum par heure, coût de construction et d’entretien au kilomètre). Introduction Optimisation appliquée en ingénierie civil 10 Abdourahmane GUEYE uploads/Science et Technologie/ recherche-operationnelle-cours-et-td.pdf