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 Universiteit van Berkeley, twee opgaven van het bord overschreef, in de veronderstelling dat het een huiswerkopdracht was. Hij vond het 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 zou de basis vormen voor zijn proefschrift en, decennia later, 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 verstandige toewijzing van beperkte middelen. Maar in tegenstelling tot eerdere oorlogen was dit conflict werkelijk van mondiale omvang en werd het voor een groot deel 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 bedenken 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 schoolbordproblemen.
Bijna 80 jaar later is de simplex-methode nog steeds een van de meest gebruikte hulpmiddelen wanneer er onder complexe beperkingen een logistieke of supply chain-beslissing moet worden genomen. Het is efficiënt en het werkt. “Het is altijd snel gegaan, 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 een merkwaardige eigenschap die lange tijd een schaduw heeft geworpen op de methode van Dantzig. In 1972 bewezen wiskundigen dat de tijd die nodig is om een taak te voltooien exponentieel kan stijgen naarmate het aantal beperkingen toeneemt. Dus hoe snel de methode in de praktijk ook mag zijn, theoretische analyses hebben consequent worst-case scenario’s opgeleverd 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 in een nieuw 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 aangedragen waarom de exponentiële looptijden waar al lang voor gevreesd werd, in de praktijk niet werkelijkheid worden. Het werk, dat voortbouwt op a mijlpaal resultaat uit 2001 door Daniël Spielman En Shang-Hua Tengis “briljant (en) mooi”, aldus Teng.
“Het is zeer indrukwekkend technisch werk, dat op meesterlijke wijze veel van de ideeën combineert die in eerdere onderzoekslijnen zijn ontwikkeld, (terwijl er een aantal echt leuke nieuwe technische ideeën aan 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 aan te pakken: stel dat een meubelbedrijf kasten, bedden en stoelen maakt. Toevallig is elke kast 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 A, BEn C om de hoeveelheid geproduceerd meubilair weer te geven, zouden we zeggen dat de totale winst evenredig is met 3A + 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. Laten we zeggen dat het bedrijf maximaal 50 artikelen per maand kan produceren A + B + C is kleiner dan of gelijk aan 50. Kasten zijn moeilijker te maken – er kunnen er niet meer dan 20 worden geproduceerd – dus A 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 – hoewel er vaak veel meer variabelen bij betrokken zijn – in een meetkundig probleem. Stel je voor dat je onze beperkingen in kaart brengt A, B En C in drie dimensies. Als A kleiner is dan of gelijk is aan 20, kunnen we ons op een driedimensionale grafiek een vlak voorstellen dat loodrecht staat op de A as, er doorheen snijdend A = 20. We zouden 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.
