Remerciez-le!

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

Republique Algerienne Democratique Et Populaire Ministère de l’Enseignement Sup

Republique Algerienne Democratique Et Populaire Ministère de l’Enseignement Supérieur et de la Recherche Scientifique Université Aboubakr Belkaïd – Tlemcen – Faculté de TECHNOLOGIE Polycopié du cours " Recherche Opérationnelle " RO Sari Triqui Lamia Maitre de conférence au département GEE Membre du Laboratoire de Productique MELT email:triquilamia@yahoo.fr Septembre 2016 Programme Recherche Opérationnelle RO 2 Programme Recherche Opérationnelle RO Introduction générale................................................................................................................................5 Chapitre 1 : Introduction à l'Optimisation..........................................................................................7 1.1 Quelques exemples de modèles mathématiques................................................................................8 1.2. Définition de la Recherche Opérationnelle RO................................................................................8 1.3 Enjeux de la RO....................................................................................................................................10 1.4 Formulation d’un problème d’optimisation......................................................................................10 1.4.1 Analyse ...............................................................................................................................................10 1.4.2 Modélisation.......................................................................................................................................10 1.4.3 Critère a optimisé ..............................................................................................................................11 1.4.4 Application a l'exemple ....................................................................................................................11 1.5 Solutions d’un problème .....................................................................................................................12 1.6 Exemples................................................................................................................................................12 1.6.1 Problème de production...................................................................................................................12 1.6.2 Réseaux de transport.........................................................................................................................13 1.7. Définitions mathématique..................................................................................................................15 1.7.1 Problème d’optimisation...................................................................................................................15 1.7.2 Critère .................................................................................................................................................15 1.7.3 Contraintes .........................................................................................................................................16 1.7.4 Non-négativité ...................................................................................................................................16 1.8 Complexité des Algorithmes...............................................................................................................16 1.8.1 Notion de Complexité .....................................................................................................................16 1.8.2 L'évaluation temporelle ....................................................................................................................17 Chapitre 2 : Programmation linéaire..................................................................................................19 2.1 Introduction...........................................................................................................................................20 2.2 Forme d’un programme linéaire.........................................................................................................20 2.2.1 Forme générale...................................................................................................................................20 2.2.2 Forme standard ou forme canonique d’un programme linéaire.................................................21 2.3 Résolution de programmes linéaires..................................................................................................22 2.3.1 Résolution graphique.........................................................................................................................22 2.3.2 Méthode de simplexe .......................................................................................................................26 2.3.3 Résolution par les Tableaux de simplexe ......................................................................................29 2.4 Dualité ...................................................................................................................................................33 2.4.1 Qu'est ce que la dualité ? .................................................................................................................34 2.4.2 Qu'elle est l'importance....................................................................................................................34 2.4.3 Comment trouver le dual ? .............................................................................................................34 2.4.4 Conditions d’optimalité primal-dual ..............................................................................................35 2.4.5 Exemple..............................................................................................................................................35 Programme Recherche Opérationnelle RO 3 Chapitre 3 : Problèmes linéaires en variables entières..................................................................38 3.1. Introduction .........................................................................................................................................39 3.2 Résolution des Problèmes Linéaires en Nombre Entières PLNE................................................40 3.2.1 Approche par énumération binaires ..............................................................................................40 3.2.1. La procédure de séparation et d’évaluation progressive (Branch & Bound)...........................42 3.2.2.1 Définitions ......................................................................................................................................42 3.2.2.2 Démarche de résolution.................................................................................................................43 Chapitre 4 : La Programmation Dynamique....................................................................................51 4.1 Définition ..............................................................................................................................................52 4.2 Problème du voyageur..........................................................................................................................52 4.2.1 Modélisation ......................................................................................................................................54 4.2.2 Résolution du problème de voyageur de commerce....................................................................55 4.3 Problème du sac à dos..........................................................................................................................56 4.3.1 Énumération complète des solutions.............................................................................................56 4.3.2 Résolution par la programmation dynamique...............................................................................58 Travaux dirigée.........................................................................................................................................61 Section 1 : Série de Travaux dirigée....................................................................................................61 TD N° 1 : Formulation mathématique....................................................................................................63 TD N° 2 : Programmation Linéaire résolution graphique....................................................................66 TD N° 3 : Algorithme des tableaux de simplexe ..................................................................................68 TD N° 4 : Programmation Linéaire En Nombre Entier......................................................................71 TD N° 5 : Programmation dynamique....................................................................................................73 Section 2 : Solution des Série de Travaux dirigée..........................................................................74 Solution TD N° 1 ......................................................................................................................................76 Solution TD N° 2 ......................................................................................................................................83 Solution TD N° 3........................................................................................................................................86 Solution TD N° 4........................................................................................................................................93 Solution TD N° 5 .......................................................................................................................................96 Conclusion générale et référence bibliographique.......................................................................100 Introduction générale Introduction générale 5 Introduction Générale La recherche opérationnelle est une discipline qui a pour rôle d'assurer la compréhension et la modélisation des systèmes industriels et du secteur public et de les traduire au monde théorique fondé principalement par des mathématiques, des statistiques et de l'informatique. L'employabilité de la recherche opérationnelle est composée de deux phases concaténées dont la première consiste à formuler mathématiquement un problème qui demande une analyse détaillée et suffisamment précise pour recueillir les caractéristiques essentielles du problème posé en plus d'un savoir-faire et d'une certaine expérience. Dans la deuxième phase on procède à la résolution du problème par l'utilisation d’algorithmes rigoureux et bien déterminés. L’objectif de ce cours est double, dans un premier temps nous allons nous concentrer sur la formulation des modèles d’optimisation. Dans cette partie, nous commencerons par la collecte des données et des informations fournies par le problème traité. Ensuite nous présentons les différentes étapes à suivre pour donner une vision mathématique globale avant de passer à la deuxième étape qui concerne la présentation des différentes techniques de résolution de ces problèmes dont le but est de trouver la meilleure solution (appelée solution optimale) pour le problème étudié. Le cours est organisé en cinq sections correspondant à des types différents de modèles d’optimisation. Les quatre premières sections correspondent aux quatre chapitres abordés dans ce cours (décrit dans le paragraphe suivant). La dernière section est réservée aux séries de travaux dirigés (TD) proposées pour ce cours. Le premier chapitre de ce document est consacré à la présentation de la recherche opérationnelle, son utilisation et les domaines qui font appel à cette discipline. Puis nous donnerons quelques rappels d’algèbre linéaire utile et présenterons quelques notions algorithmiques. Le deuxième chapitre est consacré à la formulation et la résolution d'une programmation linéaire, c’est-a-dire les problèmes où les contraintes et la fonction objective sont linéaires. Dans ce chapitre nous apprendrons comment translater et formuler des problèmes sous forme d'un programme linéaire puis nous présenterons, dans la même section les méthodes de résolution d'un programme linéaire à savoir la résolution graphique et la Introduction générale 6 résolution analytique, plus précisément l’algorithme du simplexe qui est la méthode principale pour la résolution de programmes linéaires en nombres réels. Nous conclurons en donnant un petit aperçu sur la dualité et ses principales applications dans les programmes linéaires. Le troisième chapitre traitera des problèmes en nombres entiers. La résolution de ces problèmes fait appel à des techniques et des algorithmes de résolution. Parmi eux nous présenterons dans un premier temps l'approche par énumération, suivie par une présentation de la méthode de branch and bound pour les valeurs entières. On parle de la résolution en nombres entiers lorsque les valeurs des variables doivent être entières, par rapport à la résolution en nombres réels. Le quatrième chapitre est une introduction à la programmation dynamique suivie par la présentation de quelques algorithmes permettant de résoudre efficacement certains types de problèmes d’optimisation Chaque chapitre est suivi d'une série d'exercices proposés aux étudiants sous forme de travail demandé. La dernière partie de ce document concerne les énoncés des différentes séries d'exercices à traiter. Ce cours de RO est enseigné depuis 2012, et s'adresse aux étudiants du tronc commun deuxième année de licence de la filière Génie Industriel, à l'Université de Tlemcen. Bien évidemment, ce cours reste incomplet puisque le domaine de la recherche opérationnelle est très vaste. Cependant de nombreux aspects ne sont pas étudiés faute de temps et de volume horaire. Cela dit, les notions de base choisies dans ce cours permettent aux étudiants d’acquérir des connaissances et un savoir-faire en Recherche Opérationnelle pour traiter divers problèmes. Chapitre 1 Introduction à l'Optimisation 1.1 Quelques exemples de modèles mathématiques................................................................................8 1.2. Définition de la Recherche Opérationnelle RO................................................................................8 1.3 Enjeux de la RO....................................................................................................................................10 1.4 Formulation d’un problème d’optimisation......................................................................................10 1.4.1 Analyse ...............................................................................................................................................10 1.4.2 Modélisation.......................................................................................................................................10 1.4.3 Critère a optimisé ..............................................................................................................................11 1.4.4 Application a l'exemple ....................................................................................................................11 1.5 Solutions d’un problème .....................................................................................................................12 1.6 Exemples................................................................................................................................................12 1.6.1 Problème de production...................................................................................................................12 1.6.2 Réseaux de transport.........................................................................................................................13 1.7. Définitions mathématique..................................................................................................................15 1.7.1 Problème d’optimisation...................................................................................................................15 1.7.2 Critère .................................................................................................................................................15 1.7.3 Contraintes .........................................................................................................................................16 1.7.4 Non-négativité ...................................................................................................................................16 1.8 Complexité des Algorithmes...............................................................................................................16 1.8.1 Notion de Complexité .....................................................................................................................16 1.8.2 L'évaluation temporelle ....................................................................................................................17 Chapitre 1 Introduction à l'Optimisation 8 Chapitre 1 : Introduction à l'Optimisation 1.1 Quelques exemples de modèles mathématiques Exemple 1 Une entreprise fabrique des tables et des chaises à partir de deux matières : le bois et la peinture, sachant que la réalisation d'une table nécessite 3 m de bois et 4 kg de peinture, la réalisation d'une chaise nécessite 2 m de bois et 1 kg de peinture. Les moyens financiers de l'entreprise acceptent un approvisionnement de 100 m de bois et 120 kg de peinture par semaine. Les produits ainsi fabriqués fournissent un bénéfice de 500 DA par table et 300 DA par chaise vendue. Question À partir de la description donnée, plusieurs questions se révèlent : • Quelle quantité de table et quelle quantité de chaise doit produire l'entreprise ? • Quelles sont les ressources disponibles, les limites et les barrières à ne pas dépasser ? • Quel est le but de l'entreprise ? Dans ce cas plusieurs propositions intuitives peuvent avoir lieu par exemple : • 32 tables et 0 chaise avec un bénéfice de 16000 • 20 tables et 20 chaises avec un bénéfice de 16000 • 0 table et 50 chaises avec un bénéfice de 15000 • etc. Nous remarquons qu'il y a une infinité de solutions possibles. Parmi toutes les solutions proposées, comment choisir la meilleure ? Existe-t-il une technique qui pointe directement sur la solution optimale ? Pour répondre à ces questions plusieurs techniques inspirées de la recherche Opérationnelle sont proposées. 1.2. Définition de la Recherche Opérationnelle RO La recherche Opérationnelle est une discipline qui permet de formuler des problèmes par des supports scientifiques, mathématiques et informatiques pour aider à mieux décider. La Recherche Opérationnelle ( R.O.) est avant tout un outil d’aide à la décision. Chapitre 1 Introduction à l'Optimisation 9 Autrement définie, la Recherche Opérationnelle (RO) traduit des énoncés ou des cahiers de charges liés à des problématiques spécifiques sous forme de méthodes et des démarches à base d'équation mathématique, des algorithmes et des outils statistiques. La Recherche Opérationnelle (RO) permet d'assurer la communication entre le milieu industriel (les secteurs extérieurs) et les applications théoriques dans le but de proposer les solutions les mieux adaptées à une situation donnée. La procédure utilisée par la recherche Opérationnelle RO peut être schématisée comme suit : Figure 1.1 Schéma de procédure utilisée par la RO La recherche opérationnelle (RO) est utilisée dans les domaines ou la prise de décision fait appel à la résolution des problèmes d’optimisation telle que uploads/Science et Technologie/ cours-ro-sari-triqui-lamia-final-pdf.pdf