---
tags: vaje, or, dinamicno programiranje
hackmd: https://hackmd.io/xwRNAIs4RwinQBLHR1TXjg
plugins: mathjax
---
# Operacijske raziskave - vaje 12.4.2021

---

## Dinamično programiranje

### Naloga 1

Lastnik verige $n$ trgovin z živili je kupil $m$ zabojev svežih jagod. Naj bo ${p_{ij}}$ pričakovan dobiček v trgovini $j$, če tja dostavimo $i$ zabojev. Zanima nas, koliko zabojev naj gre v vsako trgovino, da bomo imeli čim večji zaslužek. Zaradi logističnih razlogov zabojev ne želimo deliti.

1. Z dinamičnim programiranjem reši problem za podatke $m = 5$, $n = 3$ in ${p_{ij}}$ iz sledeče tabele:

| ${p_{ij}}$ | 1 | 2 | 3 |
| ---------- | -- | -- | -- |
| 0 | 0 | 0 | 0 |
| 1 | 5 | 6 | 4 |
| 2 | 9 | 11 | 9 |
| 3 | 14 | 15 | 13 |
| 4 | 17 | 19 | 18 |
| 5 | 21 | 22 | 20 |

2. Napiši algoritem, ki reši opisani problem v splošnem.

----

1. * ${z_{ij}}$ ... največji zaslužek, če razdelimo $i$ zabojev v prvih $j$ trgovin
* ${z_{i1}} = {p_{i1}}$ ($0 \le i \le m$)
* ${z_{ij}} = \max \lbrace {z_{h,j-1}} + {p_{i-h,j}} \mid 0 \le h \le i \rbrace$ ($0 \le i \le m$, $2 \le j \le n$)
* računamo v leksikografskem vrstnem redu po $i, j$
* maksimalni zaslužek $z^* = {z_{mn}}$

| ${z_{ij}}$ | 1 | 2 | 3 |
| ---------- | -- | ---------- | ---------- |
| 0 | 0 | 0 | 0 |
| 1 | 5 | 6 (0) | 6 (1) |
| 2 | 9 | 11 (0,1) | 11 (2) |
| 3 | 14 | 16 (1) | 16 (3) |
| 4 | 17 | 20 (1,2,3) | 20 (2,3,4) |
| 5 | 21 | 25 (3) | 25 (5,3) |

Optimalna razporeditev:

1. trgovina: 3
2. trgovina: 2
3. trgovina: 0

Druga optimalna razporeditev:

1. trgovina: 1
2. trgovina: 2
3. trgovina: 2

---

### Naloga 2

Podjetje ima na voljo $6000 €$ za investiranje. Na voljo so tri investicije, pri katerih je donosnost (v $1000 €$) enaka

$$
\begin{align}
r_1(d_1) &= \begin{cases}
7d_1 + 2, & \text{če $d_1 \ge 1$, in} \\
0 & \text{sicer;} \end{cases} \\
r_2(d_2) &= \begin{cases}
3d_2 + 7, & \text{če $d_2 \ge 1$, in} \\
0 & \text{sicer;} \end{cases}
\quad \text{oziroma} \\
r_3(d_3) &= \begin{cases}
4d_3 + 5, & \text{če $d_3 \ge 1$, in} \\
0 & \text{sicer;} \end{cases}
\end{align}
$$

kjer so ${d_1}, {d_2}, {d_3}$ vložki v vsako investicijo v $1000 €$. Kako naj podjetje investira svoj denar, da bo zaslužek čim večji?

----

* ${z_i}(x)$ ... največji donos, če investiramo $x \cdot 1000€$ v prvih $i$ investicij
* ${z_1}(x) = {r_1}(x)$
* ${z_i}(x) = \max \lbrace {z_{i-1}}(y) + {r_i}(x-y) \mid 0 \le y \le x \rbrace$
* $z^* = {z_3}(6)$

