Recherchez sur tout Techno-Science.net
       
Techno-Science.net : Suivez l'actualité des sciences et des technologies, découvrez, commentez
Catégories
Techniques
Sciences
Encore plus...
Techno-Science.net
Partenaires
Organismes
 CEA
 ESA
Sites Web
Photo Mystérieuse

Que représente
cette image ?
 A | B | C | D | E | F | G | H | I | J | K | L | M | N | O | P | Q | R | S | T | U | V | W | X | Y | Z | +
Recherche opérationnelle

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 (L'ingénierie désigne l'ensemble des fonctions allant de la conception et des études à la responsabilité de la construction et au contrôle des équipements d'une installation technique ou industrielle.) des systèmes.

Historique

Article de fond: Histoire de la recherche (La recherche scientifique désigne en premier lieu l’ensemble des actions entreprises en vue de produire et de développer les connaissances scientifiques. Par extension métonymique, la recherche...) opérationnelle en France

Dès le XVIIe siècle, des mathématiciens comme Blaise Pascal (Blaise Pascal (19 juin 1623, Clermont (Auvergne) - 19 août 1662, Paris) est un mathématicien et physicien, philosophe, moraliste et théologien français.) tentent de résoudre des problèmes de décision dans l'incertain avec l'espérance mathématique (L'espérance mathématique est une valeur numérique permettant de mesurer le degré d'équité d'un jeu de hasard. Elle est égale à la somme des gains (et des pertes)...). D'autres, au XVIIIe 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 ( Seconde est le féminin de l'adjectif second, qui vient immédiatement après le premier ou qui s'ajoute à quelque chose de nature identique. La seconde est une unité de mesure du temps. La seconde d'arc est une mesure d'angle plan. La...) 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 (Le mot implantation peut avoir plusieurs significations :) 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 (Un champ correspond à une notion d'espace défini:) d'application de cette discipline.

Après la guerre, les techniques se sont considérablement développées, grâce, notamment, à l'explosion (Une explosion est la transformation rapide d'une matière en une autre matière ayant un volume plus grand, généralement sous forme de gaz. Plus cette transformation s'effectue rapidement, plus la matière...) 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 (En mathématiques, la combinatoire, appelée aussi analyse combinatoire, étudie les configurations de collections finies d'objets ou les combinaisons d'ensembles finis, et les dénombrements.), aléatoire ou concurrentiel.

Un problème est dit combinatoire lorsqu'il comprend un grand nombre (La notion de nombre en linguistique est traitée à l’article « Nombre grammatical ».) 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 (Le transport est le fait de porter quelque chose, ou quelqu'un, d'un lieu à un autre, le plus souvent en utilisant des véhicules et des voies de...) 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 (Un ordinateur est une machine dotée d'une unité de traitement lui permettant d'exécuter des programmes enregistrés. C'est un ensemble de...), 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 ( Forme première d'un document : Droit : une minute est l'original d'un acte. Cartographie géologique ; la minute de terrain est la carte originale, au crayon, levée sur le terrain....) 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 (Un Parc est un terrain naturel enclos,[1] formé de bois ou de prairies, dans lequel ont été tracées des allées et chemins destinés à la chasse, à la promenade ou à l’agrément. Il se distingue du Jardin public par le...) 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 (La logistique est l'activité qui a pour objet de gérer les flux physiques d'une organisation, mettant ainsi à disposition des ressources correspondant aux besoins, aux conditions...) (tournées de véhicule (Un véhicule est un engin mobile, qui permet de déplacer des personnes ou des charges d'un point à un autre.), conditionnement…), de planification (La planification est la programmation d'actions et d'opérations à mener), et de problèmes d'emploi du temps (Le temps est un concept développé par l'être humain pour appréhender le changement dans le monde.).

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 (Dans le sens commun l'énergie désigne tout ce qui permet d'effectuer un travail, fabriquer de la chaleur, de la lumière, de produire un mouvement.) 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é (L’électricité est un phénomène physique dû aux différentes charges électriques de la matière, se manifestant par une énergie. L'électricité désigne également la branche de la physique qui...) 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 (Un réseau informatique est un ensemble d'équipements reliés entre eux pour échanger des informations. Par analogie avec un filet (un réseau est un « petit rets », c'est-à-dire un petit filet), on appelle nœud (node)...), prévisions…). Pour plus de détails, voir Plans d'approvisionnement, de production et de distribution du pétrole (Le pétrole est une roche liquide carbonée, ou huile minérale. L'exploitation de cette énergie fossile est l’un des piliers de l’économie...)

Les applications dans le domaine de l'informatique (L´informatique - contraction d´information et automatique - est le domaine d'activité scientifique, technique et industriel en rapport avec le traitement automatique de l'information par des machines telles que les...) 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 (Le mot puissance est employé dans plusieurs domaines avec une signification particulière :) de calcul et du débit (Un débit permet de mesurer le flux d'une quantité relative à une unité de temps au travers d'une surface quelconque.) du réseau, le choix d'une architecture (L’architecture peut se définir comme l’art de bâtir des édifices.) informatique (application centralisée / distribuée, traitements en temps réel ou en différé, réseau maillé (La topologie Mesh (terme anglais signifiant maille ou filet), qualifie les réseaux (filaires ou non) dont tous les hôtes sont connectés de proche en proche sans hiérarchie centrale, formant ainsi une structure...) ou en étoile (Une étoile est un objet céleste émettant de la lumière de façon autonome, semblable à une énorme boule de plasma comme le Soleil, qui est l'étoile la plus proche de la Terre.), etc.), et l'ordonnancement dans les systèmes d'exploitation.

Implantation dans le monde (Le mot monde peut désigner :) 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é (Une université est un établissement d'enseignement supérieur dont l'objectif est la production du savoir (recherche), sa conservation et sa transmission...) (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). Notons que certains problèmes simples peuvent être résolus au sein (Le sein (du latin sinus, « courbure, sinuosité, pli ») ou la poitrine dans son ensemble, constitue la région ventrale supérieure du...) 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 (Un outil est un objet finalisé utilisé par un être vivant dans le but d'augmenter son efficacité naturelle dans l'action. Cette augmentation se traduit par la simplification des actions entreprises, par une plus grande...) 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 (Les mathématiques constituent un domaine de connaissances abstraites construites à l'aide de raisonnements logiques sur des concepts tels que les nombres, les figures, les structures et les...) 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 (SENS (Strategies for Engineered Negligible Senescence) est un projet scientifique qui a pour but l'extension radicale de l'espérance de vie humaine. Par une évolution...) 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 barrage est un ouvrage d'art construit en travers d'un cours d'eau et destiné à réguler l'écoulement naturel de l'eau pour...) à un concurrent, importance des relations avec les élus, climat (Le climat correspond à la distribution statistique des conditions atmosphériques dans une région donnée pendant une période de temps donnée. Il se distingue de la météorologie...) social, etc. Le poids (Le poids est la force de pesanteur, d'origine gravitationnelle et inertielle, exercée par la Terre sur un corps massique en raison uniquement du voisinage de la Terre. Elle est égale à l'opposé de la résultante des...) 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 (L’argent ou argent métal est un élément chimique de symbole Ag — du latin Argentum — et de numéro atomique 47.) (que ce soit par développement interne (En France, ce nom désigne un médecin, un pharmacien ou un chirurgien-dentiste, à la fois en activité et en formation à l'hôpital ou en cabinet pendant une durée variable selon le...), 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 (La statistique est à la fois une science formelle, une méthode et une technique. Elle comprend la collecte, l'analyse, l'interprétation de données ainsi que la présentation...), contribuent aussi à poser efficacement les termes d'un problème.

La théorie des graphes (Le terme de graphe désigne en mathématiques une opération d'application. Il possède deux acceptions :) sert de support à la résolution d'un vaste échantillon (De manière générale, un échantillon est une petite quantité d'une matière, d'information, ou d'une solution. Le mot est utilisé dans différents domaines :) de problèmes, notamment certains issus de l'algorithmique (L'algorithmique est l’ensemble des règles et des techniques qui sont impliquées dans la définition et la conception d'algorithmes, c'est à dire de processus...) 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 (Le mot flux (du latin fluxus, écoulement) désigne en général un ensemble d'éléments (informations / données, énergie, matière, ...) évoluant dans un sens commun. Plus...).

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é (La théorie de la complexité s'intéresse à l'étude formelle de la difficulté des problèmes en informatique. Elle se distingue de la théorie de la calculabilité qui s'attache à savoir si un...) 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 (Un milliard (1 000 000 000) est l'entier naturel qui suit neuf cent quatre-vingt-dix-neuf millions neuf cent quatre-vingt-dix-neuf...) de fois plus puissants que ceux d'aujourd'hui.

Plusieurs méthodes de résolution de problèmes sont issues de l'intelligence artificielle (L'intelligence artificielle ou informatique cognitive est la « recherche de moyens susceptibles de doter les systèmes informatiques de capacités intellectuelles comparables à celles des êtres...). 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 (La théorie des jeux constitue une approche mathématique de problèmes de stratégie tels qu’on en trouve en recherche opérationnelle et en économie. Elle...), 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 (En mathématiques, un polynôme est la combinaison linéaire des puissances d'une variable, habituellement notée X. Ces objets sont largement utilisés en pratique, ne serait-ce que parce qu'ils donnent...) est de degré (Le mot degré a plusieurs significations, il est notamment employé dans les domaines suivants :) raisonnable.
  • Programmation dynamique (Inventée par le professeur Richard Bellman, la programmation dynamique permet de résoudre au moyen d'un ordinateur tout problème d'optimisation dont la fonction objectif se décrit comme la somme de fonctions monotones non-décroissantes...)
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 (La programmation dans le domaine informatique est l'ensemble des activités qui permettent l'écriture des programmes informatiques. C'est une étape importante de la conception de logiciel (voire de matériel, cf. VHDL).) dynamique (Le mot dynamique est souvent employé désigner ou qualifier ce qui est relatif au mouvement. Il peut être employé comme :) peuvent alors éventuellement permettre de résoudre le problème avec une complexité (La complexité est une notion utilisée en philosophie, épistémologie (par exemple par Anthony Wilden ou Edgar Morin), en physique, en biologie (par...) polynomiale ou pseudo-polynomiale.
  • Processus stochastiques
Les processus stochastiques concernent tous les problèmes aléatoires, en particulier des problèmes de fiabilité (Un système est fiable lorsque la probabilité de remplir sa mission sur une durée donnée correspond à celle spécifiée dans le cahier des charges.) (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 (En mathématiques, les problèmes de programmation linéaire (PL) sont des problèmes d'optimisation où la fonction objectif et les contraintes sont toutes linéaires. Néanmoins, la plupart des résultats présentés ici sont...) 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 (Un algorithme par séparation et évaluation, également appelé selon le terme anglo-saxon branch and bound, est une méthode générique de résolution de problèmes d'optimisation, et plus particulièrement...) 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 (Le mot technologie possède deux acceptions de fait :).
  • 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 (L'heuristique (du grec heuriskêin, « trouver ») est l'utilisation de règles empiriques :) ou métaheuristique.

Ouvrages d'introduction

Source: Wikipédia publiée sous licence CC-BY-SA 3.0.

Vous pouvez soumettre une modification à cette définition sur cette page. La liste des auteurs de cet article est disponible ici.