5.3 Optimering i praksis

Hva vet vi? Innholdet per sekk og prisen per sekk, og to minstekrav.

Hva må vi finne? Den billigste blandingen som oppfyller begge kravene.

Skritt 1 og 2. Navn og vilkår. La $x$ være antall sekker av fôr A og $y$ antall sekker av fôr B.

Protein: fôr A gir $2x$ enheter og fôr B gir $y$ enheter. (Vi skriver vanligvis ikke 1-tallet.) Til sammen minst 20:

$$2x + y \ge 20$$

Fiber: fôr A gir $x$ enheter og fôr B gir $2y$ enheter. Til sammen minst 22:

$$x + 2y \ge 22$$

I tillegg er $x \ge 0$ og $y \ge 0$.

Skritt 3. Objektfunksjonen. Kostnaden i kroner er

$$K = 180x + 150y$$

og den skal gjøres minst.

Skritt 4. Hjørnepunktene. Proteinlinjen $2x + y = 20$ treffer aksene i $(10, 0)$ og $(0, 20)$. Fiberlinjen $x + 2y = 22$ treffer aksene i $(22, 0)$ og $(0, 11)$.

På $y$-aksen: protein krever $y \ge 20$, fiber krever $y \ge 11$. Her er det strengeste kravet $y \ge 20$, så hjørnet er $(0, 20)$.

NB: Med minstekrav er det det største av kravene som bestemmer — motsatt av i kapittel 5.1, der vi valgte det minste. Grunnen er den samme: begge krav må være oppfylt.

På $x$-aksen: protein krever $x \ge 10$, fiber krever $x \ge 22$. Strengest er $x \ge 22$, så hjørnet er $(22, 0)$.

Krysningspunktet. Vi løser likningssettet med addisjonsmetoden. Vi ganger den andre likningen med 2:

$$x + 2y = 22 \qquad | \; \cdot 2$$
$$2x + 4y = 44$$

Vi trekker den første likningen fra denne:

$$(2x + 4y) - (2x + y) = 44 - 20$$
$$3y = 24 \qquad | \; : 3$$
$$y = 8$$

Vi setter inn i den første likningen: $2x + 8 = 20$, altså $2x = 12$ og $x = 6$.

Kontroll: protein $2 \cdot 6 + 8 = 20$ og fiber $6 + 2 \cdot 8 = 22$. Begge kravene er akkurat oppfylt.

Skritt 5. Vi regner ut $K$ i hvert hjørne.

Hjørnepunkt	$K = 180x + 150y$
$(0, 20)$	3000 kr
$(6, 8)$	2280 kr
$(22, 0)$	3960 kr

Området er ubegrenset — skraveringen slutter ikke, den går ut av bildet. Likevel finnes minimum: nivålinjen skyves nedover til venstre til den så vidt berører området, og det siste punktet den treffer, er hjørnet $(6, 8)$.
Svar: Gården bør kjøpe 6 sekker av fôr A og 8 sekker av fôr B. Det koster 2280 kr, og blandingen gir nøyaktig 20 enheter protein og 22 enheter fiber.
NB: Legg merke til at fôr B er billigst per sekk, men det lønner seg likevel ikke å kjøpe bare B. Da måtte gården ha 20 sekker for å få nok protein, og det ville koste 3000 kr. Den billigste veien er å bruke begge — akkurat som i kapittel 5.2 er det forholdet mellom pris og innhold som avgjør, ikke prisen alene.

Objektfunksjonen. Fortjenesten per hundre brød er 900 kr for grovbrød og 1100 kr for loff:

$$z = 900x + 1100y$$

Hjørnepunktene. Vi går rundt kanten.

På $y$-aksen: avtalen krever $y \ge 6$, deigmaskinen gir $y \le 14$, ovnen gir $4y \le 48$, altså $y \le 12$. Strengeste tak er 12, så $y$ ligger mellom 6 og 12. Det gir to hjørner: $(0, 6)$ og $(0, 12)$.

På $x$-aksen: avtalen krever $x \ge 6$, deigmaskinen gir $x \le 14$, ovnen gir $3x \le 48$, altså $x \le 16$. Strengeste tak er 14, så $x$ ligger mellom 6 og 14. Hjørnene er $(6, 0)$ og $(14, 0)$.

