---
tags: vaje, or, odlocanje, drevesa
hackmd: https://hackmd.io/tiaawBf5QlWBT3NVbwaJsQ
plugins: mathjax, mermaid
---
# Operacijske raziskave - vaje 23.3.2020

---

## Odločitvena drevesa

### Naloga 1

Imaš sledeče odločitveno drevo, a nisi prepričan glede vrednosti $p \in [0, 1/3]$. Poišči optimalne odločitve glede na vrednost $p$. Pričakovano vrednost želimo maksimizirati.

graph LR

A[A] -- p < 5/19 --- B[B]
A -- p >= 5/19 --- C([C: 22p-5])
B -- p > 2/7 --- D([D: 10p-2])
B == p <= 2/7 === E([E: 3p])
C -- p --- F>10]
C -- p --- G>2]
C -- 1-2p --- H>-5]
D -- 2p --- I>3]
D -- 1-2p --- J>-2]
E -- 3p --- K>1]
E -- 1-3p --- L>0]

----

$$
\begin{alignedat}{2}
E(D) &= 2p \cdot 3 + (1-2p) \cdot (-2) &&= 10p - 2 \\
E(E) &= 3p \cdot 1 + (1-3p) \cdot 0 &&= 3p \\
E(C) &= p \cdot 10 + p \cdot 2 + (1-2p) \cdot (-5) &&= 22p - 5
\end{alignedat}
$$

$$
\begin{aligned}
10p - 2 &> 3p \\
7p &> 2 \\
p &> 2/7
\end{aligned}
$$

$$
E(B) =
\begin{cases}
10p - 2 & p > 2/7 \\
3p & p \le 2/7
\end{cases}
$$

$$
\begin{aligned}
3p &> 22p - 5 \\
19p &< 5 \\
p &< 5/19 < 2/7
\end{aligned}
$$

$$
\begin{aligned}
10p - 2 &> 22p - 5 \\
12p &< 3 \\
p &< 1/4 < 2/7
\end{aligned}
$$

$$
E(A) =
\begin{cases}
3p & p < 5/19 \\
22p - 5 & p \ge 5/19
\end{cases}
$$

---

### Naloga 2

Pacient ima na voljo operacijo. Brez operacije bo živel natanko $3$ mesece. Z uspešno opravljeno operacijo bo živel natanko $12$ mesecev. Operacija je neuspešna z verjetnostjo $0.3$ (v tem primeru pacient dočaka $0$ mesecev). Cilj pacienta je maksimiranje pričakovane življenjske dobe.

1. Ali naj pacient sprejme operacijo?
2. Pacient lahko opravi predhodni test, ki z zanesljivostjo $0.9$ napove uspešnost operacije, vendar z verjetnostjo $0.005$ pacient zaradi komplikacij med testom umre. Ali naj pacient opravi test?

Nariši odločitveno drevo in odločitve sprejmi na podlagi izračunanih verjetnosti!

----

$$
\begin{aligned}
X &\dots \text{čas življenja} \\
A &\dots \text{operacija uspešna} \\
B &\dots \text{sprejme operacijo} \\
C &\dots \text{opravi test} \\
D &\dots \text{test poztiven} \\
E &\dots \text{komplikacije}
\end{aligned}
$$

$$
\begin{aligned}
P(A) &= 0.7 \\
P(\lnot A) &= 0.3 \\[1ex]
E(X \mid \lnot C \land \lnot B) &= 3 \\
E(X \mid \lnot C \land B \land A) &= 12 \\
E(X \mid \lnot C \land B \land \lnot A) &= 0 \\[1ex]
E(X \mid \lnot C \land B) &= 0.7 \cdot 12 + 0.3 \cdot 0 = 8.4 \\[1ex]
P(D \mid A) &= 0.9 \\
P(\lnot D \mid A) &= 0.1 \\
P(\lnot D \mid \lnot A) &= 0.9 \\
P(D \mid \lnot A) &= 0.1 \\[1ex]
P(E \mid C) &= 0.005 \\[1ex]
P(D) &= 0.9 \cdot 0.7 + 0.1 \cdot 0.3 = 0.66 \\
P(\lnot D) &= 0.1 \cdot 0.7 + 0.9 \cdot 0.3 = 0.34
\end{aligned}
$$

$$
\begin{alignedat}{3}
P(A \mid D) &= {P(D \mid A) \cdot P(A) \over P(D)} &&= {0.9 \cdot 0.7 \over 0.66} &&\approx 0.955 \\
P(\lnot A \mid D) &= {P(D \mid \lnot A) \cdot P(\lnot A) \over P(D)} &&= {0.1 \cdot 0.3 \over 0.66} &&\approx 0.045 \\
P(A \mid \lnot D) &= {P(\lnot D \mid A) \cdot P(A) \over P(\lnot D)} &&= {0.1 \cdot 0.7 \over 0.34} &&\approx 0.206 \\
P(\lnot A \mid \lnot D) &= {P(\lnot D \mid \lnot A) \cdot P(\lnot A) \over P(\lnot D)} &&= {0.9 \cdot 0.3 \over 0.34} &&\approx 0.794
\end{alignedat}
$$

