|
ADM II: Lineare Optimierung |
|
| |
Wintersemester 2001/2002 |
|
LV-Nr.: 0230 L 226
Diese Vorlesung hat im Wintersemester 2001/2002 stattgefunden.
| Dozent: |
Prof. Günter M. Ziegler |
| Assistent: |
Marc Pfetsch |
Inhalt
Algorithmen der linearen Optimierung (Simplex Verfahren, innere
Punkte Methoden), Polyedertheorie, Dualitätstheorie, primal-duale
Algorithmen mit Anwendungen bei Graphen und Netzwerken, ganzzahlige
lineare Optimierung.
Die Vorlesung wird durch ADM III: Kombinatorische Optimierung im
Sommersemester 2002 fortgesetzt.
Voraussetzungen:
Lineare Algebra, Programmiersprache.
Literatur
-
V. Chvátal
"Linear Programming"
Freeman, New York, 1983
Der Beweis des Dualitätssatzes, wie in der Vorlesung ausgeteilt
[ps.gz,
PDF].
Übungsblätter
- 1. Übungsblatt [
ps.gz,
TeX,
PDF
] (Abgabe: 25.10.01).
- 2. Übungsblatt [
ps.gz,
TeX,
PDF
] (Abgabe: 1.11.01).
- 3. Übungsblatt [
ps.gz,
TeX,
PDF
] (Abgabe: 8.11.01).
- 4. Übungsblatt [
ps.gz,
TeX,
PDF
] (Abgabe: 15.11.01).
- 5. Übungsblatt [
ps.gz,
TeX,
PDF
] (Abgabe: 22.11.01).
- 6. Übungsblatt [
ps.gz,
TeX,
PDF
] (Abgabe: 29.11.01).
- 7. Übungsblatt [
ps.gz,
TeX,
PDF
] (Abgabe: 6.12.01).
- 8. Übungsblatt [
ps.gz,
TeX,
PDF
] (Abgabe: 13.12.01).
- 9. Übungsblatt [
ps.gz,
TeX,
PDF
] (Abgabe: 20.12.01).
- 10. Übungsblatt [
ps.gz,
TeX,
PDF
] (Abgabe: 17.1.02).
- 11. Übungsblatt [
ps.gz,
TeX,
PDF
] (Abgabe: 24.1.02).
- 12. Übungsblatt [
ps.gz,
TeX,
PDF
] (Abgabe: 31.1.02).
- 13. Übungsblatt [
ps.gz,
TeX,
PDF
] (Abgabe: 7.2.02).
Lösungen
Test
Pivotisierungs-Applet
Es gibt ein Simplex-Algorithmus-Applet
(auf den Seiten von Robert
Vanderbei) welche den Simplex-Algorithmus im Tableau ablaufen
läßt. Damit kann man die Lösung von Aufgabe 7 selber
überprüfen.
Sonstiges
Ein frei erhältlicher Modellgenerator für Lineare Programme
ist ZIMPL von Thorsten
Koch.
Es gibt eine kurze ZIMPL
Dokumentation.
Es folgen einige Beispiele, die auch im Unix-Pool unter "/net/linopt/Modelle" liegen.
Kaffeebeispiel
- Das Kaffeebeispiel
aus der Vorlesung im ZIMPL-Format.
- ZIMPL erzeugt daraus ein
Lineares Programm,
welches im sogenannten "LP"-Format abgespeichert wird.
- Die Variablennamen müssen dabei leider gekürzt
werden. Die Übersetzung findet man in einer Übersetzungstabelle.
Raffineriebeispiel
Die Parameterdateien bestehen aus der lesbaren Form (mit Endung
".dat") und der Datei die Eingelesen wird (mit Endung
".par").
Farm-Aufgabe
Siehe Programmieraufgabe Nr. 1 auf dem 3. Übungsblatt.
Die Optimallösung ist:
2 Hektar jeweils für Baumwolle, Zwiebeln und Tomaten.
Optimalwert: 1898.52
CPLEX
Testprobleme für den Simplex-Algorithmus
Die folgenden Probleme sind einige der kleineren aus der Netlib Sammlung.
Die Daten sind die folgenden:
| Name | Zeilen | Spalten | Nichtnull | Bytes | Bounds? | Optimalwert |
| afiro | 28 | 32 | 88 | 794 | Nein | -4.6475314286E+02 |
| fit1d | 25 | 1026 | 14430 | 51734 | Ja | -9.1463780924E+03 |
| fit2d | 26 | 10500 | 138018 | 482330 | Ja | -6.8464293294E+04 |
| kb2 | 44 | 41 | 291 | 2526 | Ja | -1.7499001299E+03 |
| sc50a | 51 | 48 | 131 | 1615 | Nein | -6.4575077059E+01 |
| sc50b | 51 | 48 | 119 | 1567 | Nein | -7.0000000000E+01 |
TU Berlin |
Institut für Mathematik |
AG Diskrete Geometrie |
FTP
| Marc Pfetsch |
zuletzt aktualisiert: 6.3.2002 |