Deigmaskinen møter ovnen:

$$x + y = 14$$
$$3x + 4y = 48$$

Vi ganger den første likningen med 3:

$$x + y = 14 \qquad | \; \cdot 3$$
$$3x + 3y = 42$$

Vi trekker denne fra den andre likningen:

$$(3x + 4y) - (3x + 3y) = 48 - 42$$
$$y = 6$$

Da er $x = 14 - 6 = 8$. Kandidaten er $(8, 6)$. Kontroll mot avtalen: $8 + 6 = 14 \ge 6$ — lovlig.

Avtalen møter ovnen: $x + y = 6$ og $3x + 4y = 48$ gir $3x + 3y = 18$, og $(3x + 4y) - (3x + 3y) = 48 - 18$, altså $y = 30$ og $x = -24$. Negativt, så dette punktet ligger utenfor området. Vi forkaster det.

Vi regner ut $z$ i hvert hjørne.

Hjørnepunkt	$z = 900x + 1100y$
$(0, 6)$	6600 kr
$(0, 12)$	13 200 kr
$(6, 0)$	5400 kr
$(8, 6)$	13 800 kr
$(14, 0)$	12 600 kr

Svar: Bakeriet bør bake 800 grovbrød og 600 loff. Det gir 13 800 kr i fortjeneste.
NB: To ting er verdt å merke seg. For det første er både deigmaskinen og ovnen brukt helt opp i det beste punktet ($8 + 6 = 14$ og $3 \cdot 8 + 4 \cdot 6 = 48$) — begge er knappe. For det andre spilte leveringsavtalen ingen rolle for svaret: bakeriet baker 1400 brød uansett, langt over de 600 avtalen krever. Et vilkår som ikke påvirker løsningen, kalles ikke-bindende, og det er nyttig å si fra om det: avtalen koster bakeriet ingenting.

Vilkårene.

$$x + y \le 30 \qquad \text{(hallen)}$$
$$x \ge 8 \qquad \text{(vedtak)}$$
$$y \ge 10 \qquad \text{(vedtak)}$$
$$400x + 600y \le 15\,200 \qquad \text{(budsjett)}$$

Budsjettvilkåret forenkler vi ved å dele på 200:

$$400x + 600y \le 15\,200 \qquad | \; : 200$$
$$2x + 3y \le 76$$

Objektfunksjonen. Vi teller deltakertimer, altså hvor mange som får trene til sammen:

$$D = 18x + 12y$$

Hjørnepunktene.

$x = 8$ møter $y = 10$: punktet $(8, 10)$. Kontroll: hall $18 \le 30$, budsjett $16 + 30 = 46 \le 76$ — lovlig.

$x = 8$ møter budsjettlinjen: $2 \cdot 8 + 3y = 76$ gir $3y = 60$, altså $y = 20$. Punktet $(8, 20)$. Kontroll: hall $28 \le 30$ — lovlig.

Budsjettlinjen møter hall-linjen:

$$2x + 3y = 76$$
$$x + y = 30$$

Vi ganger den andre likningen med 2:

$$x + y = 30 \qquad | \; \cdot 2$$
$$2x + 2y = 60$$

Vi trekker denne fra den første:

$$(2x + 3y) - (2x + 2y) = 76 - 60$$
$$y = 16$$

Da er $x = 30 - 16 = 14$. Punktet er $(14, 16)$.

$y = 10$ møter hall-linjen: $x = 20$. Punktet $(20, 10)$. Kontroll: budsjett $40 + 30 = 70 \le 76$ — lovlig.

Vi regner ut $D$ i hvert hjørne.

Hjørnepunkt	$D = 18x + 12y$
$(8, 10)$	264
$(8, 20)$	384
$(14, 16)$	444
$(20, 10)$	480

Fire vilkår av fire ulike typer: to tak (hallen og budsjettet) og to gulv (de to vedtakene). Den største verdien, $D = 480$, ligger i hjørnet $(20, 10)$.
Svar: Klubben bør sette opp 20 timer barnetrening og 10 timer ungdomstrening. Da får 480 deltakertimer trening i uka.
Tolkning. Løsningen fyller hallen helt ($20 + 10 = 30$ timer) og bruker
$$400 \cdot 20 + 600 \cdot 10 = 8000 + 6000 = 14\,000$$

