Kvadratisk programmering

Kvadratisk programmering er en udvidelse af lineær programmering, hvor den størrelse, der ønskes optimeret, ikke længere er en lineær funktion, men en kvadratisk funktion. Metoden anvendes i situationer, hvor sammenhængen mellem fx pris, afsætning og overskud ikke er lineær, men hvor der stadig gælder lineære begrænsninger.

Kvadratiske modeller anvendes ofte i økonomi, hvor efterspørgsel, pris og overskud kan beskrives ved parabler. Kvadratisk programmering gør det muligt at finde den løsning, der giver størst muligt overskud eller mindst muligt tab, under givne begrænsninger.

Kvadratiske optimeringsproblemer

Et kvadratisk programmeringsproblem består af:

• en kvadratisk kriteriefunktion (ved lineær programmering er kriteriefunktion lineær)
• et løsningsområde afgrænset af lineære uligheder

En kvadratisk funktion af to variable kan fx have formen

\[
f(x,y) = ax^2 + by^2 + cxy + dx + ey + k
\]

I mange praktiske problemer vil kriteriefunktionen være konkav (åbner nedad), hvilket betyder, at der findes et maksimum.

Forskel på lineær og kvadratisk programmering

• I lineær programmering findes optimale løsninger i hjørnerne af polygonområdet
• I kvadratisk programmering kan den optimale løsning godt ligge inden for polygonområdet

Derfor kræver kvadratisk programmering ofte en kombination af:

• Differentialregning
• Undersøgelse af rande (begrænsningslinjer)

Eksempel: Maksimering af overskud ved salg af to varer

En virksomhed sælger to varer: Vare A og Vare B.

Lad:
\[
x=\text{antal solgte enheder af A},\qquad y=\text{antal solgte enheder af B}
\]

Virksomheden tjener penge på at sælge, men ved store salg falder den gennemsnitlige fortjeneste pr. enhed (udbud og efterspørgsel). Dette modelleres med en kvadratisk overskudsfunktion.

Kriteriefunktion (overskud)

Overskuddet (i kr.) modelleres ved:
\[
P(x,y)=60x+50y-0,6x^2-0,4y^2-0,2xy
\]

De negative kvadratiske led resulterer i, at funktionen har et globalt maksimum (der findes et punkt $(x,y)$, som giver det størst mulige overskud). At dette punkt også er det bedste valg i praksis kræver dog, at det opfylder de begrænsninger, der må være på de tilladte $x$- og $y$-værdier.

Begrænsninger (ressourcer)

Virksomheden har to begrænsede ressourcer:

1) Begrænsning 1:
\[
2x+y\le 100
\]
2) Begrænsning 2:
\[
x+2y\le 120
\]
Samt:
\[
x\ge 0,\quad y\ge 0
\]

Trin 1: Optimum (uden begrænsninger)

Vi finder det kritiske punkt ved at løse følgende to ligninger med to ubekendte:
\[
\frac{\partial P}{\partial x}=60-1,2x-0,2y=0
\]
\[
\frac{\partial P}{\partial y}=50-0,8y-0,2x=0
\]
Løsning til lignings-systemet giver:
\[
(x,y) = (41.30,\ 52.17)
\]

Trin 2: Evaluering af begrænsninger

Man kan se, at punktet ikke opfylder Begrænsning 1 ($2x+y\le 100$):
\[
2x+y = 2\cdot 41,30+52,17=134,77>100
\]
Punktet svarer dermed ikke til en mulig produktion, så optimum skal findes på randen af løsningsområdet.

Trin 3: Optimum på randen

Vi undersøger randen:
\[
2x+y=100 \Rightarrow y=100-2x
\]

Indsæt i overskudsfunktionen:

$$ P(x,100-2x)=60x+50(100-2x)-0,6x^2-0,4(100-2x)^2-0,2x(100-2x) $$

Hvilket kan reduceres til:

$$P(x,100-2x)=1000+100x-1,8x^2$$

Det er en parabel med maksimum i toppunktet:
\[
x=\frac{-b}{2a}=\frac{-100}{2\cdot(-1,8)}=\frac{100}{3,6} = 27,78
\]
Så:
\[
y=100-2\cdot 27,78 = 44,44
\]
Punktet opfylder også den Begrænsning 2 ($x+2y <120$):
\[
x+2y = 27,78+88,88=116,66\le 120
\]
Altså er \((27.78,44.44)\) svarer til en mulig produktion af varerne.

Overskuddet her bliver:
\[
P(27.78,44.44) = 2389
\]

Det vil sige den bedste løsning er:
\[
(x,y) = (27.78,\ 44.44)
\]
med et maksimalt overskud på ca.
\[
P_{\max} = 2389\text{ kr.}
\]

Konklusion:

Det vil sige virksomheden opnår det størst mulige overskud ved at sælge 27,78 af Vare A og 44,44 af Vare B. Virksomheden kan maksimalt få et overskud på 2389 kr. Hvis virksomheden kun kan sælge et helt antal af varerne, skal antallet rundes ned til det nærmeste hele tal.

Opsamling

I dette modul har du arbejdet med kvadratisk programmering. Du har lært at:

• Forklare, hvad kvadratisk programmering er
• Skelne mellem lineær og kvadratisk programmering
• Opstille en kvadratisk kriteriefunktion
• Finde kritiske punkter ved hjælp af partielle afledede
• Undersøge begrænsninger og rande
• Bestemme og fortolke en optimal løsning