À la fin des années 1930, le Royaume-Uni installe le long de ses côtes une chaîne de stations radar pour repérer les avions allemands. Les appareils fonctionnent, mais encore faut-il organiser la transmission des informations, le guidage des chasseurs, la répartition des stations. Des scientifiques sont chargés d'étudier non pas les appareils, mais leur utilisation, leurs « opérations » : c'est l'origine du nom operational research, recherche opérationnelle.

Pendant la guerre, des équipes mêlant physiciens, mathématiciens, biologistes et psychologues travaillent pour l'armée britannique, notamment autour du physicien Patrick Blackett, futur prix Nobel de physique. L'un de leurs sujets est la bataille de l'Atlantique : les navires marchands qui ravitaillent le Royaume-Uni traversent l'océan en convois, protégés par des navires d'escorte, et les sous-marins allemands les attaquent.

Un convoi dans l'Atlantique en 1942. Photo : U.S. Office of War Information, Wikimedia Commons, domaine public.

Faut-il de petits convois ou de grands convois ? L'analyse des données a conduit les équipes de Blackett à une conclusion surprenante : les grands convois sont proportionnellement moins vulnérables. Un raisonnement géométrique simple aide à le comprendre.

• Les navires d'un convoi occupent à peu près un disque. Si chaque navire a besoin d'une même surface, l'aire du disque est proportionnelle au nombre $n$ de navires : $\pi R^2 = k\,n$, donc $R = \sqrt{\dfrac{k\,n}{\pi}}$.
• Les escortes surveillent le bord du convoi : le nombre d'escortes nécessaires est proportionnel au périmètre $2\pi R$, donc à $\sqrt{n}$.
• Le nombre d'escortes nécessaires par navire est donc proportionnel à $\dfrac{\sqrt{n}}{n} = \dfrac{1}{\sqrt{n}}$ : une fonction décroissante de $n$.

Un convoi de $80$ navires demande, par navire, $\sqrt{2} \approx 1{,}41$ fois moins d'escortes qu'un convoi de $40$ navires, car $\dfrac{1/\sqrt{40}}{1/\sqrt{80}} = \sqrt{2}$. La réalité est plus compliquée (les sous-marins attaquaient en groupes, un grand convoi est plus facile à repérer), mais l'idée a pesé dans les décisions. D'autres études ont porté sur la profondeur de déclenchement des grenades sous-marines, ou sur la couleur des avions de patrouille pour qu'ils soient moins visibles depuis la surface.

Leonid Kantorovitch en 1975. Photo : Andreï Bogdanov, Wikimedia Commons, licence CC BY 3.0.

En 1939, en Union soviétique, le mathématicien Leonid Kantorovitch est consulté par une usine de contreplaqué de Leningrad qui veut répartir au mieux le travail entre ses machines. Il en tire une méthode générale pour organiser une production quand les ressources sont limitées : c'est la naissance de la programmation linéaire. Son travail passe largement inaperçu, en URSS comme en Occident : dans une économie planifiée, l'idée de « prix » attachés aux ressources rares, qui apparaît dans ses calculs, était suspecte.

