Mathematische Optimierungsverfahren des Operations Research (De Gruyter Studium)

Vorwort......Page 6
Inhaltsverzeichnis......Page 8
1 Einleitung......Page 11
1.1 Problemtypen......Page 14
1.2 Grundbegriffe und typische Fragestellungen......Page 25
1.3 Aufgaben......Page 28
2 Lineare Optimierung......Page 34
2.1 Problemstellung......Page 35
2.2 Geometrie linearer Optimierungsprobleme......Page 38
2.3 Primales Simplexverfahren......Page 58
2.4 Vermeidung von Zyklen......Page 72
2.5 Revidiertes primales Simplexverfahren......Page 84
2.6 Dualität und Sensitivität......Page 93
2.7 Duales Simplexverfahren......Page 112
2.8 Matrixspiele und lineare Optimierung......Page 122
2.9 Aufgaben......Page 130
3 Ganzzahlige Optimierung......Page 145
3.1 Beispiele für ganzzahlige Optimierungsprobleme......Page 146
3.2 Total unimodulare Matrizen......Page 150
3.3 Schnittebenenverfahren von Gomory......Page 152
3.4 Branch and Bound-Methoden......Page 173
3.4.1 Branch and Bound für (ILP)......Page 176
3.4.2 Branch and Bound im Allgemeinen......Page 180
3.5 Travelling Salesman-Problem......Page 190
3.6 Aufgaben......Page 199
4.1 Graphentheoretische Grundbegriffe......Page 204
4.2 Netzwerksimplexverfahren......Page 209
4.3 Maximale Flüsse in Netzwerken......Page 228
4.4 KürzesteWege......Page 244
4.4.1 Ein primaldualer Algorithmus......Page 246
4.4.2 DijkstrasAlgorithmus......Page 251
4.4.3 Algorithmus vonFloyd-Warshall......Page 262
4.5 Aufgaben......Page 267
5 Konvexe Optimierung......Page 278
5.1 Problemstellung......Page 279
5.2 Trennungssätze......Page 282
5.3 Optimalitätsbedingungen......Page 285
5.4 Dualität und Sensitivität......Page 302
5.5 Sattelpunkte und Komplementarität......Page 311
5.6 Schnittebenenverfahren......Page 320
5.7 Aufgaben......Page 328
6 Differenzierbare Optimierung......Page 334
6.1 Analytische Hilfsmittel......Page 336
6.2 Existenz von Optimallösungen......Page 347
6.3 Notwendige Optimalitätsbedingungen......Page 352
6.4 Optimalitätsbedingungen zweiter Ordnung......Page 368
6.5 Sensitivität......Page 376
6.6 Aufgaben......Page 382
7 Verfahren der nichtlinearen Optimierung......Page 387
7.1 Reduktionsmethoden......Page 389
7.2 Methode der zulässigen Richtungen......Page 390
7.3 Projektionsverfahren......Page 400
7.4 Lagrange-Newton-Verfahren......Page 403
7.5.1 Lokale Konvergenz der SQP-Methode......Page 405
7.5.2 Globalisierung der SQP-Methode......Page 409
7.5.3 Quadratische Optimierung......Page 420
7.6 Penalty-Methoden......Page 427
7.6.1 Äußere Penalty-Methoden......Page 428
7.6.2 Innere Penalty-Methoden......Page 432
7.6.3 Exakte Penalty-Methoden und Dualität......Page 437
7.7.1 Zentraler Pfad für lineare Optimierungsprobleme......Page 439
7.7.2 Pfadverfolgungsalgorithmen......Page 443
7.7.3 Ausblick auf nichtlineare Optimierungsprobleme......Page 448
7.8.1 LagrangeschesPrinzip......Page 452
7.8.2 Erweiterbarkeit......Page 453
7.8.3 Konvergenz der Multiplier-Penalty-Methode......Page 455
7.8.4 Behandlung von Ungleichungsnebenbedingungen......Page 457
7.9 Aufgaben......Page 458
8 Diskrete dynamische Optimierung......Page 465
8.1 Problemstellung und Anwendungen......Page 468
8.1.1 Diskretisierte Optimalsteuerungsprobleme......Page 469
8.1.2 Lagerhaltung......Page 472
8.1.3 Rucksackpackproblem......Page 473
8.1.4 Zuordnungsprobleme......Page 474
8.2 Das Optimalitätsprinzip von Bellman......Page 475
8.3 Methode der dynamischen Programmierung......Page 477
8.4 Diskretes Maximumprinzip......Page 480
8.5 Kontinuierliches Maximumprinzip......Page 486
8.6 Aufgaben......Page 489
9.1 Modellierung evolutionärer Algorithmen......Page 500
9.2 Konvergenzanalyse evolutionärerAlgorithmen......Page 504
9.3 Numerische Simulation evolutionärer Algorithmen......Page 515
Literaturverzeichnis......Page 523
Index......Page 533