Optimierungsmethoden

Inhaltsverzeichnis

1 Einleitung.- 1.1 Entscheidungsmodelle.- 1.2 Typen von Optimierungsmodellen.- 1.2.1 Stetige Optimierungsmodelle.- 1.2.2 Diskrete Optimierungsmodelle.- 1.2.3 Dynamische Optimierungsmodelle.- 1.3 Ausgewählte Lehrbücher.- 2 Grundlagen der linearen Programmierung.- 2.1 Formulierung des Problems.- 2.2 Das Simplex-Verfahren.- 2.2.1 Graphische Veranschaulichung.- 2.2.2 Das Simplex-Verfahren bei einem speziellen Maximum-Problem.- 2.2.3 Bestimmung einer zulässigen Ausgangslösung.- 2.2.4 Sonderfälle beim Simplex-Verfahren.- 2.3 Die Theorie des Simplex-Verfahrens.- 2.3.1 Das Eckentheorem.- 2.3.2 Das Simplex-Kriterium.- 2.3.3 Formaler Aufbau des Simplex-Tableaus.- 2.4 Dualitätstheorie.- 2.4.1 Dualität im speziellen Maximum-Problem.- 2.4.1.1 Formulierung des Problems.- 2.4.1.2 Dualitätssätze.- 2.4.1.3 Complementary Slackness und Preistheorem.- 2.4.2 Dualität im allgemeinen Fall.- 2.4.3 Beispiel.- 2.4.4 Die duale Simplex-Methode.- 3 Erweiterungen der linearen Programmierung.- 3.1 Postoptimale Analysen.- 3.1.1 Sensitivitätsanalyse.- 3.1.1.1 Veränderung der Beschränkungskonstanten.- 3.1.1.2 Veränderung der Zielfunktionskoeffizienten.- 3.1.1.3 Koeffizienten der Beschränkungsmatrix.- 3.1.2 Zusätzliche Variablen und Restriktionen.- 3.1.2.1 Zusätzliche Variablen.- 3.1.2.2 Zusätzliche Restriktionen.- 3.1.3 Parametrische Programmierung.- 3.1.3.1 Problemstellung.- 3.1.3.2 Allgemeine Eigenschaften.- 3.1.3.3 Ermittlung der kritischen Punkte bei Variation des Beschränkungsvektors.- 3.2 Das Dekompositionsprinzip.- 3.2.1 Problemstellung.- 3.2.2 Der Dekompositions-Algorithmus.- 3.2.3 Theorie des Dekompositions-Algorithmus.- 3.3 Modifikationen des Simplex-Verfahrens.- 3.3.1 Die revidierte Simplex-Methode.- 3.3.2 Beschränkte Variablen.- 3.3.3 Pivotwahl.- 3.4 Polynomiale Algorithmen und Innere-Punkt-Methoden.- 3.4.1 Komplexität der linearen Programmierung.- 3.4.2 Eine primale Innere-Punkt-Methode.- 4 Konvexe Programmierung.- 4.1 Einleitung.- 4.1.1 Konvexe Programme.- 4.1.2 Eigenschaften konvexer Programme.- 4.2 Die Kuhn-Tucker-Bedingungen.- 4.2.1 Problemstellung.- 4.2.2 Die Sattelpunkt-Bedingung.- 4.2.3 Lokale Kuhn-Tucker-Bedingungen.- 4.2.4 Modifikationen und Verallgemeinerungen.- 4.3 Quadratische Programmierung.- 4.3.1 Problemstellung.- 4.3.2 Das Verfahren von Wolfe.- 4.3.2.1 Das Vorgehen.- 4.3.2.2 Die Konvergenz des Verfahrens.- 4.3.2.3 Die modifizierte Form.- 4.4 Schnittebenen-Verfahren der konvexen Programmierung.- 4.4.1 Das Prinzip der Schnittebenen-Verfahren.- 4.4.2 Der Kelley-Algorithmus.- 4.4.3 Die Konvergenz des Kelley-Algorithmus.- 4.5 Separierbare Programme.- 4.5.1 Konvexe separierbare Programme.- 4.5.2 Nicht-konvexe separierbare Programme.- 5 Ganzzahlige Programmierung.- 5.1 Einleitung.- 5.1.1 Ganzzahlige Programme.- 5.1.2 Beispiele für die Anwendung ganzzahliger Programme.- 5.1.2.1 Das Fixkosten-Problem.- 5.1.2.2 Reihenfolge-Bedingungen.- 5.2 Lösungsverfahren der ganzzahligen linearen Programmierung.- 5.2.1 Schnittebenen-Verfahren.- 5.2.1.1 Das Fractional-Integer-Verfahren von Gomory.- 5.2.1.2 Die Konvergenz des Algorithmus.- 5.2.1.3 Kritik und Modifikationen der Schnittebenen-Verfahren.- 5.2.2 Kombinatorische Verfahren.- 5.2.2.1 Enumeration.- 5.2.2.2 Der Balas-Algorithmus.- 5.2.2.3 Das Verfahren von Land und Doig.- 5.3 Spezielle Probleme der ganzzahligen Programmierung.- 5.3.1 Das Transportmodell.- 5.3.1.1 Problemstellung.- 5.3.1.2 Lösungsverfahren.- 5.3.1.3 Die Theorie des Transportmodells.- 5.3.1.4 Stepping-Stone-Methode und Simplex-Verfahren.- 5.3.2 Assignment-Probleme.- 5.3.2.1 Das lineare Assignment-Problem.- 5.3.2.2 Das quadratische Assignment-Problem.- 5.3.3 Das Travelling-Salesman-Problem.- 5.3.4 Das Knapsack-Problem.- 5.4 Ergebnisse der Komplexitätstheorie.- 6 Heuristiken.- 6.1 Problemstellung.- 6.2 Deterministische Heuristiken.- 6.3 Zufallsgesteuerte Heuristiken.- 6.3.1 Simulation.- 6.3.2 Naturanaloge Verfahren.- 6.3.2.1 Mutativ-selektive Verfahren.- 6.3.2.2 Genetische Algorithmen.- 7 Dynamische Programmierung.- 7.1 Problemstellung.- 7.2 Optimale Rückkopplungssteuerung.- 7.2.1 Das Lösungskonzept.- 7.2.2 Beispiele.- 7.2.2.1 Optimaler Ersatzzeitpunkt einer Maschine.- 7.2.2.2 Kürzeste Wege durch ein Netzwerk.- 7.3 Die Lösungsstruktur dynamischer Programme.- 7.3.1 Das Optimalitätsprinz:ip.- 7.3.2 Lineare Politiken.- 8 Zusammenfassung.- 9 Literaturverzeichnis.