Introduktion til lineær programmering

Lineær programmering er en matematisk metode, der bruges til at finde den bedste løsning på et problem inden for nogle givne rammer. I den virkelige verden er ressourcer som tid, penge, råvarer og arbejdskraft ofte begrænsede. Lineær programmering hjælper beslutningstagere med at vælge den kombination af muligheder, der giver det største overskud eller det mindste forbrug.

Optimering

Optimering handler om at gøre noget så godt som muligt. I matematikken betyder det typisk, at vi enten vil maksimere noget (f.eks. dækningsbidrag) eller minimere noget (f.eks. omkostninger).

Hvor mange Stole? Hvor mange bænke?

Forestil dig en mindre tømrervirksomhed, der producerer stole og bænke. Der gælder for de to vare at:

• En stol giver et overskud på 400 kr.
• En bænk giver et overskud på 700 kr.

Umiddelbart ville man tro, at tømreren bare skal producere så mange bænke som muligt, da de giver det største overskud. Men tømreren har begrænsede ressourcer:

• Arbejdstid: Han har kun 40 timer om ugen. En stol tager 2 timer at lave, mens en bænk tager 5 timer.
• Lagerplads: Han har kun plads til i alt 12 enheder færdige varer på sit lager.

Hvis han kun laver bænke, kan han nå 8 stk. ($40 \text{ timer} / 5 \text{ timer}$). Overskuddet bliver $8 \cdot 700 = 5.600 \text{ kr.}$
Hvis han kun laver stole, kan han i princippet nå 20 stk., men lageret begrænser ham til 12 stk. Overskuddet bliver $12 \cdot 400 = 4.800 \text{ kr.}$

Spørgsmålet er nu: Findes der en kombination af stole og bænke, der udnytter både tiden og lagerpladsen bedre og dermed giver et endnu højere overskud? Her kommer de simple overslag til kort, og vi har brug for en matematisk model.

Matematisk model

For at løse problemet systematisk indfører vi to variable:

• $x$: antal stole
• $y$: antal bænke

Vores overskud kan nu skrives som en funktion ($f$):
$$f(x,y) = 400 \cdot x + 700 \cdot y$$

Men vi er begrænset af virkeligheden. Disse begrænsninger opstiller vi som uligheder:

• Tidsforbrug: $2x + 5y \leq 40$ (det samlede timeforbrug må ikke overstige 40)
• Lagerplads: $x + y \leq 12$ (det samlede antal møbler må ikke overstige 12)
• Intet negativt salg: $x \geq 0$ og $y \geq 0$ (man kan ikke producere et negativt antal møbler)

Et hvert par af $x$ og $y$ (producerede antal stole og bænke) skal opfylde alle disse uligheder. Lineær programmering giver en systematisk tilgang til at finde det tal-par, der både opfylder betingelserne og giver størst muligt overskud.

Opsamling

I dette indledende afsnit har vi set på:

• Lineær programmering er en metode til at træffe beslutninger under visse begrænsninger
• Praktisk tilfælde, hvor lineær programmering kan anvendes til at bestemme optimale værdi af to størrelser
• Hvordan begreber fra praktisk eksempel kan oversættes til matematiske udtryk som funktioner og uligheder

Opgaver

OPGAVE: Introduktion til lineær programmering