Die dynamische Programmierung (DP) ist ein allgemeines Prinzip zur Lösung mehrstufiger oder sequentieller Entscheidungsprobleme. Sie bietet Lösungsmöglichkeiten für Entscheidungsprobleme, bei denen eine Folge voneinander abhängiger Entscheidungen getroffen werden kann, um für das Gesamtproblem ein Optimum zu erzielen.
Das Besondere an der DP liegt demnach in der sequentiellen Lösung eines in mehrere Stufen (bzw. Perioden) aufgeteilten Entscheidungsprozesses. Dabei werden auf jeder Stufe jeweils nur die dort existierenden Entscheidungsalternativen betrachtet.
Bei vielen aus der Praxis stammenden dynamischen Optimierungsproblemen treten jedoch auch stochastische Einflüsse auf. Bei Lagerhaltungsproblemen ist z.B. die Nachfrage oft mit großen Unsicherheiten verbunden, so dass die Nachfragemenge und somit auch der Lagerbestand als Zufallsgrößen anzusehen sind.
Stochastische dynamische Optimierungsprobleme sind i.d.R. wesentlich komplizierter als die entsprechenden deterministischen Probleme.
Markov-Entscheidungsprozesse stellen das Kernstück der stochastischen dynamischen Programmierung dar und werden für die Lösung von Optimierungsproblemen mit unendlich großem (Planungs-) Horizont genutzt.
Die (stochastische) dynamische Programmierung erscheint zwar kompliziert, hat aber den Vorteil, dass viele Bedingungen und (Kosten-) Einflüsse problemlos mit berücksichtigt werden können.
Wenn mehrere Produkte gleichzeitig betrachtet werden, steigt der Rechenaufwand jedoch sehr stark an. Dafür eignen sich die Modelle der Linearen Programmierung und teilweise auch die Modelle der Flussmaximierung in Graphen (einschließlich des Transportsystems) besonders gut.
Unter den verschiedenen möglichen Lösungsverfahren ist je nach auftretender Problemstellung das vorteilhafteste auszuwählen. Erweist sich ein Problem für die Anwendung dieser Methoden jedoch als zu schwierig, bilden die heuristischen Verfahren einen weiteren Lösungsweg.
Inhaltsverzeichnis
- Einleitung - Dynamische Programmierung
- Allgemeine Form von (diskreten) dynamischen Programmen
- Diskrete deterministische Probleme
- Klassifizierung von dynamischen Programmen
- Ein Bestellmengenproblem
- Lösungsansätze für diskrete deterministische Probleme
- Das Optimalitätsprinzip von Bellman
- Rückwärts-Vorwärts-Rekursion
- Vorwärts-Rückwärts-Rekursion
- Stochastische dynamische Programmierung
- Aufgabenstellung der stochastischen dynamischen Programmierung
- Beispiele
- Unbekannter Ertrag der aktuellen Periode, bekannter Zustand der nächsten Periode
- Maximierung der Wahrscheinlichkeit für das Eintreten eines Ereignisses
- Markov-Entscheidungsprozesse
- Übergangs- und Zustandswahrscheinlichkeiten
- Ertrag und Wert eines Prozesses
- Beispiel
- Ausblick
Zielsetzung und Themenschwerpunkte
Diese Arbeit befasst sich mit den Grundlagen der stochastischen dynamischen Programmierung (DP). Ziel ist es, ein umfassendes Verständnis der Konzepte und Methoden der DP zu vermitteln, insbesondere im Kontext stochastischer Entscheidungsprobleme.
- Das Konzept der dynamischen Programmierung zur Lösung mehrstufiger Entscheidungsprobleme
- Die Anwendung der DP auf diskrete deterministische Probleme, einschließlich der Klassifizierung von Modellen und der Lösungsansätze
- Die Einführung in die stochastische dynamische Programmierung, einschließlich der Aufgabenstellung und Beispielen
- Die Analyse von Markov-Entscheidungsprozessen, die ein zentrales Element der stochastischen DP darstellen
- Ein Ausblick auf die vielfältigen Einsatzmöglichkeiten der stochastischen dynamischen Programmierung
Zusammenfassung der Kapitel
Die Arbeit beginnt mit einer Einführung in das Konzept der dynamischen Programmierung. Die grundlegende Idee, Entscheidungsprobleme in eine Sequenz von Teilproblemen zu zerlegen, wird erläutert. Anschließend werden diskrete deterministische Probleme behandelt, wobei die verschiedenen Modelle und Lösungsansätze, wie das Optimalitätsprinzip von Bellman, vorgestellt werden.
Im nächsten Kapitel wird die stochastische dynamische Programmierung behandelt, die sich mit Entscheidungsproblemen befasst, bei denen Unsicherheiten auftreten. Die Aufgabenstellung und verschiedene Beispiele werden erläutert. Schließlich werden Markov-Entscheidungsprozesse, die einen zentralen Bestandteil der stochastischen DP darstellen, analysiert.
Schlüsselwörter
Dynamische Programmierung, stochastische dynamische Programmierung, diskrete deterministische Probleme, Entscheidungsprozesse, Markov-Entscheidungsprozesse, Optimalitätsprinzip, Rekursion, Unsicherheit, Zustand, Entscheidung, Ertrag, Wert, Übergangswahrscheinlichkeit, Zustandswahrscheinlichkeit.
- Quote paper
- Dipl.-Winf. Anja Zschau (Author), 2001, Grundzüge der stochastischen dynamischen Programmierung, Munich, GRIN Verlag, https://www.hausarbeiten.de/document/9069
