5.2 Lineær optimering

Kva veit vi? To ressursar med kvar si grense, og overskotet per eining.

Kva må vi finne? Det punktet i det lovlege området som gir størst overskot.

Namn og vilkår. La $x$ vere talet på krakkar og $y$ talet på bord.

$$2x + 4y \le 80 \qquad \text{(saging)}$$
$$4x + 2y \le 100 \qquad \text{(montering)}$$
$$x \ge 0, \qquad y \ge 0$$

Objektfunksjonen. Overskotet er 300 kr per krakk og 500 kr per bord:

$$O = 300x + 500y$$

$O$ måler overskotet i kroner.

Hjørnepunkta. Dei fann vi i kapittel 5.1:

$$(0, 0), \qquad (0, 20), \qquad (20, 10), \qquad (25, 0)$$

Vi reknar ut $O$ i kvart hjørne.

$$O(0, 0) = 300 \cdot 0 + 500 \cdot 0 = 0$$
$$O(0, 20) = 300 \cdot 0 + 500 \cdot 20 = 10\,000$$
$$O(20, 10) = 300 \cdot 20 + 500 \cdot 10 = 6000 + 5000 = 11\,000$$
$$O(25, 0) = 300 \cdot 25 + 500 \cdot 0 = 7500$$

Hjørnepunkt	$O = 300x + 500y$
$(0, 0)$	0 kr
$(0, 20)$	10 000 kr
$(20, 10)$	11 000 kr
$(25, 0)$	7500 kr

Vel det beste hjørnet. Den største verdien er 11 000 kr, og han får vi i punktet $(20, 10)$.
Svar: Verkstaden bør lage 20 krakkar og 10 bord. Då blir overskotet 11 000 kr.
NB: Legg merke til at borda gir mest per stykk (500 kr mot 300 kr), men det lønner seg likevel ikkje å lage berre bord. Grunnen er at eit bord brukar dobbelt så mykje sagetid som ein krakk. Det er forholdet mellom forteneste og ressursbruk som avgjer, ikkje fortenesta åleine.

La $x$ vere hundre liter eplesaft og $y$ hundre liter pæresaft.

$$2x + 3y \le 60 \qquad \text{(presse)}$$
$$4x + y \le 60 \qquad \text{(flasker)}$$
$$x \ge 0, \qquad y \ge 0$$
$$z = 200x + 300y$$

Hjørnepunkta. Pressa treffer aksane i $(30, 0)$ og $(0, 20)$, flaskene i $(15, 0)$ og $(0, 60)$.

På $y$-aksen er det strengaste kravet $y \le 20$, så hjørnet er $(0, 20)$. På $x$-aksen er det strengaste $x \le 15$, så hjørnet er $(15, 0)$.

Kryssingspunktet finn vi med addisjonsmetoden. Vi gongar den andre likninga med 3:

$$4x + y = 60 \qquad | \; \cdot 3$$
$$12x + 3y = 180$$

Vi trekkjer den første likninga frå denne:

$$(12x + 3y) - (2x + 3y) = 180 - 60$$
$$10x = 120 \qquad | \; : 10$$
$$x = 12$$

Vi set inn i den andre likninga: $4 \cdot 12 + y = 60$, altså $y = 12$. Kryssingspunktet er $(12, 12)$.

Vi reknar ut $z$ i kvart hjørne.

Hjørnepunkt	$z = 200x + 300y$
$(0, 0)$	0 kr
$(0, 20)$	6000 kr
$(12, 12)$	6000 kr
$(15, 0)$	3000 kr

To hjørne gir nøyaktig det same. Då er verdien den same i heile kanten mellom dei.
Kvifor? Vi ser på nivålinja for $z = 6000$:
$$200x + 300y = 6000 \qquad | \; : 100$$
$$2x + 3y = 60$$
Det er akkurat grenselinja til pressa. Nivålinja er altså ikkje berre parallell med kanten — ho er kanten.

Nivålinja for $z = 6000$ er ikkje berre parallell med kanten — ho er kanten (gul). Difor gir alle punkt mellom $(0, 20)$ og $(12, 12)$ det same dekningsbidraget.

Svar: Alle punkta på kanten frå $(0, 20)$ til $(12, 12)$ gir det største dekningsbidraget på 6000 kr. Bryggeriet kan til dømes lage 600 liter eplesaft og 1600 liter pæresaft, eller inga eplesaft og 2000 liter pæresaft — dekningsbidraget blir det same.
NB: Felles for alle desse punkta er at pressa er brukt fullt ut. Det er ho som er den knappe ressursen her; flaskene blir det til overs av.

a) Objektfunksjonen er

$$z = 250x + 180y$$

Hjørnepunkta. Sylinja treffer aksane i $(20, 0)$ og $(0, 15)$, stofflinja i $(10, 0)$ og $(0, 25)$.

