|
Lineare Optimierung |
|
| |
Wintersemester 2000/2001 |
|
LV-Nr.: 0350 L 226
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 2001 wird diese Vorlesungsserie mit einer
Spezialvorlesung zur ganzzahligen Optimierung
fortgesetzt.
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.
Kontakte
Zeiten
Programmieraufgaben
Im Laufe des Semesters wird es mehrere Programmieraufgaben
geben, bei denen Algorithmen in C/C++ zu implementieren und an vorgegebenen Beispielen zu testen
sind. Programmieraufgaben werden nicht korrigiert, sondern bei einer
Programmvorführung abgenommen. Die Vorführungen finden im Unix-Pool MA 241 auf den
IBM-Rechnern statt, Termine werden in den Übungen vereinbart.
CPLEX
Dokumentation zur aktuellen CPLEX-Version 7.0
PORTA Manual
Rechnervorrangzeiten
(Unix-Pool MA 241)
| Tag | Zeit |
|---|
| Montag | 14-18 Uhr |
| Mittwoch | 9-12 Uhr |
| Freitag | 12-18 Uhr |
Zu diesen Zeiten sind für Teilnehmerinnen und Teilnehmer der Lehrveranstaltung jeweils
15 Rechnerplätze reserviert.
Übungsblätter:
- 01. Übungsblatt vom 20.10.00 (ps, pdf)
- 02. Übungsblatt vom 27.10.00 (ps, pdf)
- 03. Übungsblatt vom 03.11.00 (ps, pdf)
- 04. Übungsblatt vom 10.11.00 (ps, pdf)
- 05. Übungsblatt vom 17.11.00 (ps, pdf)
- 06. Übungsblatt vom 24.11.00 (ps, pdf)
- 07. Übungsblatt vom 01.12.00 (ps, pdf)
- 08. Übungsblatt vom 08.12.00 (ps, pdf)
- 09. Übungsblatt vom 15.12.00 (ps, pdf)
- 10. Übungsblatt vom 22.12.00 (ps, pdf)
- 11. Übungsblatt vom 12.01.01 (ps, pdf)
- 12. Übungsblatt vom 19.01.01 (ps, pdf)
- 13. Übungsblatt vom 26.01.01 (ps, pdf)
- 14. Übungsblatt vom 02.02.01 (ps, pdf)
Testbeispiele zur Fourier-Motzkin-Elimination
Beispiele affiner Abbildungen
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.
| Zuletzt aktualisiert: 1. Februar 2001 |