Varför fungerar linjär optimering?

När man löser uppgifter med linjär optimering räcker det att undersöka hörnen av definitionsmängden. Varför är det så? Det finns ju oändligt många fler punkter. Hur kan man vara säker på att ingen av dem ger ett maximum eller minimum? För att förstå det är det hjälpsamt att jämföra med vanliga linjer.

Optimering av rät linje

Ta som exempel funktionen f(x)=x+2.f(x) = x + 2. Vad är dess största värde?

Eftersom en linje fortsätter i oändlighet kommer den nå hur höga värden som helst. Det finns alltså inget maximum. Men om funktionen bara är definierad över ett visst intervall, dvs. om definitionsmängden är ett slutet intervall, måste det finnas ett maximum. Definitionsmängden kan t.ex. vara -5x5.\text{-}5 \leq x \leq 5.

En linje ändrar inte riktning, så om den lutar uppåt, som i det här fallet, måste punkten längst till höger ligga högst upp. En linje som lutar nedåt har istället sin högsta punkt längst till vänster. Därför behöver man bara undersöka definitionsmängdens ändar, dvs. x=-5x=\text{-} 5 och x=5,x=5, när man letar efter maximum. Utan att rita upp grafen kan man alltså göra insättningarna f(-5)=-5+2=-3f(5)=-5+2=7\begin{aligned} f({\color{#0000FF}{\text{-}5}}) & = {\color{#0000FF}{\text{-}5}} + 2 = \text{-} 3 \\ f({\color{#0000FF}{5}}) & = \phantom{\text{-}}{\color{#0000FF}{5}} + 2 = 7 \end{aligned} vilket visar att funktionens största värde på intervallet är 7,7, vilket nås i x=5.x=5.

Funktion av två variabler

För att rita en funktion som f(x)=x+2f(x) = x+2 kan man sätta in olika xx-värden och beräkna funktionsvärdet. Varje par av in- och ut-värde motsvarar en punkt i koordinatsystemet, och genom att binda ihop alla dessa punkter har funktionens graf ritats. Samma princip gäller för en funktion som f(x,y)=x+2y+2. f(x,y) = x+2y+2. Den här funktionen använder två variabler. yy är inte längre något som beräknas med hjälp av x,x, utan ett helt eget valfritt tal: en oberoende variabel. Därför väljs olika par av xx och yy, och för varje par beräknas ett funktionsvärde.

xx yy x+2y+2x+2y+2 f(x,y)f(x,y)
0{\color{#0000FF}{0}} 0{\color{#009600}{0}} 0+20+2{\color{#0000FF}{0}}+2\cdot{\color{#009600}{0}}+2 22
0{\color{#0000FF}{0}} 1{\color{#009600}{1}} 0+21+2{\color{#0000FF}{0}}+2\cdot{\color{#009600}{1}}+2 44
1{\color{#0000FF}{1}} 0{\color{#009600}{0}} 1+20+2{\color{#0000FF}{1}}+2\cdot{\color{#009600}{0}}+2 33
1{\color{#0000FF}{1}} 1{\color{#009600}{1}} 1+21+2{\color{#0000FF}{1}}+2\cdot{\color{#009600}{1}}+2 55

För att markera dessa punkter krävs en tredimensionell bild. Varje par av (x,y)(x,y) är en punkt i ett vanligt koordinatsystem, och därifrån markeras funktionsvärdet som en höjd ovanför xyxy-planet. När alla dessa punkter sedan markeras bildas inte längre en kurva eller linje, utan en yta.

På samma sätt som funktionen f(x)=x+2f(x) = x+2 beskriver en linje på ett plan, beskriver alltså funktionen f(x,y)=x+2y+2f(x,y) = x+2y+2 ett plan i ett rum. Samma sak gäller för alla funktioner på formen f(x,y)=ax+by+c,f(x,y) = ax + by +c, där a,ba,b och cc är konstanta värden.

Optimering av plan

En funktion av typen z=ax+by+cz = ax + by + c motsvarar alltså ett plan i rummet. Poängen är nu att oavsett hur planet vinklas kommer alltid ett hörn ligga högst upp. Det är svårt att tänka i 3D, men istället kan man hålla ut ett papper, en bit kartong eller något annat platt. Om man inte böjer pappret utan låter det vara helt plant, kommer högsta punkten alltid hamna i ett av hörnen.

Detta är helt analogt med de räta linjerna. Där skulle man gå så långt som möjligt för att nå så högt som möjligt, vilket leder till en ändpunkt. Samma sak gäller här. Någon riktning längs planet är den brantaste, och genom att gå så långt som möjligt i den riktningen når man den högsta punkten. Förutsatt att planet har raka kanter kommer den punkten alltid hamna i ett hörn.