---
tags: vaje, or, clp
hackmd: https://hackmd.io/w4_7OPkIT7asbGkUpUR1oQ
plugins: mathjax
---
# Operacijske raziskave - vaje 1.3.2021

---

## Celoštevilsko linearno programiranje

### Naloga 1

Občina Ljubljana želi projekte iz množice $\mathcal{P} = \lbrace {p_1}, {p_2}, \dots, {p_n} \rbrace$, pri čemer ima na voljo $M$ evrov kapitala. V želji po razvoju regije želijo, da se v sklopu sponzoriranih projektov ustvari vsaj $N$ delovnih mest. Projekt ${p_i}$ ($1 \le i \le n)$ potrebuje ${d_i}$ evrov finančne pomoči in zaposli ${a_i}$ ljudi. Na občini so ocenili, da ima projekt ${p_i}$ ob uspešnem dokončanju donos $c_i$ evrov. Katere projekte naj sponzorira, da bo donos čim večji? Na smiseln način modeliraj opisani problem z linearnim programom.

----

$$
x_i = \begin{cases}
1 & \text{sponzorira projekt $p_i$} \\
0 & \text{sicer}
\end{cases}
$$

$$
\begin{alignedat}{2}
\max &&\sum_{i=1}^n c_i x_i \\[1ex]
\forall i = 1, \dots, n: &\ & 0 \le x_i &\le 1, \ x_i \in \mathbb{Z} \\
&& \sum_{i=1}^n d_i x_i &\le M \\
&& \sum_{i=1}^n a_i x_i &\ge N
\end{alignedat}
$$

---

### Naloga 2

Obravnavajmo posplošen scenarij iz prejšnje naloge.

1. Denimo, da so projekti lahko med seboj odvisni. Imejmo množico $V \subseteq \mathcal{P}^2$, ki določa, da za vsak par projektov $({p_i}, {p_j}) \in V$ velja, da lahko projekt ${p_i}$ sponzoriramo le, če sponzoriramo tudi projekt ${p_j}$.

2. Nekateri izmed projektov so lahko v konfliktu. Naj bo $S \subseteq 2^\mathcal{P}$ družina množic, ki določa, da so za vsako množico $H \in S$ projekti iz $H$ med seboj v konfliktu (tj., hkrati lahko sponzoriramo le enega izmed njih.)

Opiši, kako bi modelirali opisane omejitve.

----

1. $\forall ({p_i}, {p_j}) \in V: \ {x_i} \le {x_j}$
2. $\forall H \in S: \ {\sum_{ {p_i} \in H}} {x_i} \le 1$

---

### Naloga 3 - problem prevoza in skladiščenja dobrin

V Evropski uniji je na voljo $n$ skladišč, pri čemer znašajo stroški najema $i$-tega skladišča ${f_i}$ (ne glede na zasedenost), vsako skladišče pa lahko hrani enoto dobrine. Imamo $m$ strank, ki jim dostavljamo dobrine, pri čemer ${c_{ij}}$ ($1 \le i \le n$, $1 \le j \le m$) predstavlja strošek dostave dobrine stranki $j$ iz skladišča $i$. Predpostavimo tudi, da ima vsaka stranka določeno potrebo ${d_j}$, ki ponazarja število enot dobrine, ki jo potrebuje. V katerih skladiščih naj hranimo dobrine, da bodo skupni stroški najema in dostave čim manjši? Na smiseln način modeliraj opisani problem z linearnim programom.

----

$$
x_{ij} = \begin{cases}
1 & \text{$j$-ti stranki dostavljamo iz $i$-tega skladišča} \\
0 & \text{sicer}
\end{cases}
$$

$$
\begin{alignat}{2}
\min && \sum_{i=1}^n \sum_{j=1}^m (c_{ij} + f_i) x_{ij} \\[1ex]
\forall i = 1, \dots, n \ \forall j = 1, \dots, m: && 0 \le x_{ij} &\le 1, \ x_{ij} \in \mathbb{Z} \\
\forall i = 1, \dots, n: && \sum_{j=1}^m x_{ij} &\le 1 \\
\forall j = 1, \dots, m: && \sum_{i=1}^n x_{ij} &= d_j
\end{alignat}
$$

