Logo der Fakultät Logo

Kurs 00852

Illustration

Optimierung in Graphen

Autoren/innen: Prof. Dr. Klaus Neumann; Prof. Dr. Dietrich Ohse
Workload: 200 h
SWS: 4 , WS/SS

Prüfung: Modulklausur 31801

Betreuung:

Beratung:

Kurszuordnung

Modul 31801: Problemlösen in graphischen Strukturen [WIWI]

Kurzbeschreibung

Die Abbildung und Modellierung zahlreicher Optimierungsprobleme in Graphen und die damit verbundene Reduzierung auf bekannte Teilprobleme ermöglichen die Nutzung ausgefeilter Algorithmen der Graphentheorie. Im Teil Grundlagen der Graphentheorie (KE 1) werden sowohl Grundprobleme wie auch die zugehörigen Lösungsverfahren vorgestellt. Mit Standortfragen, die etwa bei der Ansiedlung von Unternehmen aber auch bei der Platzierung von Krankenhäusern und Rettungswachen eine zentrale Rolle spielen, und der speziellen Klasse sogenannter Transportprobleme befasst sich die Kurseinheit 2 (KE 2). Sowohl exakte als auch heuristische Verfahren werden zu unterschiedlichen Problembereichen vorgestellt.

Inhaltsübersicht

Kurseinheit 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

Kurseinheit 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

21.08.2018
FernUni-Logo FernUniversität in Hagen, Lehrstuhl für BWL, insb. Quantitative Methoden und Wirtschaftsmathematik, 58084 Hagen