Hans-Peter Ziegler Algorithms for Linear Stochastic Programs and their Application in Supply Chain Network Design Problems

Zum Inhalt

Die Studie „befasst sich mit der mehrstufigen stochastischen linearen und gemischt ganzzahligen Optimierung und deren Anwendung in der Standortplanung.

Im ersten Teil des Buches werden die Grundlagen der mehrstufigen stochastischen linearen und gemischt ganzzahligen Optimierung erläutert und die benötigten Grundbegriffe aus der Statistik und der stochastischen Programmierung eingeführt. Alle Begrifflichkeiten und Lösungsansätze sind stets durch Beispiele veranschaulicht.

Besonders erwähnenswert sind dabei zwei Aspekte. Zum einen die Möglichkeit mehrstufige stochastische Programme über Pfade in einem Szenarienbaum zu beschreiben. Zum anderen die Möglichkeit anhand weniger, allgemeiner Eigenschaften den Wert eines stochastischen Programms vorherzusagen, um zu erkennen, wann ein stochastisches Problem durch ein deterministisches ersetzt werden kann.

Die wichtigsten Lösungsansätze für stochastische lineare und gemischt ganzzahlige Programme werden vorgestellt und deren Stärken und Schwächen diskutiert. Eine neue Lagrange Relaxation wird eingeführt, die es erlaubt eine bestimmte Klasse stochastischer Programme durch ein einziges deterministisches Programm zu approximieren.

Im Anschluss daran wird ein neuer Branch-and-Bound Algorithmus (NARW) hergeleitet, der basierend auf einer LP-Relaxation und einer Lagrange-Relaxation, ein gemischt ganzzahliges stochastisches Optimierungsproblem in deterministische Teilprobleme zerlegt. Dieser Ansatz wird um einen Warmstart erweitert. Zusätzlich wird gezeigt, wie aus der deterministischen Optimierung bekannte Cuts auf ein stochastisches Problem angepasst werden können und so die Lösungszeiten signifikant reduzieren.

Ein mehrstufiges stochastisches Supply Network Design Problem wird hergeleitet, welches im Gegensatz zu den bisher publizierten Modellen mehrere Perioden, mehrere Produkte, alternative Anlagemöglichkeiten und Darlehn, sowie Unsicherheit in der Kundennachfrage und in den Renditen verschiedener Investitionsalternativen berücksichtigt. Der Anteil der befriedigten Nachfrage wird in einem Service Level zusammengefasst, so dass keine zwingende Notwendigkeit besteht, die gesamte Kundennachfrage zu decken. Zusätzlich wird eine Zielrendite vorgegeben und deren Unterschreitung über ein Risikomaß in der Zielfunktion abgestraft.

Dieses neue Supply Network Design Problem wird mit NARW gelöst. Vergleiche mit dem Standard Branch-and-Bound Solver in Cplex zeigen die deutliche Überlegenheit des neuen Ansatzes.