Inhaltsverzeichnis
Die begrenzte Enumeration gehört zu den Entscheidungsbaumverfahren und ermittelt eine optimale Lösung für Rundreiseprobleme (Traveling-Salesman-Probleme).
Bei der begrenzten Enumeration existieren verschiedene Varianten. Eine dieser Varianten wird in diesem Abschnitt vorgestellt.
Methode
Vorgehensweise: Begrenzte Enumeration
1. Schritt: Zunächst mittels heuristischer Verfahren (z.B. Verfahren des besten Nachfolgers) eine Lösung ermittelt. Diese ermittelte Lösung wird dann zur oberen Schranke ausgewählt.
2. Schritt: Es werden dann die Zweige betrachtet, die Werte unterhalb der oberen Schranke aufweisen und solange weiterverfolgt, bis diese Schranke erreicht oder überschritten wird.
3. Schritt: Ist eine Reihenfolge mit allen vorhanden Knoten ermittelt worden, die unterhalb der oberen Schranke liegt, wird diese zur neuen oberen Schranke. Es wird wieder Schritt 2 betrachtet.
Das Verfahren wird solange durchgeführt bis alle Zweige abgearbeitet bzw. ausgeschlossen werden konnten. Die minimalen Kosten stellen die zuletzt gewählte obere Schranke dar. Dies ist auch gleichzeitig die optimale Lösung.
Die oben beschriebene Vorgehensweise soll im Folgenden anhand des Beispiels aus dem Abschnitt Vollständige Enumeration durchgeführt werden.
Beispiel: Begrenzte Enumeration
Gegeben sei die reduzierte Kostenmatrix (zeilen- und spaltenweise reduziert) mit den Umrüstungskosten $c_{ij}$ und den Produkten $i = 1, ... , 5$. Die Reduktionskonstante beträgt $k_R = 164 GE$.
1. Schritt: Es wird zunächst das Verfahren des besten Nachfolgers angewandt, um eine erste Lösung zu erhalten (siehe Abschnitt Verfahren des besten Nachfolgers):
Die Kosten ergeben sich zu:
Methode
$\overline{K} = 10 GE$.
Diese Kosten stellen auch gleichzeitig die obere Schranke dar.
2. Schritt: Es wird als nächstes mit der ersten Ebene begonnen und alle möglichen Kombinationen verfolgt, solange, bis die obere Schranke überschritten oder erreicht wird. Diese Äste werden nicht weiter verfolgt. Am Ende resultiert dann eine optimale Reihenfolge mit den Kosten von 8 GE:
Die Gesamtkosten ergeben sich durch Addition der Reduktionskonstante:
Methode
$K = 164 + 8 = 172 GE$.
Die ermittelte Lösung entspricht der im Abschnitt vollständige Enumeration ermittelten Lösung und ist optimal. Die optimale Reihenfolge für die Umrüstung der Produkte ist demnach:
Methode
Merke
Die begrenzte Enumeration führt zur optimalen Lösung. Der rechenaufwand ist wesentlich geringer als bei der vollständigen Enumeration aber höher als bei den heuristischen Verfahren. Je besser die durch das heuristische Verfahren ermittelte Ausgangslösung, desto schneller wird die optimale Lösung erreicht. Bei einer symmetrischen Matrix existieren zwei optimale Lösungen, wobei die eine optimale Lösung die Umkehrung der anderen optimalen Lösung ist.
Weitere interessante Inhalte zum Thema
-
Entscheidungsbaumverfahren
Vielleicht ist für Sie auch das Thema Entscheidungsbaumverfahren (Kombinatorische Optimierung) aus unserem Online-Kurs Operations Research 2 interessant.
-
Verfahren des besten Nachfolgers
Vielleicht ist für Sie auch das Thema Verfahren des besten Nachfolgers (Kombinatorische Optimierung) aus unserem Online-Kurs Operations Research 2 interessant.
