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 A LA L'OPTIMISATION EDJA Kouamé B. Table des matières Objectifs 3

INTRODUCTION A LA L'OPTIMISATION EDJA Kouamé B. Table des matières Objectifs 3 Introduction 4 I - Définition et applications 5 1. Définition et applications ................................................................................................................................ 5 2. Modélisation ................................................................................................................................................... 6 3. Polyèdre .......................................................................................................................................................... 7 4. Optimisation d'un fonctionnelle sur un polyèdre borné ou un convexe borné ................................................ 7 5. Exercices ......................................................................................................................................................... 8 Bibliographie 9 3 Définir les notions de recherche opérationnelle et d'optimisation Connaître le vocabulaire et les outils mathématiques liés aux problèmes d'optimisation. Objectifs 4 Dans ce chapitre, nous présentons les notions de recherche opérationnelle, les problèmes qu'elle permet de résoudre , le principe d'optimisation qui la sous-tend. Nous introduisons aussi le vocabulaire mathématique relatif aux problèmes d'optimisation. Dans ce cours nous utilisons le sigle R.O pour désigner la recherche opérationnelle. Introduction Définition et applications 5 1. Définition et applications Une définition possible de la R.O pourrait être la suivante : il s'agit d'un ensemble de méthodes d'analyse scientifique (maths et info.) des phénomènes d'organisation qui traite de la maximisation d'un profit, d'une performance, d'un rendement ou bien de la d'un coût, d'une dépense. minimisation La R.O. est avant tout un . Le schéma général suivi par ces méthodes est : outil d'aide à la décision Problème concret (de type R.O)→ modélisation → résolution par une méthode de R.O → interprétation des résultats → prise de décision. Beaucoup de problèmes dans divers domaines peuvent être vus comme des problèmes d'optimisation. Nous donnons ci-contre quelques exemples. Détermination d'un plan optimal de fabrication : une entreprise fabrique plusieurs produits, ce qui exige des ressources particulières (matières premières, machines, personnel ...) en quantités limitées. Chaque produit rapporte un certain bénéfice (connu) à l'entreprise. Quels produits l'entreprise doit-elle fabriquer et en quelle quantité pour réaliser le bénéfice total le plus élevé ? Une entreprise dispose de plusieurs dépôts ( ) contenant chacun un certain nombre de containers. Différents magasins ( ) commandent des containers. On connaît le coût de transport de chaque dépôt aux magasins. tâches doivent être affectées a machines (une tâche par machine). Le coût d'exécution de chaque tâche par chacune des machines est connu. Définition et applications I Définition Exemple : Quelques exemples et domaines d'applications de la R.O Un problème de production Un problème de transport. Un problème d'affectation Modélisation 6 Trouver l'affectation qui minimise le coût total. Un voyageur de commerce doit visiter n villes. La distance entre chaque ville est donnée. Trouver le plus court trajet passant par les n villes 2. Modélisation Un ensemble de conditions mathématiques devront être réalisées afin de pouvoir obtenir un maximum ou un minimum sur un ensemble donné. Parmi celles-ci , la condition de convexité de l'ensemble en question. Soit , une partie de , on dit que est convexe si et seulement si : Pour tout , le segment est inclus dans . On dit aussi que est l'enveloppe convexe de ses points. Dans : tout segment ; toute demi droite intérieure des polygones réguliers : carré, rectangle, losange, parallélogramme ; le demi-plan ; le disque ; le demi-disque. Dans :l'adhérence du cube ; de la boule (sphère) ; le demi-espace. 1. Si et sont deux parties convexes de alors est une partie convexe de . 2. Tout espace vectoriel est un convexe. Forme linéaire et convexité Soit f une forme linéaire dans , alors on a : . (demi plan de frontière d'équation : ) resp. (demi plan de frontière d'équation : ) Un problème de voyageur de commerce Définition Exemple Propriétés Exemple : Représentation graphique du convexe D. Polyèdre 7 - - - Une partie convexe de est bornée si et seulement s'il existe une boule de telle que est inclus dans . illustration : 3. Polyèdre On appelle de tout volume de dont les faces sont incluses dans des plans. polyèdre On appelle de l'intersection de 2 faces de . arête On appelle de l'intersection d'au moins arêtes. sommet Lorsque le polyèdre est non dégénéré, il possède un nombre fini de sommets. Tout sommet d'un polyèdre s'appelle aussi point « extrémal ». dans , le cube, le parallélépipède, le tétraèdre (la pyramide) sont des polyèdres. étant un polyèdre de , s'il est convexe, on dit que est un polyèdre convexe. 4. Optimisation d'un fonctionnelle sur un polyèdre borné ou un convexe borné Soit un espace vectoriel réel. On dit qu'une application est une fonctionnelle si et seulement si est linéaire. Soit une fonctionnelle définie sur un convexe borné de . Lorsque admet un maximum en un point de , ce point est toujours un sommet de . Autrement dit F atteint son maximum en un point extrémal de . Pour déterminer ce point , il suffit de construire un algorithme exploratoire. Tout algorithme exploratoire contient les étapes suivantes : 1. Initialisation de l'algorithme Définition Définition N.B : Exemple Fonctionnelle Maximum d'une fonctionnelle Exercices 8 2. Transition d'un sommet à l'autre 3. En tout sommet, tester s‘il rend F maximum 4. Détecter les situations de dégénérescence Nous reviendrons dans le chapitre suivant sur cet algorithme pour la résolution graphique qu'un programme linéaire ! 5. Exercices Une entreprise fabrique deux types de four F1 et F2 a partir de trois facteurs de production : M : heures machine ; O : heures ouvrier ; T : heures technicien. Les combinaisons de facteurs de production pour chaque type de four, le prix de vente V chaque four, le coût unitaire C en francs de chaque facteur de production et les capacités hebdomadaires K de chaque atelier sont données dans le tableau suivant : En désignant par x1 ( resp. x2) le nombre de fours de type 1 (resp. type 2), déterminer combien de fours de chaque type l'entreprise doit fabriquer chaque semaine pour maximiser sa marge Z sur le coût de production. ( A ce stade on vous demande de modéliser le problème) Bibliographie 9 [C. Prins et M. Sevaux] C. Prins et M. Sevaux - Programmation linéaire avec Excel : 55 problèmes d'optimisation modélisés pas à pas et résolus avec Excel, Eyrolles, 2011. [Chvàtal] 1. V. Chvàtal - Linear Programming, W.H.Freeman, New York, 1983. [Chvàtal] 1. V. Chvàtal - Linear Programming, W.H.Freeman, New York, 1983. [Guéret, C. Prins et M. Sevaux] 3 C. Guéret, C. Prins et M. Sevaux - Programmation linéaire : 65 problèmes d'optimisation modélisés et résolus avec Visual Xpress, Eyrolles, 2000. [iutbayonne] https://www.iutbayonne.univ-pau.fr/~grau/2A/RO/cadre3.html [techno-science] https://www.techno-science.net/definition/6353.html [Vanderbei] 2. R. J. Vanderbei - Linear Programming, Foundations and Extensions, Springer-Verlag, 2008. Bibliographie uploads/Management/ pl-cours-papier.pdf