2021-03-15.md

tags	vaje, or, clp, odlocanje
hackmd	https://hackmd.io/LfcfnlyvSDePVQvaR5M1Qg
plugins	mathjax

Operacijske raziskave - vaje 15.3.2021

---

CLP in Sage

Reševanje s Sage

---

Naloga 1

Kukavica bo izlegla $16$ jajc in jih podtaknila v $12$ gnezd, ki pripadajo dvema taščicama, štirim vrtnim penicam, trem travniškim cipam, dvema belima pastiricama in eni sovi. V vsako gnezdo lahko izleže največ tri jajca, pri čemer je verjetnost, da mladiči v gnezdu $i$ preživijo, enaka ${p_{ij}}$, kjer je $j$ število podtaknjenih jajc v gnezdu $i$ (preživijo bodisi vsi ali noben mladič v posameznem gnezdu). Pri vsaki od petih vrst ptic želi izleči vsaj eno jajce, pri taščicah pa želi izleči strogo več jajc kot pri belih pastiricah. Poleg tega pri drugi beli pastirici ne bo odložila jajca, če bo pri prvi taščici odložila dve jajci ali več. Kukavica želi maksimizirati pričakovano število preživelih mladičev.

Zapiši problem kot celoštevilski linearni program.

---

$$ x_{ij} = \begin{cases} 1 & \text{v $i$-to gnezdo odloži $j$ jajc} \\ 0 & \text{sicer} \end{cases} $$

• 1, 2: taščici
• 3, 4, 5, 6: vrtne penice
• 7, 8, 9: travniške cipe
• 10, 11: beli pastirici
• 12: sova

$$ \begin{alignedat}{2} && \max \quad \sum_{i=1}^{12} \sum_{j=1}^3 j p_{ij} x_{ij} \\ \forall i = 1, \dots, 12 \ \forall j = 1, 2, 3: &\ & 0 \le x_{ij} &\le 1, \quad x_{ij} \in \mathbb{Z} \\ \forall i = 1, \dots, 12: &\ & \sum_{j=1}^3 x_{ij} &\le 1 \\ && \sum_{i=1}^{12} \sum_{j=1}^3 j x_{ij} &= 16 \\ && \sum_{i=1}^2 \sum_{j=1}^3 j x_{ij} &\ge 1 \\ && \sum_{i=3}^6 \sum_{j=1}^3 j x_{ij} &\ge 1 \\ && \sum_{i=7}^9 \sum_{j=1}^3 j x_{ij} &\ge 1 \\ && \sum_{i=10}^{11} \sum_{j=1}^3 j x_{ij} &\ge 1 \\ && \sum_{j=1}^3 j x_{12,j} &\ge 1 \\ && \sum_{i=1}^2 \sum_{j=1}^3 j x_{ij} &\ge \sum_{i=10}^{11} \sum_{j=1}^3 j x_{ij} + 1 \\ && x_{1,2} + x_{1,3} + x_{11,1} + x_{11,2} + x_{11,3} &\le 1 \end{alignedat} $$

---

Naloga 2

Vinar Janez je pridelal $2000$ litrov rumenega muškata, $10000$ litrov laškega rizlinga in $5000$ litrov renskega rizlinga. Njegovi kupci so bara Kocka in Luka ter župnišče Sv. Martin in občina Duplek. Vsak od njih je pripravljen kupiti največ določeno količino vina po fiksni ceni, ne glede na sorto:

kupec	Kocka	Luka	župnišče	občina
cena za liter	$1.0$	$1.1$	$1.5$	$1.8$
največja količina v litrih	$15000$	$5000$	$500$	$1000$

Janez se je odločil, da bo vsako sorto prodal največ enemu kupcu, in sicer v maksimalni količini (če kupec ne kupi vsega vina iste sorte, ga Janez ohrani zase). Župan pravi, da občina drugega vina kot renskega rizlinga ne bo kupila. Bar Luka želi rumeni muškat, če bar Kocka dobi laški rizling. Pri Kocki so se dogovorili, da če občina in župnišče ne kupijo nič, tudi oni ne bodo kupili ničesar. Janezova žena pa vztraja, da če kupec $A$ kupi sorto ${s_A}$ in kupec $B$ kupi sorto ${s_B}$, potem naj sorta ${s_C}$ ostane doma ali jo kupi kupec $C$ (za neke $A, B, C$). Kako naj Janez proda vino, da bo čim več zaslužil?

