Recherche opérationnelle

Une histoire des mathématiques de la recherche opérationnelle

Combien de lignes téléphoniques installer ? Où chercher un sous-marin ? Comment produire au moindre coût ? Quand cesser de chercher ? Comment répartir des étudiants entre des hôpitaux ? En un siècle, des questions très concrètes ont donné naissance à une branche des mathématiques. Cinq épisodes, d'Erlang à Gale et Shapley, rejoués sur des planches et contrôlés par le calcul.

De quoi parle-t-on ?

La recherche opérationnelle applique les mathématiques à la décision : organiser, dimensionner, planifier, affecter, au mieux et avec des moyens limités. Le mot naît en Angleterre vers 1938, quand des scientifiques sont chargés d'étudier l'emploi des radars ; la guerre en fait une discipline, et l'après-guerre lui donne ses grandes méthodes. Mais ses racines sont plus anciennes : Monge (1781) pour les transports, Erlang (1909) pour le téléphone, Harris (1913) pour les stocks. Cette page raconte l'histoire ; les méthodes elles-mêmes (simplexe, flots, transport, affectation, sac à dos, voyageur de commerce, files d'attente, stocks…) sont détaillées dans les autres pages de recherche opérationnelle de ce cahier.

Dimensionner	Combien de lignes pour un central téléphonique : Erlang (1909–1917). Planche 1.
Chercher	Où porter l'effort pour trouver un sous-marin : Koopman (1946). Planche 2.
Optimiser	Le programme linéaire et sa méthode : Kantorovich (1939), Dantzig (1947), Klee et Minty (1972), Karmarkar (1984). Planche 3.
Décider dans le temps	La programmation dynamique et l'arrêt optimal : Bellman (1957), le problème de la secrétaire (1960). Planche 4.
Apparier	Former des couples stables : Gale et Shapley (1962), prix Nobel de Shapley et Roth (2012). Planche 5.

Erlang, 1917 : combien de lignes pour un central téléphonique ?

Agner Krarup Erlang, Compagnie des téléphones de Copenhague · « Solution de quelques problèmes de la théorie des probabilités intéressant les centraux téléphoniques automatiques » (1917)

Un central relie un quartier à la ville par c lignes. Les appels arrivent au hasard ; un appel qui trouve toutes les lignes occupées est perdu. Erlang mesure le trafic en erlangs : A = (nombre moyen d'appels par minute) × (durée moyenne d'un appel en minutes), soit le nombre moyen de lignes qu'occuperait le trafic s'il n'y avait aucune perte. Il démontre que la proportion d'appels perdus vaut B(c, A) = (Aᶜ/c!) / (1 + A + A²/2! + ⋯ + Aᶜ/c!). Pour la première fois, on calcule à l'avance l'équipement nécessaire.

Trafic offert A8 erlangs

Nombre de lignes c10

Durée des appels

À gauche, les c lignes au fil du temps : chaque barre bleue est un appel en cours ; les croix rouges sont les appels perdus. À droite, la proportion d'appels perdus en fonction du nombre de lignes (échelle logarithmique), avec le seuil de 1 %.

Proportion perdue B(c, A), formule d'Erlang

—

Contrôle : récurrence d'Erlang et simulation de 200 000 appels

—

Lignes nécessaires pour perdre moins de 1 %

—

Rendement : trafic écoulé par ligne

—

Ce qu'il faut voir. Ajouter une ligne divise les pertes bien plus que proportionnellement : la courbe plonge. Le rendement croît avec la taille : il faut 15 lignes pour 8 erlangs (53 % d'occupation) mais 53 lignes pour 40 erlangs (75 %), d'où l'intérêt de regrouper les centraux. Changez la loi des durées : la simulation ne bouge presque pas. La formule ne dépend que de la durée moyenne, une propriété (l'« insensibilité ») qu'Erlang avait pressentie et que Sevastyanov démontrera en 1957. La formule sert toujours à dimensionner les centres d'appels et les réseaux.

Koopman, 1946 : la théorie de la recherche

Patrick Blackett et le « cirque de Blackett » (1940–1942) · Bernard Koopman, Search and Screening, Operations Evaluation Group, US Navy (1946)

Pendant la bataille de l'Atlantique, les avions alliés cherchent des sous-marins. Les équipes de recherche opérationnelle, en Angleterre autour de Blackett, en Amérique autour de Morse et de Kimball, étudient les rapports de patrouille. Koopman en tire une théorie. Un avion voit un objet s'il passe à moins de W/2 ; en parcourant une longueur L dans une zone d'aire S, il « couvre » c = W·L/S. Un balayage en bandes parallèles parfaitement régulières trouve l'objet avec la probabilité c (jusqu'à 1). Une trajectoire au hasard repasse sur ses traces et ne trouve qu'avec la probabilité 1 − e⁻ᶜ. Koopman montre ensuite comment répartir l'effort quand on sait où l'objet a le plus de chances d'être. Deux onglets.

Largeur de détection W2,5 % du côté

À gauche, la zone de recherche (ses bords se raccordent, comme sur un tore), la bande balayée par l'avion, qui vole en lignes droites de longueur et de direction tirées au hasard, et 400 objets possibles, qui passent au vert quand ils sont vus. À droite, la probabilité de détection en fonction de la couverture c : balayage parfait (gris), formule de Koopman 1 − e⁻ᶜ (violet), mesure (points bleus).

Couverture parcourue c = W·L/S

—

Objets vus sur la figure

—

Formule de Koopman 1 − e⁻ᶜ

—

Contrôle : 12 trajectoires × 2 000 objets, plus grand écart à la formule

—

Un objet a disparu ; deux hypothèses sur sa position donnent la carte de probabilité de gauche. On dispose d'un effort total Z, exprimé en nombre de cases qu'on pourrait balayer une fois. Mettre un effort z sur une case où l'objet se trouve avec la probabilité p le trouve avec la probabilité p·(1 − e⁻ᶻ). Koopman montre que le meilleur plan fouille les cases où p·e⁻ᶻ, ce qu'il reste à gagner, est le même partout où l'on cherche : z = ln(p/λ) là où p > λ, rien ailleurs.

Effort total Z40

Plan

À gauche, la carte de probabilité (plus c'est foncé, plus l'objet a de chances d'être là). À droite, l'effort placé sur chaque case par le plan choisi.

Probabilité de trouver l'objet avec ce plan

—

Comparaison des trois plans

—

Contrôle : p·e⁻ᶻ égal sur les cases fouillées, plus petit ailleurs

—

Contrôle : effort placé petit à petit là où il rapporte le plus

—

Ce qu'il faut voir. Les points mesurés suivent la formule de Koopman : une recherche au hasard gaspille une part de l'effort, de plus en plus grande à mesure que la couverture augmente (63 % de chances pour c = 1, au lieu de 100 %). Pour répartir l'effort, ni l'uniforme ni la concentration ne valent le plan de Koopman. Après une fouille infructueuse, la règle de Bayes fait baisser la probabilité des zones fouillées ; on recommence sur la nouvelle carte. Placer l'effort petit à petit, toujours là où il rapporte le plus, donne exactement le plan optimal : rien n'est perdu à chercher par étapes. C'est ainsi qu'on a retrouvé le sous-marin Scorpion en 1968 et l'épave du vol Rio–Paris AF447 en 2011.

Le simplexe, 1947–1984 : une méthode rapide qui peut être lente

Leonid Kantorovich (1939) · George Dantzig, méthode du simplexe (1947) · Victor Klee et George Minty (1972) · Leonid Khachiyan (1979) · Narendra Karmarkar (1984)

Kantorovich formule en 1939 les premiers programmes linéaires pour organiser une fabrique de contreplaqué. Dantzig invente en 1947 pour l'US Air Force la méthode du simplexe : partir d'un sommet du polyèdre des solutions et passer d'un sommet à un sommet voisin meilleur jusqu'à l'optimum. En pratique elle fait peu de pas. Mais en 1972, Klee et Minty construisent un cube déformé à n dimensions sur lequel la règle de Dantzig visite les 2ⁿ sommets. Il faudra attendre 1979, puis 1984, pour des méthodes à temps garanti, qui traversent l'intérieur du polyèdre. Deux onglets.

Règle de choix de la variable entrante

À gauche, le cube de Klee et Minty en dimension 3 (chaque axe est remis à la même échelle) et le chemin suivi par le simplexe, de l'origine à l'optimum. À droite, le nombre de pivots en fonction de la dimension n (échelle logarithmique) pour les trois règles, comparé à 2ⁿ − 1, et pour des programmes tirés au hasard de même taille.

Pivots en dimension 3 avec cette règle

—

Pivots de la règle de Dantzig pour n = 1 à 12

—

Contrôle : optimum 5ⁿ⁻¹ atteint et sommets du chemin tous admissibles

—

Programmes tirés au hasard (n variables, n contraintes) : pivots moyens

—

Un petit programme : maximiser 3x + 2y sous cinq contraintes. La méthode des points intérieurs remplace le problème par maximiser 3x + 2y + μ·Σ ln(écarts) : le logarithme interdit d'approcher les bords. Quand μ décroît, la solution glisse le long du chemin central jusqu'au sommet optimal. Le simplexe, lui, longe les arêtes.

Paramètre μ (échelle logarithmique)10

À gauche, le polygone des solutions, les droites de niveau de 3x + 2y, le chemin central (violet), le point courant et le chemin du simplexe sur les arêtes (orange). À droite, l'écart de dualité en fonction de μ (échelles logarithmiques).

Point du chemin central

—

Valeur 3x + 2y (optimum : 11,5)

—

Contrôle : écart de dualité mesuré et 5·μ

—

Contrôle : prix duaux yᵢ = μ/écartᵢ, résidu de Aᵀy = c

—

Ce qu'il faut voir. Avec la règle de Dantzig, le nombre de pivots double à chaque dimension : 2ⁿ − 1, soit 4 095 pivots pour 12 variables seulement. La règle de Bland n'échappe pas non plus à la croissance exponentielle. La plus forte amélioration va ici droit au but, mais d'autres cubes déformés la piègent aussi. Sur des programmes tirés au hasard, le simplexe ne fait que quelques pivots, ce que Spielman et Teng expliqueront en 2001. Sur le chemin central, l'écart entre la valeur et sa borne duale vaut exactement 5·μ (cinq contraintes) : on sait à chaque instant que l'on est à moins de 5·μ de l'optimum. Pour les très petites valeurs de μ, les arrondis de l'ordinateur limitent la précision de ce contrôle à quelques dix-millièmes en valeur relative. Les solveurs modernes combinent les deux méthodes.

Bellman et le problème de la secrétaire : quand s'arrêter ?

Richard Bellman, Dynamic Programming (1957) · Martin Gardner, Scientific American (1960) · Dennis Lindley (1961) · Chow, Moriguti, Robbins et Samuels (1964)

Bellman fonde la programmation dynamique : pour décider au mieux maintenant, on calcule d'abord la meilleure décision au dernier instant, puis à l'avant-dernier, et ainsi de suite en remontant le temps. Le problème de la secrétaire, popularisé par Gardner en 1960, en est un exemple célèbre. n candidats se présentent un par un, dans un ordre au hasard. Après chaque entretien, on sait seulement si le candidat est meilleur que les précédents, et il faut l'engager ou le refuser définitivement. La règle : laisser passer les r − 1 premiers, puis engager le premier candidat meilleur que tous ceux qu'on a vus.

Nombre de candidats n20

On laisse passer les r − 1 premiers ; r =8

Objectif

À gauche, une série d'entretiens : la hauteur mesure la valeur du candidat, la zone grise est la phase d'observation, l'étoile marque le candidat engagé. À droite, la probabilité d'engager le meilleur en fonction de r (formule exacte, en bleu ; points : simulation) et la limite 1/e. Avec l'objectif du rang moyen, la courbe montre jusqu'à quel rang relatif on accepte un candidat à chaque instant.

Avec ce seuil r

—

Meilleur seuil et sa valeur

—

Contrôle : programmation dynamique (récurrence à rebours)

—

Contrôle : simulation

—

Ce qu'il faut voir. Le meilleur seuil est proche de n/e, soit 37 % des candidats, et la probabilité d'engager le meilleur reste proche de 1/e ≈ 36,8 %, que n vaille 20 ou 100 : c'est la « règle des 37 % ». La récurrence de Bellman, calculée à rebours, retrouve exactement la formule. Si l'on vise plutôt un bon rang en moyenne, la règle change : on devient de moins en moins exigeant à mesure que le temps passe, et le rang moyen obtenu reste inférieur à 3,87 quel que soit le nombre de candidats.

Gale et Shapley, 1962 : des appariements stables

David Gale et Lloyd Shapley, « College admissions and the stability of marriage » (1962) · Donald Knuth, Mariages stables (1976) · Alvin Roth, l'appariement des internes américains (1984) · prix Nobel de Shapley et Roth (2012)

Six étudiants doivent être répartis entre six hôpitaux, une place chacun. Chacun a ses préférences. Un appariement est instable si un étudiant et un hôpital qui ne sont pas ensemble se préfèrent mutuellement à leur partenaire : ils ont intérêt à s'entendre en dehors du système. Gale et Shapley montrent qu'un appariement stable existe toujours et donnent l'algorithme pour le trouver. Chaque étudiant libre se propose à l'hôpital qu'il préfère parmi ceux qui ne l'ont pas encore refusé ; chaque hôpital garde la meilleure proposition reçue et refuse les autres. On recommence jusqu'à ce que tout le monde soit placé. Deux onglets.

Qui propose ?

À gauche, les étudiants A à F et leurs listes de préférences ; à droite, les hôpitaux 1 à 6 et les leurs (du préféré au moins aimé). Trait vert : engagement provisoire ; flèche orange : proposition en cours ; flèche rouge : refus. Le rang de chaque partenaire dans la liste est souligné.

Propositions faites

—

Paires instables dans le résultat

—

Contrôle : examen des 720 appariements possibles

—

Rang moyen du partenaire obtenu (1 = premier choix)

—

On tire des préférences au hasard pour n étudiants et n hôpitaux, et l'on fait proposer les étudiants. Combien de propositions faut-il, et que vaut le résultat pour chaque camp ? Un étudiant se propose à ses choix dans l'ordre jusqu'à être retenu : son nombre de propositions est donc exactement le rang du partenaire qu'il obtient. Wilson (1972) puis Knuth (1976) montrent que le nombre moyen de propositions ne dépasse pas n·Hₙ, où Hₙ = 1 + 1/2 + ⋯ + 1/n ≈ ln n. Pittel montre en 1989 que les étudiants obtiennent en moyenne un partenaire de rang voisin de ln n, et les hôpitaux un partenaire de rang voisin de n/ln n.

Échelle logarithmique en n. À gauche, en bleu, le rang moyen obtenu par les étudiants, qui est aussi le nombre moyen de propositions par étudiant, comparé à la borne Hₙ (pointillé bleu) et à ln n (pointillé vert). À droite, en rouge, le rang moyen obtenu par les hôpitaux, comparé à n/ln n (pointillé rouge).

Propositions par étudiant pour n = 400 et borne H₄₀₀

—

Rang moyen obtenu par les étudiants et ln n

—

Rang des hôpitaux et n/ln n

—

Contrôle : paires instables sur tous les tirages

—

Ce qu'il faut voir. L'algorithme s'arrête toujours, sur un appariement sans aucune paire instable. Il y en a souvent plusieurs, et celui que trouve l'algorithme est le meilleur possible pour chaque membre du camp qui propose et le pire pour l'autre camp : changez de camp et comparez les rangs. Sur de grands tirages, l'écart est spectaculaire : avec 400 de chaque côté, les étudiants qui proposent obtiennent en moyenne un partenaire classé vers le 6ᵉ rang, et les hôpitaux un partenaire classé vers le 66ᵉ rang. Le système d'affectation des internes américains appliquait sans le savoir cet algorithme depuis 1952 ; Roth le découvre en 1984 et l'adapte ensuite, et des variantes servent pour les écoles de Boston et de New York et pour les dons croisés de reins.

Frise : vingt-huit jalons de la recherche opérationnelle

En trois idées

Des problèmes concrets

Le téléphone, la guerre sous-marine, la logistique militaire, l'embauche, les affectations : chaque méthode est née d'une question pratique, puis s'est révélée générale.

Optimum et garantie

Une bonne méthode donne une solution et aussi une preuve de sa qualité : formule exacte, condition d'égalité des gains marginaux, écart de dualité, absence de paire instable.

Rapide en pratique, lent au pire

Le simplexe montre qu'il faut distinguer le cas moyen du pire cas. Cette distinction est au cœur de la théorie de la complexité (Cook, Karp, 1971–1972).

Pour aller plus loin

Les méthodes croisées sur cette page sont détaillées dans d'autres pages de ce cahier : la recherche opérationnelle (simplexe, flot maximum, PERT, sac à dos, files d'attente) ; le voyageur de commerce ; le problème de transport ; le problème d'affectation ; le plus court chemin ; la gestion des stocks ; la gestion du rendement tarifaire ; la localisation des installations ; l'optimisation de portefeuille.

Lectures : Saul Gass et Arjang Assad, An Annotated Timeline of Operations Research ; George Dantzig, Linear Programming and Extensions ; Philip Morse et George Kimball, Methods of Operations Research ; Lawrence Stone, Theory of Optimal Search ; Donald Knuth, Mariages stables ; Alvin Roth, Who Gets What — and Why.

Précautions : le trafic téléphonique, la carte de probabilité de la planche 2, les préférences de la planche 5 et les programmes linéaires de la planche 3 (sauf le cube de Klee et Minty) sont fabriqués par la page. Les simulations utilisent un générateur pseudo-aléatoire à graine fixe : elles donnent les mêmes résultats à chaque visite, sauf quand on demande de nouveaux tirages.