Recherche opérationnelle : quatre portraits, des graphes au vote

Intervenant 10:00

Bienvenue dans le podcast du magazine Tangente.

Intervenant 20:03

Absolument, on est ravis d'être

Intervenant 10:05

là. Et je souhaite vraiment la bienvenue à quiconque nous écoute aujourd'hui pour cette nouvelle exploration. Alors, au programme, on va parler, accroche-toi bien, d'un immigré russe devenu bûcheron dans l'Oregon. Rien que ça. Oui, rien que ça. Et aussi d'une insulte, une vraie insulte hurlée en plein milieu d'un congrès scientifique ultra sérieux. Et surtout, on va voir comment ces événements totalement improbables ont façonné une espèce de formule secrète. La

Intervenant 20:33

fameuse formule.

Intervenant 10:35

C'est ça. La formule qui livre nos colis, qui gère nos réseaux électriques et qui pourrait même décider de nos élections présidentielles. Donc cette plongée au cœur des mathématiques s'annonce vraiment fascinante. On va décortiquer ce qu'on appelle la recherche opérationnelle.

Intervenant 20:50

La RO pour les intimes.

Intervenant 10:52

Voilà, la RO. Un truc qui a l'air super abstrait sur le papier, mais qui est en réalité la machinerie complètement cachée de notre monde moderne.

Intervenant 21:00

Et c'est vraiment toute la magie de cette discipline en fait. La recherche opérationnelle, si on doit la définir simplement, c'est la science absolue de la prise de décision et de l'optimisation.

Intervenant 11:11

Optimiser à fond quoi.

Intervenant 21:12

Exactement. Et l'objectif de notre discussion d'aujourd'hui, en s'appuyant sur un article passionnant qui retrace un peu l'histoire des grands noms de ce domaine, c'est de comprendre comment les maths sont passées de la résolution de petites énigmes plaisantes à la maîtrise totale des gigantesques systèmes logistiques mondiaux.

Intervenant 11:30

C'est un sacré bond en avant.

Intervenant 21:31

Ah oui, complètement. Et derrière cette transformation, on trouve des esprits brillants, des vrais rebelles même, qui ont totalement redessiné la frontière entre ce qui est possible et ce qui est impossible.

Intervenant 11:42

Justement, pour comprendre d'où vient cette science, je crois qu'il faut remonter un peu dans le temps, aux années qui précèdent la Seconde Guerre mondiale. Et l'histoire démarre d'une façon assez incroyable avec un certain Tobias Danzig.

Intervenant 21:53

L'histoire de Danzig, elle est fabuleuse.

Intervenant 11:55

C'est digne d'un film. C'est un immigré russe qui fuit son pays au début du 20e siècle. Il arrive aux États-Unis et il finit par travailler comme bûcheron dans l'Oregon.

Intervenant 22:04

Un bûcheron mathématicien.

Intervenant 12:06

C'est ça. Parce que ce qui est captivant, c'est que cet homme avait vraiment les mathématiques dans le sang. Donc, après des journées éreintantes à abattre des arbres, il allait s'asseoir dans un petit café du coin pour noircir des carnets entiers d'équations.

Intervenant 22:18

La passion pure quoi !

Intervenant 12:20

Ouais, la passion absolue. Et un jour, un client curieux remarque ces gribouillis super complexes. Il entame la conversation et figure-toi qu'il finit par l'aider à retrouver une place de mathématicien professionnel.

Intervenant 22:30

Heureusement pour nous d'ailleurs !

Intervenant 12:32

Clairement. Et Tobias Danzig aura plus tard un fils qu'il va nommer George Bernard, en hommage au dramaturge George Bernard Shaw, et fait ce fils qui va mais littéralement changer la face du monde.

Intervenant 22:42

Ah, ça on peut le dire. L'héritage de George Bernard Danzig est juste monumental. En fait, au moment où la Seconde Guerre mondiale éclate, il vient tout juste d'obtenir ses diplômes et il rejoint leurs forces américaines.

Intervenant 12:54

D'accord.

Intervenant 22:55

Et c'est là que l'Operations Research, la fameuse recherche pour les opérations militaires, ça prend tout son sens. L'armée américaine se retrouve face à un casse-tête gigantesque.

Intervenant 13:06

Ouais, la logistique à l'échelle mondiale j'imagine.

Intervenant 23:08

