Wykład 2020-03-10

• 1. Task assignment
  • 1.1. Zapis
• 2. Travelling salesman problem
• 3. Metoda Newtona

$S$:

• pole wyszukiwań
• możliwe rozwiązania dopuszczalne

$f(\overline{x})$

|
| .
|   .
|_______
 1 2 3 4

$[x^0, x^1, ...]$

$x^i \in \{0,1\}$
$x \in \{0,1\}^k$

|   /
|  /
| /
|/_______

TSP (Travelling salesman problem), $n=7$

Kraków, Wrocław, …

wierzchołki: $1,2,3,4,6,7$

1. Task assignment

minimalizacja czasu pracy pracowników

$c_{ij}$

$\sum_{i=1}^3\sum_{j = 1}^3c_{ij}x_{ij}$ przy czym $x_{ij} \in \{0,1\}$

$\forall i~\sum_j^3x_{ij} = 1$
$\forall j~\sum_i^3x_{ij} = 1$

1.1. Zapis

$$X = \begin{bmatrix} 0 & 1 & 0\\ 1 & 0 & 0\\ 0 & 0 & 1\\ \end{bmatrix}$$

zadanie:
$J = (2,1,3)$

pracownik:
$W = (2,1,3)$

2. Travelling salesman problem

$\sum_{i=1}^3\sum_{j = 1}^3d_{ij}x_{ij}$ przy czym $x_{ij} \in \{0,1\}$

3. Metoda Newtona

$$\mathcal{H} = \begin{bmatrix} \frac{\delta^2f}{\delta x_1^2} & \frac{\delta^2f}{\delta x_1 \delta x_2} & ... \\ ...\\ \frac{\delta^2f}{\delta x_n \delta x_1} & ...\\ \end{bmatrix}$$