Remerciez-le!

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

Notes de Cours R.O MASTER M1 RECHERCHE OPÉRATIONNELLE P L A N : INTRODUCTION RO

Notes de Cours R.O MASTER M1 RECHERCHE OPÉRATIONNELLE P L A N : INTRODUCTION RO I (OPTIMISATION COMBINATOIRE) 1. PROBLÈMES D’OPTIMISATION COMBINATOIRE 2. MÉTHODES DE RÉSOLUTION DES PROBLÈMES COMBINATOIRES RO II 3. PROGRAMMATION NON LINÉAIRE 4. THÉORIE DES JEUX BIBLIOGRAPHIE - METHODES ET MODELES DE LA RECHERCHE OPERATIONNELLE 3 tomes, A. KAUFMANN Dunod, 1974. - INTRODUCTION TO OPERATIONS RESEARCH ECKER & KUPFERSCHMID, John Wiley, 1988. - INTRODUCTION TO OPERATIONS RESEARCH HILLIER & LIEBERMAN, 7th edition, Holden day Inc., 2001. 1 Notes de Cours R.O MASTER M1 INTRODUCTION Qu'est-ce que la recherche opérationnelle ? La recherche opérationnelle (RO) vise à l'amélioration du fonctionnement des entreprises et des organismes publics par l'application de l'approche scientifique. Reposant sur l'utilisation de méthodes scientifiques, de techniques spécialisées et des ordinateurs, la RO permet d'obtenir une évaluation quantitative des politiques, stratégies et actions possibles dans le cours des opérations d'une organisation ou d'un système. La RO est apparue en Grande-Bretagne durant la Seconde Guerre mondiale, lorsqu'on décida d'employer des méthodes scientifiques pour étudier divers aspects des opérations militaires. Depuis lors, la RO est devenue un élément important du processus de prise de décision dans de nombreux contextes commerciaux, industriels et gouvernementaux, car elle permet d'appréhender de façon systématique la complexité toujours grandissante des problèmes de gestion auxquels sont confrontés tant le secteur privé que public. À la suite des succès obtenus dans le domaine militaire durant la Seconde Guerre mondiale, la RO a été appliquée durant de nombreuses années à des problèmes de nature opérationnelle dans l'industrie, le transport, etc. Depuis une dizaine d'années, le champ d'application de la RO s'est élargi à des domaines comme l'économie, la finance, le marketing et la planification d'entreprise. Plus récemment, la RO a été utilisée pour la gestion des systèmes de santé et d'éducation, pour la résolution de problèmes environnementaux et dans d'autres domaines d'intérêt public. Parmi les sujets d'application récents de la RO, on peut mentionner :  les études logistiques (Forces armées),  la sécurité ferroviaire,  la conception d'emballages,  la gestion prévisionnelle du personnel,  le transport aérien,  les opérations forestières,  l'optimisation du carburant nucléaire,  l'affectation des ressources dans un hôpital,  l'étude des réseaux de commutation,  la planification de la production. Une carrière en recherche opérationnelle Pour réussir, le chercheur opérationnel doit faire preuve de grandes habilités analytiques, d'un esprit ouvert et d'un intérêt marqué pour la résolution de problèmes pratiques. À l'heure actuelle, on retrouve des personnes possédant une formation en RO à l'intérieur d'équipes spécialisées en RO œuvrant pour certains dans divers secteurs d'organismes privés ou publics. Les méthodes de la RO sont aussi appliquées par des économistes, des ingénieurs, des scientifiques, des administrateurs et des cadres supérieurs dans la résolution de problèmes de gestion et de politique d'entreprise. Depuis l'apparition de la RO, les décideurs et les gestionnaires y ont recours très fréquemment. Ses applications sont en pleine expansion alors que l'envergure et la complexité des problèmes soumis aux praticiens de la RO n'ont pas cessé de s'accroître. En conséquence, le développement de techniques et méthodes nouvelles pour faire face à ces nouveaux problèmes a provoqué chez les gestionnaires de tous les secteurs des affaires, de l'industrie et du gouvernement une prise de conscience sans cesse grandissante de la nécessité de telles techniques et méthodes ainsi qu'une plus grande confiance en ce que la RO peut faire pour la gestion et la prise de décisions. Il y a dans les secteurs public et privé une demande croissante et un besoin certain des services de la RO. 2 Notes de Cours R.O MASTER M1 RECHERCHE OPERATIONNELLE PARTIE I 3 Notes de Cours R.O MASTER M1 CHAPITRE I PROBLÈMES D’OPTIMISATION COMBINATOIRE (POC) I. DEFINITION D’UN POC Découvrir le plus court chemin pour se rendre à un endroit précis, concevoir un circuit électronique, placer des antennes pour diffuser des chaînes TV, ou des relais pour les réseaux GSM, reconstruire le code génétique des êtres humains,… cette liste peut paraître hétérogène et provenant de domaines différents, mais elle contient des problèmes qui ont tous une structure combinatoire. En effet, chacun d’entre eux revient à choisir la meilleure combinaison parmi un nombre souvent exponentielle de possibilités. Les problèmes d’optimisation combinatoire se répartissent en 2 catégories : ceux résolus "optimalement" par des algorithmes efficaces (de complexité polynomiale), et ceux dont la résolution optimale peut prendre un temps exponentiel sur les grands cas. La théorie de la complexité permet d’évaluer et de classer les divers algorithmes disponibles pour un problème, et permet de mieux comprendre pourquoi certains problèmes ne disposent toujours pas d’algorithmes efficaces. Définition : Un POC peut être décrit en général sous la forme suivante : Min F(x) x  X Où F désigne une fonction à valeurs réelles (fonction objectif) évaluant les solutions désignées par x. Il s’agit de minimiser la fonction F sur l’ensemble de toutes les solutions réalisables noté X. Les solutions x  X peuvent être des objets mathématiques de nature très diverse ; souvent x représentera un vecteur d’un espace à n dimensions et F désignera une fonction de cet espace dans IR. L’ensemble des solutions réalisables X est généralement déterminé par des contraintes souvent exprimées comme des inégalités. Remarque : Suivant la nature de l’ensemble X et de la fonction F, le POC peut être facile (résoluble en temps polynomial) ou difficile. Par exemple, si X est un polyèdre convexe  IR net F une fonction linéaire, on retrouve un PL résoluble efficacement par le simplexe ou même par d’autres algorithmes polynomiaux. Par contre si X Z n, on retrouve des programmes en nombre entiers qui sont des problèmes difficiles ; aucun algorithme polynomial n’a été trouvé à l’heure actuelle pour les résoudre. II. NOTION DE THEORIE DE LA COMPLEXITE II.1. Complexité des algorithmes La complexité d’un algorithme A est une fonction CA(N) donnant le nombre d’instructions exécutées par A dans le pire des cas pour une donnée de taille N. La complexité est basée généralement sur le pire cas afin de borner le temps d’exécution de l’algorithme. De plus la connaissance du pire cas est critique pour les applications temps réel (contrôle aérien, robots, systèmes d’armes, etc.). Néanmoins, la complexité pire cas peut fausser notre vision sur l’efficacité d’un algorithme. Le simplexe en est l’exemple type. Malgré sa complexité pire cas exponentielle, cet algorithme est efficace pour la résolution de la plupart des PLs. On distingue en général les algorithmes polynomiaux (complexité de l’ordre d’un polynôme), et les autres, dits exponentiels. Des exemples de complexités polynomiales sont log n, n0.5, n log n, n2, … Une complexité exponentielle peut être une vraie exponentielle au sens mathématique (en , 2n) mais aussi des fonctions comme nlogn (sous exponentielle), la fonction factorielle n! et nn. Un bon algorithme est polynomial. Ce critère d’efficacité est confirmé par la pratique : - Une exponentielle dépasse tout polynôme pour n assez grand. Par exemple, 1.1n croit d’abord lentement, mais finit par dépasser n100. En plus il est rare de trouver des complexités polynomiales d’ordre supérieur à n5 en pratique. - L’ensemble des polynômes a d’intéressantes propriétés de fermeture. L’addition, la multiplication et la composition de polynômes donnent des polynômes. On peut ainsi constituer de grands algorithmes polynomiaux à partir de plus petits. 4 Notes de Cours R.O MASTER M1 L’esprit humain a du mal à appréhender ce qu’est une croissance exponentielle. Le tableau suivant illustre ces croissances, par rapport à des croissances polynomiales. Les temps de calculs supposent 0.1 nanoseconde par instruction (équivalent à un processeur cadencé à plus de 6 GHZ). Les cases non remplies ont des durées supérieures à 1000 milliards d’années (supérieur à l’âge estimé de l’univers !). Taille Complexité 20 50 100 200 500 1000 107 n log2 n 0.09 s 0.3 s 0.7 s 1.5 s 4.5 s 10 s 106 n² 0.04 s 0.25 s 1 s 4 s 25 s 100 s 105 n3 0.08 s 1.25 s 10 s 80 s 21 min 2.7 h n logn 0.04 ms 0.4 s 32 min 1.2 ans 5. 107 ans -- 2n 100 s 31 h -- -- -- -- n! 7.7 ans -- -- -- -- -- Ces calculs montrent qu’il est faux de croire qu’un ordinateur peut résoudre tous les problèmes combinatoires. « L’explosion combinatoire » est telle que l’augmentation de la puissance des ordinateurs ne change pas fondamentalement la situation. En particulier, il faut se méfier des méthodes énumératives, consistant à examiner tous les cas possibles, puisqu’elles conduisent à des algorithmes exponentiels. II.2. Complexité des POC a) POC faciles (polynomiaux)  Chemin de coût minimal (min-cost path, shortest path) Donnée : G(X,U,C) un graphe orienté valué et deux sommets s et t de X. But : Trouver un chemin de coût minimal entre s et t Ce problème apparaît dans les transports, mais également en sous problème dans de nombreux problèmes de graphes. Si G et C sont quelconques, on dispose de l’algorithme de Bellman en O(NM). L’algorithme de Dijkstra, en O(N²), est applicable quand les coûts de C sont positifs. uploads/Management/ rochap-1.pdf