Originele versie van dit verhaal verscheen erin Kuanta-tijdschrift.
In 1939, nadat hij te laat was aangekomen bij een cursus statistiek aan de Universiteit van Berkeley, kopieerde George Dantzig – een eerstejaarsstudent – twee opgaven van het bord, in de veronderstelling dat het huiswerk was. Hij vond zijn huiswerk ‘moeilijker te maken dan normaal’, vertelde 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 werd de basis van 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 wiskundeadviseur bij de nieuw gevormde Amerikaanse luchtmacht. Zoals bij alle moderne oorlogen hing de uitkomst van de Tweede Wereldoorlog af van de oordeelkundige toewijzing van beperkte middelen. Maar in tegenstelling tot eerdere oorlogen was dit conflict werkelijk mondiaal van aard en werd het grotendeels door industriële macht gewonnen. De VS zouden meer tanks, vliegdekschepen en bommenwerpers kunnen produceren dan hun vijanden. Dit wetende, zijn legers vooral geïnteresseerd in optimalisatieproblemen – dat wil zeggen, hoe ze beperkte middelen strategisch kunnen toewijzen in situaties waarbij honderden of duizenden variabelen betrokken kunnen 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 gebruik maakte van verschillende wiskundige technieken die hij had ontwikkeld bij het oplossen van zijn schoolbordprobleem bijna tien jaar eerder.
Bijna 80 jaar later is de simplex-methode nog steeds een van de meest gebruikte hulpmiddelen wanneer logistieke of supply chain-beslissingen onder complexe omstandigheden moeten worden genomen. Het is efficiënt en het werkt. ‘Hij liep altijd snel, en niemand heeft hem ooit niet snel gezien’, zei hij Sophie Huiberts van het Franse Nationale Centrum voor Wetenschappelijk Onderzoek (CNRS).
Tegelijkertijd is er een vreemde eigenschap die Dantzigs methode al lang achtervolgt. In 1972 bewezen wiskundigen dat de tijd die nodig is om een taak te voltooien exponentieel kan toenemen met het aantal obstakels. Dus hoe snel deze methode ook in de praktijk wordt gebracht, de theoretische analyse biedt consequent worst-case scenario’s die impliceren dat het exponentieel langer zou kunnen duren. Voor de simplex-methode werken “onze traditionele tools voor het bestuderen van algoritmen niet”, zei Huiberts.
Maar op een nieuwe manier papier die in december zal worden gepresenteerd op de Foundations of Computer Science-conferentie, 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 een theoretische reden gegeven waarom de lang gevreesde exponentiële looptijd in de praktijk niet werkelijkheid wordt. Werk gebouwd op a belangrijke resultaten uit 2001 door Daniël Spielman En Shang-Hua Tengis “briljant (en) mooi”, aldus Teng.
“Dit is een zeer indrukwekkend technisch werk, dat op deskundige wijze veel van de ideeën combineert die in eerder onderzoek zijn ontwikkeld, (terwijl er enkele echt goede nieuwe technische ideeën aan worden toegevoegd), “ zei Laszlo Vegheen wiskundige aan de Universiteit van Bonn die niet bij deze inspanning betrokken was.
Optimale geometrie
De simplexmethode is ontworpen om een groep 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, gebruik dan A, BEn C om de hoeveelheid geproduceerd meubilair weer te geven, zeggen we dat de totale winst evenredig is met 3A + 2B + C.
Om de winst te maximaliseren, hoeveel van elk goed moet het bedrijf produceren? Het antwoord hangt af van de obstakels waarmee u te maken krijgt. Laten we zeggen dat een bedrijf maximaal 50 artikelen per maand kan produceren A + B + C minder dan of gelijk aan 50. Kasten zijn moeilijker te maken – er kunnen er niet meer dan 20 worden geproduceerd – dus A minder dan of gelijk aan 20. Voor stoelen is speciaal hout nodig en de voorraad is beperkt C moet kleiner zijn dan 24.
De simplexmethode verandert dit soort situaties – hoewel er vaak meer variabelen bij betrokken zijn – in een geometrisch probleem. Stel je voor dat je onze beperkingen in kaart brengt A, B En C in drie dimensies. Als A kleiner dan of gelijk aan 20, kunnen we ons een vlak in een driedimensionale grafiek voorstellen dat loodrecht op staat A as, dwars doorsnijdend A = 20. We zullen bepalen dat onze oplossing op of onder dat vlak moet liggen. Op dezelfde manier kunnen we beperkingen creëren die verband houden met andere beperkingen. Wanneer ze worden gecombineerd, kunnen deze grenzen de ruimte verdelen in complexe driedimensionale vormen die veelvlakken worden genoemd.
