2021-03-08.md

tags	vaje, or, clp, grafi
hackmd	https://hackmd.io/VT9NkN-VRNuj98S6226rPQ
plugins	mathjax

Operacijske raziskave - vaje 8.3.2021

---

CLP in grafi

Naloga 1

Napiši linearni program, ki modelira določanje kromatičnega števila grafa.

---

• neusmerjen graf $G = (V, E)$
• $n = \vert V \vert$
• $t$ ... število barv

$$ x_{ui} = \begin{cases} 1 & \text{vozlišče $u$ je barve $i$} \\ 0 & \text{sicer} \end{cases} $$

$$ \begin{alignedat}{2} && \min t \\ \forall u \in V, \ \forall i = 1, \dots, n: & \ & 0 \le x_{ui} &\le 1, \quad x_{ui} \in \mathbb{Z} \\ \forall uv \in E, \ \forall i = 1, \dots, n: &\ & x_{ui} + x_{vi} &\le 1 \\ \forall u \in V: &\ & \sum_{i=1}^n x_{ui} &= 1 \\ \forall u \in V, \ \forall i = 1, \dots, n: &\ & i x_{ui} &\le t \end{alignedat} $$

---

Naloga 2 - problem trgovskega potnika

Danih je $n$ mest na zemljevidu. Strošek potovanja iz mesta $i$ v mesto $j$ je ${c_{ij}}$ ($1 \le i, j \le n$). Trgovski potnik želi obiskati vseh $n$ mest, pri tem pa minimizirati strošek potovanja. Na smiseln način modeliraj opisani problem z linearnim programom.

---

$$ x_{ij} = \begin{cases} 1 & \text{če potuje iz $i$ v $j$} \\ 0 & \text{sicer} \end{cases} $$

• ${y_i}$ ... vrednost, ki se tekom cikla (od vozlišča 1 naprej) povečuje

$$ \begin{alignedat}{2} && \min \quad \sum_{i=1}^n \sum_{j=1}^n c_{ij} x_{ij} \\ \forall i, j = 1, \dots, n: &\ & 0 \le x_{ij} &\le 1, \quad x_{ij} \in \mathbb{Z} \\ \forall i = 1, \dots, n: &\ & \sum_{j=1}^n x_{ij} &= 1 \\ \forall j = 1, \dots, n: &\ & \sum_{i=1}^n x_{ij} &= 1 \\ \forall i = 1, \dots, n, \ j = 2, \dots, n: &\ & y_j - y_i &\ge 1 - n + n x_{ij} \end{alignedat} $$