PLNE : pourquoi arrondir vélos et tricycles peut échouer

Intervenant 10:00

Bienvenue dans le podcast du magazine Tangente. Salut à tous et préparez-vous parce qu'aujourd'hui on va vraiment s'attaquer à un sujet passionnant.

Intervenant 20:07

Oh que oui, bonjour. On va explorer un concept qui a l'air un peu abstrait comme ça, mais qui est en fait partout autour de nous.

Intervenant 10:15

Exactement. Alors imaginons un instant un super ordinateur, un truc immense, une machine capable de calculer le réseau électrique parfait pour un pays tout entier, et ça en une fraction de seconde.

Intervenant 20:27

Ouais, une bête de course

Intervenant 10:28

quoi. Voilà, on lui pose le problème, on appuie sur entrée et paf, la réponse optimale jaillit instantanément. Mais, et c'est là que ça devient fou, ajoutons une toute petite règle, une contrainte qui semble vraiment anodine. On stipule à cette machine qu'il est physiquement impossible de couper les câbles en deux, il faut utiliser des câbles entiers. Et là, soudainement, cet ordinateur surpuissant s'arrête, il ventile, il rame et il annonce qu'il lui faudra genre trois siècles pour trouver la réponse.

Intervenant 20:58

Et c'est un point de départ qui pose parfaitement le vertige de la situation. Derrière ce problème de câbles entiers, on touche à ce qu'on appelle la programmation linéaire en nombre entier.

Intervenant 11:08

La fameuse PLNE.

Intervenant 21:10

C'est ça. Alors c'est un terme qui peut sembler super froid, très académique de prime abord, mais c'est littéralement le moteur caché de toute notre logistique moderne. C'est l'architecture qui fait tourner les usines, les réseaux d'énergie, les transports maritimes, enfin bref, tout ce qui nécessite de prendre des décisions parfaites dans le monde physique.

Intervenant 31:27

Mais du coup, avant de comprendre pourquoi exiger des nombres entiers, ça provoque un tel naufrage temporel, il faut poser le décor. Il faut comprendre comment ça marche quand tout va bien.

Intervenant 21:38

Oui, il faut commencer par la programmation linéaire classique sans les entiers.

Intervenant 31:42

Bon, décortiquons tout ça. Prenons une usine classique, l'entreprise Laïvo par exemple, qui fabrique des produits laitiers, du yaourt et de la crème.

Intervenant 21:51

Un très bon exemple, très visuel.

Intervenant 31:53

Bah oui, le but du gérant, il est simple, il est basique, universel. Il veut maximiser son profit avant la fermeture annuelle, c'est tout.

Intervenant 22:01

Et pour ça, il a des données chiffrées très précises. La vente d'une tonne de yaourt, que nous appellerons la variable X1 pour les maths, ça lui rapporte 500 euros.

Intervenant 32:12

OK. X1, c'est 500 euros.

Intervenant 22:14

Voilà. Et la vente d'une tonne de crème fraîche, notre variable X2, lui rapporte 450 euros. L'objectif mathématique, ce qu'on appelle la fameuse fonction objectif, c'est tout simplement d'obtenir le chiffre le plus haut possible en combinant ces deux ventes.

Intervenant 32:31

C'est logique. Sauf que le monde physique impose des limites.

Intervenant 22:34

Toujours.

Intervenant 32:35

C'est comme une recette de cuisine à grande échelle, avec un budget temps et un espace de stockage hyper strict. Enfin, on ne peut pas produire à l'infini dans son jarrage quoi.

Intervenant 22:42

Non, malheureusement.

Intervenant 32:44

D'abord, il y a le temps. L'usine dispose de 60 heures de production au total. Fabriquer une tonne de yaourt, ça prend 6 heures. Une tonne de crème, 5 heures. Voilà, premier mur.

Intervenant 22:55

Premier mur très clair.

Intervenant 32:57

Ensuite, le stockage. Il y a quinze unités modulaires disponibles dans les frigos. Une tonne de yaourt prend une unité. Mais la crème est plus capricieuse. Elle en prend deux.

Intervenant 23:06

C'est ça. Et il y a une dernière contrainte, non ?

Intervenant 33:09

Exactement, le marché lui-même. Le gérant sait qu'il ne pourra pas écouler plus de huit tonnes de yaourt. Le marché est saturé au-delà.

Intervenant 23:15

Donc toutes ces contraintes, le temps, le frigo, les limites de vente, eh bien en mathématiques, elles se traduisent par des inéquations du premier degré.

Intervenant 33:23

Des inéquations, oui.

Intervenant 23:24

Oui. Et si on essaie de visualiser la chose pour nos auditeurs, c'est comme tracer des lignes sur un graphique géant.

