Lineair programmeren

Lineair programmeren — dit is een onderdeel van wiskundig programmeren en een veelgebruikte methode binnen operations research, gericht op de ontwikkeling van theorie en methoden voor het oplossen van vraagstukken over het vinden van een extremum (maximum of minimum) van een lineaire functie bij aanwezigheid van lineaire beperkingen.

Lineair programmeren (LP) is een van de krachtigste en meest toegepaste instrumenten voor het oplossen van optimalisatievraagstukken in economie, management, planning, logistiek en andere vakgebieden.

Onderwerp en doel

De hoofdtaak van lineair programmeren — het vinden van de beste (optimale) manier om beperkte middelen te verdelen teneinde een bepaald doel te bereiken, waarbij zowel het doel als de beperkingen op het gebruik van middelen door lineaire verbanden kunnen worden uitgedrukt.

• Lineair programmeren maakt het mogelijk praktische vraagstukken op te lossen, zoals:
• Optimale productieplanning.
• Optimalisatie van transportstromen (transportvraagstuk).
• Optimale verdeling van investeringen.
• Optimaal snijden van materialen. Het toewijzingsvraagstuk.

Wiskundige formulering van het LP-vraagstuk

Het standaard lineair programmeringsvraagstuk wordt als volgt geformuleerd:

Er moeten waarden worden gevonden voor de beslissingsvariabelen die een lineaire doelfunctie maximaliseren of minimaliseren. Daarbij worden aan de beslissingsvariabelen beperkingen opgelegd in de vorm van een stelsel van lineaire gelijkheden en/of lineaire ongelijkheden. In de regel wordt een niet-negativiteitsvoorwaarde voor de beslissingsvariabelen toegevoegd (hun waarden moeten groter dan of gelijk aan nul zijn), wat vaak wordt ingegeven door de fysische of economische betekenis van het vraagstuk.

Wiskundig betekent dit het werken met lineaire functies en stelsels van lineaire vergelijkingen/ongelijkheden.

Basisbegrippen van LP

• Beslissingsvariabelen (Stuurvariabelen): Grootheden waarvan de waarden tijdens het oplossen van het vraagstuk moeten worden bepaald (bijvoorbeeld productiehoeveelheden van verschillende producten, hoeveelheden middelen die naar verschillende doelen worden geleid).
• Doelfunctie: Een lineaire functie van de beslissingsvariabelen waarvan de waarde gemaximaliseerd of geminimaliseerd dient te worden. Zij drukt het doel van het vraagstuk kwantitatief uit (bijvoorbeeld totale winst, totale kosten).
• Beperkingen: Een stelsel van lineaire gelijkheden en/of ongelijkheden waaraan de beslissingsvariabelen moeten voldoen. De beperkingen weerspiegelen middelengrenzen, technologische eisen, planningstaken en andere voorwaarden van het vraagstuk.
• Toegelaten gebied (feasible region): De verzameling van alle combinaties van waarden van de beslissingsvariabelen die aan alle beperkingen van het vraagstuk voldoen. Geometrisch vormt het toegelaten gebied in een meerdimensionale ruimte een convexe veelhoek (polyheder), mogelijk onbegrensd of leeg.
• Toegelaten oplossing: Elke combinatie van variabelewaarden die tot het toegelaten gebied behoort.
• Optimale oplossing: Een toegelaten oplossing waarbij de doelfunctie haar extremale (maximale of minimale) waarde bereikt. Als de optimale oplossing bestaat, bevindt zij zich altijd op de grens van het toegelaten gebied, ten minste in een van de hoekpunten van de convexe veelhoek van het toegelaten gebied (hoofdstelling van LP).

Methoden voor het oplossen van LP-vraagstukken

Er bestaan verschillende hoofdmethoden voor het oplossen van lineaire programmeringsvraagstukken:

• Grafische methode: Wordt toegepast voor vraagstukken met twee beslissingsvariabelen. Maakt het mogelijk het toegelaten gebied en de doelfunctie in het vlak visueel weer te geven en de optimale oplossing te vinden door analyse van de hoekpunten van het toegelaten gebied of door verschuiving van de niveaulijn van de doelfunctie.
• Simplexmethode: Een universeel iteratief algoritme, ontwikkeld door George Dantzig. De methode stapt achtereenvolgens van het ene hoekpunt van het toegelaten gebied naar een aangrenzend hoekpunt, waarbij de waarde van de doelfunctie bij elke stap verbetert, totdat de optimale oplossing is gevonden. Dit is de klassieke en meest bekende methode voor het oplossen van LP-vraagstukken.
• Inwendige-puntmethoden: Een alternatieve klasse van algoritmen die later dan de simplexmethode zijn ontwikkeld. Zij bewegen naar de optimale oplossing via het inwendige van het toegelaten gebied, in plaats van langs de grenzen ervan. Deze methoden zijn bijzonder effectief voor het oplossen van LP-vraagstukken van zeer grote omvang.

Dualiteit in lineair programmeren

Aan elk lineair programmeringsvraagstuk (het zogenaamde primaire vraagstuk) kan een ander LP-vraagstuk worden gekoppeld, het duale vraagstuk genaamd. Het primaire en het duale vraagstuk zijn nauw met elkaar verbonden:

De oplossing van het ene vraagstuk geeft informatie over de oplossing van het andere. De optimale waarden van de doelfuncties in beide vraagstukken zijn gelijk (als zij bestaan). De variabelen van het duale vraagstuk hebben een belangrijke economische interpretatie — zij corresponderen met schaduwprijzen (of duale schattingen) van middelen, en geven aan hoeveel de optimale waarde van de doelfunctie van het primaire vraagstuk verandert bij een kleine wijziging van de beperking op het betreffende middel.

Toepassingen van LP

Lineair programmeren vindt brede toepassing in:

• Economie en bedrijfsleven (productieplanning, logistiek, financiën, marketing).
• Industrie (optimalisatie van technologische processen, voorraadbeheer, snijden van materialen).
• Transport (optimalisatie van routes en dienstregelingen). Landbouw (optimalisatie van beteelde oppervlakten, voederrantsoenen).
• Energievoorziening (optimalisatie van de belasting van opwekkingscapaciteiten).

Literatuur

• Dantzig, G. Lineair programmeren, toepassingen en uitbreidingen. — M.: Progress, 1966.
• Joedин D. B., Golštejn E. G. Lineair programmeren (theorie, methoden en toepassingen). — M.: Nauka, 1969.
• Taha, Hamdy A. Operations Research: An Introduction. — Pearson. (10th ed., 2017)
• Hillier, Frederick S.; Lieberman, Gerald J. Introduction to Operations Research. — McGraw-Hill Education. (11th ed., 2021)

Zie ook

• Operations research
• Optimalisatie
• Doelfunctie
• Beperkingen
• Toegelaten gebied
• Optimale oplossing