Lineaire programmeerwiskunde

Lineair programmeren, wiskundige modelleringstechniek waarbij een lineaire functie wordt gemaximaliseerd of geminimaliseerd bij blootstelling aan verschillende beperkingen. Deze techniek is nuttig geweest voor het begeleiden van kwantitatieve beslissingen in bedrijfsplanning, industriële engineering en - in mindere mate - sociale en natuurwetenschappen.

optimalisatie: lineaire programmering

Hoewel lineair programmeren nu veel gebruikt om alledaagse beslissingsproblemen op te lossen, was het vóór 1947 relatief onbekend. Geen enkel werk van enige betekenis

De oplossing van een lineair programmeerprobleem reduceert tot het vinden van de optimale waarde (grootste of kleinste, afhankelijk van het probleem) van de lineaire uitdrukking (de objectieve functie genoemd)

onderhevig aan een reeks beperkingen uitgedrukt als ongelijkheden:

De a's, b's en c's zijn constanten die worden bepaald door de capaciteiten, behoeften, kosten, winsten en andere vereisten en beperkingen van het probleem. Uitgangspunt bij de toepassing van deze methode is dat de verschillende relaties tussen vraag en beschikbaarheid lineair zijn; dat wil zeggen, geen van de x _i wordt tot een andere macht verheven dan 1. Om de oplossing voor dit probleem te vinden, is het noodzakelijk om de oplossing van het systeem van lineaire ongelijkheden te vinden (dat wil zeggen, de reeks van n waarden van de variabelen x _i die tegelijkertijd aan alle ongelijkheden voldoet). De objectieve functie wordt vervolgens geëvalueerd door de waarden van de x _{i te vervangen} in de vergelijking die f definieert.

Toepassingen van de methode van lineaire programmering werden eind jaren dertig voor het eerst serieus uitgeprobeerd door de Sovjet-wiskundige Leonid Kantorovich en door de Amerikaanse econoom Wassily Leontief op het gebied van respectievelijk productieschema's en economie, maar hun werk werd decennia lang genegeerd. Tijdens de Tweede Wereldoorlog werd lineaire programmering op grote schaal gebruikt om transport, planning en toewijzing van middelen aan te pakken, onder voorbehoud van bepaalde beperkingen, zoals kosten en beschikbaarheid. Deze toepassingen hebben veel gedaan om de aanvaardbaarheid van deze methode vast te stellen, die in 1947 een verdere impuls kreeg met de introductie van de simplexmethode van de Amerikaanse wiskundige George Dantzig, die de oplossing van lineaire programmeerproblemen aanzienlijk vereenvoudigde.

Naarmate echter werd geprobeerd steeds complexere problemen met meer variabelen op te lossen, nam het aantal noodzakelijke bewerkingen exponentieel toe en overschreed het de rekencapaciteit van zelfs de krachtigste computers. Vervolgens ontdekte de Russische wiskundige Leonid Khachiyan in 1979 een polynoom-tijdalgoritme - waarbij het aantal computationele stappen groeit als een macht van het aantal variabelen in plaats van exponentieel - waardoor de oplossing van tot dusver ontoegankelijke problemen mogelijk werd. Het algoritme van Khachiyan (de ellipsoïde methode genoemd) was echter langzamer dan de simplex-methode wanneer het praktisch werd toegepast. In 1984 ontdekte de Indiase wiskundige Narendra Karmarkar een ander polynoom-tijdalgoritme, de inner point-methode, die competitief bleek te zijn met de simplex-methode.