---
tags: vaje, or, dinamicno programiranje, odlocanje
hackmd: https://hackmd.io/7-oJZKtGRSuGhA3Nn51-_w
plugins: mathjax
---
# Operacijske raziskave - vaje 28.3.2022

---

## Dinamično programiranje

### Naloga 1

Podjetje bo kmalu uvedlo nov izdelek na zelo konkurenčen trg, zato trenutno pripravlja marketinško strategijo. Odločili so se, da bodo izdelek uvedli v treh fazah. V prvi fazi bodo pripravili posebno začetno ponudbo z močno znižano ceno, da bi privabili zgodnje kupce. Druga faza bo vključevala intenzivno oglaševalsko kampanjo, da bi zgodnje kupce prepričali, naj izdelek še vedno kupujejo po redni ceni. Znano je, da bo ob koncu druge faze konkurenčno podjetje predstavilo svoj izdelek. Zato bo v tretji fazi okrepljeno oglaševanje z namenom, da bi preprečili beg strank h konkurenci.

Podjetje ima za oglaševanje na voljo $4$ milijone evrov, ki jih želimo čim bolj učinkovito porabiti. Naj bo $m$ tržni delež v procentih, pridobljen v prvi fazi, ${f_2}$ delež, ohranjen po drugi fazi, in ${f_3}$ delež, ohranjen po tretji fazi. Maksimizirati želimo končni tržni delež, torej količino $m {f_2} {f_3}$.

----

$$
\begin{aligned}
p_3(x) &= f_3(x) & \text{$x$ namenimo tretji fazi} \\
p_2(x) &= \max\{f_2(y) p_3(x-y) \mid 0 \le y \le x\} & \text{$x$ namenimo drugi in tretji fazi} \\
p_1(x) &= \max\{m(y) p_2(x-y) \mid 0 \le y \le x\} & \text{$x$ namenimo celotnemu projektu} \\
p^* &= p_1(4)
\end{aligned}
$$

----

1. Denimo, da želimo v vsaki fazi porabiti nek večkratnik milijona evrov, pri čemer bomo pri prvi fazi porabili vsaj milijon evrov. V spodnji tabeli so zbrani vplivi porabljenih količin na vrednosti $m$, ${f_2}$ in ${f_3}$.

| M€ | $m$ | ${f_2}$ | ${f_3}$ |
| -- | --- | ------- | ------- |
| 0 | - | 0.2 | 0.3 |
| 1 | 20 | 0.4 | 0.5 |
| 2 | 30 | 0.5 | 0.6 |
| 3 | 40 | 0.6 | 0.7 |
| 4 | 50 | - | - |

Kako naj razdelimo sredstva?

----

$$
\begin{aligned}
p_2(0) &= 0.2 \cdot 0.3 &&= 0.06 \\
p_2(1) &= \max\{0.2 \cdot 0.5, 0.4 \cdot 0.3\} &&= 0.12 \\
p_2(2) &= \max\{0.2 \cdot 0.6, \underline{0.4 \cdot 0.5}, 0.5 \cdot 0.3\} &&= 0.2 \\
p_2(3) &= \max\{0.2 \cdot 0.7, 0.4 \cdot 0.6, 0.5 \cdot 0.5, 0.6 \cdot 0.3\} &&= 0.25 \\
p^* = p_1(4) &= \max\{20 \cdot 0.25, \underline{30 \cdot 0.2}, 40 \cdot 0.12, 50 \cdot 0.06\} &&= 6
\end{aligned}
$$

Optimalna rešitev:
* 2 M€ v prvo fazo
* 1 M€ v drugo fazo
* 1 M€ v tretjo fazo

Dosežemo tržni delež 6%.

----

2. Denimo sedaj, da lahko v vsaki fazi porabimo poljubno pozitivno količino denarja (seveda glede na omejitev skupne porabe). Naj bodo torej ${x_1}$, ${x_2}$ in ${x_3}$ količine denarja v milijonih evrov, ki jih porabimo v prvi, drugi in tretji fazi. Vpliv na tržni delež je podan s formulami

$$
m = x_1 (10 - x_1), \quad
f_2 = 0.4 + 0.1 x_2, \quad \text{in} \quad
f_3 = 0.6 + 0.07 x_3 .
$$

