De grands problèmes résolus

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…

LES ARTICLES

Transports, flots et coupes

Nicolas Catusse

De nombreux problèmes de transport peuvent être modélisés à l'aide des « flots ». C'est le cas de l'acheminement d'électricité présenté dans cet article. D'autres applications classiques concernent également le transport de fluides (gaz, eau, pétrole...) ainsi que celui de personnes ou de marchandises (camion, train, bateau...).

Appréhender le hasard

Emmanuel Hyon

Les problèmes d'optimisation stochastique se définissent spécifiquement par une incertitude sur les données. Le modélisateur n'a qu'une connaissance imparfaite des données relatives au système considéré ou à son évolution. Cependant, leurs valeurs peuvent être caractérisées par des lois de probabilités.

L'optimisation équitable

Patrice Perny

Les décisions prises au sein des organisations ont souvent un impact sur plusieurs individus, qu'il convient de considérer de manière équitable. L'optimisation équitable permet de trouver des solutions efficaces tout en contrôlant l'équilibre des satisfactions.

Ordonnancement

L'art de faire chaque chose en son temps

Pierre Lemaire

Quand il faut décider quand effectuer les tâches menant à un objectif, il est parfois nécessaire de faire preuve d'imagination, ou d'abstraction. Toutes les situations pourront néanmoins s'appuyer sur la théorie de l'ordonnancement, un champ de la recherche opérationnelle très actif depuis plus d'un siècle.