kroner av budsjettet på 15 200 kr. Hallen er den knappe ressursen, ikke pengene. Klubben har 1200 kr til overs, men ingen ledige timer.

NB: Legg merke til at løsningen legger ungdomstreningen på nøyaktig minstekravet 10 timer. Det er ikke fordi ungdomstrening er mindre verdt — det er fordi objektfunksjonen bare teller hoder, og det møter flere barn per time. Hadde styret ikke vedtatt minstekravet, ville modellen foreslått 30 timer barnetrening og null ungdomstrening. Vedtaket er nettopp der for å hindre det. Dette er et godt eksempel på at objektfunksjonen aldri måler alt vi bryr oss om.

Objektfunksjonen er

$$z = 1800x + 1500y$$

Hjørnepunktene. Med fire vilkår lønner det seg å være systematisk: vi finner alle skjæringspunkter som kan være hjørner, og tester hvert av dem mot alle vilkårene.

På $y$-aksen ($x = 0$): avtalen gir $y \ge 10$; tømmer gir $y \le 60$, høvel $y \le 90$, tørke $y \le 42$. Strengeste tak er 42. Hjørnene er $(0, 10)$ og $(0, 42)$.

Tørke møter tømmer:

$$x + 3y = 126$$
$$x + y = 60$$

Vi trekker den andre fra den første:

$$(x + 3y) - (x + y) = 126 - 60$$
$$2y = 66 \qquad | \; : 2$$
$$y = 33$$

Da er $x = 60 - 33 = 27$. Kandidaten er $(27, 33)$. Høvel: $2 \cdot 27 + 33 = 87 \le 90$ — lovlig.

Tømmer møter høvel:

$$x + y = 60$$
$$2x + y = 90$$

Vi trekker den første fra den andre:

$$(2x + y) - (x + y) = 90 - 60$$
$$x = 30$$

Da er $y = 30$. Kandidaten er $(30, 30)$. Tørke: $30 + 3 \cdot 30 = 120 \le 126$ — lovlig.

Høvel møter avtalen $y = 10$: $2x + 10 = 90$ gir $x = 40$. Kandidaten er $(40, 10)$. Tømmer: $50 \le 60$, tørke: $70 \le 126$ — lovlig.

Regnearket. Vi legger hjørnepunktene i kolonne A og B og lar regnearket regne ressursbruken og dekningsbidraget:

        A     B      C           D             E             F
1       x     y      tømmer      høvel         tørke         z
2       0     10     =A2+B2      =2*A2+B2      =A2+3*B2      =1800*A2+1500*B2

Formlene fylles nedover, og i en egen celle skriver vi =MAKS(F2:F6).

Hjørnepunkt	tømmer / 60	høvel / 90	tørke / 126	$z$
$(0, 10)$	10	10	30	15 000 kr
$(0, 42)$	42	42	126	63 000 kr
$(27, 33)$	60	87	126	98 100 kr
$(30, 30)$	60	90	120	99 000 kr
$(40, 10)$	50	90	70	87 000 kr

Fem hjørner, og to av dem ligger så tett at valget mellom dem trygt kan avgjøres av noe modellen ikke måler. $z = 1800x + 1500y$ gir 98 100 kr i $(27, 33)$ og 99 000 kr i $(30, 30)$.
Svar: Sagbruket bør lage 30 m³ terrassebord og 30 m³ kledning i uka. Det gir 99 000 kr i dekningsbidrag.
Hvilke ressurser er knappe? I den beste raden ser vi at tømmeret er brukt helt opp ($60$ av $60$) og høvelen likeså ($90$ av $90$), mens tørka har litt igjen ($120$ av $126$).
Svar: Tømmer og høveltid er de knappe ressursene. Skal sagbruket tjene mer, må det skaffe mer av begge — mer tømmer alene stopper på høvelen, og mer høveltid alene stopper på tømmeret.
NB: Legg merke til hvor tett $(27, 33)$ og $(30, 30)$ ligger: 98 100 kr mot 99 000 kr, altså under én prosent. Når to hjørner er så nær hverandre, bør vi si det i svaret. Da vet den som skal bestemme, at valget mellom dem trygt kan avgjøres av noe modellen ikke måler — for eksempel hva kundene faktisk spør etter.