Hvad er lineær programmering?

Lineær programmering er en matematisk disciplin inden for optimering, som sigter mod at finde den bedst mulige løsning til en given opgave, hvor både begrænsninger og muligheder spiller en rolle. Det kan f.eks. være planlægning af produktion, logistik, lagerstyring, transport og distributionsproblemer, og det kan også omfatte investeringer eller porteføljeoptimering.

Lineær programmering kan beskrives som en metode til at optimere en lineær funktion under nogle givne begrænsninger. En lineær funktion er en matematisk formel, hvor kun første potens af variablerne indgår, og begrænsningerne angives typisk som en række lineære uligheder eller ligheder. En løsning til problemet vil være en kombination af værdier for variablerne, som respekterer begrænsningerne, og som optimerer den lineære funktion.

Lineær programmering er en praktisk og effektiv måde at finde optimale løsninger på komplekse problemer inden for en lang række områder. Det er en vigtig disciplin inden for matematisk optimering og anvendes ofte af virksomheder, organisationer og regeringer.

Historie
Lineær programmering kan spores tilbage til arbejdet med Matrisespil af den svenske matematiker Oskar Morgenstern og den ungarske matematiker John von Neumann i slutningen af 1940'erne. Det var en metode til at modellere og analysere konfliktsituationer og var ofte brugt i økonomisk teori og spilteori.

Senere, i begyndelsen af 1950'erne, udviklede den amerikanske matematiker George B. Dantzig lineær programmering som en metode til optimal planlægning af militære og industrielle operationer. Dantzig opfandt simplex-metoden, som er en algoritme, der effektivt kan finde en optimal løsning i lineære programmeringsproblemer med mange variabler og begrænsninger.

Anvendelse
Lineær programmering bruges i dag i mange forskellige områder, både inden for produktionsplanlægning og logistik og inden for mere teoretiske områder som økonomisk teori og spilteori. Den anvendes ofte til at finde optimale løsninger til opgaver såsom produktionsplanlægning, transportproblemer, investeringsplanlægning og lignende.

Matematisk er lineær programmering baseret på lineær algebra, og det er en gren af optimeringsteori. I enhver lineær programmeringsopgave er der en lineær funktion, som ønskes at blive optimeret. Funktionen optimeres under nogle begrænsninger såsom økonomiske begrænsninger, produktionstid, produktionskapacitet, salgsrestriktioner etc.

Eksempel
Et simpelt eksempel på lineær programmering kunne være en producent af ikke-alkoholiske drikkevarer, der ønsker at producere mindst 100, men højest 500 liter, af to forskellige drikkevarer til salg. Producenten har et lager med 300 liter råvare, og for at producere de forskellige drikkevarer skal der bruges forskellige mængder af råvarer. Det koster producenten $2/liter og $3/liter at producere de to drikkevarer. Hvor mange liter af hver drik skal producenten producere for at maksimere sin fortjeneste?

Dette problem kan beskrives matematisk som et lineært programmeringsproblem, hvor vi skal optimere en lineær funktion (fortjeneste) under forskellige begrænsninger (lager og produktion).

Lad x1 betegne antallet af liter af drik 1, der skal produceres, og lad x2 betegne antallet af liter drik 2, der skal produceres. Da er den lineære funktion, der skal optimeres,

Fortjeneste = 2x1 + 3x2.

Produktionen af drik 1 kræver 2 liter råvare pr. liter drik, og produktionen af drik 2 kræver 3 liter råvare pr. liter drik. Da producenten kun har 300 liter råvare til rådighed, er begrænsningen på råvarer

2x1 + 3x2 ≤ 300.

Da producenten ønsker at producere mindst 100 liter af hver drik og højest 500 liter i alt, har vi også begrænsninger på produktionen:

x1 ≥ 100 og x2 ≥ 100,
x1 + x2 ≤ 500.

Vi har nu formuleret vores problem i et lineært programmeringsformat, og vi kan bruge simplex-metoden til at finde den optimale løsning. Efter at have løst problemet får vi, at producenten skal producere 100 liter drik 1 og 200 liter drik 2 for at maksimere sin fortjeneste.

Konklusion
Lineær programmering danner grundlag for optimering af komplekse systemer og spiller en vigtig rolle i mange forskellige områder og industrier. Det gør det muligt at finde optimale løsninger til opgaver såsom produktionsplanlægning, transportproblemer, investeringsplanlægning og lignende. Metoden er baseret på matematisk programmering og lineær algebra og anvender algoritmer, der kan løse en lang række forskellige typer af problemer.