Kombinatorische Optimierung

Operations Research 2

Das Kapitel Kombinatorische Optimierung in unserem Online-Kurs Operations Research 2 besteht aus folgenden Inhalten:

1. Kombinatorische Optimierung

   Kombinatorische Optimierung

   

   Die kombinatorische Optimierung beschäftigt sich vor allem mit Reihenfolgeproblemen, die in den folgenden Abschnitten behandelt werden. Hierbei wird zunächst auf das Traveling-Salesman-Problem (Rundreiseproblem) eingegangen und Verfahren zur Lösung solcher Probleme aufgezeigt. Bei der dann folgenden Fertigungsplanung wird gezeigt, wie man die optimale Reihenfolge von Aufträgen auf zwei oder mehrere Maschinen bestimmt, so dass die Bearbeitungszeit minimiert wird. 

2. Traveling-Salesman-Problem

   Kombinatorische Optimierung > Traveling-Salesman-Problem

   

   Das Traveling-Salesman-Problem (auch: Rundreiseproblem) TSP gehört zu den kombinatorischen Optimierungsproblemen. Es handelt sich hierbei um ein Rundreiseproblem, bei welchem mehrere Orte unter Minimierung der Reisezeit oder der Kosten nacheinander angesteuert werden sollen. Dabei darf ein Ort nur einmal besucht werden. Die Reihenfolge ist dabei nicht von Bedeutung. Für die Lösung des Traveling-Salesman-Problem stehen eine Vielzahl an heuristischen und exakten Methoden ...

3. Vollständige Enumeration

   Kombinatorische Optimierung > Traveling-Salesman-Problem > 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 ...

4. Beispiel: Vollständige Enumeration (Reduktion der Matrix)

   Kombinatorische Optimierung > Traveling-Salesman-Problem > Vollständige Enumeration > Beispiel: Vollständige Enumeration (Reduktion der Matrix)

   

   Beispiel: Vollständige Enumeration beim TSPDie obige Matrix stellt eine Maschine dar mit den Produkten $i = 1, 2, 3, 4, 5$. Die Kosten $c_{ij}$ sind gegeben für die Umrüstung der Maschine von z.B. Produkt 3 auf Produkt 1 mit 32 Geldeinheiten (GE). Gesucht wird diejenige Reihenfolge mit minimalen Umrüstungskosten.Da hier die Matrix gegeben ist, muss kein Graph gezeichnet werden. Es wird zunächst die obige Matrix angepasst, indem alle unerwünschten Verknüpfungen bzw. ...

5. Beispiel: Vollständige Enumeration (Anwendung des Verfahrens)

   Kombinatorische Optimierung > Traveling-Salesman-Problem > Vollständige Enumeration > 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 ...

6. Heuristische Verfahren

   Kombinatorische Optimierung > Traveling-Salesman-Problem > Heuristische Verfahren

   

   Wie im vorherigen Abschnitt gezeigt, liefern exakte Verfahren wie die begrenzte Enumeration zwar das optimale Ergebnis, sind aber sehr rechen- und zeitaufwendig. Bei einer bestimmten Anzahl an Knoten kann nicht mal mehr mit EDV-Analage eine optimale Lösung ermittelt werden, weil die Anzahl an Kombinationen so groß ist, dass die Zeit bis eine optimale Lösung gefunden wird selbst für Rechenprogramme einfach zu groß ist.Deswegen wird auf heuristische Verfahren zurückgegeriffen. ...

7. Verfahren des besten Nachfolgers

   Kombinatorische Optimierung > Traveling-Salesman-Problem > Heuristische Verfahren > Verfahren des besten Nachfolgers

   

   Das Verfahren des besten Nachfolgers gehört zu den heuristischen Verfahren der kombinatorischen Optimierung. In diesem Abschnitt soll gezeigt werden, wie man dieses Verfahren auf ein Traveling-Salesman-Problem anwendet. Vorgehensweise: Verfahren des besten NachfolgersAusgehend von einem Knoten $i$ (einem Ort) wird derjenige Ort als Nachfolger $j$ gewählt, welcher die geringsten Kosten bzw. die geringste Zeit aufweist $\min[c_{ij}]$. Dieser Ort wird dann als Nachfolger von Ort $i$ eingetragen. ...

