version originale de C’est l’histoire apparu Magazine Quanta.
En 1939, après être arrivé en retard à son cours de statistiques à l’UC Berkeley, George Dantzig, un étudiant diplômé de première année, a copié deux problèmes au tableau, pensant qu’il s’agissait d’un devoir. Il trouva les devoirs « plus difficiles que d’habitude », calcula-t-il plus tard, et s’excusa auprès du professeur d’avoir mis quelques jours de plus pour les terminer. Quelques semaines plus tard, son professeur lui annonce qu’il a résolu deux fameux problèmes ouverts de statistique. Le travail de Dantzig servira de base à sa thèse de doctorat et, des décennies plus tard, inspirera le film. Bonne chasse.
Dantzig a obtenu son doctorat en 1946, juste après la Seconde Guerre mondiale, et est rapidement devenu conseiller en mathématiques auprès de la nouvelle US Air Force. Comme toutes les guerres modernes, l’issue de la Seconde Guerre mondiale dépendait de l’allocation judicieuse de ressources limitées. Mais contrairement aux guerres précédentes, ce conflit était véritablement mondial et il a été gagné en grande partie grâce à la pure puissance industrielle. Les États-Unis ne peuvent construire que plus de chars, de porte-avions et de bombardiers que leurs ennemis. Sachant cela, l’armée s’intéressait énormément aux problèmes d’optimisation, c’est-à-dire à la manière d’allouer stratégiquement des ressources limitées dans des situations pouvant impliquer des centaines, voire des milliers de variables.
L’Armée de l’Air a chargé Dantzig de trouver de nouvelles façons de résoudre ces problèmes d’optimisation. En réponse, il inventa la méthode du simplexe, un algorithme qui s’appuyait sur des techniques mathématiques qu’il avait développées en résolvant ses problèmes au tableau près d’une décennie plus tôt.
Près de 80 ans plus tard, la méthode simplex reste l’un des outils les plus utilisés lorsque des décisions en matière de logistique ou de chaîne d’approvisionnement doivent être prises sous des contraintes complexes. C’est efficace et ça marche. “Ça va toujours vite, et personne ne l’a jamais vu aller aussi vite”, a déclaré Sophie Hubert Centre National de la Recherche Scientifique (CNRS).
En même temps, il existe une propriété curieuse qui a longtemps éclipsé la méthode de Dantzig. En 1972, des mathématiciens ont prouvé que le temps nécessaire pour accomplir une tâche peut croître de façon exponentielle avec le nombre de contraintes. Ainsi, aussi rapide que soit la méthode en pratique, les analyses théoriques suggèrent systématiquement les pires scénarios suggérant que cela pourrait prendre un temps exponentiellement plus long. Pour les méthodes simplexes, “nos outils traditionnels d’étude des algorithmes ne fonctionnent pas”, a déclaré Huberts.
Mais d’une manière nouvelle papier À présenter en décembre lors de la conférence Foundations of Computer Science, Huiberts et al. Ilion BachUn doctorant de l’Université technique de Munich semble avoir surmonté ce problème. Ils ont rendu l’algorithme plus rapide et ont également donné des raisons théoriques pour lesquelles les temps d’exécution exponentiels tant redoutés ne se matérialisent pas dans la pratique. œuvre, qui est construite sur un Des résultats marquants Depuis 2001 Daniel Spielman Et Shang-hua TengSelon Teng, “lumineux (et) beau”.
“Il s’agit d’un travail technique très impressionnant, qui intègre habilement de nombreuses idées développées dans des axes de recherche précédents, (tout en ajoutant) de nouvelles idées techniques vraiment intéressantes”, a déclaré Laszlo VegUn mathématicien de l’Université de Bonn qui n’a pas participé à l’effort.
Géométrie optimale
La méthode simplexe a été conçue pour résoudre une telle classe de problèmes : supposons qu’une entreprise de meubles fabrique des armoires, des lits et des chaises. Par coïncidence, chaque armoire est trois fois plus rentable que chaque chaise, tandis que chaque lit est deux fois plus rentable. Nous voulions l’écrire sous forme d’expression, en utilisant UN, bEt c Pour représenter la quantité de meubles produits, on dira que la marge brute est proportionnelle à 3UN + 2b + c.
Pour maximiser les profits, combien de chaque article l’entreprise doit-elle fabriquer ? La réponse dépend des contraintes auxquelles elle est confrontée. Disons que l’entreprise peut produire un maximum de 50 articles par mois UN + b + c Inférieur ou égal à 50. Les armoires sont difficiles à fabriquer – on ne peut pas en fabriquer plus de 20 – donc UN Inférieur ou égal à 20. Les chaises nécessitent du bois spécial et sont en quantité limitée, donc c Doit être inférieur à 24.
La méthode du simplexe transforme une telle situation – bien que souvent impliquant beaucoup plus de variables – en un problème de géométrie. Imaginez représenter graphiquement nos contraintes pour UN, b Et c En trois dimensions. si UN Inférieur ou égal à 20, on peut visualiser un plan dans un graphique tridimensionnel perpendiculaire UN axe, coupez-le à UN = 20. Nous stipulerons que notre solution doit se situer quelque part sur ou en dessous de ce plan. De même, nous pouvons créer des limites associées à d’autres contraintes. Combinées, ces limites peuvent diviser l’espace en une forme tridimensionnelle complexe appelée polyèdre.
