Jetzt neu: Steuerrecht online lernen auf steuerkurse.de!
ZU DEN KURSEN!

Operations Research 2 - Beispiel: Vollständige Enumeration (Anwendung des Verfahrens)

Kursangebot | Operations Research 2 | Beispiel: Vollständige Enumeration (Anwendung des Verfahrens)

Operations Research 2

Beispiel: Vollständige Enumeration (Anwendung des Verfahrens)

Die vollständige Enumeration wird nun tabellarisch durchgeführt. Dazu geht man am Besten zunächst nach der Reihenfolge vor, betrachtet also die Reihenfolge der Umrüstung von Produkt $1$ bis $5$. Bei diesen Probleme muss am Ende wieder auf das Produkt $1$ umgerüstet werden (Hamilton Kreis).

$1 - 2 - 3 - 4 - 5 - 1$

Man stellt dann für diese Reihenfolge die Summe aller Kosten auf, um die Gesamtkosten der Umrüstung für diese Reihenfolge zu erhalten. Im zweiten Schritt varriert man dann zunächst die letzten beiden umgerüsteten Produkte. Das bedeutet also, dass nun statt $3-4$ zunächst $3-5$ und dann $4-5$ besucht wird:

$1 - 2 - 3 - 5 - 4 - 1$.

Danach werden die letzten drei Produkte varriert, also $3 - 4 - 5$:

$1 - 2 - 4 - 3 - 5 - 1$

$1 - 2 - 4 - 5 - 3 - 1$

$1 - 2 - 5 - 3 - 4 - 1$

$1 - 2 - 5 - 4 - 3 - 1$


Man erhält somit bereits 6 Reihenfolgen für die Umrüstung. Nach dieser Vorgehensweise erfolgt der weitere Ablauf. Am Ende erhält man die folgenden Tabelle mit den folgenden $(5 - 1)! = 24$ möglichen Reihenfolgen:

Die minimalen Kosten der Umrüstung sind für die Reihenfolge

Methode

Hier klicken zum Ausklappen

$1-2-4-5-3-1$                  Optimale Reihenfolge (vollstände Enumeration)

gegeben. Die Kosten betragen 10 GE. Es muss nun noch die Reduktionskonstante aus dem vorherigen Abschnitt hinzuaddiert werden um die Gesamtkosten der Umrüstung zu erhalten:

Methode

Hier klicken zum Ausklappen

Gesamte Kosten = 162 GE + 10 GE = 172 GE.

Die vollständige Enumeration stellt ein exaktes Verfahren der kombinatorischen Optimierung dar. Das Ergebnis ist die optimale Reihenfolge mit den minimalen Kosten. Das Problem der vollständigen Enumeration ist die Anzahl der möglichen Reihenfolgen mit jeder zunehmenden Knotenanzahl. Deswegen werden häufig heuristische Verfahren angewandt, die zwar keine optimale Lösung, aber eine zufriedenstellende Lösung als Ergebnis haben.