Da Reduktionskonstante und Summe aus zweitkleinstem Element gleich sind, müssen Fall (a) und (b) des 4. Schrittes durchgeführt werde. Es wird zunächst der Fall (a) für den Ast $s_1 = 172$ betrachtet.
(a) Ist die sich hier ergebene erneute Reduktionskonstante kleiner als die Summe der zweitkleinsten Elemente in Schritt 3, so wird dieser Ast weiterverfolgt. Es wird dann hierfür die reduzierte Matrix mit der gestrichenen Zeile und Spalte gewählt. Die Reduktionstionskonstante muss auf die obere Schranke addiert werden und ergibt die neue obere Schranke. Dieser Ast bedeutet, dass die Tour mit aufgenommen wird.
Es wird nun also die zuletzt betrachtete reduzierte Matrix mit der gestrichenen Zeile und Spalte herangezogen:
Der Schritt 2 wird durchgeführt. Das bedeutet also wieder die Betrachung der Nullelemente innerhalb der Matrix und die Berechnung der Summe der zweitkleinsten Elemente der zugehörigen Zeile und Spalte:
| Strecke | $1 \to 2$ | $2 \to 4$ | $4 \to 2$ | $4 \to 5$ | $5 \to 3$ | $5 \to 4$ |
| Summe | 4 | 4 | 0 | 4 | 4 | 0 |
In diesem Fall liegen nun eine Vielzahl an Werten vor. Am Besten geht man hier nun so vor, dass man eine Teilstrecke wählt, die an die bereits gefundene Teilstrecke anknüpft. Es wird gerade die Teistrecke $3 \to 1$ betrachtet. Demnach würde sich hier empfehlen die Teilstrecken $1 \to 2$ oder $5 \to 3$ zu wählen. Es wird hier $1 \to 2$ gewählt.
Es ergibt sich demnach die Teilstrecke:
$3 \to 1 \to 2$.
Es soll wieder der Zyklus $3 \to 1 \to 2 \to 3$ ausgeschlossen werden (da noch Knoten mitberücksichtigt werden soll). Dazu wird $c_{23} = \infty'$ gesetzt. Danach wird die Matrix zeilen- und spaltenweise reduziert:
Es kann keine Reduktion vorgenommen werden. Deswegen bleibt die Reduktionskonstante bei $s_3 = 172$. Das bedeutet also, dass die Aufnahme der Tour $1 \to 2$ eine zusätzliche Reduktionskonstante von 0 aufweist und die Nichtaufnahme (Summe der zweitkleinsten Elemente) einen Wert von 4. Es ergeben sich demnach die Schranken $s_3 = 172 + 0 = 172$ und $s_4 = 172 + 4 = 176$. Der Zweig $s_4$ wird nicht weiter verfolgt:
Es muss nun als nächstes für den Ast mit $s_2 = 172$ der Fall (b) betrachtet werden. Dieser Ast bedeutet die Nichtaufnahme der Teilstrecke $3 \to 1$. Hierfür wird nun die Matrix aus dem voherigen Abschnitt herangezogen (Schritt 2), vor Aufnahme der Teilstrecke $3 \to 1$:
Es wird dann das Element $c_{31} = \infty$ gesetzt (damit dieses nicht aufgenommen wird) und eine zeilen- und spaltenweise Reduktion der Matrix durchgeführt:
Die obige Matrix stellt nun die Ausgangsmatrix für den Ast mit $s_2$ dar. Hier wurde nun die Tour $3 \to 1$ ausgeschlossen, indem $c_{31} = \infty$ gesetzt worden ist. Danach wurde die Reduktion vorgenommen. Es ergibt sich eine zusätzliche Reduktionskonstante von $6 + 2 = 8$. Dies entspricht genau der Summe der zweitkleinsten Elemente. Die obere Schranke ist demnach $s_2 = 172$. Es wird nun also dieser Ast verfolgt, indem wieder Schritt 3 durchgeführt wird:
| Strecke | $1 \to 3$ | $2 \to 4$ | $3 \to 4$ | $3 \to 5$ | $4 \to 1$ | $4 \to 2$ | $4 \to 5$ | $5 \to 4$ |
| Summe | 8 | 2 | 0 | 0 | 2 | 2 | 0 | 2 |
Es wird die Strecke $1 \to 3$ ausgewählt. Es handelt sich momentan um die Tour (1,3), da der Ast betrachtet wird, welcher die Tour $3 \to 1$ ausschließt. Demnach muss das Element $c_{31} = \infty'$ gesetzt werden um den Zyklus $1 \to 3 \to 1$ zu verhindern. Das Element ist bereits gleich unendlich gesetzt worden. Es wird als nächsten die Zeile $i = 1$ und $j = 3$ gestrichen und dann die Matrixreduktion vorgenommen:
Es konnte keine Reduktion der Matrix vorgenommen werden. Mit Berücksichtigung der Tour $1 \to 3$ ergibt sich demnach die obere Schranke $s_5 = 172$. Ohne Berücksichtigung der Tour muss zur Schranke $s_2 = 172$ die Summe der zweitkleinsten Elemente addiert werden, dies ergibt eine Schranke von $s_6 = 172 + 8 = 180$. Der Entscheidungsbaum ergibt sich wie folgt:
Es ist nun deutlich zu erkennen, dass noch zwei Äste mit gleicher oberer Schranke existieren. Diese beiden Äste mit den Schranken $s_3 = s_5 = 172$ müssen nun weiterverfolgt werden. Die anderen Äste müssen nicht weiter betrachtet werden, da die oberen Schranken größer sind. Das bedeutet $s_4$ und $s_5$ müssen nicht weiter betrachtet werden. Es muss immer von der Matrix ausgegangen werden, die zuletzt für den betrachteten Schritt durchgeführt worden ist. Bei dem Ast mit $s_3$ sind die Teistrecken $3 \to 1$ und $1 \to 2$ aufgenommen worden. Es wird hier die folgende Matrix herangezogen:
Für diese wird wieder Schritt 3 durchgeführt. Dies ergibt die zusätzliche Teilstrecke von $4 \to 5$ mit der Summe $7$. Da diese Teilstrecke nicht mit der bereits gegeben Tour verbunden werden kann, wird der Zyklus $4 \to 5 \to 4$ unterbunden, indem $c_{54} = \infty'$ gesetzt wird. Danach wird wieder die Zeile $i = 4$ und die Spalte $j = 5$ gestrichen und die Matrixreduktion vorgenommen:
Es konnte keine Reduktion vorgenommen werden. Die obere Schranke ist demnach $s_7 = s_3 + 0 = 172$. Die obige Matrix stellt die Endmatrix für diesen Zweig dar. Es kann keine weitere Reduktion mehr vorgenommen werden und es gibt keine zweitkleineren Elemente mehr. Die beiden Nullelemente sind dabei die beiden letzten Teilstrecken, die in die Tour mit aufgenommen werden:
$5 \to 3$ und $2 \to 4$.
Aus den in die Tour aufgenommenen Teilstrecken kann nun die Rundreise bestimmt werden:
Methode
$1 \to 2 \to 4 \to 5 \to 3 \to 1$
Die Gesamtkosten entsprechen der oberen Schranke in der Matrix:
Methode
$K = 172 GE$.
Aus dem Abschnitt mit der begrenzten Enumeration bzw. der vollständigen Enumeration ist bekannt, dass hier bereits die optimale Reihenfolge mit den minimalen Gesamtkosten von 172 GE vorliegt. Da die optimale Reihenfolge normalerweise aber unbekannt ist, muss auch noch der Ast mit $s_5 = 172$ untersucht werden, da diese Schranke gleich der hier ermittelten Schranke ist. Würde die hier emittelte Schranke über der von $s_5$ liegen müsste der Ast natürlich ebenfalls weiter verfolgt werden. Nur wenn die Schranke $s_5$ größer als die Schranke $s_7$ wäre, müsste dieser Ast nicht weiter verfolgt werden.
Für den Ast mit der Schranke $s_5$ wird die folgende Matrix herangezogen:
Es wird nun wieder Schritt 3 angewandt. Es ergibt sich die Teilstrecke $4 \to 2$ mit der Summe $4$. Da diese Teilstrecke nicht mit der bereits gegeben Tour verbunden werden kann, wird der Zyklus $4 \to 2 \to 4$ unterbunden, indem $c_{24} = \infty'$ gesetzt wird. Danach wird wieder die Zeile $i = 4$ und die Spalte $j = 2$ gestrichen und die Matrixreduktion vorgenommen:
Die Reduktion ergibt eine zusätzliche Reduktionskonstante von $2$. Demnach wird bei Aufnahme der Tour $4 \to 2$ zur Tour $1 \to 3$ die obere Schranke zu $s_9 = s_5 + 2 = 174$. Dies liegt über der Schranke bei $s_7 = 172$.
Bei Nichtaufnahme der Tour $4 \to 2$ wird die obere Schranke bestimmt, indem die Summe aus den zweitkleinsten Elemente zur oberen Schranke $s_5$ hinzuaddiert wird: $s_{10} = 172 + 4 = 176$. Auch dieser Ast muss nicht weiter verfolgt werden, weil die Schranke über $s_7$ liegt.
Der Entscheidungsbaum ergibt sich zu:
Weitere interessante Inhalte zum Thema
-
Branch-and-Bound-Verfahren
Vielleicht ist für Sie auch das Thema Branch-and-Bound-Verfahren (Ganzzahlige Optimierung) aus unserem Online-Kurs Operations Research 2 interessant.
-
Branch-and-Bound (TSP): 1. Iteration
Vielleicht ist für Sie auch das Thema Branch-and-Bound (TSP): 1. Iteration (Kombinatorische Optimierung) aus unserem Online-Kurs Operations Research 2 interessant.
