La recherche opérationnelle est censée
résoudre des questions d’emploi du temps, d’affectation de tâches, d’ordonnancement d’étapes
de fabrication, etc., où interviennent de multiples variables et contraintes, la solution devant
être la meilleure possible — au sens d’un
meilleur coût, d’un délai minimal, ou autre. Un
exemple élémentaire de problème de recherche
opérationnelle est celui d’affecter, dans une
entreprise qui comporte 50 postes de travail,
un poste déterminé à chacun des 50 employés,
en tenant compte au mieux des aptitudes de
chacun. Pour obtenir la meilleure solution à ce
problème, on pourrait bien sûr passer en revue
toutes les possibilités, évaluer chacune puis choisir la plus avantageuse. C’est tout à fait exclu
en pratique: il faudrait explorer 50! = 50 × 49
× 48 ×... × 3 × 2 × 1 possibilités, un nombre faramineux (égal à environ 3 × 10
64
). Même si un
ordinateur pouvait parcourir un milliard de possibilités par seconde, il lui faudrait 10
48 années
pour les épuiser toutes, beaucoup plus que l’âge
estimé de l’Univers (environ 10
10 ans)!
Cet exemple laisse entrevoir l’ingéniosité
que doit déployer la recherche opérationnelle
pour traiter de tels problèmes de façon réaliste, en un temps de calcul acceptable. En plus
des outils informatiques, des techniques
mathématiques diverses et variées (algébriques, probabilistes, numériques, etc.)
entrent dans la conception de ses méthodes.
Bien que née il y a plus de cinquante ans, la
recherche opérationnelle est une science
mathématique toujours jeune : il ne se passe
guère plus de trois ans entre le moment où
une méthode est conçue dans un laboratoire
de recherche et le moment où elle passe en
production, après avoir passé l’étape du
bureau d’études. Dans le secteur aérien, les
enjeux sont tels qu’ils ont suscité la création
de nombreuses sociétés de conseils et services
mathématiques et informatiques comme le
groupe Sabre, issu du département de
recherche opérationnelle de la compagnie
American Airlines, la société Adopt issue du
laboratoire Gerad (Groupe d’études et de
les casse-tête des compagnies aériennes
67
La programmation linéaire
La programmation linéaire est le problème mathématique consistant à déterminer des quantités positives x 1 , x 2 , …, x N qui minimisent un certain « coût », supposé égal à c 1 x 1 + c 2 x 2 + ... + c N x N , où les c 1 ,
c 2 ,..., c N sont des nombres connus, et les x i étant par ailleurs soumis à des contraintes s’exprimant par des
équations linéaires (de la forme A 1 x 1 + A 2 x 2 + ... + A N x N = B, où les A i et B sont des nombres connus, qui
dépendent du problème posé). De très nombreuses questions de recherche opérationnelle peuvent se formuler
en ces termes. Si l’énoncé du problème de programmation linéaire est relativement simple, sa résolution ne
l’est pas du tout, d’autant que le nombre N d’inconnues à déterminer atteint, dans la pratique, plusieurs
milliers. Ce problème d’apparence anodine, mais de première importance pour les applications, est à l’origine des recherches les plus fructueuses en optimisation depuis une trentaine d’années. En 1947, le mathématicien américain George Dantzig proposait l’excellent et encore fréquemment utilisé algorithme du simplexe. Dans les années 1970 et 1980, d’autres algorithmes concurrents sont apparus. L’année 1984 a marqué
un tournant : un jeune mathématicien travaillant aux États-Unis, Narendra Karmarkar, découvrait un
algorithme de programmation linéaire particulièrement efficace (convergence dite polynomiale). Les idées
sous-jacentes à sa méthode ont inauguré un courant de recherche très actif (méthodes de points intérieurs),
qui a mobilisé simultanément des milliers de mathématiciens dans le monde. Grâce à ces efforts, l’industrie
dispose à présent d’une palette d’algorithmes de programmation linéaire très performants.
résoudre des questions d’emploi du temps, d’affectation de tâches, d’ordonnancement d’étapes
de fabrication, etc., où interviennent de multiples variables et contraintes, la solution devant
être la meilleure possible — au sens d’un
meilleur coût, d’un délai minimal, ou autre. Un
exemple élémentaire de problème de recherche
opérationnelle est celui d’affecter, dans une
entreprise qui comporte 50 postes de travail,
un poste déterminé à chacun des 50 employés,
en tenant compte au mieux des aptitudes de
chacun. Pour obtenir la meilleure solution à ce
problème, on pourrait bien sûr passer en revue
toutes les possibilités, évaluer chacune puis choisir la plus avantageuse. C’est tout à fait exclu
en pratique: il faudrait explorer 50! = 50 × 49
× 48 ×... × 3 × 2 × 1 possibilités, un nombre faramineux (égal à environ 3 × 10
64
). Même si un
ordinateur pouvait parcourir un milliard de possibilités par seconde, il lui faudrait 10
48 années
pour les épuiser toutes, beaucoup plus que l’âge
estimé de l’Univers (environ 10
10 ans)!
Cet exemple laisse entrevoir l’ingéniosité
que doit déployer la recherche opérationnelle
pour traiter de tels problèmes de façon réaliste, en un temps de calcul acceptable. En plus
des outils informatiques, des techniques
mathématiques diverses et variées (algébriques, probabilistes, numériques, etc.)
entrent dans la conception de ses méthodes.
Bien que née il y a plus de cinquante ans, la
recherche opérationnelle est une science
mathématique toujours jeune : il ne se passe
guère plus de trois ans entre le moment où
une méthode est conçue dans un laboratoire
de recherche et le moment où elle passe en
production, après avoir passé l’étape du
bureau d’études. Dans le secteur aérien, les
enjeux sont tels qu’ils ont suscité la création
de nombreuses sociétés de conseils et services
mathématiques et informatiques comme le
groupe Sabre, issu du département de
recherche opérationnelle de la compagnie
American Airlines, la société Adopt issue du
laboratoire Gerad (Groupe d’études et de
les casse-tête des compagnies aériennes
67
La programmation linéaire
La programmation linéaire est le problème mathématique consistant à déterminer des quantités positives x 1 , x 2 , …, x N qui minimisent un certain « coût », supposé égal à c 1 x 1 + c 2 x 2 + ... + c N x N , où les c 1 ,
c 2 ,..., c N sont des nombres connus, et les x i étant par ailleurs soumis à des contraintes s’exprimant par des
équations linéaires (de la forme A 1 x 1 + A 2 x 2 + ... + A N x N = B, où les A i et B sont des nombres connus, qui
dépendent du problème posé). De très nombreuses questions de recherche opérationnelle peuvent se formuler
en ces termes. Si l’énoncé du problème de programmation linéaire est relativement simple, sa résolution ne
l’est pas du tout, d’autant que le nombre N d’inconnues à déterminer atteint, dans la pratique, plusieurs
milliers. Ce problème d’apparence anodine, mais de première importance pour les applications, est à l’origine des recherches les plus fructueuses en optimisation depuis une trentaine d’années. En 1947, le mathématicien américain George Dantzig proposait l’excellent et encore fréquemment utilisé algorithme du simplexe. Dans les années 1970 et 1980, d’autres algorithmes concurrents sont apparus. L’année 1984 a marqué
un tournant : un jeune mathématicien travaillant aux États-Unis, Narendra Karmarkar, découvrait un
algorithme de programmation linéaire particulièrement efficace (convergence dite polynomiale). Les idées
sous-jacentes à sa méthode ont inauguré un courant de recherche très actif (méthodes de points intérieurs),
qui a mobilisé simultanément des milliers de mathématiciens dans le monde. Grâce à ces efforts, l’industrie
dispose à présent d’une palette d’algorithmes de programmation linéaire très performants.