Kako naj sedaj razdelimo sredstva?

----

$$
\begin{aligned}
p_3(x) &= 0.6 + 0.07 x \\
p_2(x) &= \max\{(0.4 + 0.1 y) (0.6 + 0.07 (x-y)) \mid 0 \le y \le x\} \\
&= \max\{-0.007 y^2 + (0.032 + 0.007 x) y + 0.24 + 0.028 x \mid 0 \le y \le x\} \\
0 &= -14 y + 32 + 7 x \\
0 \le y &= {32 + 7x \over 14} = {16 \over 7} + {1 \over 2} x \le x \\
p_2(x) &= 0.24 + 0.06 x \\
p^* = p_1(4) &= \max\{m(y) p_2(4-y) \mid 0 \le y \le x\} \\
&= \max\{(y (10 - y)) (0.24 + 0.06 (4-y)) \mid 0 \le y \le 4\} \\
&= \max\{(y (10 - y)) (0.48 - 0.06 y) \mid 0 \le y \le 4\} \\
&= \max\{0.06 y^3 - 1.08 y^2 + 4.8 y \mid 0 \le y \le 4\} \\
0 &= 0.18 y^2 - 2.16 y + 4.8 \\
y &= {2.16 - \sqrt{4.6656 - 3.456} \over 0.36} \approx 2.94 \\
p^* &\approx 6.30
\end{aligned}
$$

* pri $p_2(x)$ uporabimo $y = x$ (vse v drugo fazo, nič v tretjo)
* polinom tretje stopnje pri $p_1(4)$ ima pozitiven vodilni člen, zato ima maksimum pri manjši od ničel odvoda - ta leži znotraj intervala $[0, 4]$, tako da uporabimo to vrednost

Optimalna rešitev:
* $2.94$ M€ v prvo fazo
* $1.06$ M€ v drugo fazo
* nič v tretjo fazo

---

### Naloga 2

Dan je sledeči nelinearni program.

$$
\begin{aligned}
\max &\quad 2x_1^2 + 2x_2 + 4x_3 - x_3^2 \\[1ex]
2x_1 + x_2 + x_3 &\le 4 \\
x_1, x_2, x_3 &\ge 0
\end{aligned}
$$

Reši ga s pomočjo dinamičnega programiranja.

---

### Naloga 3

Igralec na srečo bo odigral tri partije s svojimi prijatelji, pri čemer lahko vsakič stavi na svojo zmago. Stavi lahko katerokoli vsoto denarja, ki jo ima na voljo - če izgubi partijo, zastavljeno vsoto izgubi, sicer pa tako vsoto pridobi. Pri vsaki partiji sta verjetnosti zmage in poraza enaki $1/2$. Na začetku ima $75 €$, na koncu pa želi imeti $100 €$ (ker igra s prijatelji, noče imeti več kot toliko).

Z dinamičnim programiranjem poišči strategijo stavljenja, ki maksimizira verjetnost, da bo na koncu imel natanko $100 €$.

---

## Teorija odločanja

### Naloga 4

Na ulici nas ustavi neznanec in nam predlaga met kovanca. Če pade grb, nam izplača $250000 €$, če pade glava, pa mi njemu $100000 €$. Ali naj sprejmemo ponudbo?

----

* pošten kovanec: $E(X) = {1 \over 2} 250000 € + {1 \over 2} (-100000 €) = 75000 €$
* ali si lahko privoščimo izgubiti $100000$ €?

---

### Naloga 5

Janez želi naložiti vsoto $1000 €$ v banko za dobo petih let.
Odloča se med tem, da bi jo vezal za pet let (obrestna mera $5\%$)
ali pa petkrat zaporedoma po eno leto (obrestna mera $4\%$).
Če denar veže za pet let, vmes pa varčevanje prekine,
mu pripada le obrestna mera $3\%$.
Ocenjuje, da lahko v naslednjih petih letih pride do naslednjih situacij:

* varčeval bo pet let, pri tem se obrestna mera ne spremeni,
* varčeval bo pet let, obrestna mera se po treh letih poveča za $30\%$,
* varčeval bo pet let, obrestna mera se po treh letih zmanjša za $20\%$,
* varčeval bo tri leta.

