Methoden und Modelle des Operations Research

Probleme, Modelle, Algorithmen Eine zunehmende Anzahl von Autoren [siehe z. B. Boothroyd 1978, S. 110, Miiller­ Merbach 1979, Checkland 1983] vertreten die Auffassung, da~ es zwei verschiedene Begriffe des Operations Research (OR) gibt: Ein Operations Research aus der Sicht des Praktikers und eins aus der Sicht des Mathematikers. Wahrend das OR aus der Sicht des Praktikers "die modellgestutzte Vorbereitung von Entscheidungen zur Gestaltung und Lenkung von Mensch-Maschine-Systemen zur Aufgabe hat" [Muller­ Merbach 1979, S. 295], sieht der Mathematiker das OR "als Teilgebiet der ange­ wandten Mathematik" [Gaede 1947] an. Wie es zu dieser Situation kam, wird naher im Kapitell dieses Buches beschrieben. Hier wird allerdings die Meinung vertreten, daf~ es zwar zwei Teile des Gebietes OR geben mag, da~ sie jedoch beide wichtig und notwendig fUr das OR sind und sich aus der Geschichte des OR erk1aren lassen. Urn dies fiir den Leser leichter verstandlich zu machen, ist es nutzlich, zunachst auf den hier benutzten Begriff des "Problems" etwas naher einzugehen. Bild 0 skizziert die hier angenommenen Zusammenhange. Diese Darstellung ist jedoch auf keinen Fall als ein zeitliches Ab1aufschema zu interpretieren. Zum Problem (im BewuBtsein eines Menschen) Formale Abstrak­ Sprache, tion Perception ---, BewuBtsein Anspruchsn iveaus I (subjektiv) I I Anpassung der An­ I spriiche, Anderung I des Realitatsaus­ schnitts I I I I I I I Nicht-quantifizierte I relevante Probleme I Tatbestande __ J Bild 0 Zusammenhiinge zwischen Problemen, Modellen und Algorithmen 2 Einfi.

