Ekonomi och matematik

Linjär optimering

Teori

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.

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.

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.

Exempel

Maximera vinsten med linjär optimering