De originele versie van dit verhaal verscheen erin Quanta-tijdschrift.
Toen George Dantzig, een eerstejaars student, in 1939 te laat arriveerde voor zijn cursus statistiek aan de UC Berkeley, twee opgaven van het bord overschreef, in de veronderstelling dat het huiswerk was. Hij vond het huiswerk ‘moeilijker te maken dan normaal’, zei hij later, en verontschuldigde zich bij de professor omdat hij een paar extra dagen nodig had om het af te maken. Een paar weken later vertelde zijn professor hem dat hij twee beroemde openstaande problemen in de statistiek had opgelost. Dantzigs werk zou de basis vormen voor zijn proefschrift en decennia later de inspiratie voor de film Goede wil jacht.
Dantzig promoveerde in 1946, vlak na de Tweede Wereldoorlog, en werd al snel wiskundig adviseur van de nieuw gevormde Amerikaanse luchtmacht. Zoals bij alle moderne oorlogen hing de uitkomst van de Tweede Wereldoorlog af van de zorgvuldige toewijzing van beperkte middelen. Maar in tegenstelling tot eerdere oorlogen was dit conflict werkelijk mondiaal van aard en werd het grotendeels gewonnen door louter industriële macht. De VS zouden simpelweg meer tanks, vliegdekschepen en bommenwerpers kunnen produceren dan hun vijanden. Dit wetende, was het leger intens geïnteresseerd in optimalisatieproblemen – dat wil zeggen, hoe beperkte middelen strategisch konden worden toegewezen in situaties waarbij honderden of duizenden variabelen betrokken konden zijn.
De luchtmacht gaf Dantzig de opdracht nieuwe manieren te vinden om dit soort optimalisatieproblemen op te lossen. Als reactie hierop vond hij de simplex-methode uit, een algoritme dat voortbouwde op enkele van de wiskundige technieken die hij bijna tien jaar eerder had ontwikkeld bij het oplossen van zijn whiteboard-problemen.
Bijna 80 jaar later is de simplexmethode nog steeds een van de meest gebruikte hulpmiddelen bij het nemen van logistieke of supply chain-beslissingen onder complexe beperkingen. Het is effectief en het werkt. “Het is altijd snel geweest en niemand heeft gezien dat het niet snel was”, zei hij Sophie Huiberts van het Franse Nationale Centrum voor Wetenschappelijk Onderzoek (CNRS).
Tegelijkertijd is er sprake van een vreemde eigenschap die lange tijd een schaduw over Dantzigs methode heeft geworpen. In 1972 bewezen wiskundigen dat de tijd die nodig was om een taak te voltooien exponentieel kon toenemen met het aantal beperkingen. Dus hoe snel de methode in de praktijk ook mag zijn, theoretische analyses hebben consequent worst-case scenario’s opgeleverd die suggereren dat het exponentieel langer zou kunnen duren. Voor de simplex-methode “werken onze traditionele tools voor het bestuderen van algoritmen niet”, zei Huiberts.
Maar dan in een nieuwe papier dat in december wordt gepresenteerd op de Foundations of Computer Science-conferentie van Huiberts en Eleon Bacheen promovendus aan de Technische Universiteit van München lijkt dit probleem te hebben overwonnen. Ze hebben het algoritme sneller gemaakt en ook theoretische redenen gegeven waarom de lang gevreesde exponentiële looptijden in de praktijk niet werkelijkheid worden. Het werk dat voortbouwt op a mijlpaal resultaat vanaf 2001 Daniël Spielman En Shang-Hua Tengis “briljant (en) mooi”, aldus Teng.
“Het is zeer indrukwekkend technisch werk, waarbij op meesterlijke wijze veel van de ideeën die in eerdere onderzoekslijnen zijn ontwikkeld, worden gecombineerd (en tegelijkertijd een aantal echt goede nieuwe technische ideeën worden toegevoegd), ” zei László Vegheen wiskundige aan de Universiteit van Bonn die niet bij deze inspanning betrokken was.
Optimale geometrie
De simplexmethode is ontworpen om een aantal problemen als deze op te lossen: stel dat een meubelbedrijf kasten, bedden en stoelen maakt. Toevallig is elke kledingkast drie keer zo winstgevend als elke stoel, terwijl elk bed twee keer zo winstgevend is. Als we dit als een uitdrukking willen schrijven, gebruiken we -een, BEn C om de hoeveelheid geproduceerd meubilair weer te geven, zouden we zeggen dat de totale winst evenredig is met 3-een + 2B + C.
Om de winst te maximaliseren, hoeveel van elk item moet het bedrijf maken? Het antwoord hangt af van de beperkingen waarmee het wordt geconfronteerd. Stel dat het bedrijf dan maximaal 50 artikelen per maand kan leveren -een + B + C is kleiner dan of gelijk aan 50. Kasten zijn moeilijker te maken – er kunnen er niet meer dan 20 worden geproduceerd – dus -een is kleiner dan of gelijk aan 20. Voor stoelen is speciaal hout nodig, en dat is dus beperkt verkrijgbaar C moet kleiner zijn dan 24.
De simplexmethode verandert dit soort situaties – ook al zijn er vaak veel meer variabelen bij betrokken – in een meetkundig probleem. Stel je voor dat je onze beperkingen oplegt -een, B En C in drie dimensies. Als -een kleiner is dan of gelijk is aan 20, kunnen we ons een vlak in een driedimensionale grafiek voorstellen dat loodrecht op staat -een as die er doorheen snijdt -een = 20. We zullen bepalen dat onze oplossing ergens op of onder dat vlak moet liggen. Op dezelfde manier kunnen we grenzen creëren die verband houden met de andere beperkingen. Gecombineerd kunnen deze grenzen de ruimte verdelen in een complexe driedimensionale vorm die een veelvlak wordt genoemd.
