Comment décider quand les choix possibles sont trop nombreux pour être comparés de tête ? D'où vient cette discipline, à quoi elle sert, comment se déroule une étude, et jusqu'où on peut croire ce qu'un modèle répond.
La recherche opérationnelle (RO) est la science de la décision organisée. Elle traduit en mathématiques une situation où il faut choisir, cherche le meilleur choix possible, puis vérifie que ce choix tient dans la réalité.
Une tournée de 40 clients s'améliore sous vos yeux. La décision : l'ordre de visite. La contrainte : passer une fois chez chacun. L'objectif : le trajet le plus court. Chaque progrès est obtenu en retournant un morceau du parcours.
Longueur de départ–
Longueur actuelle–
Gain déjà obtenu–
Ce mot de « recherche » peut surprendre : il ne s'agit pas d'un laboratoire, mais d'une recherche sur les opérations, c'est-à-dire sur la façon de mener une activité concrète. Les chiffres des planches sont calculés sur place dans votre navigateur et, chaque fois que c'est possible, contrôlés par une seconde méthode. Les exemples chiffrés sont inventés pour être pédagogiques ; les faits historiques ne le sont pas.
Planche 1
Des radars aux convois : d'où vient la discipline ?
La RO naît d'un constat de guerre : les machines existaient, mais personne n'étudiait scientifiquement la façon de s'en servir. Ses idées mathématiques, elles, sont plus anciennes.
Gaspard Monge étudie la façon la moins coûteuse de transporter des déblais vers des remblais : c'est un problème d'optimisation avant la lettre.
Agner Krarup Erlang, à la compagnie téléphonique de Copenhague, applique les probabilités aux appels : naissance des files d'attente.
Ford Harris publie la formule de la quantité économique à commander : les stocks entrent dans le calcul.
À la station de Bawdsey, en Angleterre, A. P. Rowe fait analyser le fonctionnement réel de la chaîne de radars. On y situe d'ordinaire la naissance de la RO moderne.
Leonid Kantorovitch formule, à Leningrad, des méthodes mathématiques pour organiser la production. Il recevra le prix Nobel d'économie en 1975.
Le physicien Patrick Blackett et son équipe pluridisciplinaire, surnommée le « Cirque », réduisent fortement le nombre d'obus nécessaires pour abattre un avion. Ses groupes passent ensuite à l'aviation côtière et à l'Amirauté.
George Dantzig invente l'algorithme du simplexe : la programmation linéaire devient praticable à grande échelle.
Bernard Roy crée à Paris la méthode des potentiels pour ordonnancer un grand chantier ; la même année apparaît aux États-Unis la méthode PERT.
American Airlines chiffre l'apport de sa gestion du rendement à 1,4 milliard de dollars sur trois ans.
UPS reçoit le prix Edelman pour ORION, l'optimisation des tournées de ses livreurs : 300 à 400 millions de dollars d'économies annuelles estimées.
L'expérience fondatrice : petits ou grands convois ?
Dans l'Atlantique, l'intuition disait qu'il valait mieux disperser les navires en nombreux petits convois. L'équipe de Blackett a compté, et conclu l'inverse. Voici pourquoi, sur un modèle jouet aux chiffres inventés : 600 navires à faire traverser, une flotte d'escorteurs à répartir. Un sous-marin qui repère un convoi coule à peu près le même nombre de navires quelle que soit sa taille.
Un convoi traverse. Quand il est repéré, les torpilles partent : le nombre de navires coulés dépend des escorteurs, pas de la taille du convoi.
Part des navires perdus selon la taille des convois. Courbe : calcul exact. Points : 400 campagnes simulées pour chaque taille. Point rouge : votre réglage.
Nombre de convois–
Escorteurs par convoi–
Escorteurs par unité de périmètre–
Part perdue, calcul exact–
Part perdue, 10 000 convois simulés–
Navires perdus sur 600–
Traversée animée : perdus / envoyés–
Ce qu'il faut retenir. Quand un convoi double, sa surface double, mais son périmètre, celui qu'il faut protéger, n'est multiplié que par √2 ≈ 1,41. Les mêmes escorteurs protègent donc mieux, et les torpilles se répartissent sur plus de navires. La RO commence ainsi : compter ce qui se passe vraiment avant de décider. Ce modèle a pourtant une limite : il ignore qu'un port ne peut pas décharger cent navires à la fois.
Planche 2
Cinq domaines, une seule grammaire
Une bobine de papier, une tournée, un planning d'hôpital, un budget, un guichet : tout se ramène aux trois mêmes questions. Que décide-t-on ? Qu'est-ce qui est interdit ? Comment juge-t-on le résultat ?
DécisionsComment découper chaque bobine de 100 cm.
ContraintesLivrer chaque largeur commandée ; ne pas dépasser 100 cm par bobine.
ObjectifUtiliser le moins de bobines possible, donc limiter la chute.
Chaque ligne est une bobine, chaque couleur une largeur commandée. Le rouge est la chute, perdue.
Bobines, plan optimal–
Bobines, règle simple–
Minimum théorique (longueur totale ÷ 100)–
Chute du plan affiché–
Contrôle par une table complète : écart–
Dans la réalité : papeteries, verreries, tôleries. C'est sur un problème de ce type, le contreplaqué d'un trust de Leningrad, que travaillait Kantorovitch en 1939.
DécisionsDans quel ordre visiter les clients.
ContraintesPartir du dépôt, voir chaque client une fois, revenir.
ObjectifLe trajet total le plus court.
Bleu : tournée optimale, parcourue par la camionnette. Orange pointillé : les clients pris dans l'ordre des appels. Le carré rouge est le dépôt.
Ordres de visite examinés–
Tournée optimale–
Ordre des appels–
Toujours le plus proche–
Contrôle par Held-Karp : écart–
Dans la réalité : chez UPS, le système ORION optimise les tournées ; INFORMS rapporte 300 à 400 millions de dollars d'économies par an et 10 millions de gallons de carburant en moins.
DécisionsCombien de soignants commencent leurs 5 jours de travail consécutifs chaque jour de la semaine.
ContraintesAssurer le besoin de chaque jour ; deux jours de repos à la suite.
ObjectifLe plus petit effectif possible.
Barres empilées : soignants présents, une couleur par jour de reprise. Trait rouge : besoin du jour. Ce qui dépasse le trait est un surplus, imposé par la règle des 5 jours consécutifs.
Effectif minimal–
Borne : plus fort besoin d'un jour–
Borne : total des besoins ÷ 5–
Journées en surplus par semaine–
Contrôle exhaustif : effectif trouvé–
Dans la réalité : plannings hospitaliers, programmes opératoires, et échanges croisés de reins entre donneurs et receveurs incompatibles, résolus par programmation linéaire en nombres entiers.
DécisionsQuels projets financer : oui ou non pour chacun.
ContraintesLe total ne dépasse pas le budget ; un projet ne se coupe pas.
ObjectifLa plus grande valeur créée.
Chaque bloc est un projet : sa largeur est son coût, le nombre écrit sa valeur créée (en k€). En haut le choix optimal ; en bas le choix du « meilleur rapport d'abord ».
Combinaisons possibles–
Dont compatibles avec le budget–
Valeur optimale–
Meilleur rapport d'abord–
Contrôle par programmation dynamique : écart–
Dans la réalité : choix d'investissements, et composition de portefeuilles depuis Harry Markowitz (1952), qui met en balance le rendement espéré et le risque.
DécisionsCombien de guichets ouvrir.
ContraintesAttente moyenne sous la cible fixée.
ObjectifLe moins de guichets possible.
En haut, une file vivante : les points attendent, puis passent aux guichets. En bas, l'attente moyenne selon le nombre de guichets ; la barre verte est le plus petit nombre qui respecte la cible.
Travail arrivant par heure (5 min par client)–
Guichets nécessaires–
Attente, formule d'Erlang–
Attente, 200 000 clients simulés–
Taux d'occupation des guichets–
Dans la réalité : centres d'appels, banques, mais aussi prix des billets : American Airlines a fait de la gestion du rendement une méthode, avec 1,4 milliard de dollars d'apport déclaré sur trois ans.
Ce qu'il faut retenir. Changez d'onglet : le vocabulaire du métier change, la structure non. C'est pourquoi une méthode née pour une compagnie de téléphone sert à un hôpital. Remarquez aussi le dernier contrôle de chaque onglet : une règle de bon sens donne souvent une solution correcte, mais pas toujours la meilleure, et seul le calcul permet de le savoir.
Planche 3
Décision, solution admissible, solution optimale
Trois mots portent toute la discipline. Un transporteur doit acheminer un volume de marchandises et choisit combien de camions et de fourgons sortir.
DécisionCe sur quoi on a la main. Ici, deux nombres entiers : camions et fourgons. Chaque point du quadrillage est une décision.
Solution admissibleUne décision qui respecte toutes les contraintes. Elle est faisable, pas forcément bonne.
Solution optimaleUne solution admissible telle qu'aucune autre ne fait mieux. Il peut y en avoir une, plusieurs, ou aucune.
Cliquez sur un point. Vert : admissible. Gris : interdit. Bleu : optimal. Le trait orange relie toutes les décisions de même coût que la vôtre. Zone verte : ce que permettraient les contraintes si l'on pouvait sortir des fractions de véhicule ; croix violette : le meilleur point de cette zone.
–
Décisions sur le quadrillage–
Dont admissibles–
Dont optimales–
Coût de votre décision–
Coût optimal–
Surcoût par rapport à l'optimum–
Contrôle, balayage par fourgons : écart–
Trois pièges à essayer.Arrondir : l'optimum fractionnaire demande 4,33 camions ; arrondi à 4, il ne transporte plus assez, et arrondi au-dessus, il coûte trop. Améliorer pas à pas : partez de 2 camions et 7 fourgons ; on s'arrête à une solution qu'aucun petit pas n'améliore, un optimum local, qui n'est pas le meilleur. Exiger trop : si aucune décision n'est admissible, le problème n'a pas de solution, et le bon réflexe est de discuter les contraintes, pas le calcul.
Planche 4
Les cinq étapes d'une étude, sur un cas complet
Une mutuelle reçoit des plaintes : on attend trop au téléphone. Suivons l'étude de bout en bout. Vous allez voir qu'un calcul exact peut donner une mauvaise réponse, et que c'est l'étape de vérification qui le révèle.
→→→→
Définir le problème : la phase la plus sous-estimée
« On attend trop » n'est pas encore un problème : c'est un symptôme. Il faut d'abord répondre à quatre questions avec ceux qui vivent la situation.
Que peut-on changer ?Les horaires des agents, par vacations de 4 heures entre 8 h et 20 h.
Que ne touche-t-on pas ?Les heures d'ouverture, le nombre d'appels, la durée moyenne d'un appel : 5 minutes.
Comment juge-t-on ?Le nombre de vacations (le coût), sous une attente moyenne d'une minute au plus.
Les données viennent du standard : les appels par heure d'une journée type, tracés ci-dessus.
Construire un modèle : traduire sans trahir
On appelle xs le nombre d'agents qui commencent à l'heure s, et bt le nombre d'agents requis à l'heure t.
minimiser Σ xs sous la contrainte Σs ≤ t < s+4 xs ≥ bt pour chaque heure t, xs entier ≥ 0
Chaque case bleue du tableau dit : « cette vacation couvre cette heure ». Tout se joue dans une dernière hypothèse : combien vaut bt ? Le modèle A prend le plus simple : assez d'agents pour absorber le travail moyen de l'heure (arrondi au-dessus). Le modèle B tient compte du hasard des appels grâce à la formule d'Erlang, avec une attente cible. Commencez par A, comme le ferait une première étude.
Résoudre : ici, la partie la plus sûre
On balaie la journée heure par heure. Dès qu'une heure manque d'agents, on ajoute des vacations qui commencent à ce moment. Comment savoir que ce résultat est le meilleur ? On peut le prouver : les heures encadrées en violet sont espacées de 4 heures au moins, donc aucune vacation n'en couvre deux. Il faut par conséquent au moins la somme de leurs besoins. Si cette somme égale notre nombre de vacations, personne ne peut faire mieux.
Vérifier : le modèle ressemble-t-il à la réalité ?
Le contrôle consiste à rejouer 300 journées où les appels arrivent au hasard et où la durée de chacun varie, ce que le modèle ne voyait pas. Une solution exacte d'un modèle faux reste fausse : résoudre n'est pas vérifier.
Interpréter : répondre à celui qui décide
La courbe vaut plus qu'un chiffre : elle montre ce que coûte chaque niveau de service. Le choix du point appartient au responsable, car il dépend de ce qu'une minute d'attente représente pour ses adhérents. L'étude l'éclaire et ne le remplace pas.
Appels sur la journée–
Besoin le plus fort (agents)–
Vacations du plan–
Borne prouvée / programmation dynamique–
Attente moyenne simulée–
Pire heure (attente moyenne)–
Coût salarial du jour (24 €/h)–
Ce qu'il faut retenir. Une étude n'est pas une ligne droite. Le modèle A est résolu parfaitement et la preuve d'optimalité est juste, pourtant la vérification le condamne : il suppose que le travail arrive régulièrement. On revient alors à l'étape 2. Ces allers-retours ne sont pas un échec de la méthode : ils sont la méthode.
Planche 5
Ce que le modèle ne voit pas : limites et qualité des données
« Tous les modèles sont faux, mais certains sont utiles », écrivait le statisticien George Box. Trois expériences pour mesurer où cela se joue : ce que l'optimisation fait des erreurs, ce que coûtent les données fausses, et ce qui se passe juste à côté de l'optimum.
On choisit le projet qui semble le meilleur parmi N. Chaque valeur est connue avec une erreur de mesure, sans aucun biais : l'erreur est tantôt positive, tantôt négative. Pourtant, celui qu'on choisit est justement celui dont l'erreur a toutes les chances d'être positive. L'optimisation ne se trompe pas au hasard : elle va chercher les erreurs favorables.
Un tirage toutes les 1,5 seconde. Orange : les valeurs estimées. Bleu : les vraies valeurs. On retient l'estimation la plus haute (rouge). Regardez sur quelle vraie valeur elle retombe.
Valeur moyenne selon l'erreur sur les données. Courbes : formules exactes. Points : simulation. L'écart entre la promesse et le réel se creuse quand les données se dégradent.
Valeur promise–
Valeur réellement obtenue–
Avec des données parfaites–
Au hasard, sans modèle0,00
Le choix est vraiment le meilleur–
Simulation contre formule : promis / réel–
La bonne nouvelle et la mauvaise. Même avec des données médiocres, le choix calculé bat le hasard : le modèle reste utile. Mais sa promesse est fausse. La formule le mesure : réel = promis × τ² / (τ² + σ²), où τ = 10 est la dispersion des vraies valeurs et σ l'erreur. Plus on compare de projets, plus la déception est grande en valeur absolue. D'où la règle : méfiez-vous du chiffre annoncé par un optimiseur, et réduisez-le avant de le croire.
Reprenons la mutuelle et son modèle B. Le modèle ne change pas, ni la cible d'une minute. Seules les données qu'on lui donne sont abîmées. Le plan calculé est ensuite jugé sur les vrais appels. Cochez les défauts.
Barres bleues : les vrais besoins en heures de travail. Barres orange : ce que voit le modèle à travers les données abîmées. Escalier vert : les agents du plan calculé. Quand il passe sous le bleu, la réalité déborde.
–
Vacations du plan–
Plan avec de bonnes données–
Attente annoncée par le modèle–
Attente réelle (150 journées simulées)–
Attente la plus longue observée–
Le classement surprend. Essayez chaque défaut seul. La saisie aberrante produit le chiffre le plus énorme et le contrôle automatique la repère aussitôt. Le trou, signalé lui aussi, coûte ici peu de chose, car les vacations de 4 heures des heures voisines couvrent 14 h. Les plus dangereux sont les défauts plausibles : censure, durée, péremption. Aucune alerte, un modèle qui annonce fièrement moins d'une minute, et des attentes plusieurs fois supérieures. On ne les découvre qu'en allant voir sur le terrain comment la donnée est produite.
Un plan de coût minimal n'a, par construction, aucun agent de trop aux heures critiques. Il est donc posé juste au bord de ses contraintes. Que se passe-t-il si un phénomène absent du modèle survient ? Ici, chaque vacation prévue peut manquer à l'appel (maladie, retard).
Attente moyenne simulée selon le taux d'absence, pour le plan optimal et pour deux plans avec marge. Le trait vertical suit votre curseur.
Plan optimal–
Plan avec 1 agent de marge–
Plan avec 2 agents de marge–
Attente du plan optimal, comparée à son attente sans absence–
Surcoût du plan à 1 agent de marge–
L'optimum est fragile, parce qu'il est optimum. La hausse de l'attente n'est pas proportionnelle à celle des absences : elle s'accélère. Quelques vacations de plus achètent une assurance qui ne sert à rien tant que tout va bien. Le « meilleur » plan au sens du modèle n'est donc pas forcément le meilleur à conseiller. Le bon réflexe : ajouter au modèle ce qu'il oublie, ou tester le plan hors de ses hypothèses.
Les hypothèses à interroger avant de croire un résultat
Hypothèse du modèle
Quand elle casse
Que faire
Les données sont justes et à jour
Mesures censurées, saisies erronées, habitudes qui changent
Remonter à la source, croiser plusieurs origines, mettre à jour
Les chiffres sont certains
Demande, durées et prix varient
Analyse de sensibilité, simulation, optimisation robuste ou stochastique
Les relations sont simples, souvent linéaires
Effets de seuil, saturation, économies d'échelle
Tester le plan hors du domaine ajusté, affiner le modèle
Le critère résume ce qui compte
Équité, qualité de vie au travail, image : ce qui n'est pas compté ne pèse rien
Plusieurs critères, regard des personnes concernées
Les gens suivent le plan
Un plan incompris ou jugé injuste n'est pas appliqué
Associer les utilisateurs dès l'étape 1, expliquer les résultats
Ce qu'il faut garder
Une grammaire
Des décisions, des contraintes, un objectif. Une solution admissible respecte tout ; une solution optimale est la meilleure des admissibles. Cette grammaire vaut pour l'usine, la route, l'hôpital, la banque et le guichet.
Une démarche
Définir, modéliser, résoudre, vérifier, interpréter, en revenant en arrière autant qu'il le faut. Résoudre n'est qu'une étape, et rarement la plus difficile.
Une prudence
Le modèle répond à la question qu'on lui pose, avec les données qu'on lui donne. Il promet toujours trop, surtout quand elles sont mauvaises. Le dernier mot revient à celui qui décide.
Pour aller plus loin
Les méthodes à peine évoquées ici ont leur propre page dans ce cahier : La recherche opérationnelle (simplexe, flot, dualité), Le voyageur de commerce, PERT et chemin critique, Le problème de transport, Le problème d'affectation, Le plus court chemin, Le problème du sac à dos, Les stocks et la chaîne d'approvisionnement, La gestion du rendement tarifaire, L'optimisation de portefeuille.
Sur les calculs. Le modèle de convois est un jouet : perte par attaque suivant une loi de Poisson tronquée, dont la moyenne décroît avec le nombre d'escorteurs par unité de périmètre (√n). Il illustre le raisonnement de Blackett sans reproduire ses chiffres. La formule d'Erlang C suppose un régime stationnaire, heure par heure ; la simulation événementielle ne le suppose pas, d'où de légers écarts aux heures qui suivent un pic. Pour la malédiction de l'optimiseur, vraies valeurs et erreurs sont normales et indépendantes, et l'espérance du maximum de N normales est calculée par intégration numérique.
Sources des faits historiques et des exemples réels