Décider au mieux quand les ressources sont comptées.
La recherche opérationnelle est née pendant la Seconde Guerre mondiale, de questions très concrètes : comment disposer les convois, où placer les radars, combien de pièces de rechange embarquer. Sa méthode est toujours la même — écrire la décision sous forme de variables, les contraintes sous forme d'inégalités, l'objectif sous forme de fonction à optimiser — mais les outils qui en découlent sont d'une variété surprenante : géométrie des polyèdres, parcours de graphes, récurrences, probabilités.
Les cinq planches suivent cette variété. Un atelier qui répartit sa production, un réseau qui achemine un flot, un chantier qui cherche sa date de fin, un sac qu'il faut remplir, une file d'attente qui s'allonge. À chaque fois, la réponse exacte est calculée par au moins deux chemins indépendants, et l'écart est affiché.
Un atelier fabrique deux produits, x et y. Chacun consomme des heures de machine, de la matière et du contrôle ; chacun rapporte une marge. Le problème s'écrit :
maximiser z = c₁·x + c₂·y
sous 2x + y ≤ b₁ (atelier) x + 3y ≤ b₂ (matière)
x + y ≤ b₃ (contrôle) x ≥ 0, y ≥ 0
Les contraintes découpent un polygone ; l'objectif est une famille de droites parallèles qu'on pousse aussi loin que possible. Le résultat central de la théorie est visible à l'œil : l'optimum est toujours atteint en un sommet. C'est ce qui rend le problème fini — et c'est ce qu'exploite l'algorithme du simplexe, qui saute de sommet en sommet en montant à chaque fois.
À côté du problème d'origine vit un second problème, son dual, dont les variables sont les prix des ressources. Le théorème de dualité forte dit que les deux ont exactement la même valeur optimale — et que le prix dual d'une ressource est ce que rapporterait une unité de plus. Une ressource non saturée a un prix nul : en acheter davantage ne sert à rien. Ci-dessous, la valeur optimale en fonction de b₁ : une ligne brisée concave dont la pente en chaque point est précisément le prix dual.
Un réseau achemine une marchandise d'une source s vers un puits t ; chaque arc a une capacité. Combien peut-on faire passer ? L'algorithme de Ford et Fulkerson cherche des chemins encore disponibles et les sature l'un après l'autre. Le théorème qui l'accompagne est l'un des plus beaux de la discipline : le flot maximum est égal à la capacité de la plus petite coupe — le débit est fixé par le goulot, et par lui seul.
Un chantier est une liste de tâches, chacune avec une durée et des antériorités. En parcourant le graphe des tâches dans l'ordre, on obtient les dates au plus tôt ; en le remontant à partir de la fin, les dates au plus tard. La différence est la marge. Les tâches de marge nulle forment le chemin critique : allonger l'une d'elles d'un jour repousse tout le projet d'un jour, tandis qu'une tâche à marge peut glisser sans conséquence.
Le bouton de raccourcissement montre le piège du « crashing » : les premiers jours gagnés coûtent un jour de projet chacun, puis un second chemin devient critique à son tour et le gain tombe à zéro. Accélérer une seule tâche ne sert plus à rien dès qu'elle n'est plus seule à commander.
Des objets, chacun avec un poids et une valeur ; un sac de capacité limitée. Que prendre ? La méthode qui vient à l'esprit — trier par valeur au kilo et remplir — est gloutonne : rapide et souvent fausse. L'examen de toutes les combinaisons est exact mais coûte 2n. La programmation dynamique tranche : elle résout le problème pour toutes les capacités intermédiaires, et chaque case du tableau ne demande qu'une comparaison.
La relaxation continue — celle où l'on s'autorise à couper un objet en deux — se résout par le glouton et fournit une borne supérieure toujours valable. Elle encadre l'optimum entier par le dessus, le glouton entier par le dessous : c'est le principe de toute méthode de séparation et évaluation.
Tout ce qui précède suppose les données connues. Il reste le cas où elles ne le sont pas : les clients arrivent au hasard, les services durent au hasard, et la file s'allonge toute seule. Le résultat le plus contre-intuitif de la recherche opérationnelle est là — l'attente n'augmente pas régulièrement avec la charge, elle explose quand on approche de la saturation, et un guichet occupé à 95 % fait attendre non pas un peu plus qu'à 90 %, mais deux fois plus.
La loi de Little, L = λ·W, est vérifiée ici sur les deux quantités mesurées, sans jamais passer par la formule théorique. Elle ne suppose ni loi d'arrivée particulière, ni discipline de service : c'est une identité de comptabilité, vraie pour n'importe quel système en régime stationnaire.
La courbe est une hyperbole : W = 1/(μ−λ). Doubler la marge de capacité restante divise l'attente par deux, ce qui explique pourquoi les dimensionnements se font sur la charge de pointe et non sur la charge moyenne — et pourquoi un service prévu « juste ce qu'il faut » est un service qui s'effondre. La simulation en souffre elle-même : pour obtenir la même précision à ρ = 0,95 qu'à ρ = 0,50, il faut environ cent fois plus de clients. C'est le même phénomène, vu du côté du calcul — aussi le nombre de clients simulés est-il augmenté automatiquement à mesure que la charge monte.
Deux guichets, deux organisations. À gauche, chacun a sa file et les clients se répartissent au hasard ; à droite, une file unique alimente les deux guichets dès que l'un se libère. La charge totale est identique. Le second système est pourtant nettement plus rapide, parce qu'il ne laisse jamais un guichet inoccupé pendant que quelqu'un attend ailleurs.
Le gain ne coûte rien : mêmes guichets, mêmes clients, même charge. Seule l'organisation change. C'est le principe de la file d'attente unique en serpentin adoptée par les banques, les aéroports et les bureaux de poste — et sa justification tient en une formule.