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 Chapitre 1: Programmation linéaire Résolution Graphique Simplexe A

Introduction Chapitre 1: Programmation linéaire Résolution Graphique Simplexe Analyse de la sensibilité Ziyad Bahou : Ziyad.bahou@hotmail.fr Dualité Prob. du transport et d’affectation Recherche opérationnelle Z. Bahou, EMI 2022/2023 Introduction Chapitre 1: Programmation linéaire Résolution Graphique Simplexe Analyse de la sensibilité Ziyad Bahou : Ziyad.bahou@hotmail.fr Dualité Prob. du transport et d’affectation Plan du cours: Introduction générale à la recherche opérationnelle.  Programmation linéaire. ‐ Algorithme du simplexe. ‐ Dualité. ‐ Problème du transport. ‐ Problème d’affectation. Optimisation dans les réseaux. ‐ Notions élémentaires de la théorie des graphes. ‐ Problème de l’arbre de poids minimal. ‐ Problèmes de cheminements optimaux dans un réseau. ‐ Problème central d’ordonnancement. (MPM, PERT, CPM) Problèmes de flot. Introduction Chapitre 1: Programmation linéaire Résolution Graphique Simplexe Analyse de la sensibilité Ziyad Bahou : Ziyad.bahou@hotmail.fr Dualité Prob. du transport et d’affectation Introduction L’optimisation • L'optimisation ou la recherche de l’optimum est un souci permanent au sain des organisations. Plus les entreprises grandissent, plus les problèmes de gestion se multiplient et se compliquent : la gestion de production, la gestion du stock, la gestion des flux financiers, la gestion des réseaux ou de circulation des biens et de services... • La résolution de ces problèmes nécessite des efforts tant au niveau de la recherche de la solution optimale qu’au niveau de la modélisation . ►Le souci N° 1 au sain des firmes est souvent du comment maximiser le profit?, minimiser les coûts? Introduction Chapitre 1: Programmation linéaire Résolution Graphique Simplexe Analyse de la sensibilité Ziyad Bahou : Ziyad.bahou@hotmail.fr Dualité Prob. du transport et d’affectation Recherche Opérationnelle • « Outil mathématique de modélisation et d’optimisation. Il permet de trouver une solution optimale ou bien une solution qui s’approche le plus possible de l’optimum » • On peut définir la Recherche Opérationnelle (RO) comme l'ensemble des domaines scientifiques, des outils et des problèmes touchant aux questions d'ordre décisionnel (dit aussi stratégique) ou d'optimisation de systèmes complexes. L'expression systèmes complexes est à prendre ici au sens le plus littéral du terme, c'est-à-dire difficile à comprendre pour un individu sans l'aide d'un modèle ou d'un ordinateur. • Les problèmes sont rendus complexes dans la RO par : leur dimension qui peut être importante, mais surtout par leur structure qui peut-être par exemple combinatoire, stochastique etc. Introduction Introduction Chapitre 1: Programmation linéaire Résolution Graphique Simplexe Analyse de la sensibilité Ziyad Bahou : Ziyad.bahou@hotmail.fr Dualité Prob. du transport et d’affectation On peut citer en exemple pertinent : ‐ la recherche d'un itinéraire sur une carte « Comment aller le plus vite ou avec le moindre coût de Rabat à Berlin, en voiture? ». ‐ l'ordonnancement des tâches à accomplir en usine « Comment ordonnancer les taches d’un projet en fonction de la main d’ œuvre, tout en minimisant sa durée? ». ‐ la décision stratégique d'investissement d'une entreprise sur un marché concurrentiel « Comment investir ses 10000 DH d’économie afin de maximiser le profit obtenu après deux ans? » . Recherche Opérationnelle Introduction Introduction Chapitre 1: Programmation linéaire Résolution Graphique Simplexe Analyse de la sensibilité Ziyad Bahou : Ziyad.bahou@hotmail.fr Dualité Prob. du transport et d’affectation La RO en entreprise ‐ Pour l'entreprise, la RO constitue un outil informatique pour aider à la gestion de l'entreprise. ‐ La RO se retrouve donc sur une même ligne d'outils que les outils de comptabilité, de gestion de Base de données ou de gestion des systèmes d'information. ‐ La RO utilise ces diverses sources de données pour aider aux décisions dans l’entreprise. ‐ Les grands groupes industriels ont quasiment toujours un département RO. Il est la plupart du temps intégré au pôle R&D mais il est parfois intégré dans des pôles plus décisionnaires, comme les conseils de décisions stratégiques. - network design (conception de réseaux de télécommunication) - transport - localisation (plant location) - micro-électronique (VLSI design) - bio-informatique, applications médicales - productique (job-shop, flow-shop,...) - ordonnancement (domaine à la limite problématique/problème...) - optimisation financière - chaîne logistique (supply chain) et création de lots (lot- sizing) - optimisation « durable » - et de nouvelles problématiques se créent régulièrement. Les grandes problématiques de la RO Introduction Introduction Chapitre 1: Programmation linéaire Résolution Graphique Simplexe Analyse de la sensibilité Ziyad Bahou : Ziyad.bahou@hotmail.fr Dualité Prob. du transport et d’affectation Les domaines de la RO Il est difficile de classer ou de lister exhaustivement tous les domaines de la RO. D'autant que ces domaines ont tous une réalité par eux-mêmes et on peut se demander quelle partie de ces domaines est dans la RO ou pas.  Aspect continu : ‐ Optimisation continue. ‐ PL. ‐ Théorie des jeux continues. ‐ Optimisation stochastique. ‐ Programmation semi-définie. ‐ Simulation continue.  Aspect discret ou combinatoire : ‐ Théorie des graphes ‐ Algorithmique, algorithmique des graphes ‐ Programmation dynamique ‐ Optimisation combinatoire exacte ou à garanti d'approximation ‐ Optimisation combinatoire heuristique ‐ Processus markovien, la file d'attente,... ‐ Simulation discrète ‐ Ordonnancement ‐ PLNE, approches polyédrales ‐ Programmation quadratique ‐ Programmation par contraintes ‐ Théorie des jeux algorithmique Introduction Introduction Chapitre 1: Programmation linéaire Résolution Graphique Simplexe Analyse de la sensibilité Ziyad Bahou : Ziyad.bahou@hotmail.fr Dualité Prob. du transport et d’affectation Les outils de la RO Il existe de nombreux outils logiciels disponibles commercialement ou libres pour résoudre des problèmes précis ou des problèmes plus généraux.  Logiciels d'optimisation (interactif ou modeleur) ‐ Solveur linéaire (cplex, xpress, glpk, gurobi, excel...) ‐ Solveur entier (cplex, xpress, glpk, gurobi,...) ‐ Solveur quadratique (cplex, xpress)  Logiciel de simulation ‐ Système de file d'attente (qnap, simula,...) ‐ Système continu  Logiciel d'aide à la décision : ‐ Outils à interface graphique de planification (SAP, produit ilog)... ‐ Outils d'analyse des problèmes (probas)...  Des API (souvent C++ ou java) d'algorithmes et de Structures de données ‐ Des frameworks permettant d'utiliser les solveurs dans un processus algorithmiques plus complexes. Par exemple les méthodes de coupes ou de générations de colonnes : Scip, Concert technology (d'ILOG),... Introduction Introduction Chapitre 1: Programmation linéaire Résolution Graphique Simplexe Analyse de la sensibilité Ziyad Bahou : Ziyad.bahou@hotmail.fr Dualité Prob. du transport et d’affectation • Découvrir le problème : En général, la découverte du sujet passe par des discussions orales, souvent contradictoires avec les différents intervenants. Il s'agit de cerner la/les questions au cours de réunion et de discussion autour d'un texte qui devient vite un cahier des charges du projet. • Modéliser : est un aspect très important et primordial. Les problèmes que l’on traite émanant de situations concrètes. Il s’agit alors de définir la situation en termes mathématiques et dans un souci d’efficacité de schématiser (modéliser) le problème. La pratique de la RO Introduction • Evaluer la complexité: Etape évidemment nécessaire, il faut étudier la complexité du problème obtenu après modélisation. C'est le moment de se rendre compte si le problème traité est difficile ou pas, si un outil classique est utilisable etc. • Choisir un outil : Le choix de l'outil signifie à la fois choisir un algorithme théorique mais aussi rechercher existe un outil informatique disponible : solveurs, architectures objets d'algorithmes, API d'algorithmes,... • Expérimentation et retour d'expérience • Intégration et vie logicielle : Etape nécessaire pour l'entreprise, il faut intégrer l'outil dans le cadre des outils de l'entreprise. L'interfaçage avec les SI de l'entreprise n'est pas une chose simple, ni d'ailleurs l'obligation fréquente de permette une certaine ergonomie de l'outil qui ne s'adresse pas à un public initié à la RO ou au math : prévoir un manuel d'utilisateur, des formations etc. Introduction Chapitre 1: Programmation linéaire Résolution Graphique Simplexe Analyse de la sensibilité Ziyad Bahou : Ziyad.bahou@hotmail.fr Dualité Prob. du transport et d’affectation Conclusion La RO est un domaine transversal entre recherche et ingénierie, entre maths et informatique, entre théorie pure et applications. On dit qu'elle traite les problèmes de la société, ce qui la montre utile à tous : en effet, il est toujours intéressant d'avoir un système mieux géré, plus économe sur les ressources, plus écologique,... tout en respectant les contraintes naturelles du droit du travail et le respect des conditions de travail. Introduction Introduction Chapitre 1: Programmation linéaire Résolution Graphique Simplexe Analyse de la sensibilité Ziyad Bahou : Ziyad.bahou@hotmail.fr Dualité Prob. du transport et d’affectation Introduction à la programmation linéaire Un outil qui permet de : • Modéliser • Résoudre toute une classe de problèmes d’optimisation. La programmation linéaire constitue l’origine de l’optimisation mathématique moderne. Son étude a été menée par George Bernard Dantzig à partir de 1947. L’algorithme du simplexe « le plus connu des méthodes de résolution », que nous présentons dans le prochain chapitre, est considéré comme un des dix algorithmes les plus importants du vingtième siècle. C’est la première fois qu’un problème avec contraintes d’inégalité a été résolu. Introduction Introduction Chapitre 1: Programmation linéaire Résolution Graphique Simplexe Analyse de la sensibilité Ziyad Bahou : Ziyad.bahou@hotmail.fr Dualité Prob. du transport et d’affectation • La programmation linéaire est un outil très puissant de la recherche opérationnelle. C’est un outil générique qui peut résoudre un grand nombre de problèmes. En effet, une fois un problème modélisé sous la forme d’´équations linéaires, des uploads/Management/ ro-chap-1.pdf