Linjär optimering

Begrepp

Optimering

Optimering handlar om att hitta den bästa lösningen på ett problem. Det kan handla om att hitta de mått som ger maximal volym för t.ex. ett bagageutrymme i en bil, eller att lägga ett så bra skolschema som möjligt utifrån olika önskemål och begränsningar. Inom matematik handlar optimering om att hitta maximum eller minimum för olika funktioner.

Begrepp

Linjär optimering

Funktioner som använder mer än en variabel är ofta väldigt svåra att hitta maximum eller minimum till, men det finns undantag. Om funktionen enbart består av förstagradstermer, som exempelvis

z = 200 x + 150 y,

kallas den linjär. Då finns ett knep som underlättar optimeringen, men det finns ett par krav för att det ska fungera:

Funktionen måste ha en begränsad definitionsmängd. Om den inte vore begränsad skulle $x$ och $y$ kunna vara hur stora som helst och därmed även värdet på $z,$ dvs. inget maximum skulle finnas.
Definitionsmängden måste begränsas av räta linjer.

Om kraven är uppfyllda måste funktionens maximum och minimum antas i hörnpunkter till definitionsmängden, så knepet är att bara undersöka dessa. Det är egentligen precis som för vanliga linjer som

y = 2 x + 3

. Linjen når bara ett maximum om definitionsmängden är begränsad, som t.ex. till

- 2 \leq x \leq 4 .

Detta maximum kan endast inträffa i en av intervallets ändpunkter.

Metod

Bestämma extremvärden med linjär optimering

För att bestämma största och minsta värde av en funktion som

z = 2 x + 4 y

krävs en begränsad definitionsmängd. Den anges ofta med ett system av olikheter, exempelvis

⎩ ⎪ ⎪ ⎨ ⎪ ⎪ ⎧ y + 0.4 x \leq 20 y - 0.5 x \geq 1 y \leq 3 x - 11,

som tillsammans beskriver vilka kombinationer av

x

och

y

som är tillåtna att sätta in i funktionen.

1

Rita området som villkoren beskriver

Olikheterna beskriver ett område som man kan markera i ett koordinatsystem.

Detta kan man göra för hand eller med räknare.

2

Bestäm hörnens koordinater

De maximala och minimala värdena på funktionen $z$ finns i områdets hörn. Man behöver därför bestämma hörnens koordinater.

I vissa fall kan man läsa av koordinaterna direkt. Här är det dock svårt att göra det, så istället får man bestämma skärningspunkterna mellan de olika linjerna genom att lösa tre olika ekvationssystem. För hörn

H_{1},

H_{2}

och

H_{3}

gäller följande system.

