"Optimierung I 002.ps.gz" - читать интересную книгу автора

Vorlesung Optimierung I WS 1998/99 Inhaltsverzeichnis 1 Einf"uhrung 1

1.1 Allgemeines und Historie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1.2 Problemstellung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1.3 Anwendungsbeispiele . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2

1.3.1 Ein Produktionsproblem . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 1.3.2 Ein F"utterungsproblem . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 1.3.3 Ein Transportproblem . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4

2 Lineare Optimierung 6

2.1 Der Fundamentalsatz "uber lineare Ungleichungen . . . . . . . . . . . . . . . . . 6 2.2 Konvexe Kegel . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 2.3 Das Lemma von Farkas und der Dualit"atsssatz . . . . . . . . . . . . . . . . . . . 8 2.4 Der Simplexalgorithmus . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 2.5 Das Simplextableau . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 2.6 Der revidierte Simplexalgorithmus . . . . . . . . . . . . . . . . . . . . . . . . . . 19 2.7 Pivotwahl und Antizykelalgorithmen . . . . . . . . . . . . . . . . . . . . . . . . 20 2.8 Der duale Simplexalgorithmus . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22

3 Ganzzahlige lineare Optimierung 24

3.1 Einf"uhrung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24 3.2 Ein Schnittebenenverfahren von Gomory . . . . . . . . . . . . . . . . . . . . . . 26

4 Konvexe Optimierung 31

4.1 Einleitung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 4.2 Konvexe Funktionen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 4.3 Trennungss"atze . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34 4.4 Der Sattelpunktsatz von Kuhn-Tucker . . . . . . . . . . . . . . . . . . . . . . . 35 4.5 Lokale Kuhn-Tucker-Bedingungen . . . . . . . . . . . . . . . . . . . . . . . . . 37 4.6 Quadratische Optimierung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40 4.7 Das Verfahren von Wolfe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42 4.8 Ein Verfahren zul"assiger Richtungen . . . . . . . . . . . . . . . . . . . . . . . . . 47

I

4.9 Ein Schnittebenenverfahren . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50 4.10 Ganzzahlige konvexe Optimierung . . . . . . . . . . . . . . . . . . . . . . . . . . 52

5 Komplexit"at und das Ellipsoid-Verfahren 54

5.1 Zeitschranken . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54 5.2 Der Simplexalgorithmus ist nicht polynomial . . . . . . . . . . . . . . . . . . . . 55 5.3 Komplexit"at von LP, LI und LSI . . . . . . . . . . . . . . . . . . . . . . . . . . 57 5.4 Ellipsoide . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59 5.5 Das Ellipsoidverfahren . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63

II Literatur

[1] Burkhard, R.E.: Methoden der ganzzahligen Optimierung, Springer, Wien-New York

1972.

[2] Collatz, L., Wetterling, W.: Optimierungsaufgaben, Springer, Berlin-New York 1971. [3] Dantzig, G.B.: Lineare Programmierung und Erweiterungen, Springer, Berlin-New York

1966.

[4] Gaede, K.W., Heinhold,J.: Grundz"uge des Operations Research, Carl-Hanser-Verlag,