-
Zeit
und Ort
Di., 12:15-14:00, Mi., 8:15-9:45, Do., 8:15-9:45, (siehe Termine in TUGonline
für Vorlesung
und Übung),
HS BE01, Steyrergasse 30, Erdgeschoss
-
Beginn: Do., 1.
März 2012, 8:15-9:45, HS BE01, Steyrergasse 30, Erdgeschoss
-
Anmeldung
via TUGonline bis 18.03.2012
-
Vorlesungsinhalt
Diese Lehrveranstaltung befasst sich mit grundlegenden Konzepten und Problemen der Mathematischen
Optimierung. Im ersten Teil der Vorlesung werden die Grundlagen der Linearen Optimierung ausführlich besprochen (Simplexverfahren, Dualitästheorie, Komplexitä der linearen Optimierung, innere Punkteverfahren). Im zweiten Teil der Vorlesung werden grundlegende Konzepte und Techniken der Ganzzahligen Optimierung eingeführt, etwa Branch-and-Bound-Verfahren,
Lagrange-Relaxation, Dynamische Optimierung, vollständige Unimodularität. Das dritte Teil der Vorlesung befasst sich mit der Nichtlinearen Optimierung insbesondere mit Quadratische Optimierung, Konvexe Optimierung, Nichtlineare Optimierung ohne Nebenbedingungen, sowie Karush-Kuhn-Tucker-Theorie.
Die Kapitelüberschriften und Stichwörter sind:
- Einführende Optimierungsmodelle
- Hauptsatz der linearen Optimierung
- Das Simplexverfahren: ausgangslösung, Spaltenauswahl, Kreisen des Verfahrens, Behandlung von Gleichungen, beschränkten Variablen und Variablen mit beliebigen Vorzeichen, Simplexiinterpretation, das revidierte Simplexverfahren, das Simplexverfahren mit LU-Zerlegung.
- Dualitätstheorie: Dualitätssätze, Hauptsatz der Spieltheorie, Trennungssätze für konvexe Mengen, das duale Simplexverfahren.
- Innere Punkteverfahren und Komplexität der linearen Optimierung:: der zentraler Pfad, Pfad-verfolgende Methoden.
- Ganzzahlige Lösungen linearer Probleme:vollstädige Unimodularität und das Transportproblem
- Ganzzahlige Optimierung: das Rucksackproblem und die Dynamische Optimierung, Branch-and-Boound-Verfahren.
- Quadratische Optimierung:konvexität und Komplexität, Innerepunktverfahren.
- Konvexe Optimierung: Innerepunktverfahren, sukzessive quadratische Approximation.
- Nichtlineare Optimierung ohne Nebenbedingungen: Line Search, Newton- und quasi-Newton-Verfahren.
- Nichtlineare Optimierung mit Nebenbedingungen: die Karush-Kuhn-Tucker Bedingungen.
-
Literatur
Literatur
Je nach Thema und Kapitel dienen folgende Bücher als Ausarbeitungsgrundlage für diese Vorlesung:
-
R.E.Burkard und U.T. Zimmermann,
Einführung in die Mathematische Optimierung
Springer Lehrbuch, 2012.
-
R. Vanderbei, Linear Programming: Foundations and Extentions , Springer US, 2010.
-
G.B. Dantzig und M.N. Thapa Linear Programming: 1: Introduction, Springer Series in Operations Research and Financial Engineering, 1998.
-
G.B. Dantzig und M.N. Thapa Linear Programming: 2: Theory and Extentions, Springer Series in Operations Research and Financial Engineering, 2010.
- A. Schrijver,
, Theory of Linear and Integer Programming,
Wiley Interscience Series in Discrete Mathematics, 1998.
- M.S. Bazaraa, H.D. Sherali und C.M. Shetty, Nonlinear Programming: Theory and Algorithms, Wiley, 2006.
- D.G. Luenberger und Y. Ye,
Linear and Nonlinear Programming (International Series in Operations Research & Management Science) , Springer US, 2008.
- L.A. Wolsey und G.L. Nemhauser,
Integer and Combinatorial Optimization, Wiley-Interscience Series
in Discrete Mathematics and Optimization, 1999.
Zum Thema Lineare Optimierung könnte auch das Skriptum von Prof. Burkard (pdf) als Literaturquelle herangezogen werden; hier wird es relativ große Überschneidungen geben.
-
Prüfungsmodus
Die Vorlesung wird anhand einer schriftlichen und einer mündlichen Prüfung benotet. Die Prüfungstermine werden je nach Bedarf mit der Vortragenden vereinbart.
Die zweistündige Übung hat einen immanenten Charakter und wird anhand von zwei Klausuren und der Mitarbeit der Studierenden in den Übungsstunden mit Hilfe
eines Punktesystems benotet.
Termine der Klausuren:
1. Übungsklausur: Fr., 4.5., 16:00-17:30.
2. Übungsklausur: Do., 5.7., 16:15-17:45.
Aufgrund des immanenten Charakters der Lehrveranstaltung gibt es genau eine Nachklausur.
Diese wird voraussichtlich in der ersten Woche oder in der letzten Woche der Sommerferien stattfinden.
Der genaue Termin wird rechtzeitig bekanntgegeben.
Beim Antreten zur Nachklausur ist zu entscheiden,
ob die erste oder die zweite Klausur wiederholt werden soll. Durch den Antritt werden die Punkte aus der wiederholten Klausur gelöscht.
Die Klausuren werden (rechtzeitig) im Prüfungssystem des TUGonline erfasst;
die Anmeldung zu den Klausuren erfolgt via TUGonline.
Bei den Übungsklausuren sind alle schriftliche Unterlagen sowie Taschenrechner mit einer Ausgabezeile erlaubt.
Dennoch sind alle
Zwischenschritte anzugeben./amnt/public_html/cela/Vorlesungen/MathOptSS12/
Bei den Klausuren ist die Verwendung von Notebooks, PDAs, Handhelds etc. nicht gestattet.
Mitarbeit im Rahmen der Übungseinheiten:
Vor jeder Übung müssen Sie online ankreuzen (Ankreuzschluss ist 45 Minuten vor
Beginn der Übung), welche Beispiele Sie gelöst haben und vorführen können.
Anhand dieser Kreuze werden per Zufallsgenerator Studierende ausgewählt, um das jeweilige
Beispiel an der Tafel vorzuführen.
Für ein Tafelbeispiel gibt es höchstens
drei Punkte. Die Punkte für die Tafelleistungen ergeben sich als arithmetisches Mittel der Punkte auf die einzelnen Tafelleistungen.
Bei besonders gut gelungener Präsentation kann pro Tafelleistung bis zu einem halben Zusatzpunkt vergeben werden.
Bei der Vorführung von Beispielen wird neben der mathematischen Korrektheit auch auf die
Qualität der Präsentation Wert gelegt. Falls die Präsentation darauf
schließen lässt, dass das Beispiel zu Unrecht angekreuzt wurde
(insbesondere bei Abwesenheit), werden sämtliche Beispiele der letzten
Übungseinheit gestrichen und/oder die Punktezahl auf die Kreuze mit 0.75 (im Wiederholungsfall auch 0.5 oder 0.25 oder 0) multipliziert.
Die Punktezahl für die Kreuze einer Übungseinheit ergibt sich als Anzahl der angekreuzten durch Anzahl der ankreuzbaren Beispiele.
Damit erhält man für jede einzelne Übungseinheit einen Punktewert zwischen 0 und 1.
Die Summe der Punkte auf die 12 besten Übungseinheiten ergibt die Punktezahl für Kreuze für das Semester.
Da es 14 Übungseinheiten gibt, ergibt sich daraus, dass zweimaliges Fernbleiben keine Auswirkungen hat.
In besonders berücksichtigungswürdigen Fällen kann bei entsprechendem Nachweis und vorheriger Vereinbarung einer
häufigeren Verhinderung Rechnung getragen werden.
Benotung:
1. Übungsklausur: 14 Punkte
2. Übungsklausur: 14 Punkte
Tafelleistungen : 3 Punkte
Kreuze: 12 Punkte
Notenschlüssel für die Bewertung der Übung:
|
1 <= P < = 22 | Nicht genügend |
|
22 < P < = 27 | Genügend |
|
27 < P <= 32 | Befriedigend |
|
32 < P < = 37 | Gut |
|
37 < P | Sehr Gut.
|
-
Online Ankreuzsystem mit Punkteeinsicht
Bei der ersten Anmeldung bitte Matrikelnummer und ein leeres Passwort eingeben, daraufhin wird ein Passwort per Email zugestellt. Beachten Sie, dass eine Anmeldung erst nach der Anmeldung zur LV im TUGonline möglich ist und dass zwischen der Anmeldung im TUGonline und der Einspielung der Daten in das Ankreuzsystem einige Zeit vergehen kann.
cela@opt.math.tu-graz.ac.at.