La ricerca operativa

Questo terzo numero speciale del 2020, che esce nei tempi abituali nonostante gli eventi tragici dell'anno, è dedicato alla Ricerca Operativa. L'équipe di Tangente ringrazia le due società scientifiche, la ROADEF e il GDR RO, che si sono profondamente coinvolte nella sua stesura. Grazie ai membri del Comitato scientifico, e in particolare a Nadia Brauner, che hanno dedicato molto tempo alla riuscita di questo numero.

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.