----

graph LR

C[opravi test?: 8.537] == ja === E([komplikacije?: 8.537])
C -- ne --- B
E -- ja: 0.005 --- w>0]
E -- ne: 0.995 --- D([pozitiven?: 8.58])
D -- ja: 0.66 --- BD
D -- ne: 0.34 --- BC
BD[sprejme?: 11.455] == ja === AD([uspešna?: 11.455])
BD -- ne --- zD>3]
AD -- ja: 0.955 --- yD>12]
AD -- ne: 0.045 --- xD>0]
BC[sprejme?: 3] -- ja --- AC([uspešna?: 2.471])
BC == ne === zC>3]
AC -- ja: 0.206 --- yC>12]
AC -- ne: 0.794 --- xC>0]
B[sprejme?: 8.4] == ja === A([uspešna?: 8.4])
B -- ne --- z>3]
A -- ja: 0.7 --- y>12]
A -- ne: 0.3 --- x>0]

Pacient naj se odloči za testiranje - če to da pozitiven rezultat, naj se odloči za operacijo, sicer pa ne. Pričakovana življenjska doba je $8.537$ mesecev.

---

### Naloga 3

Podjetje je razvilo produkt, za katerega je konkurenca pripravljena plačati $15 M€$. Če se odločijo samostojno prodajati produkt, jih vzpostavitev proizvodnje stane $6 M€$, za vsak uspešno prodan produkt pa dobijo $600 €$. Računajo, da bi z verjetnostjo $0.5$ investicija uspela in bi prodali $100000$ produktov, z verjetnostjo $0.5$ pa bi projekt propadel in bi prodali zgolj $10000$ produktov. Podjetje se lahko odloči tudi za neodvisno raziskavo trga. Ta stane $1 M€$, z verjetnostjo $2/3$ pa bo pravilno napovedala uspeh projekta (ne glede na to, ali bi ta uspel ali ne). Kako naj se podjetje odloči?

----

$$
\begin{aligned}
X &\dots \text{zaslužek} \\
A &\dots \text{opravijo raziskavo} \\
B &\dots \text{napove uspeh} \\
C &\dots \text{vzpostavijo proizvodnjo} \\
D &\dots \text{projekt uspešen}
\end{aligned}
$$

$$
\begin{aligned}
E(X \mid \lnot A \land \lnot C) &= 15 M€ \\
E(X \mid A \land \lnot C) &= 14 M€ \\
E(X \mid \lnot A \land C \land D) &= 54 M€ \\
E(X \mid A \land C \land D) &= 53 M€ \\
E(X \mid \lnot A \land C \land \lnot D) &= 0 M€ \\
E(X \mid A \land C \land \lnot D) &= -1 M€ \\[1ex]
P(D) &= 0.5 \\
P(\lnot D) &= 0.5 \\[1ex]
P(B \mid D) &= 2/3 \\
P(\lnot B \mid D) &= 1/3 \\
P(B \mid \lnot D) &= 1/3 \\
P(\lnot B \mid \lnot D) &= 2/3 \\[1ex]
P(B) &= 2/3 \cdot 0.5 + 1/3 \cdot 0.5 = 0.5 \\
P(\lnot B) &= 0.5 \\[1ex]
P(D \mid B) &= 2/3 \cdot 0.5 / 0.5 = 2/3 \\
P(D \mid \lnot B) &= 1/3 \cdot 0.5 / 0.5 = 1/3
\end{aligned}
$$

----

graph LR

A[raziskava?] -- ja --- B([napoved?: 26])
A == ne === C[proizvodnja?: 27]
B -- ja: 0.5 --- CB[proizvodnja?: 35]
B -- ne: 0.5 --- CnB[proizvodnja?: 17]
C == ja === D([uspešen?: 27])
C -- ne --- a>15]
CB == ja === DB([uspešen?: 35])
CB -- ne --- aB>14]
CnB == ja === DnB([uspešen?: 17])
CnB -- ne --- anB>14]
D -- ja: 0.5 --- b>54]
D -- ne: 0.5 --- c>0]
DB -- ja: 2/3 --- bB>53]
DB -- ne: 1/3 --- cB>-1]
DnB -- ja: 1/3 --- bnB>53]
DnB -- ne: 2/3 --- cnB>-1]

---

### Naloga 4

Rexhep Bajrami bi se rad naslednja štiri leta ukvarjal s prodajo sadja in zelenjave (po štirih letih mu poteče delovna viza). Rad bi najel parcelo za stojnico, ki bo stala $6000 €$. Če je lokacija dobra, bo imel $12000 €$ dobička, če pa je lokacija slaba, bo imel le $3000 €$ dobička. Ocenjuje, da je z verjetnostjo $2/3$ lokacija dobra, z verjetnostjo $1/3$ pa slaba.

