Modul 32621
Optimierungsmethoden des Operations Research
- Autoren/innen: Prof. Dr. Andreas Kleine; Prof. Dr. Rainer E. Burkard; Prof. Dr. Heinz Isermann; Prof. Dr. Wilhelm Rödder; Prof. Longgui Xu (VR China); Dr. Peter Zörnig
- Workload: 300 h
- Semester: WS/SS
- ECTS-Punkte: 10
- Prüfung: Modulklausur 32621
Betreuung:
-
Prof. Dr. Andreas Kleine
Lehrstuhlinhaber
E-Mail: andreas.kleine
Beratung:
-
Daniela Wiesner
beantwortet per E-Mail spezielle Fragen zum Fachgebiet.
E-Mail: daniela.wiesner
Aktuelle Hinweise
Kurzbeschreibung
Viele ökonomische Fragestellungen lassen sich als (ganzzahliges) lineares Optimierungsproblem formulieren. Die Einheiten des Moduls "`Optimierungsmethoden des Operations Research"' behandeln die Überführung realer Sachverhalte in mathematische Modelle und stellen Verfahren zur Lösung vor.
Lineare Optimierung
Nach einem einleitenden Beispiel wird die formale Lösung linearer Optimierungsaufgaben mittels Simplexalgorithmus dargestellt und ökonomisch interpretiert. Es schließen sich Ausführungen zur Dualitätstheorie der linearen Optimierung an, bevor im Kapitel zur postoptimalen Analyse untersucht wird, wie sich Veränderungen der Ausgangsdaten auf die Lösungsstruktur auswirken. Der softwaregestützten Lösung linearer Optimierungsprobleme ist ebenfalls ein Kapitel gewidmet. Die Einheit schließt mit einer praxisbezogenen Fallstudie.
Ganzzahlige Optimierung
Die Einführung behandelt zunächst ökonomische Fragestellungen, welche für die ganzzahlige Optimierung typisch sind. Darauf aufbauend werden einzelne Lösungsverfahren wie das Branch & Bound Verfahren anschaulich vertieft. Ein gesondertes Kapitel stellt eine Auswahl spezieller, ökonomisch relevanter ganzzahliger Optimierungsprobleme vor, z.B. Überdeckungsprobleme (Covering-Probleme).
Optimierung bei mehrfacher Zielsetzung
In realen Entscheidungssituationen werden vielfach mehrere, mithin konfliktbehaftete Zielstellungen simultan verfolgt. Nach der Definition grundlegender Begriffe wird gezeigt, wie sich die Menge der relevanten Lösungen eingrenzen lässt und welche Bedeutung Kompromissmodellen zukommt. Ausgewählte Vorschläge zur Ermittlung von Kompromisslösungen schließen die Betrachtungen ab.
Inhaltsübersicht
mehr erfahren
Einheit 1: Lineare Optimierung
1. Einleitung
1.1 Einordnung und Übersicht
1.2 Einführendes Beispiel und Grundlagen
2. Lineare Gleichungssysteme
2.1 Allgemeine Lösung linearer Gleichungssysteme
2.2 Basislösungen
2.2.1 Basislösungen für einfache Gleichungssysteme
2.2.2 Basislösungen für erweiterte Gleichungssysteme
3. Lineare Optimierungsaufgaben
3.1 Die Standard-Formen des linearen Optimierungsproblems
3.2 Grundideen zur Lösung von LOPs
4. Simplexalgorithmus
4.1 Verbesserung von Basislösungen und Optimalität
4.2 Die Iterationsschritte
4.3 Die Zweiphasenmethode
4.4 Entartung und Konvergenz des Simplexverfahrens
4.5 Ökonomische Interpretation der Simplex-Iterationen
5. Dualitätstheorie
5.1 Duale lineare Optimierungsprobleme
5.2 Zusammenhänge zwischen zueinander dualen linearen Optimierungsproblemen
5.3 Die duale Simplexmethode
6. Revidierte Simplexmethode
6.1 Pivotschritte und Elementarmatrizen
6.2 Der Algorithmus
7. Der Simplexalgorithmus für LOPs mit beschränkten Variablen
8. Postoptimale Analyse
8.1 Sensitivitätsanalyse
8.2 Parametrische Programmierung
8.3 Strukturelle Änderungen der Ausgangsdaten
9. LP-Software
9.1 Überblick LP-Software
9.2 Modellierung von LOPs mit GAMS
10. Fallstudie: Geschmiert AG
...
Einheit 2: Ganzzahlige Optimierung
1. Einführung in die ganzzahlige Optimierung
1.1 Optimierungsprobleme mit diskreten Variablen
1.2 Zusammenhang zwischen linearer und ganzzahliger Optimierung
1.3 Lösungskonzepte für ganzzahlige Optimierungsprobleme
1.4 Verfahren zur Lösung diskreter Optimierungsaufgaben
2. Branch und Bound Verfahren
2.1 Allgemeine Beschreibung von Branch und Bound Verfahren
2.2 Branch und Bound Verfahren zur Lösung gemischt-ganzzahliger linearer Programme
2.3 Ein Branch und Bound Verfahren zur Lösung des Rundreiseproblems
3. Schnittebenenverfahren
3.1 Schnittebenenverfahren für rein ganzzahlige lineare Programme
3.2 Ein rein-ganzzahliges Schnittebenenverfahren
3.3 Ein Schnittebenenverfahren zur Lösung gemischt-ganzzahliger linearer Programme
3.4 Benders' Dekomposition
4. Das Rucksackproblem
5. Einige spezielle Probleme der kombinatorischen Optimierung
5.1 Überdeckungs- und Partitionsprobleme
5.2 Symmetrische Rundreiseprobleme
6. Einsatz von EDV zur Lösung diskreter Optimierungsproblem
...
Einheit 3: Optimierung bei mehrfacher Zielsetzung
1. Grundlagen und Aufgabenstellungen einer Optimierung bei mehrfacher Zielsetzung
1.1 Beispiele
1.2 Aufgabenstellung eines Vektormaximumproblems
1.3 Aufgabenstellungen einer Optimierung bei mehrfacher Zielsetzung
2. Ermittlung funktionaleffizienter Lösungen eines Vektormaximumproblems
2.1 Parametrische Programme zur Lösung von Vektormaximumproblemen
2.2 Ermittlung der vollständigen Lösung eines linearen Vektormaximumproblems
3. Ermittlung einer Kompromisslösung mit Hilfe von Kompromissmodellen
3.1 Kompromissmodelle mit skalarer Präferenzfunktion
3.2 Kompromissmodelle bei vorgegebenem Zielwertvektor
4. Ermittlung einer Kompromisslösung unter Anwendung interaktiver Verfahren
4.1 Allgemeine Charakterisierung interaktiver Verfahren
4.2 Steuerung des Suchprozesses durch sukzessive Vorgabe von Untergrenzen
4.3 Steuerung des Suchprozesses durch eine Bewertung ausgewählter Trade-of-Verfahren
