Operations Research

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 6 Inhaltsverzeichnis 8 1 Kernkonzepte der linearen Optimierung 13 1.1 Einführung 13 1.2 Grundlegende Definitionen 20 1.3 Grafische Lösung 22 1.4 Standardform und grundlegende analytische Konzepte 24 1.5 Normalform und Basen 28 1.5.1 Normalform und kanonische Form 28 1.5.2 Zulässige Basislösung, Basisund Nichtbasisvariablen 32 1.6 Der Simplex-Algorithmus 35 1.6.1 Simplex-Tableau 36 1.6.2 Pivotelement und Austauschschritt 38 1.6.3 Auswahlund Stoppregeln 40 1.6.4 Verkürztes Simplex-Tableau 45 1.6.5 Anti-Zyklus-Strategien 47 1.7 Bestimmung einer Startecke für den Simplex-Algorithmus 50 1.7.1 Phase-I-Methode 51 1.7.2 Big-M-Methode 54 1.8 Dualität 55 1.8.1 Motivation und Grundbegriffe 56 1.8.2 Dualitätssätze 58 1.8.3 Algorithmische Lösung des Dualproblems 62 1.9 Der duale Simplex-Algorithmus 65 1.9.1 Auswahlund Stoppregeln 65 1.9.2 Bestimmung einer Startecke mit dualen Austauschschritten 68 1.10 Zusammenfassung 70 2 Erweiterungen und Anwendungen der linearen Optimierung 73 2.1 Sensitivitätsanalyse 73 2.1.1 Eindeutigkeit optimaler Punkte 73 2.1.2 Störungen der Zielfunktion 75 2.1.3 Störungen der rechten Seite 76 2.1.4 Schattenpreise 78 2.2 Parametrische lineare Optimierung 79 2.2.1 Variation der rechten Seite 79 2.2.2 Variation der Zielfunktion 83 2.3 Multikriterielle lineare Optimierung 89 2.3.1 Lexikographische Optimierung 92 2.3.2 Optimierung bei Zieldominanz 93 2.3.3 Gewichtungsmethode 94 2.3.4 Goal Programming 95 2.3.5 Bestimmung effizienter Punkte 98 2.4 Transportprobleme 105 2.4.1 Bestimmung einer Startecke 106 2.4.2 Optimalitätskriterium 111 2.4.3 Stepping-Stone-Methode 114 2.4.4 Lineare Zuordnungsprobleme 117 2.4.5 Totale Unimodularität 119 2.5 Zwei-Personen-Nullsummenspiele 122 2.5.1 Grundbegriffe 122 2.5.2 Gemischte Strategien und Minmax-Theorem 127 3 Graphentheorie 131 3.1 Grundlagen der Graphentheorie: Begriffe und Definitionen 132 3.2 Kürzeste Wege in Graphen 137 3.2.1 Algorithmen für das Single-Source-Shortest-Path-Problem 138 3.2.2 Algorithmen für das All-Pairs-Shortest-Paths-Problem Der Floyd-Warshalloder Tripel-Algorithmus 142 3.3 Minimale spannende Bäume und 1-Bäume 144 3.3.1 Bestimmung minimaler spannender Bäume Der Kruskal-Algorithmus 144 3.3.2 Bestimmung minimaler 1-Bäume eines Graphen 146 3.4 Eulersche und Hamiltonsche Graphen 147 3.4.1 Eulersche Graphen und das „Chinese Postman Problem“ Das Königsberger Brückenproblem (1736) 147 3.4.2 Hamiltonsche Graphen und das Traveling Salesman Problem Hamiltonsche Graphen 157 3.5 Max-Flow-Min-Cut 158 4 Netzplantechnik 163 4.1 Einführung und grundlegende Definitionen 163 4.2 Strukturplanung 165 4.2.1 Vorgangspfeilnetzpläne 166 4.2.2 Vorgangsknotennetzpläne 168 4.3 Zeitplanung 172 4.3.1 Vorgangspfeilnetzpläne 173 4.3.2 Vorgangsknotennetzpläne 175 4.3.3 Stochastische Zeitplanung 180 4.4 Kapazitätsplanung 182 4.5 Kostenplanung 183 5 Ganzzahlige Optimierung 187 5.1 Einführung und Beispiele 187 5.2 Modellierung mit ganzzahligen Variablen 194 5.2.1 Logische Verknüpfungen 194 5.2.2 Mengenbeziehungen 197 5.2.3 Alternative Nebenbedingungen 199 5.3 Komplexitätstheorie 201 5.3.1 Probleme und Algorithmen 201 5.3.2 Rechenaufwand von Algorithmen 202 5.3.3 Optimierungsund Entscheidungsprobleme 203 5.3.4 Die Klassen P, NP und NP-vollständig 204 5.4 Verfahren zur Lösung von ganzzahligen Problemen 206 5.4.1 Das Branch-&-Bound-Verfahren 207 5.4.2 Das Schnittebenenverfahren von Gomory 216 5.4.3 Das Branch-&-Cut-Verfahren 222 6 Heuristiken 223 6.1 Konstruktionsheuristiken 224 6.1.1 Zufällige Bestimmung eines zulässigen Punktes 224 6.1.2 Greedy-Verfahren 224 6.1.3 Vorausschauende Verfahren 227 6.2 Verbesserungsheuristiken 228 6.2.1 Lokale Suchverfahren 228 6.2.2 Metaheuristiken 232 6.3 Güte von Heuristiken 236 6.4 Verfahren zur Bestimmung oberer Schranken 239 6.4.1 LP-Relaxierungen 239 6.4.2 Lagrange-Relaxierungen 240 7 Nichtlineare Optimierung 245 7.1 Einführung und Beispiele 245 7.2 Unrestringierte nichtlineare Optimierung 251 7.2.1 Optimalitätsbedingung erster Ordnung 252 7.2.2 Optimalitätsbedingungen zweiter Ordnung 256 7.2.3 Iterative Verfahren 259 7.2.4 Konvexe Optimierung 265 7.3 Restringierte nichtlineare Optimierung 267 7.3.1 Optimalitätsbedingungen erster Ordnung 267 7.3.2 Konvexe Optimierung 279 7.3.3 Iterative Verfahren 283 8 Stochastische Optimierung 302 8.1 Einführung und Beispiele 302 8.2 Zweistufige stochastische lineare Optimierungsprobleme 307 8.2.1 Wertfunktion und deterministisches Äquivalent 308 8.2.2 Recourse-Matrix 312 8.2.3 Endlicher Zufallsvektor 313 8.2.4 L-shaped Algorithmus 318 8.2.5 Stufen vs. Perioden 330 8.2.6 Metriken 333 8.2.7 Allgemeine Vorgehensweise 344 8.3 Chance Constraints 347 8.3.1 Normalverteilung 348 8.3.2 Endliche Zufallsvariable 351 9 Dynamische Optimierung 357 9.1 Einführung 357 9.2 Deterministische dynamische Optimierung 363 9.2.1 Das Basismodell 363 9.2.2 Das Optimalitätskriterium 365 9.2.4 Wertiteration 367 9.2.5 Anwendungsbereiche 369 9.3 Stochastische dynamische Optimierung 371 9.3.1 Das Basismodell 371 9.3.2 Das Optimalitätskriterium 373 9.3.3 Die Optimalitätsgleichung 375 9.3.4 Wertiteration 377 9.3.5 Lösung mittels linearer Optimierung 379 9.3.6 Ein Kontrollmodell 379 9.3.7 Optimalität strukturierter Strategien 380 9.4 Verallgemeinerungen 393 10 Wartesysteme 395 10.1 Einführung 395 10.2 Berechnung der Grenzverteilung 399 10.3 Festlegung der Parameter 401 10.4 Geburtsund Todesprozesse 406 10.5 Wartesysteme, die auf einem Geburtsund Todesprozess basieren 407 10.6 Poisson-Prozesse 411 10.7 Jackson-Netzwerke 413 A Anhang 419 A.1 In der Bäckerei 419 A.2 Vektoren, innere Produkte und lineare Funktionen 421 A.3 Lineare Gleichungen und lineare Ungleichungen 424 A.4 Matrizen 431 A.5 Niveaumengen und untere Niveaumengen 436 A.6 Gradienten, Jacobiund Hesse-Matrizen 437 A.7 Eigenwerte 440 A.8 Linearisierung 441 A.9 Konvexität 442 A.10 Grundlagen der Wahrscheinlichkeitsrechnung 444 Literaturverzeichnis 448 Sachverzeichnis 451