Opiši, kako naj se odloči glede na posamezne kriterije
(optimist, pesimist, Laplace, Savage).
Določi vrednosti parametera $\alpha$,
pri katerih je po Hurwiczevem kriteriju možnih več enakovrednih odločitev.

----

shema | nespremenjena | povečana | zmanjšana | prekinitev |
------------------ | ------------- | -------- | --------- | ---------- |
5 let | 250 € | 250 € | 250 € | / |
3 leta + 2x 1 leto | 170 € | 194 € | 154 € | / |
3 leta | 90 € | 90 € | 90 € | 90 € |
5x 1 leto | 200 € | 224 € | 184 € | / |
3x 1 leto | 120 € | 120 € | 120 € | 120 € |

Dobimo odločitveno tabelo:

začetna shema | nespremenjena | povečana | zmanjšana | prekinitev |
------------------ | ------------- | -------- | --------- | ---------- |
5 let | 250 € | 250 € | 250 € | 90 € |
5x 1 leto | 200 € | 224 € | 184 € | 120 € |

* optimistov kriterij:
- 5 let: 250 €
- 5x 1 leto: 224 €
- odločimo se z petletno vezavo
* pesimistov (Waldov) kriterij:
- 5 let: 90 €
- 5x 1 leto: 120 €
- odločimo se za letno vezavo
* Laplaceov kriterij: vse možnosti enako verjetne, gledamo pričakovani dobiček
- 5 let: $(250 € + 250 € + 250 € + 90 €)/4 = 210 €$
- 5x 1 leto: $(200 € + 224 € + 184 € + 120 €)/4 = 182 €$
- odločimo se za petletno vezavo
* Savageov kriterij: minimiziramo največje obžalovanje:
- 5 let: $120 € - 90 € = 30 €$
- 5x 1 leto: $\max\lbrace 250 € - 200 €, 250 € - 224 €, 250 € - 184 €\rbrace = 66 €$
- odločimo se za petletno vezavo
* Hurwiczev kriterij: najboljša možnost z verjetnostjo $\alpha$, najslabša z verjetnostjo $(1-\alpha)$, gledamo pričakovani dobiček
- 5 let: $\alpha \cdot 250 € + (1-\alpha) \cdot 90 € = \alpha \cdot 160 € + 90 €$
- 5x 1 leto: $\alpha \cdot 224 € + (1-\alpha) \cdot 120 € = \alpha \cdot 104 € + 120 €$
- pri $\alpha = 15/28$ sta obe možnosti enako dobri, pri manjših $\alpha$ se odločimo za letno vezavo, pri večjih $\alpha$ pa za petletno vezavo

---

### Naloga 6

Trgovina pri pekarni kupuje žemlje po $0.2 €$ in jih prodaja po $0.4 €$. Skozi leta poslovanja so izračunali naslednjo porazdelitev za prodajo žemljic.

| Prodaja | $50$ | $60$ | $70$ | $80$ | $90$ | $100$ |
| ---------- | ----- | ------ | ----- | ----- | ------ | ----- |
| Verjetnost | $0.1$ | $0.15$ | $0.3$ | $0.2$ | $0.15$ | $0.1$ |

Če žemelj zmanjka, naročijo pri pekarni razliko, pri čemer jih žemlja tedaj stane $0.3 €$. Ob koncu dneva jim pekarna odkupi presežek po $0.15 €$ na žemljo. Koliko žemelj se trgovini splača kupiti?

----

* $X$ ... število kupljenih žemelj
* $Y$ ... dobiček

$$
\begin{aligned}
E(Y \mid X = 70) &= -70 \cdot 0.2 € + 0.1 \cdot (50 \cdot 0.4 € + 20 \cdot 0.15 €) + 0.15 \cdot (60 \cdot 0.4 € + 10 \cdot 0.15 €) \\ &+ 0.3 \cdot 70 \cdot 0.4 € + 0.2 \cdot (80 \cdot 0.4 € - 10 \cdot 0.3 €) + 0.15 \cdot (90 \cdot 0.4 € - 20 \cdot 0.3 €) \\ &+ 0.1 \cdot (100 \cdot 0.4 € - 30 \cdot 0.3 €) = 13.925 €
\end{aligned}
$$

* podobno za ostala števila kupljenih žemelj
* odločimo se za možnost, kjer je pričakovani dobiček največji