Skip to content

2021-03-01.md

Latest commit

 

History

History
179 lines (132 loc) · 5.5 KB

2021-03-01.md

File metadata and controls

179 lines (132 loc) · 5.5 KB
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} $$