contents
. . . . | Lineare Optimierung |
|
|
Lineare Optimierung - WS 1999/2000
Prof. Dr. Rolf H. Möhring
Ekkehard Köhler
Termine
Sprechzeiten
Rechnervorrangzeiten
Tag | Zeit |
Dienstag | 9:00-14:00 Uhr |
Freitag | 14:00-18:00 Uhr |
Zu diesen Zeiten wird Teilnehmern der Lehrveranstaltung ein Rechnerplatz
garantiert.
Literatur
Als Lektüre zur Vertiefung und Erweiterung des Vorlesungsstoffes verweisen
wir auf folgende Bücher:
- V. Chvátal:
"Linear Programming",
W.H. Freeman and Company, New York, 1980
- Christos H. Papadimitriou, Kenneth Steiglitz:
"Combinatorial Optimization: Algorithms and Complexity",
Prentice Hall, Englewood Cliffs, NJ, 1982
- Robert J. Vanderbei:
"Linear Programming: Foundations and Extensions"',
International Series in Operations Research and Management Science,
Kluwer Academic Publ., 1998
Darüber hinaus empfehlen wir jedem Teilnehmer der Vorlesung,
weitere Literatur per Datenbankrecherche zu suchen. Eine komfortable
Möglichkeit dazu bietet die MATH Database in Karlsruhe,
die über WWW verfügbar ist. Eine Liste anderer
interessanter Links zum Thema kann man hier
finden.
Übungsblätter
Im Laufe des Semesters wird jede Woche an dieser Stelle ein
Übungsblatt zur Verfügung gestellt. Insgesamt werden
voraussichtlich 14 Übungsblätter zu bearbeiten sein. Die
Bearbeitungszeit beträgt eine Woche. Die Abgabe erfolgt eine
Woche nach der Ausgabe vor der Übung.
Hier sind die LaTeX-Files der Übungsblätter:
- 1. Übungsblatt (LaTeX, dvi, postscript)
- 2. Übungsblatt (LaTeX, dvi, postscript)
- 3. Übungsblatt (LaTeX, dvi, postscript, Abbildung als eps Datei)
- 4. Übungsblatt (LaTeX, dvi, postscript)
- 5. Übungsblatt (LaTeX, dvi, postscript)
- 6. Übungsblatt (LaTeX, dvi, postscript)
- 7. Übungsblatt (LaTeX, dvi, postscript)
- 8. Übungsblatt (LaTeX, dvi, postscript)
- 9. Übungsblatt (LaTeX, dvi, postscript)
- 10. Übungsblatt (LaTeX, dvi, postscript)
- 11. Übungsblatt (LaTeX, dvi, postscript)
- 12. Übungsblatt (LaTeX, dvi, postscript)
- 13. Übungsblatt (LaTeX, dvi, postscript)
- 14. Übungsblatt (LaTeX, dvi, postscript)
Hinweise zur Behandlung der LaTeX-Files.
Programmieraufgaben
Einige der Übungsaufgaben werden
Programmieraufgaben sein, bei denen verschiedene Algorithmen zu
implementieren und an Beispielen zu testen sind. Zur Bearbeitung
empfehlen wir die Programmiersprachen C bzw. C++.
Programmieraufgaben werden nicht korrigiert, sondern bei einer
Programmvorführung abgenommen.
Nähere Informationen zur Verwendung von LEDA sind im LEDA Online-Manual zu finden.
Nähere Informationen zur Verwendung von Funktionen von CPLEX sind
im CPLEX Manual zu finden. Eine Postscriptversion des Manuals ist im
Unixpool zu finden unter:
/usr/local/cplex/DOC/cplexdoc4.ps.
Optimierungssoftware
Einige Übungsaufgaben erfordern die Benutzung von CPLEX,
einem kommerziellen Programm u.A. zur Lösung von linearen
Programmen. Hinweise zur Arbeit mit CPLEX sind hier zu finden.
Die Eingabe komplexerer LPs in CPLEX ist nichts sehr
komfortabel. Um die Arbeit hier zu erleichtern, gibt es verschiedene
Modellierungssprachen, die es erlauben, LPs sehr einfach zu
formulieren und z.B. Parameter dieser LPs in separaten Files zu
verwalten. Eine solche Modellierungssprache ist AMPL. Leider
existiert im Moment im Unix-Pool keine Lizenz für dieses
Programm, aber man kann es leicht auf dieser Seite ausprobieren.
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. Außerdem wird die aktive Mitarbeit in der
Übung vorausgesetzt.
|