Recherche opérationnelle
30864
30039852
2008-05-27T08:53:12Z
192.54.193.57
/* Applications pratiques */
{{à illustrer}}
La '''recherche opérationnelle''' (aussi appelée '''[[aide à la décision]]''') peut être définie comme l'ensemble des méthodes et techniques rationnelles d'analyse et de synthèse des phénomènes d'[[organisation]] utilisables pour élaborer de meilleures décisions.
''La recherche opérationnelle (RO) propose des modèles conceptuels pour analyser des situations complexes et permet aux décideurs de faire les choix les plus efficaces.'' <ref>Présentation de la RO par JC Billaut : http://www.roadef.org/content/road/pdf/ROetGI.pdf</ref>
Le domaine est fortement lié à l'[[ingénierie des systèmes]].
== Historique ==
{{Loupe|Histoire de la recherche opérationnelle en France}}
Dès le {{XVIIe siècle}}, des [[mathématicien]]s comme [[Blaise Pascal]] tentent de résoudre des problèmes de décision dans l'incertain avec l'[[moyenne|espérance mathématique]]. D'autres, au {{XVIIIe s}} et {{XIXe siècle}}, résolvent des problèmes combinatoires. Au début du {{XXe siècle}}, l'étude de la [[gestion de stock]] peut être considérée comme étant à l'origine de la recherche opérationnelle moderne avec la [[formule du lot économique]] (dite formule de Wilson) proposée par Harris en [[1913]].
Mais ce n'est qu'avec la [[Seconde Guerre mondiale]] que la pratique va s'organiser pour la première fois et acquérir son nom. En [[1940]], [[Patrick Blackett]] est appelé par l'[[état-major]] anglais à diriger la première équipe de recherche opérationnelle, pour résoudre certains problèmes tels que l'implantation optimale de [[radar]]s de surveillance. Le qualificatif « opérationnelle » vient du fait que la première application d'un groupe de travail organisé dans cette discipline avait trait aux opérations [[militaire]]s. La dénomination est restée par la suite, même si le domaine [[militaire]] n'est plus le principal [[champ d'application]] de cette discipline.
Après la guerre, les techniques se sont considérablement développées, grâce, notamment, à l'explosion des capacités de calcul des [[ordinateur]]s. Les domaines d'application se sont également multipliés.
== Types de problèmes traités ==
La recherche opérationnelle peut aider le décideur lorsque celui-ci est confronté à un problème [[optimisation combinatoire|combinatoire]], [[aléatoire]] ou [[concurrence|concurrentiel]].
Un problème est dit [[optimisation combinatoire|combinatoire]] lorsqu'il comprend un grand nombre de solutions admissibles parmi lesquelles on cherche une solution optimale ou proche de l'optimum. Exemple typique : déterminer où installer 5 centres de distribution parmi 30 sites d'implantation possibles, de sorte que les coûts de transport entre ces centres et les clients soient minimum. Ce problème ne peut être résolu par une simple énumération des solutions possibles par l'esprit humain, puisqu'il en existe 30 x 29 x 28 x 27 x 26 / (5x4x3x2) = 142 506 (!). Et même si un problème de cette taille peut être résolu par énumération par un ordinateur, les décideurs sont régulièrement confrontés à des problèmes infiniment plus complexes, où le nombre de solutions acceptables se compte en milliards de milliards (voir [[explosion combinatoire]]).
Un problème est dit [[aléatoire]] s'il consiste à trouver une solution optimale face à un problème qui se pose en termes incertains. Exemple typique : connaissant la [[loi de probabilité|distribution aléatoire]] du nombre de personnes entrant dans une administration communale en une minute et la distribution aléatoire de la durée de traitement du cas d'une personne, déterminer le nombre minimum de guichets à ouvrir pour qu'une personne ait moins de 5% de chances de devoir attendre plus de 15 minutes.
Un problème est dit [[concurrence|concurrentiel]] s'il consiste à trouver une solution optimale face à un problème dont les termes dépendent de l'interrelation entre ses propres agissements et ceux d'autres décideurs. Exemple typique : fixer une politique de [[prix]] de vente, sachant que les résultats d'une telle [[politique]] dépendent de la politique que les concurrents adopteront.
== Applications pratiques ==
Les problèmes que la R.O. peut aider à résoudre sont soit stratégiques (on peut citer le choix d'investir ou pas, le choix d'une implantation, le dimensionnement d'une flotte de véhicules ou d'un parc immobilier…) ou opérationnelles (notamment l'[[ordonnancement]], la gestion de stock, les prévisions de ventes…).
La [[gestion de projet]]s est une composante très importante de la communauté de recherche opérationnelle. De nombreux travaux traitent de l'[[théorie de l'ordonnancement|ordonnancement]] et de la [[gestion de projet]]s, mais aussi de [[logistique]] (tournées de véhicule, [[problème de bin packing|conditionnement]]…), de [[planification]], et de problèmes d'[[emploi du temps]].
Dans le cadre de l'[[industrie manufacturière]], la recherche opérationnelle permet notamment de trouver des plans de productions ([[ordonnancement]] de production), de disposer au mieux les machines dans un atelier, de diminuer le gaspillage des [[matière première|matières premières]] (problèmes de découpe) ou de l'[[énergie]] ou bien encore d'optimiser le conditionnement et la livraison des produits intermédiaires ou finis.
Dans le domaine de la [[finance]], les problèmes d'[[investissement]] sont des problèmes classiques de recherche opérationnelle. Ils consistent en général à maximiser le profit (ou l'[[espérance mathématique|espérance]] de profit) obtenu à partir d'un montant donné en combinant au mieux les différentes possibilités offertes à l'investisseur.
La recherche opérationnelle a aussi des applications dans le domaine de l'[[énergie]]. Elle est couramment utilisée dans l'[[industrie pétrolière]], principalement dans l'établissement des plans de production, l'approvisionnement des bruts, l'utilisation des unités de raffinage, et le choix des canaux de distribution les plus rentables. De même, les opérateurs du [[Marché de l'électricité]] font largement appel à la recherche opérationnelle tant pour des problèmes stratégiques (par exemple des investissements sur le réseau) que pour des questions plus opérationnelles (stabilité du réseau, prévisions…). Pour plus de détails, voir [[Plans d'approvisionnement, de production et de distribution du pétrole]]
Les applications dans le domaine de l'[[informatique]] sont très nombreuses elles aussi. On peut citer, entre autres, le choix de la localisation et du nombre de [[serveur informatique|serveurs]] à mettre en place, de la capacité de stockage, de la puissance de calcul et du débit du [[réseau]], le choix d'une [[architecture informatique]] (application centralisée / distribuée, traitements en temps réel ou en différé, réseau maillé ou en étoile, etc.), et l'[[ordonnancement dans les systèmes d'exploitation]].
== Implantation dans le monde des entreprises ==
Très peu d'entreprises emploient des chercheurs opérationnels pour aider le [[décideur]] à résoudre ses problèmes. Lorsque de tels problèmes se posent, ils sont généralement soumis à un gros cabinet de conseil ou au département de recherche opérationnelle d'une université (bien que la tendance actuelle soit à l'externalisation de ces compétences universitaires ''via'' de petites sociétés privées appelées [[spin-off]], répondant mieux aux besoins du monde industriel). Certains problèmes simples peuvent être résolus au sein même de l'entreprise, la plupart des universités ayant intégré des cours d'introduction à la recherche opérationnelle dans les programmes des ingénieurs, des mathématiciens, des informaticiens, des contrôleurs de gestion et, moins souvent, des économistes.
Malgré son importance intrinsèque, la R.O. est encore peu utilisée dans le monde industriel, soit à cause du manque d'(in)formation des décideurs, soit par le manque de pertinence de l'outil ou sa difficulté de mise en œuvre. Les principales craintes émises par le décideurs quant à l'application de modèles R.O. dans son entreprise sont :
*Une prise en compte limitée des facteurs
::Pour les questions stratégiques, la réponse « pure et parfaite » d'une solution mathématique semble rarement applicable ''de facto''. Même si la recherche opérationnelle intègre beaucoup de facteurs, si certains aspects sont relativement faciles à [[Modèle mathématique|modéliser]] au sens mathématique du terme (le coût, la rentabilité, la distance, la durée, la cadence, par exemple), d'autres éléments sont en revanche plus difficiles à modéliser : contraintes légales, volonté commerciale de faire barrage à un concurrent, importance des relations avec les élus, climat social, etc. Le poids de ces éléments dans la décision est pourtant important, parfois déterminant.
*Un investissement important
::L'outil mathématique lui-même exige un niveau élevé de connaissances mathématiques, une bonne aptitude à modéliser les problèmes et décrire les facteurs ; ces contraintes sont consommatrices de temps et d'argent (que ce soit par développement interne, qui consomme des ressources; ou par développement externe, qui consomme de l'argent). Il est alors nécessaire de trouver un équilibre entre l'investissement nécessaire et les retombées prévues.
*Pour des événements peu fréquents
::L'entreprise ne bénéficie pas de l'effet d'expérience : d'une fois sur l'autre, le problème concerne un service différent, ou les responsables ont changé entre deux études. Il est donc difficile d'entretenir les compétences R.O. à l'intérieur de l'entreprise.
Le décideur devra prendre ces différents aspects en compte lorsqu'il décidera ou non de mettre en œuvre des modèles de recherche opérationnelle dans son entreprise.
== Relations avec d'autres disciplines ==
La recherche opérationnelle se situe au carrefour de différentes sciences et technologies. Par exemple, l'analyse [[économique]] est souvent nécessaire pour définir l'objectif à atteindre ou pour identifier les contraintes d'un problème.
Elle est aussi liée à l'[[ingénierie des systèmes]]. Par rapport à celle-ci, le champ d'application de la recherche opérationnelle est historiquement plus axé sur les événements incertains et l'industrie, et ses méthodes plus particulièrement mathématiques.
La recherche opérationnelle utilise de nombreuses méthodes issues de théories [[mathématiques]] diverses. En ce sens, une partie de la recherche opérationnelle peut être considérée comme une branche des [[mathématiques appliquées]]. Les mathématiques, notamment les [[statistiques]], contribuent aussi à poser efficacement les termes d'un problème.
La [[théorie des graphes]] sert de support à la résolution d'un vaste échantillon de problèmes, notamment certains issus de l'[[algorithmique]] classique, tels que les [[Algorithme de Dijkstra|problèmes de plus court chemin]], le [[problème du voyageur de commerce]], les problèmes d'ordonnancement de tâches, les problèmes de planning ou encore les problèmes d'[[algorithme de Ford-Fulkerson|optimisation de flux]].
Les progrès de l'[[informatique]] sont intimement liés à l'accroissement des applications de la recherche opérationnelle. Une puissance de calcul importante est nécessaire à la résolution de problèmes de grande taille. Cette puissance est cependant loin de constituer une panacée : la [[théorie de la complexité]] nous apprend que certains problèmes ne peuvent pas être résolus de manière optimale dans un temps raisonnable, même si l'on considère des ordinateurs un milliard de fois plus puissants que ceux d'aujourd'hui.
Plusieurs méthodes de résolution de problèmes sont issues de l'[[intelligence artificielle]]. Alors que l'approche de l'intelligence artificielle est de proposer des méthodes de résolution génériques, la recherche opérationnelle utilise ces méthodes en les spécialisant pour les rendre plus efficaces à résoudre des classes plus restreintes de problèmes.
On peut aussi citer la [[théorie des jeux]], bien connue des économistes, qui aide à résoudre les problèmes concurrentiels.
== Principales (classes de) méthodes ==
* [[Algorithmes]] polynomiaux
:: Certains problèmes de recherche opérationnelle ne sont pas [[NP-complet]]s. Dans ce cas, on utilise un algorithme [[théorie de la complexité|polynomial]] pour le résoudre, si le polynôme est de degré raisonnable.
* [[Programmation dynamique]]
:: Certains problèmes ont de ''bonnes'' caractéristiques qui permettent de les résoudre à l'aide d'une [[relation de récurrence|formule de récurrence]]. Les méthodes de [[programmation dynamique]] peuvent alors éventuellement permettre de résoudre le problème avec une complexité [[théorie de la complexité|polynomiale]] ou [[théorie de la complexité|pseudo-polynomial]]e.
* Processus [[stochastique]]s
:: Les [[processus stochastiques]] concernent tous les problèmes aléatoires, en particulier des problèmes de fiabilité (de systèmes, de composants électroniques…) et des phénomènes d'attente.
* [[Simulation informatique]]
:: La simulation est souvent employée pour résoudre des problèmes de RO, notamment dans le milieu non académique.
* Programmation linéaire et non linéaire
:: La [[programmation linéaire]] est très souvent utilisée pour résoudre des problèmes combinatoires. Elle permet de résoudre très efficacement les problèmes dans lesquels les variables sont continues. Lorsqu'il y a des variables discrètes, programmation linéaire et méthodes arborescentes (voir ci-après) peuvent être combinées.
:: La [[programmation non-linéaire]] peut aussi être utilisée. La possibilité d'utiliser des contraintes ou des fonctions objectifs non linéaires offre une puissance de modélisation très importante mais les algorithmes de résolution des programmes non linéaires sont significativement moins efficaces que ceux de la programmation linéaire.
* Méthodes arborescentes
:: Les méthodes de type [[Algorithme A*|A*]] ou [[branch and bound]] sont couramment utilisées pour trouver la solution exacte d'un problème de recherche opérationnelle. Pour une résolution efficace, un soin particulier est apporté au calcul de '''bornes''' supérieures ou inférieures pour la valeur de la solution.
:: La [[programmation par contraintes]] permet de mettre en œuvre rapidement et efficacement de telles méthodes de recherche arborescente. Plusieurs bibliothèques (logiciels) d'optimisation commerciales ou non reposent sur cette approche (ILOG Solver, Chip, Mozart/Oz, FaCiLe). De nombreux logiciels d'optimisation de problèmes réels utilisent ainsi cette technologie.
* [[Heuristique]]s et [[métaheuristique]]s
:: Lorsque la solution optimale ne peut être obtenue en un temps raisonnable, on a souvent recours à des méthodes approchées de type [[heuristique]] ou [[métaheuristique]].
== Ouvrages d'introduction ==
* Robert Faure, Bernard Lemaire et Christophe Picouleau. [http://www.eyrolles.com/Sciences/Livre/9782100046911/Precis_de_recherche_operationnelle.php?xd=dd6bfcf0d5872c13f3a2d13c05283048 ''Précis de Recherche Opérationnelle''] - Méthodes et exercices d'application - 5{{e}} édition. Dunod.
* Dominique de Werra, Thomas M. Liebling et Jean-François Hêche. [http://www.eyrolles.com/Sciences/Livre/9782880744465/livre-recherche-operationnelle-pour-ingenieurs-i.php''Recherche opérationnelle pour ingénieurs''] - Presses polytechniques et universitaires romandes. 2003.
* Eric Jacquet-Lagrèze. [http://www.fnac.com/Shelf/article.asp?PRID=921761&Mn=2&Ra=-1&To=0&Nu=2&Fr=3 ''Programmation Linéaire - Modélisation et mise en œuvre informatique''] Collection : P.I.Q. Poche - Editeur : Economica
== Liens externes ==
* {{fr}} [http://www.roadef.org ROADEF] : société française de recherche opérationnelle et d'aide à la décision
* {{fr}} [http://www.eurodecision.com/ Site d'EURODECISION]
* {{en}} [http://www.informs.org/Resources/ INFORMS Resources]
* {{fr}} [http://www.wearegeeks.info/-MOCA- Suite d'articles traitant de modélisation, optimisation et complexité des algorithmes] en rapport direct avec la recherche opérationnelle
== Notes ==
<references/>
[[Catégorie:Recherche opérationnelle]]
[[af:Operasionele navorsing]]
[[ar:بحوث عمليات]]
[[ca:Investigació operativa]]
[[da:Operationsanalyse]]
[[de:Operations Research]]
[[en:Operations research]]
[[es:Investigación de Operaciones]]
[[fa:تحقیق در عملیات]]
[[he:חקר ביצועים]]
[[it:Ricerca operativa]]
[[ja:オペレーションズ・リサーチ]]
[[ko:운용 과학]]
[[nl:Operationeel onderzoek]]
[[pl:Badania operacyjne]]
[[pt:Investigação operacional]]
[[ru:Исследование операций]]
[[sk:Operačná analýza]]
[[sr:Операциона истраживања]]
[[sv:Operationsanalys]]
[[th:การบริหารการจัดการ]]
[[tr:Yöneylem araştırması]]
[[uk:Дослідження операцій]]
[[zh:運籌學]]