Einführung.- 1 Die Geschichte des Operations Research.- 1.1 Der Ursprung im mihtärischen Bereich.- 1.2 Weiterentwicklung im zivilen Bereich.- 1.3 Literatur zur Geschichte des Operations Research.- 2 Entscheidungs- und Spieltheorie.- 2.1 Entscheidungstheoretische Richtungen.- 2.2 Grundmodelle der Entscheidungslogik.- 2.2.1 Das Grundmodell der Entscheidungsfällung.- 2.2.2 Entscheidungssituationen.- 2.2.3 Rationale Nutzenfunktionen.- 2.2.4 Rationalität von Ungewißheitsentscheidungen.- 2.3 Grundmodelle der Spieltheorie.- 2.3.1 Spielsituationen und Spielmodelle.- 2.3.2 Zweipersonen-Nullsummenspiele.- 2.3.3 Zweipersonen-Nichtnullsummenspiele.- 2.3.4 N-Personenspiele (Theorie der Koalitionsbildung).- 2.4 Deskriptive Entscheidungstheorie.- 2.5 Entscheidungen in schlecht strukturierten Situationen.- 2.5.1 Einführung.- 2.5.2 Zadeh’s Min/Max-Theorie der Unscharfen Mengen.- 2.5.3 Unscharfe Entscheidungen.- 2.5.4 Alternative Systeme.- 2.6 Aufgaben zu Kapitel 2.- 2.7 Ausgewählte Literatur zu Kapitel 2.- 3 Lineares Programmieren.- 3.1 Einführung.- 3.2 Grundlegende Theorie.- 3.3 Das Simplex-Verfahren.- 3.3.1 Elemente des Simplex-Algorithmus.- 3.3.2 Erweiterungen des Simplex-Algorithmus.- 3.4 Dualität im Linearen Programmieren.- 3.4.1 Dualitätstheorie.- 3.4.2 Duale Simplex-Methode.- 3.5 Postoptimale Analysen.- 3.5.1 Sensitivitätsanalysen.- 3.5.2 Parametrisches Programmieren.- 3.6 Ganzzahliges Lineares Programmieren.- 3.6.1 Einführung.- 3.6.2 Das Schnittebenenverfahren von Gomory.- 3.7 Vektormaximummodelle.- 3.7.1 Grundmodelle.- 3.7.2 Lösungswege.- 3.8 Stochastisches und Unscharfes Lineares Programmieren.- 3.8.1 Stochastisches Lineares Programmieren.- 3.8.2 Unscharfes Lineares Programmieren.- 3.9 Spezielle Strukturen.- 3.10 Lineares Programmieren und Spieltheorie.- 3.11 Aufgaben zu Kapitel 3.- 3.12 Ausgewählte Literatur zu Kapitel 3.- 4 Nichtlineare Programmierung.- 4.1 Einführung.- 4.2 Konvexe Programmierung und Kuhn-Tucker-Theorie.- 4.3 Quadratisches Programmieren.- 4.3.1 Grundlagen.- 4.3.2 Der Algorithmus von Wolfe.- 4.4 Separables konvexes Programmieren.- 4.4.1 Grundlagen.- 4.4.2 ? und ?-Methoden des Separablen Programmierens.- 4.5 Strafkostenverfahren.- 4.5.1 Penalty-Verfahren.- 4.5.2 Barriere-Verfahren.- 4.5.3 SUMT-Verfahren.- 4.6 Geometrisches Programmieren.- 4.6.1 Grundlagen.- 4.6.2 Die Bestimmung von Minimallösungen.- 4.6.3 Die Minimierung von Funktionen bei Ungleichungs nebenbedingungen.- 4.7 Aufgaben zu Kapitel 4.- 4.8 Ausgewählte Literatur zu Kapitel 4.- 5 Entscheidungsbaumverfahren.- 5.1 Einführung.- 5.2 Dynamisches Programmieren.- 5.2.1 Grundlegende Theorie.- 5.2.2 Verschiedene Formen der Stufenoptimierung.- 5.2.3 Rechnerische Effizienz des Dynamischen Programmierens.- 5.3 Branch and Bound-Verfahren.- 5.3.1 Grundlagen.- 5.3.2 Branch and Bound zur Lösung eines Fertigungssteuerungsmodells.- 5.3.3 Branch and Bound-Verfahren zur Lösung von Gemischt-Ganzzahligen Linearen Programmen.- 5.3.4 Die Bestimmung globaler Optima im Separablen Programmieren.- 5.4 Aufgaben zu Kapitel 5.- 5.5 Ausgewählte Literatur zu Kapitel 5.- 6 Theorie der Warteschlangen.- 6.1 Grundstrukturen.- 6.2 Klassifizierung und Beschreibung von Warteschlangenmodellen.- 6.3 Einige stochastische Prozesse.- 6.3.1 Die Beschreibung und Klassifizierung stochastischer Prozesse.- 6.3.2 Markov-Prozesse.- 6.3.3 Poisson-Prozesse.- 6.3.4 Geburts- und Sterbeprozesse.- 6.4 Die Modellierung von Warteschlangensystemen.- 6.4.1 Das System M/M/1.- 6.4.2 Das System M/M/1/R.- 6.5 Warteschlangenmodelle als Entscheidungshilfe.- 6.6 Aufgaben zu Kapitel 6.- 6.7 Ausgewählte Literatur zu Kapitel 6.- 7 Heuristische Verfahren.- 7.1 Eigenschaften und Arten heuristischer Verfahren.- 7.2 Anwendungsbereiche heuristischer Verfahren.- 7.3 Die Entwicklung heuristischer Verfahren.- 7.3.1 Grundlagen des Verfahrensentwurfes.- 7.3.2 Analyse und Synthese heuristischer iterativer Verfahren.- 7.4 Die Qualität heuristischer Verfahren.- 7.5 Beispiele heuristischer Verfahren.- 7.5.1 Vogelsche Approximationsmethode (VAM).- 7.5.2 Die Savings-Heuristik.- 7.5.3 Heuristisches ganzzahliges Programmieren.- 7.6 Aufgaben zu Kapitel 7.- 7.7 Ausgewählte Literatur zu Kapitel 7.- 8 Graphen, Bäume, Netze, Netzpläne.- 8.1 Grundlagen der Graphentheorie.- 8.1.1 Graphen.- 8.1.2 Bäume und Gerüste.- 8.1.3 Netze und Netzwerke.- 8.2 Graphentheoretische Verfahren.- 8.2.1 Die Ermittlung kürzester Wege in Netzwerken.- 8.2.2 Die Ermittlung längster Wege.- 8.2.3 Die Ermittlung maximaler Flüsse.- 8.3 Netzpläne mit deterministischer Struktur.- 8.3.1 Grundlagen.- 8.3.2 Strukturplanung.- 8.3.3 Kapazitätsplanung.- 8.3.4 Kostenplanung.- 8.4 Netzpläne mit stochastischer Struktur.- 8.5 Aufgaben zu Kapitel 8.- 8.6 Ausgewählte Literatur zu Kapitel 8.- Lösungen der Aufgaben.- Sachwortverzeichnis.