changed 4 years ago

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.

Select a repo