Intervenant 33:31

Un graphique à deux dimensions, avec X1 et X2.

Intervenant 23:34

Exactement. Une ligne représente la limite des 60 heures, une autre la limite des 15 frigos, et ces lignes, elles se croient sur le graphique et elles finissent par enfermer une zone.

Intervenant 33:44

Une sorte de polygone en fait.

Intervenant 23:46

C'est ça, un polygone géométrique. Ce polygone, c'est ce qu'on appelle la région des solutions admissibles.

Intervenant 33:52

D'accord.

Intervenant 23:53

Chaque point à l'intérieur de cette forme géométrique est une combinaison possible de yaourt et de crème qui respecte absolument toutes les règles de l'usine qu'on vient de citer.

Intervenant 34:04

Sauf qu'on ne cherche pas juste une solution qui fonctionne, genre un point au hasard au milieu. On veut la solution qui rapporte le maximum d'argent possible. On veut vraiment le point en or.

Intervenant 24:14

Et c'est là qu'interviennent les algorithmes d'optimisation classiques. Et particulièrement un algorithme très célèbre, mentionné d'ailleurs dans le hors-série 72 de Tangente, qui s'appelle l'algorithme du simplex.

Intervenant 34:26

Ah, le fameux simplex.

Intervenant 24:28

Oui. Sans entrer dans la machinerie lourde de comment il est codé, le simplex part d'un coin de ce polygone et il glisse le long des bords.

Intervenant 34:36

Il se promène sur le contour, quoi.

Intervenant 24:38

Exactement, il vérifie chaque sommet de la forme géométrique jusqu'à trouver celui qui culmine le plus en haut en termes de profit. Et dans un problème de programmation linéaire dit continu, et bien cette recherche prend une fraction de millisecondes.

Intervenant 34:52

C'est instantané.

Intervenant 24:53

L'ordinateur trouve le sommet optimal quasi immédiatement.

Intervenant 34:57

Sauf que là, le résultat a de quoi faire un peu sourire. L'ordinateur, dans sa perfection théorique absolue, il annonce que le bénéfice maximal sera très exactement de 5142 euros et environ 85 centimes, ou plus précisément 6 septièmes d'euros.

Intervenant 25:12

C'est très précis.

Intervenant 35:14

Très. Et pour atteindre ce montant absurde, il ordonne aux gérants de produire très exactement 6 tonnes et 3 septièmes de yaourt et 4 tonnes et 2 septièmes de crème. Je vois mal un gérant mesurer des septièmes de tonne avec une balance de précision géante.

Intervenant 25:28

Ah mais figure-toi que dans l'industrie laitière, bah c'est faisable.

Intervenant 35:32

Vraiment ?

Intervenant 25:33

Bah oui, le yaourt c'est un fluide, la crème c'est malléable. C'est divisible à l'infini en fait. On peut techniquement peser 6 tonnes plus 428 kilos plus quelques grammes et arrêter la machine à ce moment précis.

Intervenant 35:48

Ah ouais, c'est vrai !

Intervenant 25:49

La réalité physique s'accommode parfaitement de la solution mathématique continue. On peut glisser doucement sur les bords de notre fameux polygone, parce que la matière glisse avec

Intervenant 36:00

nous. D'accord, ok. Le yaourt coule, c'est fluide. C'est là que ça devient vraiment intéressant. Parce que imaginons que notre usine là y vaut, du jour au lendemain, elle change totalement de modèle économique. Fini les laitages, place à la métallurgie lourde.

Intervenant 26:13

Oh, un virage radical !

Intervenant 36:15

Totalement ! L'usine fabrique désormais des vélos qui remplacent les yaourts et des tricycles qui remplacent la crème. Et par un miracle absolu de l'ingénierie, les temps de montage, l'espace dans les entrepôts et les bénéfices sont rigoureusement identiques.

Intervenant 26:29

Ah, pratique pour notre problème guéri !

Intervenant 36:32

N'est-ce pas ? Les équations n'ont pas changé d'une seule virgule. Le polygone mathématique sur le graphique, c'est exactement le même.

Intervenant 26:39

Le polygone est le même, oui. Mais la nature fondamentale de la matière qu'on manipule vient de muter.

Intervenant 36:45

Bah oui, un vélo ça coule pas. On peut pas descendre dans l'atelier, regarder le chef de production et lui dire « bon, l'ordinateur a parlé, produisez-moi six vélos entiers et trois septièmes d'un autre vélo ».

Intervenant 26:54

Ce serait absurde.

Intervenant 36:56

Qu'est-ce qu'on est censé livrer ? Un guidon, une pédale et un pneu. C'est n'importe quoi !