Recherche opérationnelle

Patrick Blackett.

Dès le XVII^e siècle, des mathématiciens comme Christiaan Huygens et Blaise Pascal (problème des partis) 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 ou la gestion des convois d'approvisionnement. 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.

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 minimums. 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 bien 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 à 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.

Un diagramme de Gantt, représentation fréquente de l'ordonnancement.

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…) soit opérationnels (notamment l'ordonnancement, la gestion de stock, l'affectation de moyens (humains ou matériels) à des tâches, 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éhicules, 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.

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

Le problème du voyageur de commerce : calculer un plus court circuit qui passe une et une seule fois par toutes les villes (ici 15 villes).

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é des algorithmes 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.

• 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 complexité 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 l'optimalité de gestion des files d'attente.

• Théorie des graphes

Les problèmes d'ordonnancement sont résolus à l'aide des graphes.

• Simulation informatique

La simulation est souvent employée pour résoudre des problèmes de RO, notamment dans le milieu non académique.

• Optimisation linéaire et non linéaire

L'optimisation 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, optimisation linéaire et méthodes arborescentes (voir ci-après) peuvent être combinées.

L'optimisation 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 problèmes d'optimisation non linéaire sont significativement moins efficaces que ceux de l'optimisation linéaire.

• Méthodes de complémentarité linéaire et non 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.