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