Linjär optimering

{{ 'ml-heading-theory' | message }}

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=200x+150y, z = 200x + 150y, 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 xx och yy kunna vara hur stora som helst och därmed även värdet på z,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=2x+3y = 2x + 3. Linjen når bara ett maximum om definitionsmängden är begränsad, som t.ex. till -2x4.\text{-} 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=2x+4yz=2x+4y krävs en begränsad definitionsmängd. Den anges ofta med ett system av olikheter, exempelvis {y+0.4x20y0.5x1y3x11, \begin{cases}y+0.4x\leq20 \\ y-0.5x\geq1 \\ y\leq3x-11, \end{cases} som tillsammans beskriver vilka kombinationer av xx och yy som är tillåtna att sätta in i funktionen.

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

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

De maximala och minimala värdena på funktionen zz 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 H1,H_1, H2H_2 och H3H_3 gäller följande system. H1:{y=3x11y=0.5x+1H2:{y=-0.4x+20y=3x11H3:{y=0.5x+1y=-0.4x+20\begin{aligned} &H_1: \quad \begin{cases}y=3x-11 \\ y=0.5x+1 \end{cases}\\ \\ &H_2: \quad \begin{cases}y=\text{-}0.4x+20 \\ y=3x-11 \end{cases}\\ \\ &H_3: \quad \begin{cases}y=0.5x+1 \\ y=\text{-}0.4x+20 \end{cases} \end{aligned} Lösningarna på ekvationssystemen ger hörnens koordinater. I de två nedre systemen har koordinaterna avrundats till en decimal. H1:{x=4.8y=3.4H2:{x=9.1y=16.4H3:{x=21.1y=11.6\begin{aligned} &H_1: \quad \begin{cases}x=4.8 \\ y=3.4 \end{cases}\\ \\ &H_2: \quad \begin{cases}x=9.1 \\ y=16.4 \end{cases}\\ \\ &H_3: \quad \begin{cases}x=21.1 \\ y=11.6 \end{cases} \end{aligned}

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

(x,y)(x,y) 2x+4y2x+4y zz
(4.8,3.4)(4.8,3.4) 24.8+43.42\cdot4.8+4\cdot3.4 23.2{\color{#FF0000}{23.2}}
(9.1,16.4) (9.1,16.4) 29.1+416.42\cdot9.1+4\cdot16.4 83.883.8
(21.1,11.6) (21.1,11.6) 221.1+411.62\cdot21.1+4\cdot11.6 88.6{\color{#009600}{88.6}}

Det största och minsta värdet är alltså 88.688.6 respektive 23.2.23.2.

Uppgift

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 44 1616 3535
Läsk 22 44 2828

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

Visa lösning Visa lösning

Uppgifter

Nivå 1
1.1
{{ 'ml-btn-focusmode-tooltip' | message }} settings_overscan

Grethe säljer blåbär och hallon längs väg 21.21. En liter blåbär säljs för 3535 kr och en liter hallon säljs för 3030 kr. Totalt får det plats max 4040 liter bär i cykelsläpet.

a

Ställ upp en funktion, z,z, som beskriver Grethes vinst om hon säljer xx liter blåbär och yy liter hallon.

b

Vad blir Grethes maximala vinst om hon fyller hela cykelsläpet?

1.2
{{ 'ml-btn-focusmode-tooltip' | message }} settings_overscan

Funktionen z=4x+3yz = 4x + 3y är definierad på det markerade området. Vad är funktionens minsta värde?

1.3
{{ 'ml-btn-focusmode-tooltip' | message }} settings_overscan

Bestäm det maximala värdet på funktionen m=5x+11ym=5x+11y då följande bivillkor gäller. {yx1y+0.5x7x0y0 \begin{cases}y-x\leq1 \\ y+0.5x\leq7 \\ x\geq0 \\ y\geq0 \end{cases}

1.4
{{ 'ml-btn-focusmode-tooltip' | message }} settings_overscan

Bestäm största och minsta värde för funktionen z=11x+13yz = 11x + 13y på det område som uppfyller följande bivillkor. {y+16020xy+2.5x42.5y5x10y0 \begin{cases}y + 160 \geq 20x \\ y + 2.5x \leq 42.5 \\ y \leq 5x - 10 \\ y\geq 0 \end{cases}

Nivå 2
2.1
{{ 'ml-btn-focusmode-tooltip' | message }} settings_overscan

Sture har ett enmansföretag som köper in färdiga trädetaljer i furu. Han tillverkar enbart två produkter, pallar och byråer. Stures arbetsuppgifter består av att montera och lacka dessa, vilket han inte kan göra samtidigt. Följande data gäller för hans produktion:

NP-pall-byra.svg
Arbetstimmar (h)
Pall Byrå Tillgängliga arbetstimmar
per vecka (h)
Montering 0.250.25 0.500.50 1515
Lackning 0.400.40 1.001.00 2525
Vinst per produkt 150150 kr 320320 kr

Antag att Sture tillverkar xx pallar och yy byråer under en vecka.

a

Sture får en order på 4040 pallar och 1010 byråer. Hinner han tillverka dessa under en arbetsvecka?

b

Bestäm den maximala vinst som Stures företag kan göra under en arbetsvecka.

Nationella provet HT12 3b
2.2
{{ 'ml-btn-focusmode-tooltip' | message }} settings_overscan

Tanel har ett wrapföretag tillsammans med Dave. De gör två typer av wraps (rostbiff och falafel) som tar olika lång tid att göra. Tillsammans lägger de ner 3535 timmar i veckan på tillverkning av wraps. Rostbiffwrapen är lite större och kräver mer omslagspapper. Totalt har de 200200 meter papper.

Rostbiff Falafel
Tillverkning 44 min 66 min
Papper 7575 cm 5050 cm
Vinst per wrap 1212 kr 1717 kr

Förutsatt att de säljer alla wraps de tillverkar, vad är deras maximala veckovinst och hur många ska de göra av varje sort?

2.3
{{ 'ml-btn-focusmode-tooltip' | message }} settings_overscan

Ett företag behöver extra utrymme och undersöker vilka sorters förråd som finns hos ett magasineringsföretag. Det finns två varianter att välja på, F1\text{F}1 och F2\text{F}2. Area, volym och månadskostnad per förråd redovisas i tabellen.

Förråd Area (m2)\left(\text{m}^2\right) Volym (m3)\left(\text{m}^3\right) Kostnad (kr)
F11 1515 8181 18001800
F22 3030 5454 15001500

Om företaget vet att arean och volymen totalt måste vara minst 210 m2210 \text{ m}^2 respektive 486 m3,486 \text{ m}^3, vilken kombination av förråd ska väljas för att minimera kostnaden och hur stor blir denna?

Nivå 3
3.1
{{ 'ml-btn-focusmode-tooltip' | message }} settings_overscan

Per-Ohlson planerar att tjäna lite extra genom att odla tomat- och majsplantor. Tomatplantorna behöver 44 gram gödsel per dag och planta medan det behövs 88 gram till majsplantorna. Per-Ohlsons marsvin genererar dock bara 3434 gram gödsel per dag. Han har också begränsat med utrymme på sin balkong, där han har 2.25m22.25\,\text{m}^2 över till sin odling. Av detta behöver varje tomatplanta 0.4m20.4\,\text{m}^2 medan majsplantorna behöver 0.2m2.0.2\,\text{m}^2. Om han kan sälja tomatplantorna för 4040 kr och majsplantorna för 5050 kr, hur många av varje bör han plantera?

Nivå 4
4.1
{{ 'ml-btn-focusmode-tooltip' | message }} settings_overscan

Villes Supersaft är en blandning av två saftsorter. Saft AA har en koncentration på 15%15\, \% och kostar 4040 kr per liter medan saft BB har en koncentration på 25%25\, \% och kostar 5555 kr per liter. Ville har listat ut att smaken blir bäst om blandningens koncentration är minst 17%17\,\% och maximalt 18%18\,\%. Till en fest behövs minst 3030 liter Supersaft. Det visar sig att han har kvar 77 liter av saft BB sedan tidigare som han kan använda om han vill. Hur många liter av varje sort ska han köpa för att få så billig Supersaft som möjligt?

Test
{{ 'mldesktop-selftest-notests' | message }} {{ article.displayTitle }}!
{{ tests.error }}

{{ 'ml-heading-exercise' | message }} {{ focusmode.exercise.exerciseName }}

keyboard_backspace
{{ section.title }} keyboard_backspace {{ 'ml-btn-previous' | message }} {{ 'ml-btn-previous-exercise' | message }} {{ 'ml-btn-next-exercise' | message }} keyboard_backspace {{ 'ml-btn-next-exercise' | message }}