La recherche opérationnelle

Ce troisième hors série de 2020, qui paraît dans les délais habituels malgré les événements tragiques de l'année, est consacré à la Recherche Opérationnelle. L'équipe de Tangente remercie les deux sociétés savantes, la ROADEF et le GDR RO, qui se sont impliquées profondément dans sa rédaction. Merci aux membres du Comité scientifique, et en particulier à Nadia Brauner, qui ont consacré beaucoup de temps à la réussite de ce numéro.

Un problème à un million de dollars : trouver une solution est-il aussi facile que la vérifier ? Écrit sous la forme  « P = NP ? », ce problème est pour l'instant toujours ouvert. Ainsi, montrer qu'un emploi du temps vérifie les contraintes imposées est facile, mais en trouver un qui convienne ? S'il faut les énumérer un par un pour les tester, on risque d'y passer un temps plus long que l'âge du soleil, alors qu'on aimerait avoir la solution dans les cinq minutes ou les vingt-quatre heures. On cherche d'abord à identifier les problèmes que l'on sait résoudre rapidement. Pour les autres, on utilisera si possible des recherches arborescentes intelligentes, des algorithmes exacts efficaces de type cheminement combinatoire, ou des méthodes approchées (métaheuristiques).

Certains grands problèmes d'optimisation possèdent une solution algorithmique efficace. C'est le cas quand il s'agit de trouver le plus court chemin parmi un nombre immense de possibilités, de faire transiter un flot (d'électricité, d'eau, d'information…) dans un réseau ou de résoudre un programme « linéaire », ne nécessitant pas d'énumérer toutes les solutions potentielles. Ces questions ont le bon goût d'appartenir à la classe P des problèmes qui peuvent être résolus en temps « raisonnable » (parfois polynomial). Les algorithmes associés, dont certains, comme le simplexe, sont classés parmi les dix plus importants du xxe siècle, ont gravé le nom de leur découvreur dans l'histoire de l'informatique : Dijkstra, Ford et Fulkerson, Bellman…

Du découpage électoral à l'organisation d'un service hospitalier, en passant par la protection de la biodiversité ou l'utilisation des énergies renouvelables, les applications de la recherche opérationnelle concernent des domaines très variés, parfois inattendus, où ses méthodes de modélisation et ses outils permettent d'aider l'humain dans sa prise de décision. Le but : trouver une solution optimale (ou au moins « pas trop mauvaise ») parmi un grand nombre de possibilités. La R.O. permet la conception, la configuration et l'exploitation de systèmes complexes qui ont une grande importance dans les entreprises ou pour les collectivités territoriales.