Lineair programmeren

Van Wikipedia

In de wiskunde, meer speciaal in de Operationele 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 de grondlegger van lineaire programmereing Georg 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.

Inhoud 1 Voorbeeld 2 Theorie 3 Algoritmen 4 Geheeltallig lineair programmeren

[bewerk] 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₁ op en gerst een bedrag S₂. Het lijkt lucratief om alleen het gewas met de hoogste opbrenst 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₁,P₁) en voor gerst (F₂,P₂). 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₁ en x₂, dan kan de optimale verdeling van het beschikbare oppervlak aan landbouwgrond over de beide gewassen als lineair programmeringsprobleem worden uitgedrukt:

maximaliseer		(de winst)
met voorwaarde		(beperking op totale gebied)
		(beperking op meststof)
		(beperking op insecticide)
		(kan geen negatief gebied beplanten)

[bewerk] Theorie

Geometrisch bepalen de lineaire beperkingen een convex veelvlak, dat het uitvoerbare 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) dan 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 wordt 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.)

[bewerk] 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.

[bewerk] Geheeltallig lineair programmeren

Als wordt vereist dat de onbekende variabelen allen geheeltallig zijn, dan wordt het probleem een geheeltallig lineair programmeringsprobleem genoemd (IP). 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).

Een geavanceerd algoritme om grote geheeltallige lineaire programma's op te lossen is vertraagde kolomgeneratie.