Lineair programmeren

In de wiskunde, meer speciaal in het operationeel onderzoek, of Engels: OR voor Operations Research, is lineair programmeren of lineaire programmering een methode voor het oplossen van zogenaamde lineaire programmeringsproblemen, kortweg LP-problemen. Dat zijn optimaliseringsproblemen waarin de doelfunctie en de randvoorwaarden alle lineair zijn.

Voorbeeld met twee variabelen, dat zijn er in de praktijk meer. De voorwaarden bepalen het convexe toegestane gebied. De doelfunctie wordt pas hierna ingevoerd.

Programmering moet daarbij niet in de zin van een computerprogramma worden opgevat, maar in de betekenis van planning. De naam werd in het midden van de jaren 40 ingevoerd door een van de grondleggers van de lineaire programmering, George Dantzig, lang voor de computer voor de berekeningen bij lineair programmeren werd ingezet.

Lineaire programmering is om verscheidene redenen een belangrijke discipline in de optimalisering. Veel praktische problemen in wetenschappelijk onderzoek kunnen als lineaire programmeringsproblemen worden uitgedrukt. Bepaalde speciale gevallen van lineaire programmering, zoals de problemen van stromen in een netwerk, worden genoeg van belang geacht om onderzoek naar gespecialiseerde algoritmen voor hun oplossing te doen. De werking van een aantal algoritmen voor andere soorten optimaliseringsproblemen berust erop deelproblemen als LP-problemen op te lossen. De ideeën over lineaire programmering hebben in de loop van de tijd veel aan de optimaliseringstheorie voortgebracht, zoals de begrippen dualiteit, decompositie en convex.

Geschiedenis

De Sovjet-Russische wiskundige Leonid Kantorovitsj besprak in 1939 in zijn boek 'Wiskundige methoden in de organisatie en planning van de productie' voor het eerst de methode van de lineaire programmering. Gezien het enorme belang van de planeconomie in de Sovjet-Unie is het geen verrassing dat de oorsprong van deze tak van wiskunde in Rusland ligt. Kantorovitsj kreeg mede voor dit werk in 1975 de Nobelprijs in de Economie. De Amerikaan Frank L. Hitchcock kwam kort daarna met een artikel over een transportprobleem, maar het werk van beide mannen kreeg, zeker in het westen, weinig aandacht.

George Dantzig begreep halverwege de jaren veertig dat veel praktische restricties zich door lineaire ongelijkheden laten beschrijven, en verving de tot dan toe gebruikte vuistregels voor het oplossen van planningsproblemen door een lineaire doelfunctie. Daarmee introduceerde hij een duidelijke scheiding tussen het doel van de optimalisatie en de middelen om het planningsprobleem op te lossen. De doorbraak kwam in 1947, toen Dantzig zijn werk over de simplexmethode publiceerde. Dit algoritme is nog steeds een van de meest gebruikte middelen om tot een oplossing voor een 'linear programma' te komen. Het Amerikaanse leger, speciaal de luchtmacht, pikte het werk van Dantzig snel op, als middel om militaire inzet en de logistiek daar omheen verder te verbeteren. Hij ontwikkelde in de jaren daarna, samen met onder andere John von Neumann, Oskar Morgenstern en Tjalling Koopmans, de theorie verder en zij legden verschillende verbanden met de speltheorie.

Theorie

De lineaire beperkingen, de randvoorwaarden, bepalen een veelvlak, dat het toegelaten gebied wordt genoemd. Het toegelaten gebied is convex. Er komt in de optimale oplossing altijd een hoekpunt van dit toegelaten gebied voor, omdat de doelstellingsfunctie ook lineair is. De optimale oplossing kan ook het lijnstuk tussen twee hoekpunten van het toegestane gebied zijn.

Er zijn twee situaties waarin geen optimale oplossing kan worden gevonden. Ten eerste is het toegestane gebied leeg, als de randvoorwaarden elkaar tegenspreken. Ten tweede kan het veelvlak in de richting van de doelstellingsfunctie onbegrensd zijn, bijvoorbeeld: maximaliseer $x_{1}+3\ x_{2}$ met voorwaarden $x_{1}\geq 0$, $x_{2}\geq 0$ en $x_{1}+x_{2}\geq 10$, waarbij er geen optimale oplossing is, aangezien er oplossingen met willekeurig hoge waarden van de doelstellingsfunctie kunnen worden geconstrueerd.

Behalve bij deze twee gevallen is er altijd een hoekpunt waarin een optimum wordt bereikt. Nochtans is het optimum niet noodzakelijke uniek: het is mogelijk een reeks optimale oplossingen te hebben die een rand of een vlak van het veelvlak bestrijken.

Voorbeeld

