Modul 31801

Problemlösen in graphischen Strukturen

  • Autoren/innen: Prof. Dr. Klaus Neumann; Prof. Dr. Dietrich Ohse; Prof. Dr. Wilhelm Rödder; Dr. Friedhelm Kulmann; Dr. Heinz Peter Reidmacher
  • Workload: 300 h
  • Semester: WS/SS
  • ECTS-Punkte: 10
  • Prüfung: Modulklausur 31801

Betreuung:

Beratung:

Aktuelle Hinweise

Kurzbeschreibung

Bei der Lösung zahlreicher Optimierungsprobleme bedient man sich der Repräsentation in Graphen, um bei der Aufgabenstellung geeignete Algorithmen aus diesem Bereich nutzen zu können.

Grundlagen der Graphentheorie und Netzwerkoptimierung:
Die Abbildung und Modellierung betriebswirtschaftlicher Aufgabenstellungen in Graphen und die damit verbundene Reduzierung auf bekannte Teilprobleme ermöglichen die Nutzung ausgefeilter Algorithmen der Graphentheorie. In der Einheit 1 werden sowohl Probleme der Wege- und Flussoptimierung wie auch die zugehörigen Lösungsverfahren vorgestellt.

Standortplanung und Transportoptimierung:
Mit der Frage der Standortplanung und der speziellen Klasse der Transportprobleme sowie deren jeweiligen Lösung befasst sich die Einheit 2, in der auch verwandte Probleme analysiert und teilweise in ein „klassisches“ Transportproblem transformiert werden.

Optimierung mit intelligenten Strategien:
Viele praktische Aufgabenstellungen lassen sich als kombinatorische Optimierungsprobleme formulieren, für die keine effizienten Algorithmen existieren. In Einheit 3 werden zunächst die exakten Methoden Branch & Bound und der A*-Algorithmus gegenübergestellt; außerdem wird auf einige spezielle Ausprägungen der Nachbarschaftssuche eingegangen. Ausgehend von Verbesserungsverfahren werden im weiteren Teil die neueren Entwicklungen Simulated Annealing, Tabu-Search und die Genetischen Algorithmen behandelt.

Inhaltsübersicht

mehr erfahren

Einheit 1: Grundlagen der Graphentheorie

1. Grundbegriffe
1.1 Praktische Probleme, die auf Graphen und Netzwerke führen
1.2 Grundlegende Definitionen
1.3 Kantenfolgen in Graphen und Pfeilfolgen in Digraphen
1.4 Erreichbarkeit und Zusammenhang in Graphen und Digraphen
1.5 Charakteristische Matrizen zu Graphen und Digraphen
1.6 Für Anwendungen wichtige Klassen von Graphen und Digraphen
1.7 Bewertete Graphen und Netzwerke

2. Graphen und Computer
2.1 Rechenaufwand von Algorithmen
2.2 Einige wichtige Graphen-Algorithmen

3. Minimalgerüste und kürzeste Wege
3.1 Minimalgerüste
3.2 Kürzeste Wege von einem zu allen Knoten (Baumalgorithmen)
3.3 Bellmans Verfahren für zyklenfreie Netzwerke
3.4 Dijkstras Algorithmus für Netzwerke mit nichtnegativer Bewertung
3.5 Das Verfahren von Ford für Netzwerke mit beliebiger Bewertung
3.6 Kürzeste Wege zwischen allen Knoten: Der TripelAlgorithmus von Floyd und Warshall

4. Flüsse in Netzwerken
4.1 Flüsse und Schnitte in Netzwerken
4.2 Flüsse in Graphen und Zirkulationsflüsse
4.3 Der Algorithmus von Ford und Fulkerson zur Bestimmung eines maximalen Flusses
4.4 Bestimmung eines zulässigen Anfangsflusses
4.5 Kostenminimale Flüsse und Zirkulationsflüsse
4.6 Optimalitätsbedingungen für Zirkulationsflüsse
4.7 Der Out-of-Kilter-Algorithmus zur Bestimmung eines kostenminimalen Zirkulationsflusses

Einheit 2: Standortplanung und Transportoptimierung

5. Optimale Standortplanung
5.1 Standardfragen der Standortplanung
5.2 Mediane und Zentren
5.3 Überdeckungsprobleme
5.4 Warehouse Location Probleme

6. Modellierung von Transportproblemen
6.1 Alternative Darstellungsformen
6.2 Verallgemeinerungen des klassischen Transportproblems
6.3 Lösungsverfahren für Transportprobleme

7. Mengenorientierte Verfahren für das Transportproblem
7.1 Die Lösung des Transportproblems mit der Simplex-Methode
7.2 Die Stepping-Stone-Methode
7.3 Bestimmung einer zulässigen Ausgangslösung
7.4 Implementierung primaler Methoden
7.5 Ganzzahligkeit und vollständige Unimodularität

8. Mengen und preisorientierte Verfahren für Transport und Umladeprobleme
8.1 Das Umladeproblem
8.2 Der LP-Ansatz für das Umladeproblem
8.3 Das Out-of-Kilter-Verfahren
8.4 Sonderprobleme

9. Die Ungarische Methode: Ein preisorientiertes Verfahren zur Lösung des Zuordnungsproblems
9.1 Das Zuordnungsproblem
9.2 Duale Zulässigkeit
9.3 Flussänderung
9.4 Potentialänderung
9.5 Netzwerkorientierte Darstellung der Ungarischen Methode
9.6 Die Ungarische Methode in Transporttableauform

Einheit 3: Optimierung mit Intelligenten Strategien

1. Komplexität
1.1. Allgemeine Komplexitätsbetrachtungen
1.2. Die Komplexität spezieller Algorithmen

2. Exakte Methoden
2.1. Das Branch & Bound-Verfahren
2.2. Das A*-Verfahren als Bestensuchverfahren
2.3. Vergleich von A*- und Branch & Bound-Verfahren
2.4. Beispiel zu Suchstrategien

3. Klassische Heuristiken
3.1. Klassifizierung
3.2. Eröffnungsverfahren
3.3. Verbesserungsverfahren
3.4. Kritische Beurteilung klassischer Heuristiken
3.5. Praxisbeispiel Bandbreitennutzung

4. Simulated Annealing
4.1. Physikalischer Hintergrund und Grundidee
4.2. Algorithmische Realisierung
4.3. Beispiele zum Simulated Annealing
4.4. Übungen zur Anwendung von Simulated Annealing

5. Tabu Search
5.1. Die Grundidee des Tabu-Search
5.2. Vermeidung von Zyklen
5.3. Berechnung des TSP-Beispiels
5.4. Ein Praxisbeispiel: Digitaler Hörfunk
5.5. Übungen zur Anwendung von Tabu Search

6. Genetische Algorithmen
6.1. Einführung in die Genetischen Algorithmen
6.2. Basiswissen zum Genetischen Algorithmus
6.3. Beispiele zum Genetischen Algorithmus
6.4. Genetische Algorithmen in der Praxis
6.5. Übungen zu Genetischen Algorithmen

Links zu weiteren Informationen

08.10.2024