or
or
By clicking below, you agree to our terms of service.
New to HackMD? Sign up
Syntax | Example | Reference | |
---|---|---|---|
# Header | Header | 基本排版 | |
- Unordered List |
|
||
1. Ordered List |
|
||
- [ ] Todo List |
|
||
> Blockquote | Blockquote |
||
**Bold font** | Bold font | ||
*Italics font* | Italics font | ||
~~Strikethrough~~ | |||
19^th^ | 19th | ||
H~2~O | H2O | ||
++Inserted text++ | Inserted text | ||
==Marked text== | Marked text | ||
[link text](https:// "title") | Link | ||
 | Image | ||
`Code` | Code |
在筆記中貼入程式碼 | |
```javascript var i = 0; ``` |
|
||
:smile: | ![]() |
Emoji list | |
{%youtube youtube_id %} | Externals | ||
$L^aT_eX$ | LaTeX | ||
:::info This is a alert area. ::: |
This is a alert area. |
On a scale of 0-10, how likely is it that you would recommend HackMD to your friends, family or business associates?
Please give us some advice and help us improve HackMD.
Syncing
xxxxxxxxxx
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?
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.
Č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.