ISBN: 3790800430
TITLE: Optimierungsmethoden
AUTHOR: Kistner
TOC:

1 Einleitung 1
1.1 Entscheidungsmodelle 1
1.2 Typen von Optimierungsmodellen 4
1.2.1 Stetige Optimierungsmodelle 4
1.2.2 Diskrete Optimierungsmodelle 6
1.2.3 Dynamische Optimierungsmodelle 7
1.3 Ausgewhlte Lehrbcher 8
2 Grundlagen der linearen Programmierung 11
2.1 Formulierung des Problems 11
2.2 Das Simplex-Verfahren 14
2.2.1 Graphische Veranschaulichung 14
2.2.2 Das Simplex-Verfahren bei einem speziellen Maximum-Problem 16
2.2.3 Bestimmung einer zulssigen Ausgangslsung 23
2.2.4 Sonderflle beim Simplex-Verfahren 25
2.3 Die Theorie des Simplex-Verfahrens 29
2.3.1 Das Eckentheorem 29
2.3.2 Das Simplex-Kriterium 37
2.3.3 Formaler Aufbau des Simplex-Tableaus 38
2.4 Dualittstheorie 41
2.4.1 Dualitt im speziellen Maximum-Problem 41
2.4.1.1 Formulierung des Problems 41
2.4.1.2 Dualittsstze 42
2.4.1.3 Complementary Slackness und Preistheorem 45
2.4.2 Dualitt im allgemeinen Fall 48
2.4.3 Beispiel 52
2.4.4 Die duale Simplex-Methode 53
3 Erweiterungen der linearen Programmierung 57
* 3.1 Postoptimale Analysen 57
3.1.1 Sensitivittsanalyse 58
3.1.1.1 Vernderung der Beschrnkungskonstanten 58
3.1.1.2 Vernderung der Zielfunktionskoeffizienten 62
3.1.1.3 Koeffizienten der Beschrnkungsmatrix 65
3.1.2 Zustzliche Variablen und Restriktionen 65
3.1.2.1 Zustzliche Variablen 65
3.1.2.2 Zustzliche Restriktionen 68
3.1.3 Parametrische Programmierung 70
3.1.3.1 Problemstellung 70
3.1.3.2 Allgemeine Eigenschaften 70
3.1.3.3 Ermittlung der kritischen Punkte bei Variation des Beschrnkungsvektors 73
* 3.2 Das Dekompositionsprinzip 79
3.2.1 Problemstellung 79
3.2.2 Der Dekompositions-Algorithmus 83
3.2.3 Theorie des Dekompositions-Algorithmus 94
* 3.3 Modifikationen des Simplex-Verfahrens 99
3.3.1 Die revidierte Simplex-Methode 99
3.3.2 Beschrnkte Variablen 101
3.3.3 Pivotwahl 106
* 3.4 Polynomiale Algorithmen und Innere-Punkt-Methoden 109
3.4.1 Komplexitt der linearen Programmierung 109
3.4.2 Eine primale Innere-Punkt-Methode 111
4 Konvexe Programmierung 123
4.1 Einleitung 123
4.1.1 Konvexe Programme 123
4.1.2 Eigenschaften konvexer Programme 126
4.2 Die Kuhn-Tucker-Bedingungen 129
4.2.1 Problemstellung 129
* 4.2.2 Die Sattelpunkt-Bedingung 131
4.2.3 Lokale Kuhn-Tucker-Bedingungen 135
* 4.2.4 Modifikationen und Verallgemeinerungen 139
4.3 Quadratische Programmierung 139
4.3.1 Problemstellung 139
4.3.2 Das Verfahren von Wolfe 141
4.3.2.1 Das Vorgehen 141
* 4.3.2.2 Die Konvergenz des Verfahrens 146
* 4.3.2.3 Die modifizierte Form 151
4.4 Schnittebenen-Verfahren der konvexen Programmierung 153
4.4.1 Das Prinzip der Schnittebenen-Verfahren 153
4.4.2 Der Kelley-Algorithmus 154
* 4.4.3 Die Konvergenz des Kelley-Algorithmus 162
4.5 Separierbare Programme 165
4.5.1 Konvexe separierbare Programme 165
4.5.2 Nicht-konvexe separierbare Programme 168
5 Ganzzahlige Programmierung 171
5.1 Einleitung 171
5.1.1 Ganzzahlige Programme 171
5.1.2. Beispiele fr die Anwendung ganzzahliger Programme 173
5.1.2.1 Das Fixkosten-Problem 173
5.1.2.2 Reihenfolge-Bedingungen 174
5.2 Lsungsverfahren der ganzzahligen linearen Programmierung 175
5.2.1 Schnittebenen-Verfahren 175
5.2.1.1 Das Fractional-Integer-Verfahren von Gomory 175
5.2.1.2 Die Konvergenz des Algorithmus 181
5.2.1.3 Kritik und Modifikationen der Schnittebenen-Verfahren 183
5.2.2 Kombinatorische Verfahren 184
5.2.2.1 Enumeration 184
* 5.2.2.2 Der Balas-Algorithmus 187
5.2.2.3 Das Verfahren von Land und Doig 197
5.3 Spezielle Probleme der ganzzahligen Programmierung 206
5.3.1 Das Transportmodell 206
5.3.1.1 Problemstellung 206
5.3.1.2 Lsungsverfahren 208
* 5.3.1.3 Die Theorie des Transportmodells 217
* 5.3.1.4 Stepping-Stone-Methode und Simplex-Verfahren 222
5.3.2 Assignment-Probleme 224
5.3.2.1 Das lineare Assignment-Problem 224
5.3.2.2 Das quadratische Assignment-Problem 225
5.3.3 Das Travelling-Salesman-Problem 231
5.3.4 Das Knapsack-Problem 234
* 5.4 Ergebnisse der Komplexittstheorie 239
6 Heuristiken 239
6.1 Problemstellung 239
6.2 Deterministische Heuristiken 239
6.3 Zufallsgesteuerte Heuristiken 249
6.3.1 Simulation 250
6.3.2 Naturanaloge Verfahren 252
6.3.2.1 Mutativ-selektive Verfahren 254
6.3.2.2 Genetische Algorithmen 259
7 Dynamische Programmierung 265
7.1 Problemstellung 265
7.2 Optimale Rckkopplungssteuerung 266
7.2.1 Das Lsungskonzept 266
7.2.2 Beispiele 268
7.2.2.1 Optimaler Ersatzzeitpunkt einer Maschine 268
7.2.2.2 Krzeste Wege durch ein Netzwerk 271
7.3 Die Lsungsstruktur dynamischer Programme 273
7.3.1 Das Optimalittsprinzip 274
7.3.2 Lineare Politiken 274
8 Zusammenfassung 277
9 Literaturverzeichnis 281
Sachverzeichnis 287
END