8. Verfahren des besten Nachfolgers (Ausgangsmatrix)

   Kombinatorische Optimierung > Traveling-Salesman-Problem > Heuristische Verfahren > Verfahren des besten Nachfolgers > Verfahren des besten Nachfolgers (Ausgangsmatrix)

   

   Gegeben sei die Matrix mit den Umrüstungskosten $c_{ij}$ und den Produkten $i = 1,...,5$.Man geht nun wie folgt vor. Beginnend bei dem Produkt 1 wird nun das Produkt gesucht, welches als nächstes umgerüstet wird. Dabei werden die kleinsten Umrüstungskosten gewählt. Das Produkt 3 mit 34 GE besitzt die geringsten Umrüstungskosten:$1 - 3$Danach wird von Produkt 2 ausgehen derjenige Nachfolgerknoten mit den geringsten Umrüstkosten gewählt usw.Es ergibt sich die ...

9. Verfahren des besten Nachfolgers (reduzierte Matrix)

   Kombinatorische Optimierung > Traveling-Salesman-Problem > Heuristische Verfahren > Verfahren des besten Nachfolgers > Verfahren des besten Nachfolgers (reduzierte Matrix)

   

   Das Verfahren soll außerdem anhand der reduzierten Kostenmatrix betrachtet werden. Hierbei wird zunächst eine Zeilenreduktion vorgenommen, wobei das kleinste Element der Zeile von den anderen Elementen der Zeile subtrahiert wird:Danach wird eine Spaltenreduktion vorgenommen, indem der kleinste Wert der Spalte von allen anderen Elementen der Spalte subtrahiert wird. Dies ist nur für die letzte Spalte möglich, da die anderen Spalten als kleinsten Wert Null besitzen:Die Reduktionskonstante ...

10. Verfahren der sukzessiven Einbeziehung von Stationen

    Kombinatorische Optimierung > Traveling-Salesman-Problem > Heuristische Verfahren > Verfahren der sukzessiven Einbeziehung von Stationen

    

    In diesem Abschnitt wird das Verfahren der sukzessiven Einbeziehung von Stationen behandelt. Dieses Verfahren gehört zu den heuristischen Verfahren der kombinatorischen Optimierung.Vorgehensweise: Verfahren der sukzessiven Einbeziehung von StationenDas Verfahren der sukzessiven Einbeziehung von Stationen wird durchgeführt, indem zunächst ein beliebiger Ausgangszyklus bestimmt wird. Dieser Ausgangszyklus beinhaltet zunächst nur einen beliebigen Anfangskonten, welcher auch gleichzeitig ...

11. Einbeziehung von Stationen (Ausgangsmatrix)

    Kombinatorische Optimierung > Traveling-Salesman-Problem > Heuristische Verfahren > Verfahren der sukzessiven Einbeziehung von Stationen > Einbeziehung von Stationen (Ausgangsmatrix)

    

    Das Verfahren der sukzessiven Einbeziehung von Stationen wird anhand der Ausgangsmatrix dargestellt. Es kann aber ebenfalls die reduzierte Kostenmatrix herangezogen werden, es resultiert dasselbe Ergebnis. Hierzu wird die folgende Matrix mit den Umrüstungskosten $c_{ij}$ und den Produkten $i = 1,...,5$ betrachtet:Es wird nun zunächst ein beliebiger Anfangszyklus bestimmt und die Kosten für diesen Zyklus mitangegeben:Reihenfolge           Kosten   ...

12. Entscheidungsbaumverfahren

    Kombinatorische Optimierung > Traveling-Salesman-Problem > Entscheidungsbaumverfahren

    

    Eine weitere Möglichkeit neben der vollständigen Enumeration und den heuristischen Verfahren ist die Lösung von Rundreiseprobleme mit den Entscheidungsbaumverfahren. Diese Verfahren liefern eine optimale Reihenfolge und damit minimale Kosten bzw. Zeiten. Der Rechenaufwand bei den Entscheidungsbaumverfahren ist lange nicht so hoch wie bei der vollständigen Enumeration, aber wesentlich größer als bei den heuristischen Verfahren.In den folgenden Abschnitten werden die ...

13. Begrenzte Enumeration

    Kombinatorische Optimierung > Traveling-Salesman-Problem > Entscheidungsbaumverfahren > 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.Vorgehensweise: Begrenzte Enumeration1. Schritt: Zunächst mittels heuristischer Verfahren (z.B. Verfahren des besten Nachfolgers) eine Lösung ermittelt. Diese ermittelte Lösung wird dann ...

