ZU DEN KURSEN!

Operations Research 2 - Begrenzte Enumeration

Kursangebot | Operations Research 2 | Begrenzte Enumeration

Operations Research 2

Begrenzte Enumeration

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

Hier klicken zum Ausklappen

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$.

Begrenzte Enumeration Verfahren des besten Nachfolgers


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):

Begrenzte Enumeration Verfahren des besten Nachfolgers

Die Kosten ergeben sich zu:

Methode

Hier klicken zum Ausklappen

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

Begrenzte Enumeration TSP

Die Gesamtkosten ergeben sich durch Addition der Reduktionskonstante:

Methode

Hier klicken zum Ausklappen

$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

Hier klicken zum Ausklappen $1 - 2 - 4 - 5 - 3 - 1$    Optimale Reihenfolge (begrenzte Enumeration)

Merke

Hier klicken zum Ausklappen

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.