Operations Research

Description

Das vorliegende Lehrbuch ist eine Einführung in das Operations Research, die mathematisch stringent vorgeht, ohne jedoch den Leser mit Beweisen zu überfrachten. Stattdessen werden die mathematischen Sachverhalte ausführlich begründet und durch weit mehr als einhundert Abbildungen illustriert. Das Buch ist gleichermaßen für Ingenieure, Mathematiker und Wirtschaftswissenschaftler geeignet. Mit mehr als vierhundert Seiten stellen die Autoren genügend Auswahlmöglichkeiten zur Verfügung, um es als Grundlage für unterschiedlich angelegte Operations-Research-Vorlesungen zu verwenden. Darüber hinaus setzt dieses Buch an den richtigen Stellen neue Akzente und bereichert den Bestand der bisherigen Lehrbücher zu diesem Fachgebiet. Ein ausführlicher Anhang verdeutlicht die für das Verständnis des Buches notwendigen mathematischen Grundkonzepte, um den unterschiedlichen Voraussetzungen in der Vielfalt der Bachelor- und Masterprogramme Rechnung zu tragen. Die korrigierte und erweiterte dritte Auflage dieses Buches erhält ein neues, ausführliches Kapitel zur stochastischen Optimierung. Vorwort Inhaltsverzeichnis 1 Kernkonzepte der linearen Optimierung 1.1 Einführung 1.2 Grundlegende Definitionen 1.3 Grafische Lösung 1.4 Standardform und grundlegende analytische Konzepte 1.5 Normalform und Basen 1.5.1 Normalform und kanonische Form 1.5.2 Zulässige Basislösung, Basisund Nichtbasisvariablen 1.6 Der Simplex-Algorithmus 1.6.1 Simplex-Tableau 1.6.2 Pivotelement und Austauschschritt 1.6.3 Auswahlund Stoppregeln 1.6.4 Verkürztes Simplex-Tableau 1.6.5 Anti-Zyklus-Strategien 1.7 Bestimmung einer Startecke für den Simplex-Algorithmus 1.7.1 Phase-I-Methode 1.7.2 Big-M-Methode 1.8 Dualität 1.8.1 Motivation und Grundbegriffe 1.8.2 Dualitätssätze 1.8.3 Algorithmische Lösung des Dualproblems 1.9 Der duale Simplex-Algorithmus 1.9.1 Auswahlund Stoppregeln 1.9.2 Bestimmung einer Startecke mit dualen Austauschschritten 1.10 Zusammenfassung 2 Erweiterungen und Anwendungen der linearen Optimierung 2.1 Sensitivitätsanalyse 2.1.1 Eindeutigkeit optimaler Punkte 2.1.2 Störungen der Zielfunktion 2.1.3 Störungen der rechten Seite 2.1.4 Schattenpreise 2.2 Parametrische lineare Optimierung 2.2.1 Variation der rechten Seite 2.2.2 Variation der Zielfunktion 2.3 Multikriterielle lineare Optimierung 2.3.1 Lexikographische Optimierung 2.3.2 Optimierung bei Zieldominanz 2.3.3 Gewichtungsmethode 2.3.4 Goal Programming 2.3.5 Bestimmung effizienter Punkte 2.4 Transportprobleme 2.4.1 Bestimmung einer Startecke 2.4.2 Optimalitätskriterium 2.4.3 Stepping-Stone-Methode 2.4.4 Lineare Zuordnungsprobleme 2.4.5 Totale Unimodularität 2.5 Zwei-Personen-Nullsummenspiele 2.5.1 Grundbegriffe 2.5.2 Gemischte Strategien und Minmax-Theorem 3 Graphentheorie 3.1 Grundlagen der Graphentheorie: Begriffe und Definitionen 3.2 Kürzeste Wege in Graphen 3.2.1 Algorithmen für das Single-Source-Shortest-Path-Problem 3.2.2 Algorithmen für das All-Pairs-Shortest-Paths-Problem Der Floyd-Warshalloder Tripel-Algorithmus 3.3 Minimale spannende Bäume und 1-Bäume 3.3.1 Bestimmung minimaler spannender Bäume Der Kruskal-Algorithmus 3.3.2 Bestimmung minimaler 1-Bäume eines Graphen 3.4 Eulersche und Hamiltonsche Graphen 3.4.1 Eulersche Graphen und das „Chinese Postman Problem“ Das Königsberger Brückenproblem (1736) 3.4.2 Hamiltonsche Graphen und das Traveling Salesman Problem Hamiltonsche Graphen 3.5 Max-Flow-Min-Cut 4 Netzplantechnik 4.1 Einführung und grundlegende Definitionen 4.2 Strukturplanung 4.2.1 Vorgangspfeilnetzpläne 4.2.2 Vorgangsknotennetzpläne 4.3 Zeitplanung 4.3.1 Vorgangspfeilnetzpläne 4.3.2 Vorgangsknotennetzpläne 4.3.3 Stochastische Zeitplanung 4.4 Kapazitätsplanung 4.5 Kostenplanung 5 Ganzzahlige Optimierung 5.1 Einführung und Beispiele 5.2 Modellierung mit ganzzahligen Variablen 5.2.1 Logische Verknüpfungen 5.2.2 Mengenbeziehungen 5.2.3 Alternative Nebenbedingungen 5.3 Komplexitätstheorie 5.3.1 Probleme und Algorithmen 5.3.2 Rechenaufwand von Algorithmen 5.3.3 Optimierungsund Entscheidungsprobleme 5.3.4 Die Klassen P, NP und NP-vollständig 5.4 Verfahren zur Lösung von ganzzahligen Problemen 5.4.1 Das Branch-&-Bound-Verfahren 5.4.2 Das Schnittebenenverfahren von Gomory 5.4.3 Das Branch-&-Cut-Verfahren 6 Heuristiken 6.1 Konstruktionsheuristiken 6.1.1 Zufällige Bestimmung eines zulässigen Punktes 6.1.2 Greedy-Verfahren 6.1.3 Vorausschauende Verfahren 6.2 Verbesserungsheuristiken 6.2.1 Lokale Suchverfahren 6.2.2 Metaheuristiken 6.3 Güte von Heuristiken 6.4 Verfahren zur Bestimmung oberer Schranken 6.4.1 LP-Relaxierungen 6.4.2 Lagrange-Relaxierungen 7 Nichtlineare Optimierung 7.1 Einführung und Beispiele 7.2 Unrestringierte nichtlineare Optimierung 7.2.1 Optimalitätsbedingung erster Ordnung 7.2.2 Optimalitätsbedingungen zweiter Ordnung 7.2.3 Iterative Verfahren 7.2.4 Konvexe Optimierung 7.3 Restringierte nichtlineare Optimierung 7.3.1 Optimalitätsbedingungen erster Ordnung 7.3.2 Konvexe Optimierung 7.3.3 Iterative Verfahren 8 Stochastische Optimierung 8.1 Einführung und Beispiele 8.2 Zweistufige stochastische lineare Optimierungsprobleme 8.2.1 Wertfunktion und deterministisches Äquivalent 8.2.2 Recourse-Matrix 8.2.3 Endlicher Zufallsvektor 8.2.4 L-shaped Algorithmus 8.2.5 Stufen vs. Perioden 8.2.6 Metriken 8.2.7 Allgemeine Vorgehensweise 8.3 Chance Constraints 8.3.1 Normalverteilung 8.3.2 Endliche Zufallsvariable 9 Dynamische Optimierung 9.1 Einführung 9.2 Deterministische dynamische Optimierung 9.2.1 Das Basismodell 9.2.2 Das Optimalitätskriterium 9.2.4 Wertiteration 9.2.5 Anwendungsbereiche 9.3 Stochastische dynamische Optimierung 9.3.1 Das Basismodell 9.3.2 Das Optimalitätskriterium 9.3.3 Die Optimalitätsgleichung 9.3.4 Wertiteration 9.3.5 Lösung mittels linearer Optimierung 9.3.6 Ein Kontrollmodell 9.3.7 Optimalität strukturierter Strategien 9.4 Verallgemeinerungen 10 Wartesysteme 10.1 Einführung 10.2 Berechnung der Grenzverteilung 10.3 Festlegung der Parameter 10.4 Geburtsund Todesprozesse 10.5 Wartesysteme, die auf einem Geburtsund Todesprozess basieren 10.6 Poisson-Prozesse 10.7 Jackson-Netzwerke A Anhang A.1 In der Bäckerei A.2 Vektoren, innere Produkte und lineare Funktionen A.3 Lineare Gleichungen und lineare Ungleichungen A.4 Matrizen A.5 Niveaumengen und untere Niveaumengen A.6 Gradienten, Jacobiund Hesse-Matrizen A.7 Eigenwerte A.8 Linearisierung A.9 Konvexität A.10 Grundlagen der Wahrscheinlichkeitsrechnung Literaturverzeichnis Sachverzeichnis