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

Operations Research 2 - Vollständige Enumeration

Kursangebot | Operations Research 2 | Vollständige Enumeration

Operations Research 2

Vollständige Enumeration

Die vollständige Enumeration kann herangezogen werden, um das in vorherigen Abschnitt dargstellte Traveling-Salesman-Problem zu lösen. Bei der vollständigen Enumeration werden alle möglichen Lösungen ermittelt und danach die Lösung mit dem geringsten Wert ausgewählt, es handelt sich also um ein exaktes Verfahren zur Bestimmung einer optimalen Lösung. Für das Traveling-Salesman-Problem bedeutet dies, dass zunächst alle möglichen Rundreisen ermittelt werden und danach diejenige Rundreise mit den geringsten Kosten oder der kürzesten Zeit ausgewählt wird. 

Merke

Hier klicken zum Ausklappen

Anstelle von einer Rundreise von Ort $i$ zum Ort $j$, kann es sich hierbei auch um eine Maschine handeln die von Produkt $i$ auf Produkt $j$ umgerüstet wird.

Das Problem der vollständigen Enumeration ist die Anzahl der möglichen Lösungen. Für $n$-Knoten existieren $(n - 1)!$ mögliche Lösungen. Die manuelle Anwendung der vollständigen Enumeration ist bis zu einer Knotenanzahl von $n = 6$ gerade noch vertretbar:

$(6 - 1)! = 5! = 1 \cdot 2 \cdot 3 \cdot 4 \cdot 5 = 120$

Bei einer Knotenanzahl von $n = 6$ existieren also 120 mögliche Lösungen. Bei einer Knotenanzahl von $n = 7$ schon 720 mögliche Lösungen uws.

In diesem Abschnitt sol gezeigt werden, wie man die vollständige Enumeration anwendet, wenn $n = 5$ Knoten gegeben sind. Die möglichen Lösungen sind dann $(5 - 1)! = 24$.


In den folgenden zwei Abschnitten wird das Verfahren der vollständigen Enumeration anhand des Traveling-Salesman-Problems dargestellt.