$$
\begin{alignedat}{3}
z_2(x) &= \max &&\{ r_1(y) + r_2(x-y) \mid 0 \le y \le x \} \\
&= \max&(&\ \{0 \mid x-1 < y \le 1, \ y \le x\} &\ (x &< 2) \\
&& \cup &\ \{7y+2 \mid x-1 < y, \ 1 \le y \le x\} &\ (x &\ge 1) \\
&& \cup &\ \{3x - 3y + 7 \mid y < 1, \ 0 \le y \le x-1 \} &\ (x &\ge 1) \\
&& \cup &\ \{3x + 4y + 9 \mid 1 \le y \le x-1\}) &\ (x &\ge 2) \\
&&&= \begin{cases}
0 & 0 \le x < 1 \\
\max\{0, 7x+2, 3x+7\} & 1 \le x < 2 \\
\max\{7x+2, 3x+7, 7x+5\} & 2 \le x \le 6
\end{cases} \\
&&&= \begin{cases}
0 & 0 \le x < 1 \\
3x+7 & 1 \le x < 5/4 \\
7x+2 & 5/4 \le x < 2 \\
7x+5 & 2 \le x \le 6
\end{cases} \\[1ex]
z_3(6) &= \max &&\{ z_2(y) + r_3(6-y) \mid 0 \le y \le 6 \} \\
&= \max &(&\ \{29 - 4y \mid 0 \le y < 1 \} \\
&& \cup &\ \{36 - y \mid 1 \le y < 5/4\} \\
&& \cup &\ \{31 + 3y \mid 5/4 \le y < 2\} \\
&& \cup &\ \{34 + 3y \mid 2 \le y \le 5\} \\
&& \cup &\ \{5 + 7y \mid 5 < y \le 6\}) \\
&= \max &&\{29, 35, 49, 47\} \\
&= 49 &&& (y = 5)
\end{alignedat}
$$

Največji zaslužek $z^* = 49$ dobimo, če vložimo:

1. investicija: 4000 €
2. investicija: 1000 €
3. investicija: 1000 €

---

### Naloga 3

Nori profesor Boltežar stanuje v stolpnici z $n$ nadstropji, oštevilčenimi od $1$ do $n$. Nori stanovalci tega bloka radi mečejo cvetlične lončke z balkonov. Boltežar bi rad ugotovil, katero je najvišje nadstropje, s katerega lahko pade cvetlični lonček, ne da bi se razbil. Jasno je, da če se lonček razbije pri padcu iz $k$-tega nadstropja, potem se razbije tudi pri padcu s $(k+1)$-tega nadstropja. Če bi Boltežar imel le en cvetlični lonček, bi ga lahko metal po vrsti od najnižjega nadstropja navzgor, dokler se ne bi razbil. V najslabšem primeru bi lonček torej vrgel $n$ krat (možno je, da bi lonček preživel tudi padec iz najvišjega nadstropja).

Ker ima Boltežar doma $k$ cvetličnih lončkov, lahko do rezultata pride tudi z manjšim številom metov. S pomočjo dinamičnega programiranja bi rad poiskal strategijo metanja, ki bi minimizirala število potrebnih metov v najslabšem primeru.

1. Napiši rekurzivne enačbe za opisani problem.
2. Napiši algoritem, ki reši opisani problem. Oceni tudi njegovo časovno zahtevnost v odvisnosti od $n$ in $k$.

----

* ${p_{ij}}$ ... največje število potrebnih metov, če imamo še $j$ lončkov in $i$ nadstropij za preveriti
* ${p_{0j}} = 0$ ($j \ge 0$)
* ${p_{i0}} = \infty$ ($i \ge 1$)
* ${p_{ij}} = 1 + \min \lbrace \max \lbrace {p_{h-1,j-1}}, {p_{i-h,j}} \rbrace \mid 1 \le h \le i \rbrace$
* računamo vrednosti ${p_{ij}}$ v leksikografskem vrstnem redu po $i, j$
* $p^* = {p_{nk}}$

def loncki(n, k):
    p = [[0] * (k+1), *([float('inf')] for _ in range(n))]
    for i in range(1, n+1):
        for j in range(1, k+1):
            m = float('inf')
            for h in range(1, i+1):
               m = min(m, max(p[h-1][j-1], p[i-h][j]))
            p[i].append(m+1)
    return p[n][k]

Časovna zahtevnost: $O(n^2 k)$

---

### Naloga 4

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}$.

----

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?

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?

---

### Naloga 5

Vodja prodaje pri založniku učbenikov za fakulteto ima na voljo $6$ trgovskih potnikov, ki jim želi dodeliti eno od treh regij, v kateri bodo delovali. V vsaki regiji mora delovati vsaj en trgovski potnik. Naj bo ${p_{ij}}$ pričakovana porast v prodaji v regiji $j$, če bo tam delovalo $i$ trgovskih potnikov:

| ${p_{ij}}$ | 1 | 2 | 3 |
| ---------- | -- | -- | -- |
| 1 | 35 | 21 | 28 |
| 2 | 48 | 42 | 41 |
| 3 | 70 | 56 | 63 |
| 4 | 89 | 70 | 75 |

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

---

### Naloga 6

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 7

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 €$.