5.2 Lineær optimering

Hva vet vi? To ressurser med hver sin grense, og overskuddet per enhet.

Hva må vi finne? Det punktet i det lovlige området som gir størst overskudd.

Skritt 1 og 2. Navn og vilkår. La $x$ være antall krakker og $y$ antall bord.

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

Skritt 3. Objektfunksjonen. Overskuddet er 300 kr per krakk og 500 kr per bord:

$$O = 300x + 500y$$

$O$ måler overskuddet i kroner.

Skritt 4. Hjørnepunktene. Dem fant vi i kapittel 5.1:

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

Skritt 5. Vi regner ut $O$ i hvert 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

Skritt 6. Svar. Den største verdien er 11 000 kr, og den får vi i punktet $(20, 10)$.
Svar: Verkstedet bør lage 20 krakker og 10 bord. Da blir overskuddet 11 000 kr.
NB: Legg merke til at bordene gir mest per stykk (500 kr mot 300 kr), men det lønner seg likevel ikke å lage bare bord. Grunnen er at et bord bruker dobbelt så mye sagetid som en krakk. Det er forholdet mellom fortjeneste og ressursbruk som avgjør, ikke fortjenesten alene.

La $x$ være 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ørnepunktene. Pressa treffer aksene i $(30, 0)$ og $(0, 20)$, flaskene i $(15, 0)$ og $(0, 60)$.

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

Krysningspunktet finner vi med addisjonsmetoden. Vi ganger den andre likningen med 3:

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

Vi trekker den første likningen fra denne:

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

Vi setter inn i den andre likningen: $4 \cdot 12 + y = 60$, altså $y = 12$. Krysningspunktet er $(12, 12)$.

Vi regner ut $z$ i hvert 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ørner gir nøyaktig det samme. Da er verdien den samme i hele kanten mellom dem.
Hvorfor? Vi ser på nivålinjen for $z = 6000$:
$$200x + 300y = 6000 \qquad | \; : 100$$
$$2x + 3y = 60$$
Det er akkurat grenselinjen til pressa. Nivålinjen er altså ikke bare parallell med kanten — den er kanten.

Nivålinjen for $z = 6000$ er ikke bare parallell med kanten — den er kanten (gul). Derfor gir alle punkter mellom $(0, 20)$ og $(12, 12)$ det samme dekningsbidraget.

Svar: Alle punktene på kanten fra $(0, 20)$ til $(12, 12)$ gir det største dekningsbidraget på 6000 kr. Bryggeriet kan for eksempel lage 600 liter eplesaft og 1600 liter pæresaft, eller ingen eplesaft og 2000 liter pæresaft — dekningsbidraget blir det samme.
NB: Felles for alle disse punktene er at pressa er brukt fullt ut. Det er den knappe ressursen her; flaskene blir det til overs av.

a) Objektfunksjonen er

$$z = 250x + 180y$$

Hjørnepunktene. Sylinjen treffer aksene i $(20, 0)$ og $(0, 15)$, stofflinjen i $(10, 0)$ og $(0, 25)$.

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

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

Vi regner ut $z$ i hvert 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) Verkstedet kan ikke lage $5{,}7$ kurver. Vi tester heltallspunktene rundt hjørnet, og husker at begge vilkårene må være oppfylt.

Punkt	$3x + 4y \le 60$	$5x + 2y \le 50$	$z = 250x + 180y$
$(6, 11)$	$62$ — nei	$52$ — nei	ulovlig
$(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 lovlige kombinasjonen av hele tall er $(6, 10)$.
Svar: Verkstedet bør lage 6 kurver og 10 vesker. Det gir 3300 kr.
Vi taper
$$3357 - 3300 = 57$$
altså om lag 57 kr på at antallet må være hele tall. Det er under 2 % av den teoretiske grensen.
NB: Legg merke til at $(6, 10)$ bruker alt stoffet ($5 \cdot 6 + 2 \cdot 10 = 50$) og nesten all sytiden. Det er et godt tegn: et optimum ligger så å si alltid tett opptil en eller flere grenser.

Objektfunksjonen er

$$z = 900x + 1200y$$

Hjørnepunktene. Med tre vilkår må vi være systematiske. Vi finner alle kandidatene og tester hver av dem mot alle vilkårene.

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

Modning møter arbeid:

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

Vi trekker den første fra den andre:

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

Da er $x = 70 - 50 = 20$. Kandidaten er $(20, 50)$. Melk: $2 \cdot 20 + 50 = 90 \le 100$ — lovlig.

Melk møter modning:

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

Vi trekker den andre fra den første:

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

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

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

Regnearket. Vi setter hjørnepunktene i to kolonner og lar regnearket gjøre 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

Formlene i rad 2 fylles nedover for alle hjørnepunktene, og i en egen celle skriver vi =MAKS(F2:F6).

Hjørnepunkt	melk	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 myk ost i uka. Det gir 78 000 kr i dekningsbidrag.
NB: Se på kolonnene for ressursbruk i den beste raden. Modningsrommet og arbeidstiden er brukt helt opp ($70$ og $120$), mens melka ikke er det ($90$ av $100$). Melk er altså ikke den knappe ressursen her. Skal meieriet tjene mer, hjelper det ikke å kjøpe mer melk — det er hyllemeter og timer som må til.