Vendedor ambulante - Programación Lineal

Entonces hice esta pregunta y acepté una respuesta, pero me di cuenta de que todavía no entiendo esto y no puedo acceder a mi pregunta anterior. Tenemos el problema del viajante de comercio

Etiqueta las ciudades con los números$0, ...,n$y definir:

$x_{ij} = \begin{cases} 1 & \text{the path goes from city } i \text{ to city } j \\ 0 & \text{otherwise} \end{cases}$

Para$i = 0, ...,n$, dejar$u_i$ser una variable artificial, y finalmente tomar$c_{ij}$ser la distancia de la ciudad$i$a la ciudad$j$. Entonces TSP se puede escribir como el siguiente problema de programación lineal entera:

$\begin{align} \min &\sum_{i=0}^n \sum_{j\ne i,j=0}^nc_{ij}x_{ij} && \\ & 0 \le x_{ij} \le 1 && i,j=0, \cdots, n \\ & u_{i} \in \mathbf{Z} && i=0, \cdots, n \\ & \sum_{i=0,i\ne j}^n x_{ij} = 1 && j=0, \cdots, n \\ & \sum_{j=0,j\ne i}^n x_{ij} = 1 && i=0, \cdots, n \\ &u_i-u_j +nx_{ij} \le n-1 && 1 \le i \ne j \le n \end{align}$

La última restricción,$u_i-u_j +nx_{ij} \le n-1$se asegura de que no haya subtours. Sin embargo, no veo qué es esto. Wikipedia dice lo siguiente:

Para demostrar que cada solución factible contiene solo una secuencia cerrada de ciudades, basta con mostrar que cada subtour en una solución factible pasa por la ciudad 0 (observando que las igualdades aseguran que solo puede haber un tour). Pues si sumamos todas las desigualdades correspondientes a$x_{ij}=1$para cualquier subtour de$k$pasos que no pasan por la ciudad 0, obtenemos:$nk \leq (n-1)k$.

No entiendo esto en absoluto. Cómo es el$nk \leq (n-1)k$¿obtenido? ¿Y cómo evita esto que haya subtours? No tengo ni idea.

En cuanto a las variables ficticias, ¿para qué sirven? Wikipedia dice:

Ahora debe demostrarse que para cada recorrido individual que cubre todas las ciudades, hay valores para las variables ficticias$u_i$que satisfacen las restricciones.

Pero no explica en absoluto por qué estas variables ficticias son necesarias y qué agregan a la desigualdad. Estoy perplejo.

Esta pregunta se ha hecho antes aquí (pero la respuesta no me ayuda en absoluto) y aquí (por mí, pensé que ayudó pero no fue así), pero ninguna de las respuestas ayuda y mi pregunta es ligeramente diferente, en su mayoría centrándose en cómo obtuvieron la expresión$nk \leq (n-1)k$y por qué esto evita que se formen subtours