Handelsreisender - Lineare Programmierung

Also habe ich gerade diese Frage gestellt und eine Antwort akzeptiert, aber mir wurde klar, dass ich das immer noch nicht verstehe und nicht auf meine vorherige Frage zugreifen kann. Wir haben das Problem des Handlungsreisenden

Beschriften Sie die Städte mit den Nummern$0, ...,n$und definieren:

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

Für$i = 0, ...,n$, lassen$u_i$sei eine künstliche Variable und nimm schließlich$c_{ij}$die Entfernung von der Stadt sein$i$zur Stadt$j$. Dann kann TSP als das folgende ganzzahlige lineare Programmierproblem geschrieben werden:

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

Die letzte Einschränkung,$u_i-u_j +nx_{ij} \le n-1$stellt sicher, dass es keine Subtouren gibt. Ich sehe jedoch nicht, was das ist. Wikipedia sagt folgendes:

Um zu beweisen, dass jede zulässige Lösung nur eine geschlossene Folge von Städten enthält, genügt es zu zeigen, dass jede Teiltour in einer zulässigen Lösung durch die Stadt 0 verläuft (wobei zu beachten ist, dass die Gleichheiten sicherstellen, dass es nur eine solche Tour geben kann). Denn wenn wir alle entsprechenden Ungleichungen summieren$x_{ij}=1$für jede Subtour von$k$Schritte, die nicht durch die Stadt 0 führen, erhalten wir:$nk \leq (n-1)k$.

Ich verstehe das überhaupt nicht. Wie ist die$nk \leq (n-1)k$erhalten? Und wie verhindert das, dass es überhaupt Subtouren gibt? Ich habe keine Ahnung.

Welchen Zweck erfüllen die Dummy-Variablen? Wikipedia sagt:

Es muss nun gezeigt werden, dass es für jede einzelne Tour, die alle Städte abdeckt, Werte für die Dummy-Variablen gibt$u_i$die die Einschränkungen erfüllen.

Aber es erklärt überhaupt nicht, warum diese Dummy-Variablen notwendig sind und was sie zur Ungleichung hinzufügen. Ich bin ratlos.

Diese Frage wurde hier schon einmal gestellt (aber die Antwort hilft mir überhaupt nicht) und hier (von mir, ich dachte, es hat geholfen, aber es hat nicht funktioniert), aber keine der Antworten hilft und meine Frage ist meistens etwas anders sich darauf konzentrieren, wie sie den Ausdruck erhalten haben$nk \leq (n-1)k$und warum dies verhindert, dass sich Subtouren bilden