---

### Naloga 4 - problem kombinatorične dražbe

Dražitelj ponuja predmete iz množice $A$ in prejme ponudbe $\lbrace ({B_i}, {c_i}) \rbrace{_{i=1}^k}$, pri čemer je ${c_i}$ cena, ki jo udeleženec dražbe ponudi za predmete v množici ${B_i} \subseteq A$. Katere ponudbe naj dražitelj sprejme, da maksimizira dobiček, če lahko vsak predmet proda največ enkrat? Modeliraj opisani problem z linearnim programom.

----

$$
x_i = \begin{cases}
1 & \text{sprejme ponudbo $(B_i, c_i)$} \\
0 & \text{sicer}
\end{cases}
$$

$$
\begin{alignedat}{2}
&& \max \ \sum_{i=1}^k c_i x_i \\[1ex]
\forall i = 1, \dots, k: && 0 \le x_i &\le 1, \ x \in \mathbb{Z} \\
\forall a \in A: && \sum_{B_i \ni a} x_i &\le 1
\end{alignedat}
$$

---

### Naloga 5

Definiraj problem dominacijske množice v grafu in zapiši celoštevilski linearni program, ki rešuje opisani problem.

----

* neusmerjen graf $G = (V, E)$
* dominacijska množica $D \subseteq V$, tako da za vsako vozlišče $u \in V \setminus D$ velja, da ima soseda v $D$
* optimizacijski problem: poišči najmanjšo dominacijsko množico
- težek problem!

$$
x_u = \begin{cases}
1 & \text{vozlišče $u$ je v dominacijski množici} \\
0 & \text{sicer}
\end{cases}
$$

$$
\begin{alignedat}{2}
&& \min \ \sum_{u \in V} x_u \\[1ex]
\forall u \in V: &\ & 0 \le x_u &\le 1, \ x_u \in \mathbb{Z} \\
\forall u \in V: &\ & x_u + \sum_{uv \in E} x_v &\ge 1
\end{alignedat}
$$

---

### Naloga 6

Napiši linearni program, ki modelira iskanje najkrajše poti med danima vozliščema $u$ in $v$ v usmerjenem grafu $G = (V, E)$.

----

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

$$
\begin{alignat}{2}
&& \min \ \sum_{e \in E} x_e \\[1ex]
\forall e \in E: &\ & 0 \le x_e &\le 1, \ x_e \in \mathbb{Z} \\
\forall w \in V \setminus \{u, v\}: &\ & \sum_{yw \in E} x_{yw} - \sum_{wz \in E} x_{wz} &= 0 \\
&& \sum_{uz \in E} x_{uz} &= 1 \\
&& \sum_{yv \in E} x_{yv} &= 1
\end{alignat}
$$

---

### Naloga 7

Napiši linearni program, ki poišče razdalje od danega vozlišča $u$ v usmerjenem grafu $G = (V, E)$.

----

* $n = \vert V \vert$
* ${x_v}$ ... razdalja od $u$ do $v$

$$
y_e = \begin{cases}
1 & \text{če je povezava $e$ v drevesu najkrajših poti} \\
0 & \text{sicer}
\end{cases}
$$

$$
\begin{alignedat}{2}
&& \min \ \sum_{v \in V} x_v \\[1ex]
\forall v \in V: &\ & x_v &\ge 0, \ x_v \in \mathbb{Z} \\
\forall e \in E: &\ & 0 \le y_e &\le 1, \ y_e \in \mathbb{Z} \\
&& x_u &= 0 \\
\forall v \in V \setminus \{u\}: &\ & \sum_{wv \in E} y_{wv} &= 1 \\
&& \sum_{wu \in E} y_{wu} &= 0 \\
\forall vw \in E: &\ & x_w - x_v &\ge 1 - n + n y_{vw}
\end{alignedat}
$$