H_{1} : {y = 3 x - 11 y = 0.5 x + 1 H_{2} : {y = - 0.4 x + 20 y = 3 x - 11 H_{3} : {y = 0.5 x + 1 y = - 0.4 x + 20

Lösningarna på ekvationssystemen ger hörnens koordinater. I de två nedre systemen har koordinaterna avrundats till en decimal.

H_{1} : {x = 4.8 y = 3.4 H_{2} : {x = 9.1 y = 16.4 H_{3} : {x = 21.1 y = 11.6

3

Sätt in koordinater i funktionen

Nu sätter man in koordinaterna från respektive hörn i funktionen $z = 2 x + 4 y$ för att se vilka av dessa som ger största och minsta värde på $z .$

$(x, y)$	$2 x + 4 y$	$z$
$(4.8, 3.4)$	$2 \cdot 4.8 + 4 \cdot 3.4$	$23.2$
$(9.1, 16.4)$	$2 \cdot 9.1 + 4 \cdot 16.4$	$83.8$
$(21.1, 11.6)$	$2 \cdot 21.1 + 4 \cdot 11.6$	$88.6$

Det största och minsta värdet är alltså $88.6$ respektive $23.2 .$

Maximera vinsten med linjär optimering

fullscreen

Ett företag producerar och säljer exklusiv apelsinsaft och apelsinläsk. Tillverkningstid, apelsinåtgång och hur stor vinst företaget gör per liter visas i tabellen.

Produkt	Tid (h)	Apelsiner (st.)	Vinst (kr)
Saft	$4$	$16$	$35$
Läsk	$2$	$4$	$28$

Hur mycket kan företaget maximalt tjäna på en vecka, om man vet att de anställda tillsammans får jobba max $84$ h/vecka och att apelsintillgången är $192$ st./vecka?

Visa Lösning

Vi kallar antal liter saft för

x

och antal liter läsk för

y .

Funktionen som ska maximeras ska beskriva den totala vinsten. Eftersom varje liter saft ger vinsten

35

kr och motsvarande vinst för läsken är

28

kr blir vinstfunktionen

z = 35 x + 28 y .

Variablerna

x

och

y

kan inte anta vilka värden som helst. Eftersom båda beskriver antal liter kan de inte vara negativa:

{x \geq 0 y \geq 0 .

Vidare finns det begränsningar på antalet apelsiner och antal timmar personalen kan jobba. Tillverkningstiden för saften är

4

timmar per liter och därför tar det

4 x

timmar att producera

x

liter saft. På samma sätt tar det

2 y

timmar att producera

y

liter läsk. Detta får inte överstiga

84

timmar, vilket ger villkoret

4 x + 2 y \leq 84 .

På liknande sätt kan man bestämma ett villkor för apelsintillgången då man vet att det går åt

16

st. per liter saft och

4

st. per liter läsk. Det totala antalet apelsiner får inte överstiga

192

st./vecka, så

16 x + 4 y \leq 192 .

De fyra bivillkoren samlas i ett system av olikheter:

⎩ ⎪ ⎪ ⎪ ⎪ ⎨ ⎪ ⎪ ⎪ ⎪ ⎧ 4 x + 2 y \leq 84 16 x + 4 y \leq 192 x \geq 0 y \geq 0 .

Detta område vill vi nu rita upp så vi börjar med att lösa ut

y

i de två översta olikheterna.

4 x + 2 y \leq 84

SubIneq

$VL - 4 x \leq HL - 4 x$

2 y \leq - 4 x + 84

DivIneq

$VL / 2 \leq HL / 2$

y \leq - 2 x + 42

Nu tar vi den andra.

16 x + 4 y \leq 192

SubIneq

$VL - 16 x \leq HL - 16 x$

4 y \leq - 16 x + 192

DivIneq

$VL / 4 \leq HL / 4$

y \leq - 4 x + 48

Den första olikheten beskriver alla punkter på och under linjen

y = - 2 x + 42

och den andra beskriver alla punkter på och under linjen

y = - 4 x + 48 .

Olikheterna

x \geq 0

och

y \geq 0

betyder att både

x

och

y

måste vara

0

eller positiva, så alla punkter måste vara i första kvadranten.

Funktionens största värde antas i något av hörnen så vi bestämmer koordinaterna för dem. Vi börjar med linjernas skärningspunkt.

- 2 x + 42 = - 4 x + 48

AddEqn

$VL + 4 x = HL + 4 x$

2 x + 42 = 48

SubEqn

$VL - 42 = HL - 42$

2 x = 6

DivEqn

$VL / 2 = HL / 2$

x = 3

Skärningspunktens

x

-koordinat är

3 .

Vi sätter in detta i en av funktionerna för att beräkna

y

-koordinaten:

y = - 2 x + 42 \Rightarrow y = - 2 \cdot 3 + 42 = 36 .

Det ena hörnet är alltså

(3, 36) .

Det övre hörnet är där linjen

y = - 2 x + 42

skär

y

-axeln. Där är

x = 0

och

y

-värdet blir linjens

m

-värde dvs.

y = 42 .

Det högra hörnet är där

y = - 4 x + 48

skär

x

-axeln. Där är

y

-koordinaten

0

och vi bestämmer

x

-värdet genom att lösa ekvationen

0 = - 4 x + 48 vilket ger x = 12 .

Det sista hörnet är i origo dvs. (0,0). För att avgöra vilket hörn som ger störst värde på vinstfunktionen sätter vi in punkternas koordinater och jämför funktionsvärdena.

$(x, y)$	$35 x + 28 y$	$z$
$(0, 0)$	$35 \cdot 0 + 28 \cdot 0$	$0$
$(0, 42)$	$35 \cdot 0 + 28 \cdot 42$	$1176$
$(12, 0)$	$35 \cdot 12 + 28 \cdot 0$	$420$
$(3, 36)$	$35 \cdot 3 + 28 \cdot 36$	$1113$

Det största värdet som

z = 28 x + 35 y

antar är alltså

1176

vilket betyder att den maximala veckovinsten är

1176 kr .

Linjär optimering

Kanaler

Direktmeddelanden

Begrepp

Optimering

Begrepp

Linjär optimering

Metod

Bestämma extremvärden med linjär optimering

Exempel

Maximera vinsten med linjär optimering