14. Branch-and-Bound Verfahren am Traveling-Salesman-Problem

    Kombinatorische Optimierung > Traveling-Salesman-Problem > Entscheidungsbaumverfahren > Branch-and-Bound Verfahren am Traveling-Salesman-Problem

    

    In diesem Abschnitt soll das Branch-and-Bound-Verfahren für ein Rundreiseproblem (Traveling-Salesman-Problem) aufgezeigt werden. Vorgehensweise: Branch-and-Bound am Traveling-Salesman-Problem1. Schritt: Die Kostenmatrix wird zunächst so umgeformt, dass alle nichtvorhandenen Verbindungen (Nullelemente) und alle extrem abweichenden Elemente gleich unendlich gesetzt werden.2. Schritt: Die angepasste Kostenmatrix wird zeilen- und spaltenweise reduziert. Hierfür wird das kleinste Element ...

15. Branch-and-Bound (TSP): 1. Iteration

    Kombinatorische Optimierung > Traveling-Salesman-Problem > Entscheidungsbaumverfahren > Branch-and-Bound Verfahren am Traveling-Salesman-Problem > Branch-and-Bound (TSP): 1. Iteration

    

    In diesem und den folgenden Abschnitten soll das Branch-and-Bound-Verfahren am Traveling-Salesman-Problem (TSP) ausführlich behandelt werden. Die Schritte aus dem vorherigen Abschnitt sind dabei die Grundlage für die Anwendung des Verfahrens und werden im Folgenden nochmals aufgeführt und näher erläutert.Gegeben sei die folgende Kostenmatrix mit den Umrüstungskosten $c_{ij}$ und den Produkten $i = 1, ... , 5$:1. Schritt:  Die Kostenmatrix wird zunächst ...

16. Branch-and-Bound (TSP): Weitere Iterationen

    Kombinatorische Optimierung > Traveling-Salesman-Problem > Entscheidungsbaumverfahren > Branch-and-Bound Verfahren am Traveling-Salesman-Problem > Branch-and-Bound (TSP): Weitere Iterationen

    

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

17. Fertigungsablaufplanung

    Kombinatorische Optimierung > Fertigungsablaufplanung

    

    Zu den Reihenfolgeproblemen zählen neben den Rundreiseproblemen (Traveling-Salesman-Problemen) ebenfalls die Fertigungsablaufplanung. Bei der Fertigungsablaufplanung handelt es sich um verschiedene Aufträge, deren Bearbeitungsreihenfolge auf mehreren Maschinen so abgestimmt werden soll, dass die Bearbeitungszeit minimiert wird. Hierbei wird zwischen Flow-Shop- und Job-Shop-Problemen unterschieden. In diesem Kurs sollen nur Flow-Shop-Probleme behandelt werden und gezeigt werden, wie man ...

18. Flow-Shop-Probleme

    Kombinatorische Optimierung > Fertigungsablaufplanung > Flow-Shop-Probleme

    

    Flow-Shop-Probleme entstehen immer dann, wenn Aufträge auf verschiedenen nachgelagerten Maschinen bearbeitet werden sollen, die Maschinenreihenfolge der einzelnen Aufträge jedoch gleich ist. D.h. also, dass alle Aufträge die gleichen Maschinen in der gleichen Reihenfolge durchlaufen müssen. Dies birgt das Problem, dass einzelne Aufträge andere Aufträge während der Fertigung nicht überholen können.Ein Flow-Shop-Problem liegt ...

19. Johnson-Algorithmus

    Kombinatorische Optimierung > Fertigungsablaufplanung > Johnson-Algorithmus

    

    Der Johnson-Algorithmus liefert für den 2-Maschinen-Fall eine optimale Reihenfolge der jeweiligen Aufträge, die beide Maschinen in derselben Reihenfolgen durchlaufen. Die Bestimmung der optimale Reihenfolge der Aufträge erfolgt, indem die minimale Bearbeitungszeit als Entscheidungskriterium herangezogen wird. Dies soll anhand eines Beispiels dargestellt werden.Beispiel: Johnson-AlgorithmusGegeben seien folgende Aufträge $A_i$ und ihre Bearbeitungszeiten $p_{ij}$ ...