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

Skript zur Vorlesung

Optimierung

Sommersemester 1996

Prof. Seidel

Inhaltsverzeichnis 1 Lineares Programmieren 1

1.1 Geometrische Grundlagen der Linearen Programmierung . . . . . . . . . . . . . . . . . . . . . . . 1

1.1.1 Niedrigste-Punkte-Problem (NPP) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1.1.2 Problem der H"ochsten V-Kombination . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 1.2 Algebraische Grundlagen der Linearen Programmierung . . . . . . . . . . . . . . . . . . . . . . . 3

1.2.1 Das primale Problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 1.2.2 Das duale Problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 1.2.3 Bezug zur geometrischen Interpretation (d = 2) . . . . . . . . . . . . . . . . . . . . . . . . 7 1.2.4 Starke Dualit"at . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 1.2.5 Der Simplex-Algorithmus . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 1.2.6 Die Perturbationsmethode . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 1.2.7 Der Zwei-Phasen Simplex-Algorithmus . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 1.2.8 Geometrische Interpretation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 1.2.9 Algebraischer Simplexalgorithmus . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 1.2.10 Wie schnell ist der Simplex-Algorithmus . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 1.3 Der Duale Simplex-Algorithmus . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 1.4 Sensitivit"atsanalyse . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31

1.4.1 "Anderung der Zielfunktion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32 1.4.2 "Anderung des Begrenzungsvektors . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32 1.4.3 Hinzunahme einer Nebenbedingung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33 1.5 Ellipsoidmethode . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34

1.5.1 Komplexit"at der Linearen Programmierung . . . . . . . . . . . . . . . . . . . . . . . . . . 34 1.5.2 Ellipsoid-Methode . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36 1.5.3 Der Ellipsoid-Algorithmus . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43 1.5.4 Aufwand pro Iteration . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50 1.6 Karmarkars "Projektiver Skalierungsalgorithmus" . . . . . . . . . . . . . . . . . . . . . . . . . . . 52 1.7 Das Revidierte Simplex Verfahren . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57

1.7.1 Simplexschritt via W"orterbuch . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57 1.7.2 Revidierter Simplexschritt . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58 1.8 Netz-Simplex (Network Simplex) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59

1.8.1 Das Transportproblem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59 1.8.2 Netzwerk-Simplexschritt . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62 1.8.3 Wie bekommt man eine Anfangsl"osung? . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67 1.8.4 Matchings und Coverings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70 1.8.5 Bipartite Graphen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70 1.8.6 Optimale Zuweisungsprobleme . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73 1.9 Ganzzahlige und gemischte lineare Programme . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76

1.9.1 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76 1.9.2 Das Travelling Salesman Problem - L"osungsans"atze . . . . . . . . . . . . . . . . . . 77 1.9.3 Approximative L"osungsans"atze . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78 1.10 Matching-Probleme in allgemeinen Graphen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83 1.11 Der Bl"uten-Schrumpf Algorithmus . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85i

ii INHALTSVERZEICHNIS 2 Approximationsalgorithmen 88

2.1 Planungsprobleme . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 88

2.1.1 PCS - Precedence Constrained Scheduling . . . . . . . . . . . . . . . . . . . . . . . . . . . 88 2.1.2 SIT - Scheduling of Independent Tasks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 90 2.2 Das Gewichtete Rucksackproblem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 95

2.2.1 Das Rucksackproblem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 95 2.2.2 Das gewichtete Rucksackproblem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 96 2.2.3 FPTAS f"ur gewichtetes Rucksackproblem . . . . . . . . . . . . . . . . . . . . . . . . . . . 96

3 Branch and Bound 98

3.1 Der Algorithmus . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 98