Optimierungsmethoden

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 Die Lineare Programmierung.- 2.1 Formulierung des Problems.- 2.2 Das Simplex-Verfahren.- 2.2.1 Graphische Veranschaulichung.- 2.2.2 Das Simplex-Verfahren beim 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.- * 2.5 Postoptimale Analysen.- 2.5.1 Sensitivitätsanalyse.- 2.5.1.1 Sensitivitätsanalyse bei Veränderung der Beschränkungskonstanten.- 2.5.1.2 Sensitivitätsanalyse bei Veränderung der Zielfunktionskoeffizienten.- 2.5.1.3 Sensitivitätsanalyse bei Veränderung der Koeffizienten der Beschränkungsmatrix.- 2.5.2 Zusätzliche Variablen und Restriktionen.- 2.5.2.1 Zusätzliche Variablen.- 2.5.2.2 Zusätzliche Restriktionen.- 2.5.3 Parametrische Programmierung.- 2.5.3.1 Problemstellung.- 2.5.3.2 Generelle Eigenschaften parametrischer Programme.- 2.5.3.3 Ermittlung der kritischen Punkte bei Variation des Beschränkungsvektors.- * 2.6 Das Dekompositionsprinzip.- 2.6.1 Problemstellung.- 2.6.2 Der Dekompositions-Algorithmus.- 2.6.3 Theorie des Dekompositions-Algorithmus.- * 2.7 Weiterentwicklungen.- 2.7.1 Modifikationen des Simplex-Verfahrens.- 2.7.1.1 Die revidierte Simplex-Methode.- 2.7.1.2 Beschränkte Variablen.- 2.7.1.3 Pivotwahl.- 2.7.2 Polynomiale Algorithmen.- 2.8 Literaturhinweise.- 3 Konvexe Programmierung.- 3.1 Einleitung.- 3.1.1 Konvexe Programme.- 3.1.2 Eigenschaften konvexer Programme.- 3.2 Die Kuhn-Tucker-Bedingungen.- 3.2.1 Problemstellung.- * 3.2.2 Die Sattelpunkt-Bedingungen.- * 3.2.3 Lokale Kuhn-Tucker-Bedingungen.- * 3.2.4 Modifikationen und Verallgemeinerungen.- 3.3 Verfahren der konvexen Programmierung.- 3.3.1 Quadratische Programmierung.- 3.3.1.1 Problemstellung.- 3.3.1.2 Das Verfahren von Wolfe.- 3.3.1.2.1 Das Vorgehen.- * 3.3.1.2.2 Die Konvergenz des Verfahrens.- * 3.3.1.2.3 Die modifizierte Form des Verfahrens von Wolfe.- 3.3.2 Schnittebenen-Verfahren der konvexen Programmierung.- 3.3.2.1 Das Prinzip der Schnittebenen-Verfahren.- 3.3.2.2 Der Kelley-Algorithmus.- * 3.3.2.3 Die Konvergenz des Kelley-Algorithmus.- 3.3.3 Separierbare Programme.- 3.3.4 Gradienten-Verfahren.- 3.3.4.1 Die Methode des steilsten Abstiegs.- 3.3.4.2 Das Verfahren der projizierten Gradienten von Rosen.- * 3.3.4.3 Theoretische Grundlagen des Verfahrens von Rosen.- 3.4 Literaturhinweise.- 4 Ganzzahlige Programmierung.- 4.1 Einleitung.- 4.1.1 Ganzzahlige Programme.- 4.1.2 Beispiele für die Anwendung ganzzahliger linearer Programme.- 4.1.2.1 Das Fixkosten-Problem.- 4.1.2.2 Reihenfolge-Bedingungen.- 4.2 Lösungsverfahren der ganzzahligen linearen Programmierung.- 4.2.1 Schnittebenen-Verfahren.- 4.2.1.1 Das Fractional Integer-Verfahren von Gomory.- * 4.2.1.2 Die Konvergenz des Algorithmus.- 4.2.1.3 Kritik und Modifikation der Schnittebenen-Verfahren.- 4.2.2 Kombinatorische Verfahren.- 4.2.2.1 Enumeration.- 4.2.2.2 Der Balas-Algorithmus.- 4.2.2.3 Das Verfahren von Land und Doig.- 4.3 Spezielle Probleme der ganzzahligen Programmierung.- 4.3.1 Das Transportmodell.- 4.3.1.1 Problemstellung.- 4.3.1.2 Lösungsverfahren.- * 4.3.1.3 Die Theorie des Transportmodells.- * 4.3.1.4 Stepping-Stone-Methode und Simplex-Verfahren.- 4.3.2 Das Assignment-Problem.- 4.3.2.1 Das lineare Assignment-Problem.- 4.3.2.2 Das quadratische Assignment-Problem.- 4.3.3 Das Travelling-Salesman-Problem.- 4.3.4 Das Knapsack-Problem.- 4.4 Ergebnisse der Komplexitätstheorie.- 4.5 Literaturhinweise.- 5 Dynamische Programmierung.- 5.1 Problemstellung.- 5.2 Optimale Rückkopplungssteuerung.- 5.2.1 Das Lösungskonzept.- 5.2.2 Beispiele.- 5.2.2.1 Optimaler Ersatzzeitpunkt einer Maschine.- 5.2.2.2 Kürzeste Wege durch ein Netzwerk.- 5.3 Die Lösungsstruktur dynamischer Programme.- 5.3.1 Das Optimalitätsprinzip.- 5.3.2 Lineare Politiken.- 5.4 Literaturhinweise.- 6 Zusammenfassung.- 7 Literaturverzeichnis.- 8 Sachverzeichnis.