Description
Dieses Lehrbuch gibt einen berblick ber Optimierungsmethoden und stellt die wichtigsten Algorithmen dieses Gebiets dar. Darber hinaus vermittelt es theoretische Grundlagen und begrndet die angewendeten Rechenverfahren. Entsprechend der Zielgruppe werden nur diejenigen mathematischen Kenntnisse vorausgesetzt, die in den Lehrveranstaltungen zur Einfhrung in die Mathematik fr Wirtschaftswissenschaftler vermittelt werden. Die Neuauflage wurde – unter Beibehaltung der Grundkonzeption des Buches – vollstndig berarbeitet und um ein Kapitel ber Lsungsheuristiken und insbesondere naturanaloge Verfahren erweitert. 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 Ausgewhlte Lehrbcher.- 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 zulssigen Ausgangslsung.- 2.2.4 Sonderflle 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 Dualittstheorie.- 2.4.1 Dualitt im speziellen Maximum-Problem.- 2.4.1.1 Formulierung des Problems.- 2.4.1.2 Dualittsstze.- 2.4.1.3 Complementary Slackness und Preistheorem.- 2.4.2 Dualitt 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 Sensitivittsanalyse.- 3.1.1.1 Vernderung der Beschrnkungskonstanten.- 3.1.1.2 Vernderung der Zielfunktionskoeffizienten.- 3.1.1.3 Koeffizienten der Beschrnkungsmatrix.- 3.1.2 Zustzliche Variablen und Restriktionen.- 3.1.2.1 Zustzliche Variablen.- 3.1.2.2 Zustzliche 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 Beschrnkungsvektors.- 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 Beschrnkte Variablen.- 3.3.3 Pivotwahl.- 3.4 Polynomiale Algorithmen und Innere-Punkt-Methoden.- 3.4.1 Komplexitt 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 fr die Anwendung ganzzahliger Programme.- 5.1.2.1 Das Fixkosten-Problem.- 5.1.2.2 Reihenfolge-Bedingungen.- 5.2 Lsungsverfahren 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 Lsungsverfahren.- 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 Komplexittstheorie.- 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 Rckkopplungssteuerung.- 7.2.1 Das Lsungskonzept.- 7.2.2 Beispiele.- 7.2.2.1 Optimaler Ersatzzeitpunkt einer Maschine.- 7.2.2.2 Krzeste Wege durch ein Netzwerk.- 7.3 Die Lsungsstruktur dynamischer Programme.- 7.3.1 Das Optimalittsprinz:ip.- 7.3.2 Lineare Politiken.- 8 Zusammenfassung.- 9 Literaturverzeichnis.