På $y$-aksen er det strengaste $y \le 15$, så hjørnet er $(0, 15)$. På $x$-aksen er det strengaste $x \le 10$, så hjørnet er $(10, 0)$. Kryssingspunktet rekna vi ut i kapittel 5.1:

$$\left(\frac{40}{7}, \frac{75}{7}\right) \approx (5{,}7,\ 10{,}7)$$

Vi reknar ut $z$ i kvart hjørne:

$$z(0, 15) = 180 \cdot 15 = 2700$$
$$z(10, 0) = 250 \cdot 10 = 2500$$
$$z\left(\frac{40}{7}, \frac{75}{7}\right) = 250 \cdot \frac{40}{7} + 180 \cdot \frac{75}{7} = \frac{10\,000}{7} + \frac{13\,500}{7} = \frac{23\,500}{7} \approx 3357$$

Svar: Den største verdien er $\displaystyle \frac{23\,500}{7} \approx 3357$ kr, i hjørnepunktet $\displaystyle \left(\frac{40}{7}, \frac{75}{7}\right)$.

b) Verkstaden kan ikkje lage $5{,}7$ korger. Vi testar heiltalspunkta rundt hjørnet, og hugsar at begge vilkåra må vere oppfylte.

Punkt	$3x + 4y \le 60$	$5x + 2y \le 50$	$z = 250x + 180y$
$(6, 11)$	$62$ — nei	$52$ — nei	ulovleg
$(6, 10)$	$58$ — ja	$50$ — ja	3300 kr
$(5, 11)$	$59$ — ja	$47$ — ja	3230 kr
$(5, 10)$	$55$ — ja	$45$ — ja	3050 kr
$(4, 12)$	$60$ — ja	$44$ — ja	3160 kr

Den beste lovlege kombinasjonen av heile tal er $(6, 10)$.
Svar: Verkstaden bør lage 6 korger og 10 vesker. Det gir 3300 kr.
Vi tapar
$$3357 - 3300 = 57$$
altså om lag 57 kr på at talet må vere heile tal. Det er under 2 % av den teoretiske grensa.
NB: Legg merke til at $(6, 10)$ brukar alt stoffet ($5 \cdot 6 + 2 \cdot 10 = 50$) og nesten all sytida. Det er eit godt teikn: eit optimum ligg så å seie alltid tett opp til ei eller fleire grenser.

Objektfunksjonen er

$$z = 900x + 1200y$$

Hjørnepunkta. Med tre vilkår må vi vere systematiske. Vi finn alle kandidatane og testar kvar av dei mot alle vilkåra.

På $y$-aksen: mjølk gir $y \le 100$, modning gir $y \le 70$, arbeid gir $y \le 60$. Strengast er 60, så hjørnet er $(0, 60)$.

Modning møter arbeid:

$$x + y = 70$$
$$x + 2y = 120$$

Vi trekkjer den første frå den andre:

$$(x + 2y) - (x + y) = 120 - 70$$
$$y = 50$$

Då er $x = 70 - 50 = 20$. Kandidaten er $(20, 50)$. Mjølk: $2 \cdot 20 + 50 = 90 \le 100$ — lovleg.

Mjølk møter modning:

$$2x + y = 100$$
$$x + y = 70$$

Vi trekkjer den andre frå den første:

$$(2x + y) - (x + y) = 100 - 70$$
$$x = 30$$

Då er $y = 70 - 30 = 40$. Kandidaten er $(30, 40)$. Arbeid: $30 + 2 \cdot 40 = 110 \le 120$ — lovleg.

På $x$-aksen: mjølk gir $x \le 50$, modning gir $x \le 70$, arbeid gir $x \le 120$. Strengast er 50, så hjørnet er $(50, 0)$.

Reknearket. Vi set hjørnepunkta i to kolonnar og lèt reknearket gjere resten:

        A       B        C              D              E              F
1       x       y        melk           modning        arbeid         z
2       0       0        =2*A2+B2       =A2+B2         =A2+2*B2       =900*A2+1200*B2

Formlane i rad 2 blir fylte nedover for alle hjørnepunkta, og i ei eiga celle skriv vi =MAKS(F2:F6).

Hjørnepunkt	mjølk	modning	arbeid	$z$
$(0, 0)$	0	0	0	0 kr
$(0, 60)$	60	60	120	72 000 kr
$(20, 50)$	90	70	120	78 000 kr
$(30, 40)$	100	70	110	75 000 kr
$(50, 0)$	100	50	50	45 000 kr

Svar: Meieriet bør lage 2000 kg fast ost og 5000 kg mjuk ost i veka. Det gir 78 000 kr i dekningsbidrag.
NB: Sjå på kolonnane for ressursbruk i den beste rada. Modningsrommet og arbeidstida er brukte heilt opp ($70$ og $120$), medan mjølka ikkje er det ($90$ av $100$). Mjølk er altså ikkje den knappe ressursen her. Skal meieriet tene meir, hjelper det ikkje å kjøpe meir mjølk — det er hyllemeter og timar som må til.