Zapiši problem kot celoštevilski linearni program.

---

$$ x_{ij} = \begin{cases} 1 & \text{proda sorto $j$ kupcu $i$} \\ 0 & \text{sicer} \end{cases} $$

$$ \begin{alignedat}{2} \max &\ & 2000 x_{K,RM} + 2200 x_{L,RM} &+ 750 x_{Ž,RM} + 1800 x_{O,RM} \\ &+& 10000 x_{K,LR} + 5500 x_{L,LR} &+ 750 x_{Ž,LR} + 1800 x_{O,LR} \\ &+& 5000 x_{K,RR} + 5500 x_{L,RR} &+ 750 x_{Ž,RR} + 1800 x_{O,RR} \[1ex] \forall i, j: &\ & 0 \le x_{ij} &\le 1, \quad x_{ij} \in \mathbb{Z} \\ \forall i: &\ & \sum_j x_{ij} &\le 1 \\ \forall j: &\ & \sum_i x_{ij} &\le 1 \\ && x_{O,RM} + x_{O,LR} &= 0 \\ && x_{K,LR} &\le x_{L,RM} \\ && \sum_j x_{K,j} &\le \sum_j (x_{Ž,j} + x_{O,j}) \\ && x_{A,s_A} + x_{B,s_B} + \sum_{i \ne C} x_{i,s_C} &\le 2 \end{alignedat} $$

---

Naloga 3

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

---

• neusmerjen graf $G = (V, E)$ predstavimo kot usmerjen graf
• cene povezav ${c_e}$ ($e \in E$)
  • ${c_{uv}} = {c_{vu}}$
• fiksiramo vozlišče $u \in V$ kot koren
• $y_v$ ... vrednost, ki se povečuje, ko sledimo povezavam v drevesu od korena naprej

$$ x_e = \begin{cases} 1 & \text{povezava $e$ je v drevesu} \\ 0 & \text{sicer} \end{cases} $$

$$ \begin{alignedat}{2} && \min \quad \sum_{e \in E} c_e x_e \\ \forall e \in E: &\ & 0 \le x_e &\le 1, \quad x_e \in \mathbb{Z} \\ && \sum_{wu \in E} x_{wu} &= 0 \\ \forall v \in V \setminus {u}: && \sum_{wv \in E} x_{wv} &= 1 \\ \forall vw \in E: && y_w - y_v &\ge 1 - n + n x_{vw} \end{alignedat} $$

---

Naloga 4

Na oddelku za matematiko je zaposlenih $n$ asistentov, ki jim moramo dodeliti vaje pri $m$ predmetih. Za asistenta $i$ ($1 \le i \le n$) naj bosta ${a_i}$ in ${b_i}$ najmanjše in največje število ur, ki jih lahko izvaja, ter ${N_i} \subseteq {1, 2, \dots, m}$ množica predmetov, ki jih ne želi izvajati. Za predmet $j$ ($1 \le j \le m$) naj bo ${c_j}$ število skupin za vaje pri predmetu, ter ${u_j}$ število ur vaj na skupino. Poleg tega vemo, da sta asistenta $p$ in $q$ skregana, zato pri nobenem predmetu ne smeta oba izvajati vaj.

Predmete želimo asistentom dodeliti tako, da bomo ob upoštevanju njihovih želja minimizirali največje število različnih predmetov, ki smo jih dodelili posamezenmu asistentu.

Zapiši celoštevilski linearni program, ki modelira zgoraj opisani problem.

Namig: napiši program s spremenljivko $t$, ki je dopusten natanko tedaj, ko vsak asistent dobi največ $t$ različnih predmetov, in potem minimimiziraj $t$.

---

Teorija odločanja

Naloga 5

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?

---

• Ali je kovanec pošten?
• $X$ ... dobiček
• $E(X) = 0.5 \cdot 250000 € + 0.5 \cdot (-100000 €) = 75000 €$
• pričakovani dobiček je pozitiven
• ali si lahko res privoščimo negativen izid?

---

Naloga 6

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?

---

• $k$ ... število kupljenih žemelj
• $X$ ... število prodanih žemelj
• $Y$ ... dobiček

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

Kupijo naj 80 žemelj, pričakovani dobiček je tedaj 14.1 €.