Lineair programmeren

In de lineaire programmering wordt de set van toegestane punten (blauw) begrensd door lineaire vergelijkingen (Hypervlakken (groen)).

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

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

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. Historisch hebben de ideeën over lineaire programmering veel centrale concepten van de optimaliseringstheorie voortgebracht, zoals dualiteit, decompositie en het belang van convexiteit en zijn generalisaties.

Geschiedenis

De methode van de lineaire programmering werd in 1939 voor het eerst door de Sovjet-Russische wiskundige Leonid Kantorovitsj besproken in zijn boek "Wiskundige methoden in de organisatie en planning van de productie“. Gezien het enorme belang van de planeconomie in de Sovjet-Unie komt het niet als een verrassing dat de oorsprong van deze tak van wiskunde uit Rusland komt. Mede voor dit werk kreeg Kantorovitsj in 1975 de Nobelprijs in de Economie. Kort daarna kwam de Amerikaan, Frank L. Hitchcock met een artikel over een transportprobleem. Het werk van beide mannen kreeg, zeker in het westen, echter weinig aandacht.

Halverwege de jaren veertig begreep George Dantzig, dat veel praktische restricties zich door lineaire ongelijkheden laten beschrijven, en verving de tot daartoe 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 het simplexalgoritme publiceerde. Dit algoritme is heden ten dage 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 inzetten en de logistiek daar omheen verder te verbeteren. In de jaren daarna ontwikkelden Dantzig, John von Neumann, Oscar Morgenstern, Tjalling Koopmans en anderen de theorie verder en legden zij ook verbanden met de speltheorie.

Theorie

Geometrisch bepalen de lineaire beperkingen een convex veelvlak, dat het toegelaten gebied wordt genoemd. Aangezien de doelstellingsfunctie ook lineair is, zijn alle lokale optima automatisch globale optima. De lineaire doelstellingsfunctie impliceert ook dat een optimale oplossing slechts op een grenspunt van het uitvoerbare gebied kan voorkomen.

Er zijn twee situaties waarin geen optimale oplossing kan worden gevonden. Ten eerste, als de randvoorwaarden elkaar tegenspreken (bijvoorbeeld, x ≥ 2 en x ≤ 1), is het uitvoerbare gebied leeg, en er kan geen optimale oplossing zijn, aangezien er geen oplossingen zijn die aan alle voorwaarden voldoen.

Ten tweede kan het veelvlak in de richting van de doelstellingsfunctie onbegrensd zijn (bijvoorbeeld: maximaliseer x₁ + 3 x₂ met voorwaarden x₁ ≥ 0, x₂ ≥ 0, x₁ + x₂ ≥ 10), waarbij er geen optimale oplossing is aangezien de oplossingen met willekeurig hoge waarden van de doelstellingsfunctie kunnen worden geconstrueerd.

Behalve bij deze twee pathologische voorwaarden zal het optimum altijd in een hoekpunt van het veelvlak worden bereikt. Nochtans is het optimum niet noodzakelijke uniek: het is mogelijk om een reeks optimale oplossingen te hebben die een rand of een vlak van het veelvlak bestrijken, of zelfs het volledige veelvlak. (Deze laatste situatie zou voorkomen als de objectieve functie uniform gelijk aan nul was.)

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 aanduiden met respectievelijk $x_{1}$ en $x_{2}$, dan 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 te lopen naar hoekpunten met opeenvolgend hogere waarden van de doelstellingsfunctie tot het optimum wordt bereikt. Hoewel dit algoritme in de praktijk vrij efficiënt is en kan worden gewaarborgd dat het globale optimum gevonden wordt als bepaalde voorzorgsmaatregelen tegen eindeloze lussen worden genomen, heeft het in het ergste geval een slecht gedrag: het is mogelijk om een lineair programmeringsprobleem te construeren waarvoor de simplexmethode een aantal stappen neemt dat exponentieel met betrekking tot de probleemgrootte is.

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

In het algemeen worden LP-randvoorwaardevervullers gebruikt voor optimalisering van diverse problemen in de industrie, zoals optimalisering van stromen in vervoersnetwerken.

In sommige gevallen heeft het probleem een structuur waarbij de meerderheid van de variabelen waarde 0 zullen hebben in een oplossing. In zo'n geval kan het 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 gestuurd door de schaduwprijzen (ook wel de dualen) van de huidige oplossing. Deze schaduwprijzen bestaan zolang het hoofdprobleem geen geheeltalligheidsvoorwaarden bevat.

Geheeltallig lineair programmeren

Als wordt vereist dat de onbekende variabelen allen geheeltallig zijn, dan wordt het probleem een geheeltallig lineair programmeringsprobleem genoemd (IP of ILP, integer (linear) programming). In het algemeen zijn deze problemen 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 (in plaats van willekeurige gehele getallen). Als slechts vereist wordt dat enkele onbekende variabelen gehele getallen zijn, dan wordt het probleem een gemengd geheeltallig programmeringsprobleem genoemd (MIP, mixed integer programming).

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 geheeltalligheid van variabelen 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, kan de uitkomst van de LP-relaxatie bij toeval toch geheeltallig zijn, waarmee ook de optimale oplossing voor het geheeltallig probleem is gevonden. Als de oplossing van de LP-relaxatie fractioneel is, zijn er twee belangrijke technieken waarmee de oplossing geheeltallig gemaakt kan worden. Zo is het mogelijk om extra voorwaarden aan het probleem toe te voegen waarmee fractionele oplossingen uit de toegelaten oplossingsruimte worden gesneden (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 gebruikt kan worden.