Operacijske raziskave

« 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.

  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.


\[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)$.


\[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}\]