En 1947, aux États-Unis, le mathématicien George Dantzig, qui travaille sur la planification de l'armée de l'air américaine, invente indépendamment une méthode de calcul très efficace, la méthode du simplexe. Les ordinateurs naissants permettent de l'appliquer à des problèmes de plus en plus grands. En 1975, Kantorovitch et l'économiste américain d'origine néerlandaise Tjalling Koopmans reçoivent le prix de la Banque de Suède en sciences économiques en mémoire d'Alfred Nobel (souvent appelé « prix Nobel d'économie ») pour leurs travaux sur la répartition optimale des ressources. Dantzig, au grand étonnement de beaucoup, n'y est pas associé.

Un atelier fabrique deux modèles de meubles, A et B. On note $x$ le nombre de meubles A et $y$ le nombre de meubles B fabriqués par semaine. Les ressources sont limitées :

• le montage : un meuble A ou un meuble B demande $1$ jour de montage, et l'atelier dispose de $8$ jours : $x + y \leqslant 8$ ;
• le bois : un meuble A demande $2$ m³ de bois, un meuble B $1$ m³, et l'atelier en reçoit $12$ m³ : $2x + y \leqslant 12$ ;
• la finition : un meuble A demande $1$ heure de vernissage, un meuble B $3$ heures, sur $18$ heures disponibles : $x + 3y \leqslant 18$ ;
• enfin $x \geqslant 0$ et $y \geqslant 0$.

Un meuble A rapporte $30$ € de bénéfice, un meuble B $20$ €. Le bénéfice de la semaine est

Il s'agit de rendre $P$ maximal en respectant toutes les contraintes. Les contraintes et le bénéfice s'écrivent avec des expressions du premier degré en $x$ et $y$ : d'où le nom de programmation linéaire.

Dans un repère, chaque contrainte délimite un demi-plan. Par exemple, la droite d'équation $x + y = 8$ passe par $(8\,;0)$ et $(0\,;8)$, et les points qui vérifient $x + y \leqslant 8$ sont ceux situés du côté de l'origine, puisque $0 + 0 \leqslant 8$. Les points qui vérifient toutes les contraintes forment un polygone, la région admissible. Ses sommets s'obtiennent en résolvant des systèmes de deux équations.

• $x + y = 8$ et $2x + y = 12$ : en soustrayant, $x = 4$, puis $y = 4$. Ce point vérifie bien $x + 3y = 16 \leqslant 18$.
• $x + y = 8$ et $x + 3y = 18$ : en soustrayant, $2y = 10$, donc $y = 5$ et $x = 3$. Ce point vérifie $2x + y = 11 \leqslant 12$.
• Sur les axes : $(0\,;0)$, $(6\,;0)$ (car $2x \leqslant 12$) et $(0\,;6)$ (car $3y \leqslant 18$).

Calculons le bénéfice en chaque sommet.

Le meilleur sommet est $(4\,;4)$ : $4$ meubles A et $4$ meubles B, pour un bénéfice de $200$ €. La partie suivante démontre qu'aucun point de la région ne fait mieux.

Les points où le bénéfice vaut un nombre $k$ donné sont sur la droite d'équation $30x + 20y = k$. Quand $k$ augmente, cette droite se déplace parallèlement à elle-même, en s'éloignant de l'origine. Le bénéfice maximal correspond à la dernière position où la droite touche encore la région admissible. Dans la figure, le premier curseur déplace la droite ; le second change le bénéfice d'un meuble B, et l'on voit le sommet optimal changer.

Avec un bénéfice de $20$ € par meuble B, la droite quitte la région en $(4\,;4)$ pour $k = 200$. Si un meuble B rapporte $30$ €, les bénéfices aux sommets deviennent $0$, $180$, $240$, $240$ et $180$ : la droite de bénéfice est alors parallèle au côté qui joint $(4\,;4)$ et $(3\,;5)$, et tous les points de ce côté sont optimaux. Au-delà, l'optimum passe en $(3\,;5)$.

Un magasin vend chaque année $D$ unités d'un produit, à un rythme régulier. À chaque commande, il paie un coût fixe $a$ (transport, traitement administratif), quelle que soit la quantité commandée. Garder une unité en stock coûte $h$ par an (place, assurance, argent immobilisé). S'il commande $q$ unités à la fois :

• il passe $\dfrac{D}{q}$ commandes par an, qui coûtent $\dfrac{aD}{q}$ ;
• son stock part de $q$ à chaque livraison et descend régulièrement jusqu'à $0$ : il vaut en moyenne $\dfrac{q}{2}$, et coûte $\dfrac{hq}{2}$ par an.

Pourquoi un stock moyen de $\dfrac{q}{2}$ ? Entre deux livraisons, sur une durée $T$, le stock est la fonction affine $s(t) = q - \dfrac{q}{T}\,t$. Sa valeur moyenne est $\dfrac{1}{T}\displaystyle\int_0^T s(t)\,\mathrm{d}t$.

• Une primitive de $s$ est $S(t) = qt - \dfrac{q}{2T}\,t^2$.
• Donc $\displaystyle\int_0^T s(t)\,\mathrm{d}t = S(T) - S(0)$, c'est-à-dire $qT - \dfrac{qT}{2} = \dfrac{qT}{2}$.
• En divisant par $T$, la valeur moyenne vaut $\dfrac{q}{2}$.

Le coût annuel total est donc

Commander souvent de petites quantités coûte cher en commandes ; commander rarement de grandes quantités coûte cher en stockage. Il faut trouver le bon compromis.

Prenons $D = 1\,200$ unités par an, $a = 50$ € par commande et $h = 3$ € par unité et par an.

Le meilleur choix du tableau est $q = 200$, et l'on remarque qu'en ce point les deux coûts sont égaux. Est-ce le minimum ?

C'est la formule de Wilson, établie en 1913 par l'ingénieur américain Ford Harris et popularisée dans les années 1930 par R. H. Wilson. Avec l'exemple :

soit $q^* = \sqrt{40\,000} = 200$.

Les deux coûts sont égaux à l'optimum. En effet $(q^*)^2 = \dfrac{2aD}{h}$ donne $\dfrac{h\,q^*}{2} = \dfrac{aD}{q^*}$. Notons $c$ cette valeur commune : le coût minimal est $2c$.

Une formule robuste. Si l'on commande $\lambda q^*$ au lieu de $q^*$ (avec $\lambda > 0$), le coût devient $\dfrac{c}{\lambda} + c\,\lambda = c\left(\lambda + \dfrac{1}{\lambda}\right)$. Pour $\lambda = 2$ ou $\lambda = \dfrac{1}{2}$, on obtient $2{,}5\,c$, soit seulement $25\,\%$ de plus que le minimum $2c$ : se tromper du simple au double coûte relativement peu. C'est ce que montrait le tableau (750 € au lieu de 600 €).

Le tableur ci-dessous calcule le coût pour différentes quantités commandées. On peut changer la demande $D$ (cellule B2), le coût d'une commande $a$ (B3) et le coût de stockage $h$ (B4), avec un point décimal. La cellule B5 calcule $q^*$ avec la formule =(2*B3*B2/B4)**0.5, où **0.5 signifie « puissance $0{,}5$ », c'est-à-dire racine carrée.

Une entreprise doit affecter trois livreurs A, B et C à trois tournées T1, T2 et T3, un livreur par tournée. Selon leur domicile et leur véhicule, ils ne mettent pas le même temps. Les durées, en heures, sont :

On veut rendre minimale la durée totale. Combien d'affectations possibles ? On choisit la tournée de A ($3$ choix), puis celle de B parmi les deux restantes ($2$ choix), et C prend la dernière ($1$ choix) : $3 \times 2 \times 1 = 6$ affectations. Énumérons-les :

La meilleure affectation est A sur T2, B sur T1, C sur T3, pour $12$ heures.

Une idée naturelle : choisir d'abord le plus petit temps du tableau, puis le plus petit parmi ceux qui restent possibles, et ainsi de suite. C'est un algorithme glouton : à chaque étape, il prend ce qui semble le meilleur sur le moment, sans revenir en arrière.

• Le plus petit temps est $2$ : A sur T1.
• Parmi B et C, sur T2 et T3, le plus petit temps est $6$ : C sur T3.
• Il reste B sur T2, $7$ heures.

Total : $15$ heures, alors que l'optimum est $12$ heures. En prenant tout de suite la meilleure case pour A, l'algorithme a privé B de T1, où B était aussi très rapide. L'algorithme glouton est rapide, mais il ne garantit pas l'optimum.

Avec $n$ livreurs et $n$ tournées, le même raisonnement donne $n \times (n-1) \times \cdots \times 1$ affectations : c'est la factorielle de $n$, notée $n!$.

Un ordinateur qui examinerait un milliard d'affectations par seconde mettrait environ $77$ ans pour en examiner $2{,}4 \times 10^{18}$ (une année compte environ $3{,}15 \times 10^{7}$ secondes). La factorielle croît plus vite que n'importe quelle suite géométrique ; démontrons-le pour la raison $2$.

Essayer toutes les possibilités devient vite impossible : c'est l'explosion combinatoire. Pour l'affectation, il existe heureusement une méthode exacte et rapide, la méthode hongroise, publiée par Harold Kuhn en 1955, dont le nombre d'opérations croît seulement comme $n^3$. Pour d'autres problèmes, comme celui du voyageur de commerce (trouver le plus court circuit passant par $n$ villes), on ne connaît aucune méthode exacte rapide, et l'on se contente de bonnes solutions approchées, par exemple avec les algorithmes présentés dans le texte Les algorithmes génétiques.