Optimering vha. lineær programmering

I dette modul gennemgås hvordan det er muligt ved hjælp af lineær programmering systematisk at udpege det punkt $(x,y)$, der enten maksimerer eller minimerer kriteriefunktionen.

LP-algoritmen

Optimering handler om at finde den bedst mulige løsning inden for de rammer, der er defineret af begrænsningerne. For at løse et optimeringsproblem systematisk følger man en fast procedure, som kaldes LP-algoritmen.

LP-algoritmen:

1. Definition af variable: Fastlæg hvad $x$ og $y$ repræsenterer.
2. Opstilling af kriteriefunktion: Definer målet (f.eks. at maksimere dækningsbidraget).
3. Opstilling af begrænsninger: Formuler uligheder for ressourcer (tid, lager, m.m.).
4. Tegning af polygonområde: Visualisér de mulige løsninger i et koordinatsystem.
5. Bestemmelse af optimal løsning: Find det bedste punkt i polygonområdet (niveaulinjemetoden eller hjørneinspektion).

Når man har gennemført de første fire trin, findes der to primære metoder til at udføre det sidste og afgørende trin: niveaulinjemetoden og hjørnepunktsinspektion. De to metoder vil blive gennemgået i det følgende.

Niveaulinjemetoden

Niveaulinjemetoden bygger på en visuel forståelse af, hvordan kriteriefunktionen ændrer sig på tværs af koordinatsystemet. Da alle niveaulinjer for en funktion er parallelle, kan man finde den optimale løsning ved at “forskyde” en niveaulinje gennem polygonområdet.

Fremgangsmåde:

1. Indtegn en vilkårlig niveaulinje $N$ for kriteriefunktionen (f.eks. $N(0)$).
2. Bestem vækstretningen for funktionen (hvilken vej stiger værdien?).
3. Parallelforskyd niveaulinjen i vækstretningen, indtil den netop rører det sidste punkt i polygonområdet, før den forlader det.

Det punkt, hvor niveaulinjen sidst har kontakt med det mulige område, kaldes det optimale punkt. Koordinaterne $(x, y)$ i dette punkt repræsenterer den optimale kombination.

Hjørnepunktsinspektion

En central sætning inden for lineær programmering fastslår, at hvis der findes en optimal løsning, vil den altid findes i et af hjørnepunkterne i polygonområdet (eller på en af kanterne mellem to hjørner). Dette gør det muligt at finde løsningen matematisk uden nødvendigvis at parallelforskyde linjer præcist.

Fremgangsmåde:

1. Indsæt koordinaterne for hvert hjørne i kriteriefunktionen $f(x, y)$.
2. Sammenlign resultaterne. Det hjørne, der giver den højeste værdi (ved maksimering) eller laveste værdi (ved minimering), er den optimale løsning.

Eksempel: Hvis et polygonområde har hjørnerne $A(0,0)$, $B(0,8)$, $C(4,6)$ og $D(10,0)$, og kriteriefunktionen er $f(x,y) = 100x + 200y$, beregner man:

• $f(A) = 100 \cdot 0 + 200 \cdot 0 = 0$
• $f(B) = 100 \cdot 0 + 200 \cdot 8 = 1600$
• $f(C) = 100 \cdot 4 + 200 \cdot 6 = 1600$
• $f(D) = 100 \cdot 10 + 200 \cdot 0 = 1000$

Her giver både punkt B og C det højeste dækningsbidrag. Det betyder, at alle punkter på linjen mellem B og C faktisk er optimale.

Den optimale løsning i praksis

Når det optimale punkt $(x, y)$ er fundet, skal resultatet altid tolkes i forhold til den oprindelige økonomiske problemstilling.

• $x$- og $y$-værdierne er dine beslutningsvariable. De fortæller os, hvad vi skal gøre (f.eks. “producer 4 enheder af vare X og 6 enheder af vare Y”).
• Funktionsværdien $f(x, y)$ fortæller os om resultatet (f.eks. “det maksimale dækningsbidrag bliver 1600 kr.”).

I mange praktiske tilfælde kan man kun producere hele enheder (man kan f.eks. ikke sælge 4,2 stole). Hvis det optimale punkt ikke er et heltal, må man undersøge de nærmeste hele tal-par $(x, y)$, der ligger inden for polygonområdet, for at finde den bedste realistiske løsning.

Opsamling

Dette modul har givet fremgangsmåden, når man vil bruge lineær programmering til at bestemme et maksimum eller et minimum. Du har nu lært at:

• Følge LP-algoritmen fra definition af variable til færdig løsning.
• Bruge niveaulinjemetoden til visuelt at finde det optimale punkt.
• Anvende hjørnepunktsinspektion til at regne dig frem til den bedste løsning.

Opgaver

OPGAVE: Optimering vha. lineær programmering