Mathematische Optimierung
SS 2013, 4 VO/2 UE
(502.552 / 502.553)

E. Dragoti-Cela
Institut für Optimierung und Diskrete Mathematik

• Zeit und Ort

Mi., 12:15-14:00, Do., 8:15-9:10, Fr., 8:15-9:45, (siehe Termine in TUGonline für Vorlesung und Übung),
HS BE01, Steyrergasse 30, Erdgeschoss

• Beginn: Mi., 6. März 2013, 12:15-13:45, HS BE01, Steyrergasse 30, Erdgeschoss
• Anmeldung
via TUGonline bis 15.03.2013
• 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.
und wenn es die zeitlichen Restriktionen erlauben
• 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.
Das ist die Hauptreferenz für die Kapitel über die lineare Optimierun und is auch als ebook im TUCampus vorhanden.
• 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.
• 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.

Eine notwendige Bedingung für ein positives Vorlesungs- und Übungszeugnis ist die Bearbeitung eines Miniprojekts (siehe weiter unten).


Termine der Klausuren:

1. Übungsklausur: Mo., 13.5., 18:00-20:00.
2. Übungsklausur: Fr., 5.7., 15:30-17:30.


Die Klausuren werden (rechtzeitig) im Prüfungssystem des TUGonline erfasst;
die Anmeldung zu den Klausuren erfolgt ausschließlich via TUGonline.


Aufgrund des immanenten Charakters der Lehrveranstaltung gibt es genau eine Nachklausur.
Diese wird voraussichtlich in der letzten Woche der Sommerferien stattfinden.
Der genaue Termin wird rechtzeitig bekanntgegeben.
Die Anmeldung zur Nachklausur erfolgt ausschließlich via TUGonline.


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.

Bei den Übungsklausuren sind alle schriftlichen Unterlagen sowie Taschenrechner mit einer Ausgabezeile erlaubt. Dennoch sind alle Zwischenschritte anzugeben. Die Verwendung von internetfähigen Geräten wie Notebooks, PDAs, Handhelds, Handys etc. ist nicht gestattet.


Bei jeder Klausur können maximal 16 Punkte erworben werden.
Für ein positives Übungszeugnis müssen bei den Klausuren in Summe mindestens 14 Punkte erreicht werden.


Mitarbeit im Rahmen der Übungseinheiten:
Für ein positives Übungszeugnis muss jeder Studierender mindestens zwei Mal an der Tafel vorrechnen. Unter allen Kandidatem, die ein bestimmtes Beispiel vorrechnen möchten, wird die Übungsleiterin, unter Berücksichtigung der Anzhal der bereits getätigten Tafelmeldungen, eine Kandidatin bzw. einen Kandidaten aussuchen. Jede Tafelmeldung ist maximal 2 Punkte Wert. Bei der Bewertung der Tafelmeldungen wird neben der mathematischen Korrektheit auch auf die Qualität der Präsentation Wert gelegt.


Das Miniprojekt Die Miniprojekte werden in Gruppen bearbeitet. Jede Gruppe besteht aus 5 Personen und erhält eine eigene Aufgabe, die die Modellierung und Lösung eines realitätsnahen Optimierungsproblems umfasst (siehe Liste von Papers im Anschluss). Das Modell soll mit Hilfe der algebraischen Modellierungssprache AMPL formuliert und mit einem der durch AMPL unterstützten Solver gelöst werden. Eine kurze Einfürung in AMPL wird im Rahmen der Vorlesung gegeben. Sinn und Zweck des Miniprojekts ist jedoch auch die individuelle und selbstständige Auseinandersetzung der Studierenden mit AMPL und den jeweiligen Solvern.
Die Gruppeneinteilung und die Aufgabenzuordnung werden im Laufe des Semesters erfolgen, nachdem die theoretischen Grundlagen für die Bearbeitung der Miniprojekte vorhanden sind.
Die Präsentation der Miniprojekte wird im Rahmen von zwei Lehrveranstaltungseinheiten
gegen Ende des Semesters erfolgen.
Das Miniprojekt wird mit maximal 2 Punkten bewertet.
Details über die Abgabe und Präsentation der Miniprojekte.


Themen für das Miniprojekt

1. De Angelis, Ricciardi, und Storchi,
   Optimizing blood assignment in a donation-transfusion system,
   Intl. Trans. in Op. Res. 8, 2001, 183-192. pdf File
   
2. S. Koch, S. König und G. Wäscher,
   Linear programming for a cutting plane in the wood processing industry - a case study,
   /amnt/public_html/cela/Vorlesungen/MathOptSS13/ Faculty of Economics and Management, Otto von Guericke Universität Magdeburg, 2008. pdf File
   