1. Z odločitvenim drevesom opiši njegove možnosti in ugotovi, kako naj se odloči ter kakšen dobiček naj pričakuje.
2. Za nasvet lahko vpraša znanca Seada, ki "ima nos" za tovrstne posle. Sead mu lahko da nasvet, a zanj zahteva $1200 €$. Dobro je znano, da ima Sead naslednje pogojne verjetnosti $P(\text{Seadovo mnenje} \mid \text{kakovost parcele})$:

| | dobra | slaba |
| ------------- | ----- | ----- |
| **priporoča** | $2/3$ | $1/2$ |
| **odsvetuje** | $1/3$ | $1/2$ |

Ali naj vpraša Seada za nasvet? Kakšen je pričakovani dobiček?

----

$$
\begin{aligned}
X &\dots \text{dobiček} \\
A &\dots \text{vprašamo za mnenje} \\
B &\dots \text{priporoča} \\
C &\dots \text{najem} \\
D &\dots \text{dobra odločitev}
\end{aligned}
$$

$$
\begin{aligned}
E(X \mid \lnot A \land \lnot C) &= 0 \\
E(X \mid A \land \lnot C) &= -1200 \\
E(X \mid \lnot A \land C \land D) &= 6000 \\
E(X \mid \lnot A \land C \land \lnot D) &= -3000 \\
E(X \mid A \land C \land D) &= 4800 \\
E(X \mid A \land C \land \lnot D) &= -4200 \\[1ex]
P(B \mid D) &= 2/3 \\
P(\lnot B \mid D) &= 1/3 \\
P(B \mid \lnot D) &= 1/2 \\
P(\lnot B \mid \lnot D) &= 1/2
\end{aligned}
$$

graph LR

A[vpraša za mnenje?] -- ja --- B([priporoča?: 1800])
A == ne === C[najame?: 3000]
B -- ja: 11/18 --- CB[najame?: 2345.45]
B -- ne: 7/18 --- CnB[najame?: 942.86]
C == ja === D([dobra odločitev?: 3000])
C -- ne --- a>0]
CB == ja === DB([dobra odločitev?: 2345.45])
CB -- ne --- aB>-1200]
CnB == ja === DnB([dobra odločitev?: 942.86])
CnB -- ne --- anB>-1200]
D -- ja: 2/3 --- b>6000]
D -- ne: 1/3 --- c>-3000]
DB -- ja: 8/11 --- bB>4800]
DB -- ne: 3/11 --- cB>-4200]
DnB -- ja: 4/7 --- bnB>4800]
DnB -- ne: 3/7 --- cnB>-4200]

---

### Naloga 5

Mudi se ti na izpit, a ravno v trenutku, ko prideš na postajo Konzorcij, odpelje avtobus številka 1. Na prikazovalniku se izpiše, da bo naslednji avtobus številka 1 prispel čez $10$ minut, naslednji avtobus številka 6 čez $6$ minut, naslednji avtobus številka 14 pa čez $2$ minuti.

Avtobusa 1 in 6 ob ugodnih semaforjih potrebujeta $6$ minut do postaje pri FE, pri čemer se lahko čas vožnje zaradi rdeče luči na semaforju pri FF podaljša za $1$ minuto. Verjetnosti, da bo rdečo luč imel avtobus 1, da bo rdečo luč imel avtobus 6, ter da bosta oba avtobusa imela zeleno luč, so enake $1/3$ (zaradi majhnega razmaka se ne more zgoditi, da bi oba avtobusa naletela na rdečo luč). Avtobus številka 1 nadaljuje pot do postaje pri FMF, za kar potrebuje še $2$ minuti.

Avtobus številka 14 potrebuje $5$ minut do postaje pri študentskih domovih, od tam pa greš peš do postaje pri FE, za kar potrebuješ še $4$ minute. Pri tem prečkaš železnico -- če mimo pripelje vlak (kar se zgodi z verjetnostjo $0.05$), se čas hoje podaljša za $3$ minute. Ko prideš na postajo pri FE (ne glede na to, ali si prišel z avtobusom 6 ali 14), te čakajo še $4$ minute hoje do FMF, vendar moraš najprej prečkati Tržaško cesto. Če je na semaforju rdeča luč (kar se zgodi z verjetnostjo 0.9, neodvisno od drugih dogodkov), se lahko odločiš, da $2$ minuti počakaš na zeleno luč in potem nadaljuješ peš, ali pa da greš nazaj do postaje in počakaš na avtobus številka $1$ (ki bo, tako kot prej, vozil še $2$ minuti do FMF).

Kakšne bodo tvoje odločitve, da bo pričakovano trajanje poti do FMF čim krajše? Nariši odločitveno drevo in odločitve sprejmi na podlagi izračunanih verjetnosti!

----