« nazaj
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}\]