3. N.S. Walmsley und P. Hearn,
   An application of linear programming in the defence environment,
   Intl. Trans. in Op. Res. 10, 2003, 155-167. pdf File
4. J.V. Caixeta-Filho, J.M. van Swaay-Neto und R.L. Lopes,
   Linear programming applied to the flower sector: a Gladioulus buld production case study,
   Intl. Trans. in Op. Res. 7, 2000, 525-537. pdf Fil /amnt/public_html/cela/Vorlesungen/MathOptSS13/e
5. J. Karlsson, M. Rönnqvist und J. Bergström,
   Short term harvest planning including scheduling of harvest crews,
   Intl. Trans. in Op. Res. 10, 2003, 413-431. pdf File
/amnt/public_html/cela/Vorlesungen/MathOptSS13/
6. O. Gyles and O. Montecillo,
   Linear programming and future landuse scenarios,
   43th Annual Conference of the Australian Agricultural and Resource Economics Society, 1999. pdf File
7. R. Chatturvedi, K. Bhattacharya und J. Parick,
   Transmission planning for Indian Power Grid: a mixed integer programming approach,
   Intl. Trans. in Op. Res. 6, 1999, 465-482. pdf File
8. R. Chattopadhyay,
   Production and maintenace planning for electricity generators: modeling and applications to indian power systems,
   Intl. Trans. in Op. Res. 8, 2001, 465-490. pdf File
9. M. Yu, H. Inoue und A. Shi,
   Portfolio optimization problems with linear programming models,
   Tokyo University of Science, School of Management, Discussion paper, 2006. pdf File
10. A. Ölafsson und S. Wright,
    Linear programming formulation and algorithms for radiotherapy treatment planning,
    Optimization Methods and Software 21 (2), 2006, 201-231. pdf File
11. E.K. Lee, T. Fox und J. Crocker,
    Integer programming applied to intensity-modulated radiation therapy treatment planning,
    Annals of Operations Research 119 , 2003, 165-181. pdf File
12. S. Daskalaki, T. Bibas und E. Housos,
    An integer programming formulation for a case study in unversity timetabling,
    European Journal of Operational Research 153, 2004, 117-135. pdf File
/amnt/public_html/cela/Vorlesungen/MathOptSS13/
13. U. Özdemir,
    Methodology for crew-pairing problem in airline crew scheduling,
    Master Theses, Bogazici Univesity, 2009. pdf File


Somit ergibt sich eine maximale Anzahl von 38 = 2*16+2*2+2 zu erreichenden Punkten.


Es gibt auch die Möglichkeit Bonuspunkte zu erwerben: wenn für das Vorrechnen eines Beispiels keine Kandidatin/keinen Kandidaten gibt, die/der weniger als zweimal an der Tafel war, dann dürfen andere Freiwillige das Beispiel vorrechnen und maximal einen Punkt pro vorgerechnetem Beispiel erwerben. Es können maximal 2 Bonuspunkte erworben werden.


Notenschlüssel für die Bewertung der Übung:

0 <= P <= 19	Nicht genügend
19 < P <= 24	Genügend
24 < P <= 29	Befriedigend
29 < P <= 34	Gut
34 < P	Sehr Gut.



• Übungsblätter (pdf)
  • 1. Übungsblatt zu besprechen am Do., 14.3.
  • 2. Übungsblatt zu besprechen am Mi., 20.3.
  • 3. Übungsblatt zu besprechen am Mi., 17.4.
  • 4. Übungsblatt zu besprechen am Mi., 24.4.
  • 5. Übungsblatt zu besprechen am Do., 2.5. und am Mi., 8.5.
  • 6. Übungsblatt zu besprechen am Fr., 17.5.
  • 7. Übungsblatt zu besprechen am Mi., 22.5.
  • 8. Übungsblatt zu besprechen am Mi., 29.5.
  • 9. Übungsblatt zu besprechen am Fr., 7.6.
  • 10. Übungsblatt zu besprechen am Fr., 14.6.
  • 11. Übungsblatt zu besprechen am Mi., 19.6.
  • 12. Übungsblatt zu besprechen am Mi., 26.6.
  • Sonstige Unterlagen (pdf)
    • Ein generisches innere Punkteverfahren fü lineare Optimierungsprobleme mit Newton-Schritten.
      Achtung: keine gute Bildqualität (handgeschrieben bzw. eingescannt).

  ---

  
    cela@opt.math.tu-graz.ac.at.

  Back to my homepage

  Letzte Änderung: Juni 2013

  ---