Mathematische Optimierungsverfahren des Operations Research (eBook)

lt;!doctype html public "-//w3c//dtd html 4.0 transitional//en">

Matthias Gerdts, Universität der Bundeswehr München, Germany; Frank Lempio, University of Bayreuth, Germany.

Matthias Gerdts, Universität der Bundeswehr München; Frank Lempio, Universität Bayreuth.

Vorwort 6
Inhaltsverzeichnis 8
1 Einleitung 12
1.1 Problemtypen 15
1.2 Grundbegriffe und typische Fragestellungen 26
1.3 Aufgaben 29
2 Lineare Optimierung 35
2.1 Problemstellung 36
2.2 Geometrie linearer Optimierungsprobleme 39
2.3 Primales Simplexverfahren 59
2.4 Vermeidung von Zyklen 73
2.5 Revidiertes primales Simplexverfahren 85
2.6 Dualität und Sensitivität 94
2.7 Duales Simplexverfahren 113
2.8 Matrixspiele und lineare Optimierung 123
2.9 Aufgaben 131
3 Ganzzahlige Optimierung 146
3.1 Beispiele für ganzzahlige Optimierungsprobleme 147
3.2 Total unimodulare Matrizen 151
3.3 Schnittebenenverfahren von Gomory 153
3.4 Branch and Bound-Methoden 174
3.4.1 Branch and Bound für (ILP) 177
3.4.2 Branch and Bound im Allgemeinen 181
3.5 Travelling Salesman-Problem 191
3.6 Aufgaben 200
4 Netzwerkflussprobleme 205
4.1 Graphentheoretische Grundbegriffe 205
4.2 Netzwerksimplexverfahren 210
4.3 Maximale Flüsse in Netzwerken 229
4.4 KürzesteWege 245
4.4.1 Ein primaldualer Algorithmus 247
4.4.2 DijkstrasAlgorithmus 252
4.4.3 Algorithmus vonFloyd-Warshall 263
4.5 Aufgaben 268
5 Konvexe Optimierung 279
5.1 Problemstellung 280
5.2 Trennungssätze 283
5.3 Optimalitätsbedingungen 286
5.4 Dualität und Sensitivität 303
5.5 Sattelpunkte und Komplementarität 312
5.6 Schnittebenenverfahren 321
5.7 Aufgaben 329
6 Differenzierbare Optimierung 335
6.1 Analytische Hilfsmittel 337
6.2 Existenz von Optimallösungen 348
6.3 Notwendige Optimalitätsbedingungen 353
6.4 Optimalitätsbedingungen zweiter Ordnung 369
6.5 Sensitivität 377
6.6 Aufgaben 383
7 Verfahren der nichtlinearen Optimierung 388
7.1 Reduktionsmethoden 390
7.2 Methode der zulässigen Richtungen 391
7.3 Projektionsverfahren 401
7.4 Lagrange-Newton-Verfahren 404
7.5 Sequentielle Quadratische Programmierung 406
7.5.1 Lokale Konvergenz der SQP-Methode 406
7.5.2 Globalisierung der SQP-Methode 410
7.5.3 Quadratische Optimierung 421
7.6 Penalty-Methoden 428
7.6.1 Äußere Penalty-Methoden 429
7.6.2 Innere Penalty-Methoden 433
7.6.3 Exakte Penalty-Methoden und Dualität 438
7.7 Innere-Punkte-Verfahren 440
7.7.1 Zentraler Pfad für lineare Optimierungsprobleme 440
7.7.2 Pfadverfolgungsalgorithmen 444
7.7.3 Ausblick auf nichtlineare Optimierungsprobleme 449
7.8 Multiplier-Penalty-Methoden 453
7.8.1 LagrangeschesPrinzip 453
7.8.2 Erweiterbarkeit 454
7.8.3 Konvergenz der Multiplier-Penalty-Methode 456
7.8.4 Behandlung von Ungleichungsnebenbedingungen 458
7.9 Aufgaben 459
8 Diskrete dynamische Optimierung 466
8.1 Problemstellung und Anwendungen 469
8.1.1 Diskretisierte Optimalsteuerungsprobleme 470
8.1.2 Lagerhaltung 473
8.1.3 Rucksackpackproblem 474
8.1.4 Zuordnungsprobleme 475
8.2 Das Optimalitätsprinzip von Bellman 476
8.3 Methode der dynamischen Programmierung 478
8.4 Diskretes Maximumprinzip 481
8.5 Kontinuierliches Maximumprinzip 487
8.6 Aufgaben 490
9 Evolutionäre Algorithmen 501
9.1 Modellierung evolutionärer Algorithmen 501
9.2 Konvergenzanalyse evolutionärerAlgorithmen 505
9.3 Numerische Simulation evolutionärer Algorithmen 516
Literaturverzeichnis 524
Index 534

lt;P>„Das Buch spart nicht mit guten Abbildungen und detaillierten Beispielen sowie sinnvollen Aufgaben."
Prof. Dr. Karl Hubert, Technische Hochschule Nürnberg