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

Vorlesung Optimierung I und II

WS 1998/99 und SS 1999

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

I

4.6 Quadratische Optimierung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40 4.7 Das Verfahren von Wolfe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42 4.8 Ein Verfahren zul"assiger Richtungen . . . . . . . . . . . . . . . . . . . . . . . . . 47 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

6 Kombinatorische Optimierung 66

6.1 Begriffe aus der Graphentheorie . . . . . . . . . . . . . . . . . . . . . . . . . . . 66 6.2 Das Problem des k"urzesten Wegs . . . . . . . . . . . . . . . . . . . . . . . . . . 68 6.3 Minimal spannende B"aume . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74 6.4 Maximale Fl"usse und der Algorithmus von Ford-Fulkerson . . . . . . . . . . . . 79 6.5 Kostenminimale Fl"usse . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86 6.6 Branch and Bound Verfahren f"ur TSP . . . . . . . . . . . . . . . . . . . . . . . 88 6.7 Heuristiken und lokale Suche . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92 6.8 Ein approximierender Algorithmus . . . . . . . . . . . . . . . . . . . . . . . . . 96 6.9 Dynamische Programmierung . . . . . . . . . . . . . . . . . . . . . . . . . . . . 98

7 Spieltheorie 102

7.1 Allgemeines und Historie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102 7.2 Grundlegende Begriffe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102 7.3 Endliche Matrixspiele . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 104 7.4 Existenz von Gleichgewichtspunkten . . . . . . . . . . . . . . . . . . . . . . . . 110 7.5 Bimatrixspiele . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 116 7.6 Spiele "uber dem Einheitsquadrat . . . . . . . . . . . . . . . . . . . . . . . . . . 119 7.7 Das Oligopolspiel . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 129