Lineêre programmering

Lineêre programmering (LP) is 'n studieveld in operasionele navorsing.

Die studieveld fokus op 'n wiskundige probleem wat bestaan uit 'n lineêre funksie wat gemaksimeer (of geminimeer) moet word onderhewig aan 'n aantal lineêre ongelykhede. Die funksie heet "die doelfunksie" en die ongelykhede word "die beperkings" genoem. In die algemene probleem is daar ook "tekenvereistes" wat vereis dat die veranderlikes almal nie-negatief moet wees.

Lineêre programmering is die breinkind van George Dantzig wat gedurende die Tweede Wêreldoorlog sekere logistiese probleme uitgedruk het as 'n lineêre funksie (die doelfunksie) wat geoptimeer moet word onderhewig aan 'n aantal lineêre beperkings. Hy was skynbaar foutiewelik onder die indruk dat die meerdimensionele ruimte wat deur die beperkings geskep word 'n meetkundige figuur bekend as 'n simpleks vorm en het sy oplossingsprosedure daarna vernoem; die simpleksmetode.

Lineêre programmering is een van die eerste misleidende benamings wat sedertdien gereeld in die tegnologie gesien word. By die eerste oogopslag dink mense dat lineêre programmering (LP) 'n vorm van (of soort) rekenaarprogrammering is. In werklikheid verwys die woord programmering na die proses om 'n program van aksie te vind. Die simpleksmetode het niks met simplekse te doen nie en LP het niks met rekenaarprogrammering uit te waai nie. Alles vreeslik verwarrend!

Die simpleksmetode en uitbreidings en verbeterings daarop was vir baie jare die enigste oplossingsbenadering tot LP-probleme. Die klassifisering van probleme volgens hulle oplossingsmoeilikheidsgraad of kompleksiteit en die opvolgende klassifisering van LP-probleme as behorende tot die moeilikste groep, het die aansporing tot nuwe benaderings verskaf. In 1979(?) het die Rus Khachiyan die eerste werklik nuwe benadering voorgestel wat dan ook LP uit die moeilikste kategorie uitgehaal het deur aan te toon dat LP-probleme opgelos kan word in polinoomtyd. In 1984 het Karmarkar 'n meer doeltreffende metode gevind.