Modules MADRO/MAIAD Projet de la partie Méthodologie
Contents
1. 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 LP de Coin OR xpress glpk gurobi excel Solveur entier cplex xpress glpk gurobi Solveur quadratique cplex xpress Solveur continu solveur pour programme semi d fini Logiciel de simulation Syst me de file d attente qnap Syst me continu Logiciel d aide la d cision Outils interface graphique de planification SAP produit ilog Outils d analyse des probl mes probas API souvent C ou java d algorithmes et de Structures de donn es cutting plane ou pricing Scip Concert technology d ILOG algo de graphes boost lemon 2 4 Les grands probl mes probl matiques de la RO En plus des domaines scientifiques qui sont plut t th oriques la RO se subdivise tradition nellement en probl matiques qui se sont peu peu constitu s en v ritables probl mes On peut ainsi consid rer qu il existe de v ritables communait s scientifiques qui sans avoir pour tant un bagage th orique commun se retrouvent pour parler d applications et parfois mettre en concurrence leurs outils algorithmiques pour r soudre les m mes instances d un m me prob l me On peut ainsi consid rer network design conception de r seaux de t l communication tra2. en demandant explicitement de ne pas toucher ce qui n est pas dans le cahier des charges Il faut insister l dessus par exemple impossibilit de recruter de nouveaux collaborateurs d acheter un v hicule suppl mentaire etc L autre aspect important est la collecte des donn es Il est parfois impossible d obtenir les donn es r elles du probl me alors qu elles conditionnent tout le probl me En effet si la di mension du probl me est petite ou si les donn es sont tellement correll es qu elles simplifient le probl me etc On parle alors des degr s de libert de l nonce qui sont plus ou moins ferm es e Mod liser L tape de mod lisation est primordiale Elle n cessite d avoir pris le recul n cessaire sur le sujet pour choisir l outil de mod lisation UML graphe r seau de p tri PL PLNE SDP ordo Attention on utilise tr s souvent un mod le trop compliqu ce qui revient tenter d utiliser un marteau piqueur pour ouvrir une noix Or l outil utilis m me s il donne un mod le valide peut tre tr s lourd manier temps de calcul On peut m me commettre l erreur d utiliser un outil exponentiel pour r soudre un probl me polynomial Souvent lors de la conception d un mod le on doit utiliser des hypoth ses simplificatrices lin arisation n gliger des param tres etc Il est n cessaire de bien les indiquer dans le cahier des charges e Valider le mod le Il est indi
3. matiques des math maticiens depuis le XVI me si cle Blaise Pascal Euler l utilisation de la RO dans la soci t remonte la seconde guerre mondiale En effet jusque l les probl mes restaient g r s un niveau humain par des entreprises de petites tailles ou par des entreprises g r es selon des principes hi rarchis s qui simplifiaient les probl mes On fait traditionnellement remonter l apparition de la RO l organisation par les alli s du d barquement en Normandie A cette occasion il fallait g rer au mieux l implantation rapide de radars d acheminement de troupes la gestion de leur alimentation des contacts entre unit etc L arm e alli e fit appel des math maticiens et quelques premiers informaticiens pour aider ces d cisions Le mot Op rationnel viendrait donc du terme militaire En tout cas le mot Op rationnel d signe plus s rement l aspect appliqu des d cisions prises il ne suffit pas de donner approximativement o placer des radars il faut en indiquer avec pr cision le lieu et assurer du bon fonctionnement du syst me Les entreprises ont par fois ainsi une division op rationnelle ou conseil strat gique qui appuie les d cisions de la direction Si les premiers calculs num riques des ann es 40 ont t r alis s la main exemple l algorithme du simplexe d roul la main c est bien entendu l arriv e des ordinateurs qui pe
4. donn es ou de gestion des systt mes d information En fait la RO utilise ces diverses sources de donn es pour aider aux d cisions dans l entreprise 1 2 1 Au sein de l entreprises Les grands groupes industriels ont quasiment toujours un d partement RO Il est la plupart du temps int gr au p le R amp D mais il est parfois int gr dans des p les plus d cisionnaires Les entreprises de transport ont videmment un grand besoin de RO pratiquemment toutes leurs d cisions demandent des outils de RO Par exemple la Sncf poss de une culture RO particuli re cr e et accumul e en interne depuis un si cle On retrouve aussi cela dans l arm e l aviation civile etc En revanche certaines grosses entreprises ont jongl avec leur service RO le r duisant ou l augmentant selon les p riodes cela s explique par leurs r alit s strat giques souvent fluctuantes par exemple EDF n a plus cherch conomiser l nergie avec l arriv e du nucl aire m me situation pour France T l com l arriv e de la fibre optique Certains d partement RO en R amp D d entreprise sont parfois de v ritables lieux de recherche acad mique d connect des r alit s de l entreprise On ne peut que constater la fin progres sive de ces d partements au profit d une gestion plus orient e Ainsi les d partements RO deviennent des pourvoyeurs d experts et de concepteur logicieil pour les autres d partements de l entrep
5. etc ou bas sur un outil particulier logiciel de r solution artelys eurodecision dynasys On peut les diviser en deux grandes cat gories les entreprises de d cisions strat giques qui louent les services d un expert pour une d cision pr cise ou une r organisation d un service en g n ral ce sont des personnes exp riment es docteur chercheur les entreprises de conception logicielle RO elle propose de construire un outil informatique sp cifique l entreprise interfac avec les syst mes d information SI de l entreprises En g n ral cet outil demande un suivi sur le long terme qui permet la PME d avoir un contrat renouvel r guli rement La PME r utilise souvent le m me noyau algorithmique d un logiciel l autre 1 2 3 Les entreprises de production logicielle On peut mettre part les entreprises qui proposent des logiciels tr s g n raux pour la RO D une part les entreprises qui ont une comp tence scientifique lev e souvent issus d un chercheur universitaire Il s agit en g n ral d un ou deux rarement plus algorithmes tr s comp titifs c est le cas de Cplex PL PLNE rachet par ILOG puis par IBM de Xpresse rachet par Dash puis par de LISP etc Ces entreprises en g n ral ne vivent pas que de leurs produits logiciels elles sont galement une entreprise de consulting de tr s au niveau scientifique D autre part certains produits l
6. M2 IAD Universit Paris 6 2011 2012 Modules MADRO MAIAD Projet de la partie M thodologie de la Recherche Op rationnelle Document 0 5 Qu est ce que la Recherche Op rationnelle L objectif de document est de donner une vue d ensemble de ce que l on appelle Recherche Op rationnelle dans le monde acad mique et industriel Il ne s agit que d une vision partielle et certainement subjective pour plus de d tails voir des ouvrages plus exhaustifs 1 D finitions et historique On peut d finir la Recherche Op rationnelle RO comme l ensemble des domaines scien tifiques 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 par leur dimension qui peut tre importante mais surtout par leurs structures qui peut tre par exemple combinatoires concurrentielles al atoires etc On peut citer en exemple pertinent la recherche d un itin raire sur une carte l ordonnancement des t ches accomplir en usine la d cision strat gique d investissement d une entreprise sur un march concurrentiel 1 1 Historique rapide Si l on peut consid rer que les probl mes de RO remontent aux jeux math
7. ances de l outil produit Mener sa campagne d exp rimentations demandent d avoir suffisamment d instances de types divers et de tailles croissantes Il faut d gager les performances mais aussi les d fauts et les limitations Il est aussi utile de mettre en vidence les caract ristiques fines des r actions de l outil on peut ainsi d gager des cas faciles o le probl me est parfois polynomial indiquer la r action de l algorithme dans le cas o les donn es sortent du cadre initial on parle de robustesse ou dans le cas o les donn es sont non v rifi es on parle de fiabilit e 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 pas de zy 10 pr voir un manuel d utilisateur des formations etc D autre part il faut souvent pr voir que l outil aura une vie apr s votre expertise Cela con siste pr voir un manuel du concepteur pour permettre de reprendre votre code Cela consiste aussi garder en main les comp tences n cessaires pour faire cette volution collaborateurs form s etc e Plannification des projets de RO Un probl me crucial pour les entreprises de conseils en RO l val
8. nsport 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 3 La pratique de la RO Que ce soit dans le cadre d une grande entreprise ou d une soci t de conseil le sp cialiste de RO d couvre le probl me de RO et doivent y r pondre en temps limit L universitaire d couvre g n ralement des probl mes plus difficiles en ayant davantage de temps pour trouver des r ponses On peut consid rer qu il existe une d marche pour approcher et r soudre un probl me de RO d marche qui d pend fortement du temps disponible mais qui globalement suit le sch ma suivant e D couvrir le probl me En g n ral la d couverte du sujet passe par des discussions orales souvent conradictoires 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 cachier des charges du projet Il est important de cerner le projet dans sa globalit certains probl mes n existent que parce que les gens se refusent changer le cadre du probl me Inversement un probl me peut tre pos
9. ogiciels vedettes contiennent au sein d une interface d di e l entreprise des outils de RO c est le cas des logiciels de SAP ou m me d Excel de Microsoft qui contient un solveur PL 1 3 La communaut scientifique RO On peut affirmer que la communaut RO est principalement n e au sein des d partements R amp D des grands groupes industriels Ces chercheurs sont fr quemment devenus des univer sitaires prenant des postes en informatique mais aussi en s imposant comme une mati re int gr e aux math matiques parfois m me en conomie ou en productique Depuis il existe des quipes de RO dans ces 4 domaines universitaires permettant ainsi une r elle richesse de cultures et d approches En fait beaucoup d universitaires d clarent g n ralement faire partie de la communaut RO et de la communaut plus particuli re en math matique informatique Par exemple nous allons dans ce projet aborder la RO sous langle de l Optimisation Combinatoire La RO s exprime au travers de journaux scientifiques sp cifiques Operations Research The journal of the Operational research society royaume uni 4OR France Belgique Italie Rairo European Journal of OR Mathematics of OR annals of OR Computers and OR Et des journaux appartenant des domaines scientifiques que l on peut inclure dans POR Mathematical Programming Discrete Mathematics Computational Optimization and Algo rithm Et des journaux tr s s
10. p cialis s sur des domaines particuliers de la RO Tranporta tion Networks Journal of Scheduling La RO se r unit au sein de f d ration de la RO soci t philantropique en france ROADEF on en retrouve dans chaque pays italie UK USA Japon Les f d rations europ ennes sont regroup s dans la f d ration de f d ration EURO Idem au niveau international avec IFORS Il existe galement des conf rences sur les m mes th mes que les journaux parfois avec le m me nom ou que les f d rations de RO La conf rence EURO rassemble jusqu plusieurs milliers participants C est l occasion d couter en un m me lieu les chercheurs et les in g nieurs de l industrie des entreprises publiques de l arm e et de l universit Il existe aussi des conf rences de RO sp cialis es sur des th mes pr cis par ex T l com AlgoTel Inoc 2 La RO ensemble de probl mes et d outils On consid re habituellement que la RO est finalement un ensemble de domaine scientifique de probl mes classiques et d outils 2 1 Le cadre de la RO Le cadre des probl mes de RO est assez large il concerne tous les probl mes de d cision et d optimisation Il est plus facile de dire ce qui ne rel ve pas de la RO quand un probl me est de structure simple mais de tr s grande taille cela peut plut t demander un outil de gestion de base de donn es ou de SI quand le probl me n a pas de solutions videntes qu on
11. peut se demander s il existe une solution si la question exige des quations complexes ce sont certainement des math matiques si le probl me demande une simplification de part sa nature physique ou biologique il s agit plut t d utiliser des comp tences dans ces domaines si le probl me semble difficile mais ne concerne que des instances tr s tr s r duites quasiment solvables la main il n y a peut tre pas besoin de d velipper un mod le ou des outils exemple un TSP 3 villes 2 2 Les domaines scientifiques 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 file d attente simultation discr te ordonnancement PLNE approches poly drales programmation quadratique programmation par contraintes th orie des jeux algorithmique Plus g n ral Complexit des probl mes D cidabilit des probl mes 2 3 Les outils
12. rises Ils jouent ainsi le r le de consultants internes connaisseurs du m tier de l entreprise Aussi ils effectuent une r elle veille scientifique permettant l entreprise d avoir connaissance des nouvelles avanc es techniques ou de les acqu rir rapidement Avec la disparition progressive des services de recherche RO en entreprise les chercheurs acad miques en RO se retrouvent parfois loign s des probl mes de ces grosses entreprises en effet le dialogue est rendu plus difficile Les chercheurs en R amp D taient une interface entre les deux mondes industrielles et universitaires Les PME parfois gestionnaires de probl mes complexes issus des nouvelles technologie par exemple n ont pas la dimension suffisante pour poss der leurs propres d partements de RO Elles font recours des consultants ext rieurs Les grosses entreprises le font galement parfois m me en d pit de la pr sence de comp tences RO en leur sein 1 2 2 Les consultants RO Les consultants en RO sont demand s par les entreprises pour r pondre des besoins pr cis ou ponctuels Ils sont parfois universitaires ce qui est tr s r pandu dans le monde anglo saxon mais bien plus rare en France Il existe de plus en plus de petites soci t s de service SSII consulting conseil strat gique qui proposent leurs comp tences aux entreprises Elles sont souvent sp cialis s sur un type de probl mes transport gestion planification
13. rmet ce domaine d avoir une v ritable mise en pratique Les grands groupes industriels souvent confront s la reconstruction d apr s guerre em ploient dans leur service de Rercherche et D veloppement R amp D des chercheurs et des in g nieurs en RO C est le cas en France de la SNCF d EDF GDF du CNET labo historique des t l coms fran ais C est le cas partout dans le monde diverses chelles Avec l envol e industrielle et la g n ralisation de l informatique on peut constater un creux historique de la RO dans les ann es 70 C est en fait cette m me poque que les chercheurs souvent math maticiens inventent de nouveaux proc d s de RO s appuyant sur la puis sance des ordinateurs La RO redevient la mode apr s les premi res crises conomiques et cologiques des ann es 70 80 On peut constater m me une r elle envol e depuis quelques ann es renforc e encore par la crise conomique actuelle mieux g rer pour moins d penser La f d ration europ enne de RO s amuse ainsi d finir la RO comme la science de la bonne gestion Science of better 1 2 La RO en entreprise Pour l entreprise la RO constitue un outil informatique pour aider la gestion de l entreprise on parle alors de science de la gestion Managment science ou Business managment tools La RO se retrouve donc sur une m me ligne d outils que les outils de comptabilit de gestion de Base de
14. spensable de boucler la d marche de mod lisation en valident le mod le les hy poth ses les dimensions et les donn es C est une tape parfois difficile voire impossible si l interlocuteur se refuse signer le cahier des charges ou fait preuve de mauvaise foi etc e Evaluer la complexit et l tat de l art 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 Cette tude se couple avec un tat de l art plus ou moins exhaustif des travaux d j faits sur ce probl me ou des probl mes proches C est l occasion de d couvrir comment a t trait ce probl me etc e Choisir d un outil s il existe Le choix de l outil signifie la fois choisir un algorithme th orique mais aussi rechercher s il existe un outil informatique disponible solveurs architectures objets d algorithmes API d algorithmes o Etude scientifique et algorithmique Sans commentaire e Exp rimentation et retour d exp rience La phase de tests exp rimentaux est souvent n glig e car elle arrive toute la fin de l tude Pour le partenaire elle est pourtant essentielle Elle gagne tre entamm e d s le d but de l tude par exemple en construisant une benchmark compl te et valid e d instance permet tant de bien valuer les perform
15. uation pr alable du temps qui doit tre consacr la d marche globale d analyse et de r solution du probl me Si ce temps est impos l avance tout est conditionn par cela Par exemple certains consultants ne se donnent que quelques jours cela emp he pratiquement tout d veloppement th orique ou pratique d algorithmes et pousse l utilisation syst matique de solveurs 4 Conclusion Sans sectarisme la RO est un domaine transversal entre recherche et ing nieurie entre maths et informatique entre th orie pure et applications On dit qu elle traite les probl mes de la cit 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
Download Pdf Manuals
Related Search