« nazaj
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.