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
1 Einleitung – Dynamische Programmierung
1.1 Allgemeine Form von (diskreten) dynamischen Programmen
1.2 Diskrete deterministische Probleme
1.2.1 Klassifizierung von dynamischen Programmen
1.2.2 Ein Bestellmengenproblem
1.3 Lösungsansätze für diskrete deterministische Probleme
1.3.1 Das Optimalitätsprinzip von Bellman
1.3.2 Rückwärts-Vorwärts-Rekursion
1.3.3 Vorwärts-Rückwärts-Rekursion
2 Stochastische dynamische Programmierung
2.1 Aufgabenstellung der stochastischen dynamischen Programmierung
2.2 Beispiele
2.2.1 Unbekannter Ertrag der aktuellen Periode, bekannter Zustand der nächsten Periode
2.2.2 Maximierung der Wahrscheinlichkeit für das Eintreten eines Ereignisses
3 Markov-Entscheidungsprozesse
3.1 Übergangs- und Zustandswahrscheinlichkeiten
3.2 Ertrag und Wert eines Prozesses
3.3 Beispiel
4 Ausblick
Zielsetzung und Themenfelder
Die Arbeit erläutert die Grundzüge der stochastischen dynamischen Programmierung und deren Anwendung bei sequentiellen Entscheidungsprozessen unter Unsicherheit. Ziel ist es, Methoden zur Ermittlung optimaler Politiken bei mehrstufigen Optimierungsproblemen aufzuzeigen und durch praxisnahe Beispiele zu verdeutlichen.
- Grundlagen der deterministischen dynamischen Programmierung
- Stochastische Einflussfaktoren in Optimierungsproblemen
- Bellman’sche Funktionalgleichungen und Rekursionsverfahren
- Markov-Entscheidungsprozesse mit unendlichem Planungshorizont
Auszug aus dem Buch
Unbekannter Ertrag der aktuellen Periode, bekannter Zustand der nächsten Periode
Die Supermarktkette SUPERSPAR kauft täglich 6 Flaschen Milch zum Preis von je € 1 pro Flasche von einer Molkerei. Jede Milchflasche wird in einer der 3 Filialen der SUPERSPAR zum Preis von jeweils € 2 verkauft. Die Molkerei ist vertraglich verpflichtet, nicht verkaufte Flaschen für jeweils € 0,5 zurückzukaufen. Unglücklicherweise ist die Nachfrage in den 3 SUPERSPAR-Filialen ungewiss. Daten früherer Perioden zeigen die folgende (tägliche) Nachfrage:
SUPERSPAR möchte nun die 6 Flaschen so auf die Filialen verteilen, dass der erwartete Gewinn maximal wird. Da die Kosten € 6 pro Tag betragen, konzentrieren wir uns auf den täglich erwarteten Ertrag. ri(gi): erwarteter Ertrag aus dem Verkauf von gi Flaschen in Filiale i. fi(z): maximal erwarteter Ertrag aus dem Verkauf von z Flaschen in den Filialen i,i+1,...,3. f3(z) ist nach dieser Definition der erwartete Ertrag aus dem Verkauf von z Flaschen in Filiale 3. Es folgt: f3(z) = r3(z).
Zusammenfassung der Kapitel
1 Einleitung – Dynamische Programmierung: Einführung in das allgemeine Prinzip sequentieller Entscheidungsprobleme und die Zerlegung von Optimierungsproblemen in Teilprobleme.
2 Stochastische dynamische Programmierung: Erweiterung des deterministischen Ansatzes um stochastische Einflüsse, insbesondere bei Lagerhaltungsproblemen, unter Verwendung der Bellman’schen Funktionalgleichung.
3 Markov-Entscheidungsprozesse: Analyse von Entscheidungsprozessen mit unendlich langem Planungshorizont unter Nutzung von Übergangsmatrizen und ökonomischen Werten.
4 Ausblick: Diskussion der Komplexität stochastischer dynamischer Programmierung und Verweis auf alternative Lösungsverfahren wie Lineare Programmierung oder heuristische Methoden.
Schlüsselwörter
Stochastische dynamische Programmierung, Optimalitätsprinzip, Bellman-Gleichung, Markov-Entscheidungsprozess, Sequentielle Entscheidung, Übergangswahrscheinlichkeit, Optimierung, Ertragswert, Strategie, Politik, Planungshorizont, Entscheidungsbaum, Rekursionsverfahren, Lagerhaltung, Zielfunktion.
Häufig gestellte Fragen
Worum geht es in dieser Arbeit grundsätzlich?
Die Arbeit behandelt die methodischen Grundlagen der stochastischen dynamischen Programmierung und deren Anwendung zur Lösung von mehrstufigen Entscheidungsproblemen, bei denen Unsicherheiten eine Rolle spielen.
Was sind die zentralen Themenfelder?
Die Schwerpunkte liegen auf deterministischen und stochastischen dynamischen Programmen, dem Bellman’schen Optimalitätsprinzip sowie den Markov-Entscheidungsprozessen.
Was ist das primäre Ziel der Untersuchung?
Das Ziel ist die Vermittlung der Lösungsansätze für sequentielle Entscheidungsprobleme, um bei gegebenen Zuständen eine optimale Politik für den gesamten Planungszeitraum zu finden.
Welche wissenschaftlichen Methoden werden verwendet?
Es werden mathematische Optimierungsverfahren wie Rückwärts- und Vorwärts-Rekursionen, Bellman-Gleichungen sowie mathematische Modellierungen von Markov-Ketten genutzt.
Was wird im Hauptteil der Arbeit behandelt?
Der Hauptteil gliedert sich in die formale Beschreibung der dynamischen Programmierung, deren stochastische Erweiterung und die detaillierte Betrachtung von Markov-Entscheidungsprozessen inklusive Anwendungsbeispielen.
Welche Schlüsselwörter charakterisieren die Arbeit?
Wichtige Begriffe sind insbesondere die dynamische Programmierung, das Optimalitätsprinzip, die Bellman-Gleichung und stochastische Entscheidungsprozesse.
Wie werden Milchflaschen in den Filialen optimal verteilt?
Die optimale Verteilung wird durch eine rückwärts gerichtete dynamische Programmierung bestimmt, bei der der erwartete Ertrag der einzelnen Filialen sukzessive maximiert wird.
Was unterscheidet das "aktive" vom "passiven" Management im Beispiel?
Im Beispiel werden vier Strategien unterschieden, die definieren, ob das Management in den Zuständen "Betrieb stockt" oder "Betrieb läuft" tätig (k=1) oder untätig (k=0) bleibt, was unterschiedliche Auswirkungen auf Übergangswahrscheinlichkeiten und Erträge hat.
- Quote paper
- Dipl.-Winf. Anja Zschau (Author), 2001, Grundzüge der stochastischen dynamischen Programmierung, Munich, GRIN Verlag, https://www.grin.com/document/9069
