Lerninhalte |
Lehrziel:
- Die Studierenden lernen Grundprinzipien der linearen und graphentheoretischen Optimierung und - erwerben Fähigkeiten zur Modellierung praktischer Probleme als lineare bzw. graphentheoretische Probleme. - Sie erwerben Fähigkeiten zur Implementierung der behandelten Algorithmen mit C++. - Sie werden mit wichtigen kombinatorischen Beweismethoden vertraut gemacht.
Inhalt:
- Modellierung: Beispiele linearer und graphentheoretischer Optimierungsprobleme, einfache Lösungsansätze - Simplexmethode: Normalform, Basisdarstellungen und Ecken von Polyedern, Simplex-Algorithmus - Dualitätstheorie: duale Probleme und duale Simplextabellen, Dualitätssätze, Anwendungen - Graphentheorie: Grundbegriffe, Eulersche und Hamiltonsche Kreise, Baumkriterien - Graphentheoretische Algorithmen: Komplexität von Algorithmen, Speicherung von Graphen, Suchalgorithmen, Minimalgerüste und kürzeste Wege, Längste Wege und Projektplanung - Netzwerktheorie: Maximalflüsse in Netzwerken, Kostenminimale Flüsse, Zuordnungsprobleme und weitere Anwendungen - Dynamische Optimierung: Floyd/Warshall-Algorithmus und Standortplanung, Geschichtete Netzwerke und das Bellmansche Optimalitätsprinzip, Rucksackprobleme, das Rundreiseproblem und weitere Anwendungen
|