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 Graphen, Digraphen und Matrizen
1.6 Für Anwendungen wichtige Klassen von Graphen und Digraphen
1.7 Bewertete Graphen und Digraphen, Netzwerke

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

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 OutofKilterAlgorithmus 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 Verallgemeinerungen des klassischen Transportproblems
6.2 Lösungsverfahren für Transportprobleme

7. Mengenorientierte Verfahren für das Transportproblem
7.1 Die Lösung des Transportproblems mit der SimplexMethode
7.2 Die SteppingStoneMethode
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

Ergänzungen : Multimedia

Der Lehrtext zur KE1 des Kurses »Optimierung in Graphen« wird nicht nur als Printkurs sondern auch in einer multimedialen Version als sogenannter Hörkurs angeboten. Zu allen Kapiteln spricht Herr Prof. Rödder eine überblickartige Einleitung, bevor die wesentlichen Inhalte verbal erklärt und ausführlich erläutert werden. Der Audioteil umfasst insgesamt drei CDs, der sowohl vor- als auch nachbereitend zu der ebenfalls mitgelieferten Multimedia-CD gehört werden kann. Auf der vierten CD ist das gesamte Kursmaterial sowohl kompakt mit vielen zusätzlichen Animationen, als auch in der ausführlichen Form gespeichert. Die komplette Box wird mit dem Kursmaterial ausgeliefert.

Literatur

Das Literaturverzeichnis zum Kurs 00852 »Optimierung in Graphen« steht im sogenannten virtuellen Semesterapparat online zur Verfügung. Von dort haben Sie die Möglichkeit, direkt im Katalog der UB, Aleph nachzuschlagen, ob ein gewünschtes Buch verfügbar ist.
Darüber hinaus gibt es noch weitere Recherchemöglichkeiten.

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