Hier is een voorbeeld van een lineair programmeringsprobleem. Een landbouwer heeft een stuk landbouwgrond, zeg $A$ vierkante kilometer groot. Hij kan er tarwe, gerst of een combinatie van beide op verbouwen. Tarwe brengt per oppervlakte-eenheid een bedrag $S_{1}$ op en gerst een bedrag $S_{2}$. Het lijkt lucratief om alleen het gewas met de hoogste opbrengst te gaan verbouwen, maar er zijn beperkingen aan de verbouw vanwege de benodigde kunstmest en insecticide. De benodigde hoeveelheden daarvan per oppervlakte-eenheid zijn voor de beide gewassen verschillend, en wel voor tarwe ($F_{1},P_{1}$) en voor gerst ($F_{2},P_{2}$). De landbouwer heeft een beperkte toelaatbare hoeveelheid $F$ meststof en $P$ insecticide, die kunnen worden gebruikt. Als we de oppervlakten, die met tarwe en gerst worden beplant, met respectievelijk $x_{1}$ en $x_{2}$ aanduiden, kan de optimale verdeling van het beschikbare oppervlak aan landbouwgrond over de beide gewassen als lineair programmeringsprobleem worden uitgedrukt:

maximaliseer	$\,S_{1}x_{1}+S_{2}x_{2}$	de winst
met voorwaarde	$\,x_{1}+x_{2}\leq A$	beperking op totale gebied
	$\,F_{1}x_{1}+F_{2}x_{2}\leq F$	beperking op meststof
	$\,P_{1}x_{1}+P_{2}x_{2}\leq P$	beperking op insecticide
	$\,x_{1}\geq 0,\,x_{2}\geq 0$	kan geen negatief gebied beplanten

Algoritmen

Het simplexalgoritme lost LP-problemen op door een aannemelijke oplossing te construeren bij een hoekpunt van het veelvlak en dan langs randen van het veelvlak naar hoekpunten te lopen met opeenvolgend hogere waarden van de doelstellingsfunctie tot het optimum wordt bereikt. Hoewel dit algoritme in de praktijk vrij efficiënt is en er kan worden gewaarborgd dat het globale optimum wordt gevonden als bepaalde voorzorgsmaatregelen tegen eindeloze lussen worden genomen, kost het in het ergste geval veel tijd: het is mogelijk om een lineair programmeringsprobleem te construeren waarvoor de simplexmethode een aantal stappen neemt dat exponentieel met betrekking tot de probleemgrootte is.

Narenda Karmarkar ontwikkelde in 1984 de 'projecterende methode'. Dit is het eerste algoritme dat goed presteert, zowel in theorie en in de praktijk. Het behoort tot de inwendige puntmethode.

In het algemeen worden LP-randvoorwaardevervullers gebruikt om diverse problemen in de industrie mee te optimaliseren, zoals van stromen in vervoersnetwerken.

Het kan voorkomen dat de meeste variabele waarden in een oplossing gelijk aan 0 zijn. Het kan in zo'n geval efficiënt zijn om de variabelen niet in eerste instantie allemaal in het probleem op te nemen, maar ze pas toe te voegen als ze interessant blijken te zijn. Algoritmes die dit principe toepassen maken gebruik van vertraagde kolomgeneratie. Vaak worden nieuwe variabelen gezocht door middel van een deelprobleem wat doorgaans het 'pricing probleem' wordt genoemd. Hierbij wordt het pricing probleem door de schaduwprijzen gestuurd, ook wel de dualen, van de huidige oplossing. Deze schaduwprijzen bestaan zolang er in het hoofdprobleem geen voorwaarden voorkomen dat variabelen een geheel getal moeten zijn.

Geheeltallig lineair programmeren

Als wordt vereist dat alle onbekende variabelen een geheel getal moeten zijn, wordt het probleem een geheeltallig lineair programmeringsprobleem genoemd. Deze problemen zijn in het algemeen moeilijker op te lossen dan LP-problemen. Het 0-1 probleem is een speciaal geval van het geheeltallig lineair programmeringsprobleem, waarbij de variabelen alleen de waarden 0 of 1 mogen aannemen. Als slechts wordt vereist dat enkele onbekende variabelen gehele getallen zijn, dan wordt het probleem een gemengd geheeltallig programmeringsprobleem genoemd.

Soms wordt eerst de LP-relaxatie opgelost en gekeken of die een toegelaten oplossing oplevert voor het oorspronkelijke probleem. Bij de LP-relaxatie wordt de eis van dat de variabelen geheel moeten zijn weggelaten. In het geval dat de voorwaardenmatrix totaal unimodulair is zal de oplossing van de LP-relaxatie geheeltallig zijn. Als dit niet het geval is, geeft de LP-relaxatie een oplossing met alleen gehele getallen, waarmee de optimale oplossing voor het geheeltallige lineaire programmeringsprobleem is gevonden. Als er in de LP-relaxatie breuken voorkomen, zijn er twee belangrijke technieken waarmee de oplossing geheeltallig kan worden gemaakt. Zo is het mogelijk om extra voorwaarden aan het probleem toe te voegen waarmee oplossingen waarin breuken voorkomen uit de toegelaten oplossingsruimte worden geëlimineerd. Deze techniek wordt wel cutting planes genoemd. Een andere aanpak is het gebruik van branch and bound, waarbij de waarde van de LP-relaxatie als natuurlijke onder- of bovengrens kan worden gebruikt.

Voetnoten