Recherche opérationnelle
| Sommaire |
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. 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 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. « 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, notamment, à 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 :
Problèmes combinatoires
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 / (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). Heureusement, des techniques comme la méthode branch and bound permettent de trouver une solution qui reste souvent acceptable par une énumération partielle.
Problèmes aléatoires
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.
Problèmes concurrentiels
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.
Relations avec d'autres disciplines
La recherche opérationnelle se situe au carrefour de différentes sciences.
Économie
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.
Pétrole
Cet outil est couramment utilisé dans l'industrie pétrolière, principalement dans l'établissement des plans de production à long terme, à moyen terme, annuel, trimestriel et mensuel.
Les résultats permettent aux décideurs d'avoir un guide pour faire les meilleurs choix dans les investissements, dans l'approvisionnement des bruts, dans l'utilisation des unités de raffinage, dans les canaux de distribution les plus rentables.
Voir aussi l'article de fond : Programmation linéaire.
Voir aussi l'article de fond : Pétrole.
Voir aussi l'article de fond : Raffinage du pétrole.
Voir aussi l'article de fond : Plans d'approvisionnement, de production et de distribution du pétrole.
Informatique
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. En Théorie de la complexité, on dit que ces problèmes appartiennent à la classe des problèmes NP. Pour eux, le chercheur opérationnel fera le plus souvent appel à des heuristiques, qui sont des solutions approchées dont le calcul est possible dans un temps acceptable.
L'informatique peut également constituer un domaine d'application. Exemples :
- choix de la localisation de serveurs et du nombre de serveurs à mettre en place pour obtenir un temps de réponse raisonnable,
- choix de la capacité de stockage, de la puissance de calcul et du débit du réseau
- 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.)
Mathématiques
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, des contrôleurs de gestion et, moins souvent, des économistes.
Les problèmes que la R.O. peut aider à résoudre sont souvent 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. Malgré son importance intrinsèque, la R.O. est peu utilisée, moins à cause du manque de formation des décideurs que du manque de pertinence de l'outil.
- Une prise en compte limitée des facteurs
- Pour les questions stratégiques, la réponse « pure et parfaite » d'une solution mathématique est rarement applicable de facto. Même si la recherche opérationnelle intègre beaucoup de facteurs, elle ne prend en compte que ce qui est modélisable : le coût, la rentabilité, la distance, la durée, la cadence, par exemple. Elle ne peut traiter les éléments de choix 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 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.
- 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.
Face à ces difficultés, le décideur d'entreprise fera souvent le choix d'une solution heuristique. Si malgré tout la R.O. apparaît pertinente, sa mise en œuvre sera externalisée.
Principales (classes de) méthodes
Théorie des graphes
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 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), les problèmes d'ordonnancement de tâche, les problèmes de planning ou encore les problèmes d'optimisation de flux (algorithme de Ford-Fulkerson).
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 (voir exemple de problème aléatoire).
ex (simpliste) : la formule de Wilson
Programmation linéaire et non linéaire
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 :
2x + 5y - z <= 15
-3x + 15y + 4z <= 58
x >= 0, y >= 0 et z >= 0
La programmation non linéaire est similaire, mais la fonction à maximiser (minimiser) et les contraintes ne sont plus du premier degré.
Théorie des jeux
La théorie des jeux, bien connue des économistes, aide à résoudre les problèmes concurrentiels.
Méta-heuristiques
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étaheuristique est une méthode, ou plus précisément, un canevas 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é.
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.
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
Liens externes
- ROADEF: Société française de recherche opérationnelle et d'aide à la décision
- INFORMS Resources (en anglais)