Zur Seite der TU

Lineare Optimierung

(ADM II)

 Zur Seite des Instituts für Mathematik
 

Wintersemester 2003

  
LV-Nr.: 0230 L 226
 

Prof. Dr. Martin Grötschel
  

Inhalt

Die Entwicklung der linearen Optimierung ist (nach Einschätzung vieler Fachleute) der wichtigste Beitrag der Mathematik des 20. Jahrhunderts zur Lösung praktischer Fragestellungen in Industrie und Wirtschaft. Vermutlich benutzt heute jede größere Firma Methoden der linearen Optimierung auf die eine oder andere Weise bei ihrer planerischen oder operativen Tätigkeit. Die Vorlesung gibt eine Einführung in die Theorie und Praxis der linearen Optimierung und behandelt Grundzüge der ganzzahligen Optimierung. Neben der Skizzierung numerischer Aspekte und der Diskussion von Implementationsfragen wird besonderer Wert auf eine geometrische Begründung der Verfahren der linearen und ganzzahligen Optimierung gelegt. Vorlesungsthemen sind u.a.:
Fourier-Motzkin-Elimination, das Farkas-Lemma und Dualitätssätze, Optimalitätskriterien, Polyedertheorie, der Simplex-Algorithmus (primal, dual, revidiert), Innere-Punkte-Methoden, die Ellipsoid-Methode, Primal-Dual-Verfahren, Schnittebenenverfahren der ganzzahligen Optimierung.

Voraussetzungen:

Lineare Algebra, Grundzüge der Analysis, Graphen- und Netzwerkalgorithmen.

Geplante Fortsetzung:

Diese Vorlesung ist der zweite Teil des Studienschwerpunktes ``Algorithmische Diskrete Mathematik'' in den Studiengängen Mathematik, Techno- und Wirtschaftsmathematik. Im Sommersemester 2004 wird diese Vorlesungsserie mit einer Spezialvorlesung zur Gemischt-Ganzzahligen Optimierung fortgesetzt.

Im Sommersemester 2004 wird außerdem ein Seminar über Graphenfärbung angeboten.

Literatur

V. Chvátal, ``Linear Programming'', Freeman, New York, 1983.
G.B. Dantzig, ``Linear Programming and Extentions'', Princeton University Press, Princeton, 1963.
M. Padberg, ``Linear Optimization and Extensions'', Springer-Verlag, Berlin, 1995.
A. Schrijver, ``Theory of Linear and Integer Programming'', Wiley, Chichester, 1986.
R.J. Vanderbei, ``Linear Programming: Foundations and Extentions'', Kluwer Academic Publishers, Dordrecht, 1998.

Vorlesungsskriptum   (Version vom 13. Januar 2004, Kapitel 1 - 13, ps-File, pdf-File)

Kontakte

   
Sprechstunde
 Raum Telefon email
Dozent: Prof. Dr. Martin Grötschel n.V. MA 302 84185-210 groetschelzib.de
Assistent: Dr. Frank Lutz Do   10:00 - 11:30 MA 624 314-25 751 lutzmath.tu-berlin.de
Tutor: Raman Sanyal Di   10:00 - 11:30 MA 843 sanyalmath.tu-berlin.de
Sekretariat (TU): Elke Pose Mo - Do   9:30 - 11:30 MA 627 314-23 354 posemath.tu-berlin.de
Sekretariat (ZIB): Bettina Kasse n.V. 3025 84185-209 kassezib.de

Zeiten

Vorlesung: Di 16 - 18 MA 042 Prof. Dr. Martin Grötschel
Mi 14 - 16 MA 042
Übung: Di 12 - 14 MA 042 Dr. Frank Lutz
Tutorien: Do 10:15 - 11:45 MA 750 Raman Sanyal
Do 14:15 - 15:45 MA 750

Übungsblätter:

Standardformate .ieq für Porta und .lp für CPLEX

Testbeispiele zur Fourier-Motzkin-Elimination

Scheinkriterien

50% der Punkte aus den Übungsblättern 1 bis 7 und 50% der Punkte aus den Übungsblättern 8 bis 14 sowie die erfolgreiche Bearbeitung aller Programmieraufgaben.

Programmieraufgaben

Im Laufe des Semesters wird es mehrere Programmieraufgaben geben, bei denen Algorithmen in Java oder in C/C++ zu implementieren und an vorgegebenen Beispielen zu testen sind. Programmieraufgaben werden nicht korrigiert, sondern bei einer Programmvorführung abgenommen.

Verfügbare Software

Modellierungsaufgabe mit ZIMPL

Kaffeebeispiel

Raffineriebeispiel

Die Parameterdateien bestehen aus der lesbaren Form (mit Endung ".dat") und der Datei, die eingelesen wird (mit Endung ".par"):

Farm-Aufgabe

Siehe 3. Programmieraufgabe auf dem 8. Übungsblatt. Die Optimallösung ist: 2 Hektar jeweils für Baumwolle, Zwiebeln und Tomaten;
Optimalwert: 1898.52.

Valid HTML 4.0! Zuletzt aktualisiert: 9. Februar 2004