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

Optimierung I Theorie und Praxis der linearen Optimierung

Prof. Dr. J. Zowe Wintersemester 1990/91

Erstellt von Helmut Hahn auf einen Atari Mega/STE

Grafiken von Andreas Gassner und Helmut Hahn

Inhalt:

1. Einleitung und Beispiele . . . . . . . . . . . . . . . . . . . . . . . . . 1 2. Graphische Darstellung und L"osung von LP's . . . . . . . . . . . . . . . . 6 3. Hauptsatz der linearen Optimierung . . . . . . . . . . . . . . . . . . . . 10 4. Das Simplexverfahren . . . . . . . . . . . . . . . . . . . . . . . . . . 14 5. Bestimmung einer zul"assigen Ausgangsl"osung . . . . . . . . . . . . . . . . 25 6. Kreisen des Simplexverfahrens, Lexikographisches Simplexverfahren . . . . . . 32 7. Absch"atzung der Iterationsschritte beim Simplexverfahren . . . . . . . . . . 38 8. Das Simplexverfahren beim Vorliegen von Gleichungen und freien Variablen . . 42 9. Das revidierte Simplexverfahren (revised simplex) . . . . . . . . . . . . . . 48 10. Das Simplexverfahren mit LU-Zerlegung, Stabilisiertes Simplexverfahren . . . . 52 11. Duale lineare Programme . . . . . . . . . . . . . . . . . . . . . . . . . 55 12. Beweis des Dualit"atssatzes . . . . . . . . . . . . . . . . . . . . . . . . 61 13. Das duale Simplexverfahren . . . . . . . . . . . . . . . . . . . . . . . 65 14. Ganzzahlige lineare Programme (ILP) . . . . . . . . . . . . . . . . . . . 70 15. Das Transportproblem . . . . . . . . . . . . . . . . . . . . . . . . . . 78 16. Das Zuordnungsproblem (assignment problem) . . . . . . . . . . . . . . . 85 17. Das Traveling-Salesman-Problem, Das Branch and Bound Prinzip . . . . . . . 90

1. Einleitung und Beispiele Die Anf"ange der (linearen) Optimierung begr"undete Kantorovicz 1939 mit seinen "Mathematicals Methods in the organisation and planing of production". Von Dantzig wurde 1951 das Simplexverfahren entwickelt, welches bis heute den Standardalgorithmus zur L"osung linearer Optimierungsaufgaben darstellt. Mit Computern ist es m"oglich, Gleichungssysteme Ax = b, wobei A eine (n \Theta n)-Matrix ist, mit einem Zeitaufwand O( 1=3n3) zu l"osen, was f"ur die Optimierung von grosser Bedeutung ist.

(Nichtlineare) Optimierung Die typische Problemstellung in der nichtlinearen Optimierung lautet

min f (x) N:B: x 2 X;

wobei X durch implizite und explizite Restriktionen definiert wird. Abbildung 1.1 veranschaulicht ein einfaches Problem von diesem Typ mit einer expliziten Restriktion, g(x) ^ 0.

Abb. 1.1

- IRn

6

rmin f(x) rmin f(x) unter N.B. g(x) ^ 0 g-z ""

f x j g(x) ^ 0 g

Probleme dieser Art sollen allerdings im zweiten Teil dieser Vorlesung behandelt werden. Lineare Optimierung Wir betrachten im ersten Teil der Vorlesung zun"achst den Fall, dass die Zielfunktion und alle Nebenbedingungen linear in x sind.

Beispiele f"ur lineare Probleme

Um ein besseres Verst"andnis f"ur Optimierungsprobleme zu schaffen, betrachten wir zun"achst einige Beispiele.

ffl Produktionsmodelle