« nazaj
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.
-
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}$.
-
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.
- $\forall ({p_i}, {p_j}) \in V: \ {x_i} \le {x_j}$
- $\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
\[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}\]