| |
|
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.
= Historique =
Dès le XVIIe 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 XVIIIe siècle et XIXe siècle, résolvent des problèmes combinatoires.
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'Etat 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. "Opérationnelle" vient donc du fait que la première application d'un groupe de travail organisé dans cette discipline avait trait aux opérations militaires. Le nom est resté par la suite, même si le domaine militaire n'est plus le principal champ d'application de cette pratique.
Après la guerre, les techniques se sont considérablement développées, grâce, notemment, à l'explosion des capacités de calcul des ordinateurs. Les domaines d'applications se sont également multipliés.
= Champs d'application =
La recherche opérationnelle peut aider le décideur lorsque celui-ci est confronté à un problème appartenant à un des types suivants :
Un problème est dit combinatoire lorsqu'il comprend un grand nombre de solutions admissibles parmis lesquels 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 manière à ce 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 * 29 * 28 * 27 * 26 = 17.100.720 (!). Et même si un problème de cette taille pourrait ê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.
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 agissments 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.
= Relations avec d'autres disciplines =
La recherche opérationnelle se situe au carrefour de différentes sciences.
Outre le fait que les principales applications pratiques se situent dans ce domaine, l'analyse économique est souvent nécessaire pour définir l'objectif à atteindre ou pour identifier les contraintes d'un problème.
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 : il a en effet été prouvé que certains problèmes, parmi lesquels certains liés à la recherche opérationnelle, ne peuvent être résolus de manière optimale par un ordinateur dans un temps raisonnable et cela, même si l'on considère des ordinateurs un milliard de fois plus puissants que ceux d'aujourd'hui. Pour ces problèmes, le chercheur opérationnel fera le plus souvent appel à des techniques empruntées à l'intelligence artificielle, permettant de trouver en un temps acceptable des solutions proches de l'optimum.
L'informatique peut également constituer un domaine d'application, en matière de localisation de serveurs, de nombre de serveurs à mettre en place pour obtenir un temps de réponse raisonnable...
Beaucoup de méthodes utilisées par la recherche opérationnelle sont issues de théories mathématiques diverses. En ce sens, la recherche opérationnelle est une branche des mathématiques appliquées.
Au délà des méthodes, les mathématiques, en particulier les statistiques, contribuent à poser efficacement les termes d'un problème.
= 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 consultance ou, le plus souvent, au département de recherche opérationnelle d'une université.
Notons que les 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 et, moins souvent, des économistes.
= Principales (classes de) méthodes =
La théorie des graphes sert de suport à la résolution d'un vaste échantillon de problèmes, certains issus de l'algorithmique classique, tels que la recherche du plus court chemin entre deux endroits, le problème du voyageur de commerce (dans lesquels on cherche le chemin le plus court passant par n points) ou encore les problèmes d'ordonnancement des tâches (problèmes de planning).
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 (voir exemple de problème aléatoire).
La programmation linéaire consiste à maximiser (ou minimiser) une fonction linéaire sous des contraintes linéaires (ces contraintes sont le plus souvent exprimées par des inégalités). "Linéaire" s'entend ici par "du premier degré". Elle intervient dans la résolution de problèmes combinatoires.
Exemple :
Max (3x + 7y - 2z)
ayant :
La programmation non linéaire est similaire, mais la fonction à maximiser (minimiser) et les contraintes ne sont plus du premier degré.
La théorie des jeux, bien connue des économistes, aide à résoudre les problèmes concurrentiels.
Une heuristique est une méthode pour résoudre de manière approchée un type de problème particulier, dont la solution optimale ne peut être obtenue (car, par exemple, son obtention nécessiterait d'un ordinateur un calcul de plusieurs milliers d'années).
Une méta-heuristique est une méthode, ou plus précisément, un cannevas de méthodes, pour résoudre de manière approchée tous les problèmes dont la solution optimale ne peut être obtenue. La méthode ne dépend donc plus du type de problème auquel on est confronté.
Les méta-heuristiques sont souvent empruntées à l'intelligence artificielle, comme les algorithmes génétiques, le recuit simulé ou la recherche tabou.
= Ouvrages d'introduction =
Robert Faure, Bernard Lemaire et Christophe¨Picouleau. Précis de Recherche Opérationnelle - Méthodes et exercices d'application - 5e édition. Dunod.
= Liens externes =
ROADEF: Société française de recherche opérationnelle et d'aide à la décision
INFORMS Resources (en anglais)
Problèmes combinatoires
Problème aléatoires
Problèmes concurrentiels
Economie
Informatique
Mathématiques
Théorie des graphes
Processus stochastiques
Programmation linéaire et non linéaire
2x + 5y - z <= 15
-3x + 15y + 4z <= 58
x >= 0, y >= 0 et z >= 0 Théorie des jeux
Méta-heuristiques