Skip to content

2020-03-16.md

Latest commit

 

History

History
168 lines (128 loc) · 5.04 KB

2020-03-16.md

File metadata and controls

168 lines (128 loc) · 5.04 KB
tags vaje, or, clp, odlocanje
hackmd https://hackmd.io/r1KPyCgeRFe0FKhqe8weRw
plugins mathjax

Operacijske raziskave - vaje 16.3.2020

CLP in grafi

Naloga 1 - problem trgovskega potnika

Danih je $n$ mest na zemljevidu. Strošek potovanja iz mesta $i$ v mesto $j$ je $c_{ij}$ ($1 \le i, j \le n$). Trgovski potnik želi obiskati vseh $n$ mest, pri tem pa minimizirati strošek potovanja. Na smiseln način modeliraj opisani problem z linearnim programom.

$$ \begin{aligned} x_{ij} &= \begin{cases} 1 & \text{gremo od mesta $i$ do mesta $j$} \\ 0 & \text{sicer} \end{cases} \\ y_i &\dots \text{naraščajoča vrednost v mestu $i$} \end{aligned} $$

$$ \begin{aligned} x_{ij} = 1 &\Rightarrow y_j \ge y_i + 1 \\ x_{ij} = 0 &\Rightarrow y_j \ge y_i + 1 - n \end{aligned} $$

$$ \min \sum_{i=1}^n \sum_{j=1}^n c_{ij} x_{ij} $$

$$ \begin{alignedat}{2} \forall i, j = 1, \dots, n:&& 0 \le x_{ij} &\le 1, \quad x_{ij} \in \mathbb{Z} \\ \forall i = 1, \dots, n:&& \sum_{j=1}^n x_{ij} &= 1 \\ \forall j = 1, \dots, n:&& \sum_{i=1}^n x_{ij} &= 1 \\ \forall i = 1, ..., n \ \forall j = 2, ..., n:&& y_i + 1 - n &\le y_j - n x_{ij} \end{alignedat} $$

Naloga 2

S celoštevilskim linearnim programom modeliraj problem iskanja minimalnega vpetega drevesa v grafu.

$$ \begin{aligned} G = (V, E) &\dots \text{usmerjen graf} \\ c_{ij} &\dots \text{cene povezav} \\ x_{ij} &= \begin{cases} 1 & \text{povežemo vozlišče $i$ z vozliščem $j$} \\ 0 & \text{sicer} \end{cases} \end{aligned} $$

$$ \min \sum_{i=1}^n \sum_{j=1}^n c_{ij} x_{ij} $$

$$ \begin{alignedat}{2} \forall i, j = 1, \dots, n:&& 0 \le x_{ij} &\le 1, \quad x_{ij} \in \mathbb{Z} \\ \forall j = 2, \dots, n:&& \sum_{i=1}^n x_{ij} &= 1 \\ && \sum_{i=1}^n x_{i1} &= 0 \\ \forall i, j = 1, \dots, n:&& \ y_i + 1 - n &\le y_j - n x_{ij} \end{alignedat} $$

Teorija odločanja

Naloga 3

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?

  • če sprejmemo: $250000 € \cdot {1 \over 2} - 100000 €\cdot {1 \over 2} = 75000 €$
  • če ne sprejememo: $0 €$
  • upanje govori v prid sprejetju!
  • ali si lahko privoščimo izgubiti $100000 €$?

Naloga 4

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?

$$ \begin{aligned} X &\dots \text{dobiček} \\ k &\dots \text{število kupljenih žemelj} \end{aligned} $$

$$ \begin{aligned} E(X \mid k = 50) &= 50 \cdot 0.2 + 0.1 \cdot (0.15 \cdot 10 + 0.3 \cdot 20 + 0.2 \cdot 30 + 0.15 \cdot 40 + 0.1 \cdot 50) \\ &= 12.45 \\ E(X \mid k = 60) &= 60 \cdot 0.2 - 0.25 \cdot 0.1 \cdot 10 + 0.1 \cdot (0.3 \cdot 10 + 0.2 \cdot 20 + 0.15 \cdot 30 + 0.1 \cdot 40) \\ &= 13.3 \\ E(X \mid k = 70) &= 70 \cdot 0.2 - 0.25 \cdot (0.1 \cdot 20 + 0.15 \cdot 10) + 0.1 \cdot (0.2 \cdot 10 + 0.15 \cdot 20 + 0.1 \cdot 30) \\ &= 13.925 \\ E(X \mid k = 80) &= 80 \cdot 0.2 - 0.25 \cdot (0.1 \cdot 30 + 0.15 \cdot 20 + 10 \cdot 0.3) + 0.1 \cdot (0.15 \cdot 10 + 0.1 \cdot 20) \\ &= 14.1 \\ E(X \mid k = 90) &= 90 \cdot 0.2 - 0.25 \cdot (0.1 \cdot 40 + 0.15 \cdot 30 + 20 \cdot 0.3 + 10 \cdot 0.2) + 0.1 \cdot 0.1 \cdot 10 \\ &= 13.975 \\ E(X \mid k = 100) &= 100 \cdot 0.2 - 0.25 (0.1 \cdot 50 + 0.15 \cdot 40 + 30 \cdot 0.3 + 20 \cdot 0.2 + 10 \cdot 0.15) \\ &= 13.625 \end{aligned} $$

Kupijo naj $80$ žemelj.

Naloga 5

Veliki koncert skupine FiM se bo odvijal v dvorani s $100$ neoznačenimi sedeži. Prireditelj se lahko odloči, da proda $100$, $101$, $102$ ali $103$ karte (povpraševanja je dovolj). Znane so verjetnosti $p_0 = 0.2$, $p_1 = 0.3$, $p_2 = 0.4$ in $p_3 = 0.1$, kjer je $p_i$ verjetnost, da $i$ kupcev kart ne pride na koncert (ne glede na število prodanih kart). Vsaka prodana karta prinese $10 €$ dobička, vsak obiskovalec, ki ne bo mogel v dvorano, pa pomeni $30 €$ stroškov (ker je že plačal $10 €$ za karto, ima torej organizator $20 €$ izgube). Koliko kart naj prireditelj proda, da bo pričakovani dobiček čim večji?

$$ \begin{aligned} X &\dots \text{dobiček} \\ k &\dots \text{število prodanih kart} \end{aligned} $$

$$ \begin{aligned} E(X \mid k=100) &= 100 \cdot 10 = 1000 \\ E(X \mid k=101) &= 101 \cdot 10 - 0.2 \cdot 30 = 1010 - 6 = 1004 \\ E(X \mid k=102) &= 102 \cdot 10 - 0.2 \cdot 30 \cdot 2 - 0.3 \cdot 30 = 1020 - 12 - 9 = 999 \\ E(X \mid k=103) &= 103 \cdot 10 - 0.2 \cdot 30 \cdot 3 - 0.3 \cdot 30 \cdot 2 - 0.4 \cdot 30 = 1030 - 18 - 18 - 12 = 982 \end{aligned} $$

Prodajo naj $101$ karto.