Recherche operationnelle

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^[1].

Le domaine est fortement lié à l'ingénierie des systèmes.

Sommaire 1 Historique 2 Types de problèmes traités 3 Applications pratiques 4 Implantation dans le monde des entreprises 5 Relations avec d'autres disciplines 6 Principales (classes de) méthodes 7 Ouvrages d'introduction 8 Liens externes 9 Notes

Historique

Dès le XVII^e siècle, des mathématiciens comme Blaise Pascal tentent de résoudre des problèmes de décision dans l'incertain avec l'espérance mathématique. D'autres, au XVIII^e et XIX^e siècle, résolvent des problèmes combinatoires. Au début du XX^e 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 radars 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 militaires. 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 ordinateurs. 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 combinatoire, aléatoire ou concurrentiel.

Un problème est dit 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) / (1 x 2 x 3 x 4 x 5) = 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 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 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 projets est une composante très importante de la communauté de recherche opérationnelle. De nombreux travaux traitent de l'ordonnancement et de la gestion de projets, mais aussi de logistique (tournées de véhicule, 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è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 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 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é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 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'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-complets. Dans ce cas, on utilise un algorithme 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 formule de récurrence. Les méthodes de programmation dynamique peuvent alors éventuellement permettre de résoudre le problème avec une complexité polynomiale ou pseudo-polynomiale.

• Processus stochastiques

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 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.

• Heuristiques et métaheuristiques

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. Précis de Recherche Opérationnelle - Méthodes et exercices d'application - 6^e édition. Dunod.

• Dominique de Werra, Thomas M. Liebling et Jean-François Hêche. Recherche opérationnelle pour ingénieurs - Presses polytechniques et universitaires romandes. 2003.

• Eric Jacquet-Lagrèze. Programmation Linéaire - Modélisation et mise en œuvre informatique Collection : P.I.Q. Poche - Editeur : Economica

• J.G. Kemeny, A. Schleifer, J.L. Snell, G.L. Thompson, trad. par M. Didier, Les mathématiques modernes dans la pratique des affaires, Paris, Dunod, 1964.

Liens externes

• (fr) ROADEF : société française de recherche opérationnelle et d'aide à la décision
• (en) INFORMS Resources
• (fr) Suite d'articles traitant de modélisation, optimisation et complexité des algorithmes en rapport direct avec la recherche opérationnelle

Notes

Informatique théorique
Théorie du calcul	Calculabilité Décidabilité et indécidabilité • Ensemble récursif • Problème de l'arrêt • Récursivement énumérable Modèle de calcul Automate fini • Automate cellulaire • Machine de Turing • Thèse de Church Modes de calcul Concurrence • Parallèlisme • Théorie de l'ordonnancement Mesure et échelle de complexité Réduction polynomiale • Problème NP-complet
Logique, syntaxe et sémantique	Logique mathématique Assistant de preuve • Calcul des prédicats • Correspondance de Curry-Howard • Fonction récursive • Lambda-calcul • Théorème d'incomplétude de Gödel • Théorie des types Grammaire formelle et systèmes de réécriture Compilation • Expression rationnelle • Grammaire formelle • Langage rationnel • Théorie des langages Sémantique Sémantique des langages de programmation • Sémantique dénotationnelle • Sémantique axiomatique • Sémantique opérationnelle Spécifier, vérifier et concevoir des programmes Interprétation abstraite • Méthodes formelles • Model checking
Algorithmique, complexité et mathématiques discrètes	Algorithmique Algorithme génétique • Algorithme glouton • Algorithme probabiliste • Complexité algorithmique • Diviser pour régner • Heuristique • Programmation dynamique Problèmes et algorithmes numériques Algorithme du simplexe • Géométrie algorithmique • Algorithme d'Euclide • Test de primalité Problèmes et algorithmes non-numériques Algorithmes de la théorie des graphes • Arbre (informatique) • Liste (informatique) • Table de hachage • Tas (informatique) Théorie des graphes Coloration de graphe • Problèmes de cheminement Recherche opérationnelle Optimisation • Optimisation combinatoire • Théorie de l'ordonnancement Données et codage Codage • Codage de l'information • Compression de données • Cryptage • Cryptanalyse • Cryptographie • Théorie de l'information

• Portail de l’informatique
• Portail de la programmation informatique