Lineare Optimierung WS '03/04


Aktuelle Informationen und Hinweise


Allgemeine technische Hinweise


Inhaltliche Hinweise

Im Verlaufe des Semesters werden u.a. (!) folgende Themen behandelt:
Bei allen Themen wird versucht, einige historische Zusammenhänge zu vermitteln und auch ein wenig die Anschauung zu schulen.
Im kommenden Semester wird der Optimierungszyklus fortgesetzt mit der Veranstaltung ``Diskrete Optimierung''. Im Anschluß an eine Seminarteilnahme (wahrscheinlich sowohl im SS 2004 als auch im WS 2004/05 möglich) können Diplomarbeiten vergeben werden.


Termine

Vorlesung: Dienstag 09:45 - 11:15 Uhr PK 4.1 Sándor Fekete
  Donnerstag 11:30 - 13:00 Uhr PK 4.1 Sándor Fekete
Große Übungen Dienstag 15:00 - 16:30 Uhr PK 4.1 Laura Heinrich-Litan
Kleingruppe 1 Mittwoch 11:30 - 13:00 Uhr Inga Hafemann
Kleingruppe 2 Mittwoch 15:00 - 16:30 Uhr Ulla Neumann


Sprechstunden:

   
Sprechstunde
Raum Telefon email
Dozent: Sándor Fekete Di 11:15 - 12:00 Uhr F 524 391-7551 sandor.fekete AT tu-bs.de
Assistentin: Laura Heinrich-Litan n.V. F 523 391-7561 litan AT tu-bs.de
HiWinen: Inga Hafemann per Mail n.V. - i.hafemann AT tu-bs.de
  Ulla Neumann per Mail n.V. - u.neumann AT tu-bs.de


Übungsblätter

  • 1. Übung  [ Postscript, Postscript (gzipped), PDF
  • 2. Übung  [ Postscript, Postscript (gzipped), PDF
  • 3. Übung  [ Postscript, Postscript (gzipped), PDF
  • 4. Übung  [ Postscript, Postscript (gzipped), PDF
  • 5. Übung  [ Postscript, Postscript (gzipped), PDF
  • 6. Übung  [ Postscript, Postscript (gzipped), PDF
  • 7. Übung  [ Postscript, Postscript (gzipped), PDF
  • 8. Übung  [ Postscript, Postscript (gzipped), PDF
  • 9. Übung  [ Postscript, Postscript (gzipped), PDF
  • 10. Übung  [ Postscript, Postscript (gzipped), PDF
  • 11. Übung  [ Postscript, Postscript (gzipped), PDF
  • 12. Übung  [ Postscript, Postscript (gzipped), PDF
  • Aus dem vorigen Semester:
  • Klausur [ Postscript, Postscript (gzipped), PDF
  • Klausurergebnis [ Postscript (gzipped), PDF

  • Anlagen zur Erläuterung

  • Anlage 1: Simplex-Verfahren mit beschränkten Variablen [ Postscript, Postscript (gzipped), PDF
  • Anlage 2: Simplex-Verfahren mit freien Variablen [ Postscript, Postscript (gzipped), PDF
  • Anlage 3: Ausgleichsprobleme [ Postscript, Postscript (gzipped), PDF
  • Anlage 4: Das duale Simplexverfahren [ Postscript, Postscript (gzipped), PDF
  • Anlage 5: Das primal-duale Simplexverfahren [ Postscript, Postscript (gzipped), PDF
  • Anlage 6: Sensitivitätsanalyse [ Postscript, Postscript (gzipped), PDF

  • Literatur und Links

    Verschiedene Skripten zur Optimierung.
    Die wichtigsten Skripten gibt es auch direkt hier:
    Einführung in die Optimierung
    Lineare Optimierung, Teil 1
    Lineare Optimierung, Teil 2
    Diskrete Optimierung
    (Die einzelnen Kapitel werden in der Vorlesung in anderer Reihenfolge behandelt!)

    Die Webseite zu meiner Vorlesung Lineare Optimierung aus dem WS 2002/03. Dort gibt es auch alte Übungsblätter und Klausuraufgaben.
    (Allerdings wird die Vorlesung dieses Semester deutlich anders aussehen!)

  • Bücher: Die letzten beiden Bücher behandeln hauptsächlich Themen aus der diskreten Optimierung, aber aufgrund der engen Verbindungen sind einige Teile auch hier nützlich.
    Zum Nacharbeiten eine detaillierte Übersicht möglichst präziser Literaturtips zu den einzelnen Kapiteln der Vorlesung; das bedeutet im Einzelnen nicht, dass alles genau so vorkommt und vorkam, aber man findet jeweils eine ganze Menge zur Ergänzung und an weiteren Details.
  • Kapitel 0, Grundlagen: (Diverse!)
  • Kapitel 1, Explizite Varianten: Skript Zimmermann, Kapitel 2, ab Seite 14
  • Kapitel 2, Duale Verfahren: Skript Zimmermann, Kapitel 3, ab Seite 24
  • Kapitel 3, Matrixspiele: Chvatal, Kapitel 15, ab Seite 228
  • Kapitel 4, Netzwerk- und Transportprobleme: Chvatal, Kapitel 19, ab Seite 291. (Weiterführend ist Kapitel 20 mit einigen interessanten Anwendungen, z.B. über bipartites Matching!)
  • Kapitel 5, Darstellung von Polyedern: Skript Zimmermann, Kapitel 6, ab Seite 46. (Achtung! Das Ende des Kapitels ist oben im Teil 2 zu finden!) Ich habe mich in einigen Aspekten mehr auf Schrijver gestützt, Kapitel 7 und 8.
  • Kapitel 6, Schnittebenen: Papdimitriou, Kapitel 14, ab Seite 326.
  • Kapitel 7, Sensitivitätsanalyse: Skript Zimmermann, Kapitel 5, ab Seite 38
  • Kapitel 8 Komplexitätstheorie: Garey/Johnson, Kapitel 3, ab Seite 45 (vor allem Seiten 48/49 und 53-56), aber auch z.B. Papdimitriou, Kapitel 15, ab Seite 342.
  • Kapitel 9, Komplexität der Linearen Optimierung: Papdimitriou, Kapitel 8, ab Seite 156, aber auch diverse andere (Schrijver, Kapitel 13 und 14, Korte/Vygen).

    Weitere Links:

  • Ein sehr schönes elektronisches Skript aus Wien. Die Seiten zur linearen Optimierung geben einen ganz guten Überblick mit vielen Bildern.

  • Eine Anwortliste zu Linearer Optimierung. (Englisch, sehr viele Details zu Software, Literatur etc.)

  • Eine Linksammlung zu Polytopen und Polyedern.

  • Ein Java-Applet zur Simplex-Visualisierung.


  • Last modified: Wed Feb 18 10:01:40 CET 2004
    <sandor.fekete AT tu-bs.de>