Exactement. Comment déployer des dizaines de milliers de soldats, acheminer des vivres, répartir le carburant de la manière la plus efficace possible alors que les ressources sont strictement limitées ? Il fallait vraiment mathématiser la logistique. Et donc, après la guerre, en 1947 très précisément, Danzig publie une invention qui va révolutionner l'industrie entière. La méthode simplex.

Intervenant 13:34

Pour que notre audience visualise bien, ça répond à ce qu'on appelle un problème de programmation linéaire. Pour imager un peu le truc, on peut penser à la préparation d'une valise quand on part en voyage.

Intervenant 23:45

Oui, très bonne analogie.

Intervenant 13:46

Voilà, on a un but précis qui est de maximiser la valeur ou l'utilité des objets qu'on met dedans sous des contraintes très strictes qui ne se négocient absolument pas. Genre le poids maximum autorisé par la compagnie aérienne ou la taille de la valise.

Intervenant 23:59

C'est exactement ça.

Intervenant 14:01

Mais ça, bon, c'est le problème. Comment ça marche ? La solution simplex ? Comment la méthode simplex de Danzig s'y prend concrètement pour trouver la valise parfaite sans avoir à essayer les combinaisons une par une ? Ce qui prendrait des années.

Intervenant 24:14

C'est là qu'intervient le génie géométrique de Danzig. Plutôt que de voir des bêtes listes de nombres, il se dit qu'il faut visualiser le problème comme une forme géométrique en plusieurs dimensions. C'est ce qu'on appelle un polyèdre.

Intervenant 14:26

Ok, un polyèdre ?

Intervenant 24:27

Ouais. Imaginons qu'on se trouve sur une montagne géométrique, tu vois, mais on a les yeux bandés. Chaque sommet de cette montagne, ça correspond à une solution possible pour notre valise. D'accord. Le sommet le plus haut de tous, c'est la solution optimale, la valise absolument parfaite. Et la méthode Semplex, elle nous dit juste ça. On se place sur un sommet au hasard, on tâte un peu avec notre pied les arêtes qui partent de ce sommet, on choisit une arête qui monte et on marche le long de cette arête jusqu'au sommet suivant.

Intervenant 14:55

Et on recommence, c'est ça ?

Intervenant 24:56

C'est ça. On recommence, on choisit une nouvelle arête qui monte, et ainsi de suite, jusqu'à ce qu'on ne puisse plus monter. Mais

Intervenant 15:01

attends, si on a les yeux bandés sur cette montagne mathématique, comment on sait qu'on n'est pas juste arrivé sur un petit sommet secondaire, genre un faux plat, et qu'il n'y a pas une montagne beaucoup plus haute juste à côté ?

Intervenant 25:13

Ah ! C'est la question centrale de l'optimisation, ça. Et la réponse, elle réside dans la nature même des programmes linéaires. En fait, ils forment toujours des polyèdres convexes.

Intervenant 15:24

Convexe, c'est-à-dire ?

Intervenant 25:26

Pour faire simple, une forme convexe, ça ne possède aucun creux ni de faux sommets. Ça ressemble à un diamant parfaitement taillé où tout converge vers une seule et unique pointe maximale.

Intervenant 15:37

Oh, d'accord.

Intervenant 25:39

Donc, avec le simplex, à la seconde où tu te trouves sur un sommet et que toutes les arêtes autour de toi redescendent, tu as la preuve mathématique absolue et irréfutable que tu es au sommet de la montagne. On ne suppose pas qu'on a fait de notre mieux. On certifie purement et simplement qu'il est impossible de faire mieux.

Intervenant 15:58

C'est vertigineux quand on y pense. Une garantie absolue. Et avec l'arrivée des tout premiers ordinateurs, j'imagine que cet algorithme, il a dû transformer des pans entiers de l'industrie. On l'a vu appliquer à l'agriculture pour savoir quoi planter, à l'énergie et évidemment au transport routier.

Intervenant 26:15

Évidemment, oui.

Intervenant 16:16

D'ailleurs, Danzig s'est attaqué au célèbre problème du voyageur de commerce, c'est-à-dire trouver le trajet le plus court pour visiter plein de villes et revenir au point de départ sans repasser deux fois au même endroit. Et il a réussi à calculer le trajet optimal pour les 48 États américains.

Intervenant 26:31

C'était un exploit colossal pour l'époque.

Intervenant 16:34

Bah oui.