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
- Anhang
- Literaturverzeichnis
Zielsetzung und Themenschwerpunkte
Die Arbeit befasst sich mit den Grundzügen der stochastischen dynamischen Programmierung. Sie stellt ein umfassendes Konzept zur Lösung mehrstufiger Entscheidungsprobleme dar, wobei die Unsicherheit über zukünftige Entwicklungen berücksichtigt wird. Die Arbeit beleuchtet sowohl deterministische als auch stochastische dynamische Programmierungsprobleme und zeigt anhand von Beispielen die Anwendung in verschiedenen Bereichen, wie z.B. Bestellmengenproblemen, Lagerhaltung und Entscheidungsfindung unter Unsicherheit.
- Grundlagen der dynamischen Programmierung
- Stochastische Einflüsse in Entscheidungsproblemen
- Anwendung der stochastischen dynamischen Programmierung
- Markov-Entscheidungsprozesse
- Optimierungsprobleme mit unendlich großem Horizont
Zusammenfassung der Kapitel
Das erste Kapitel führt in die dynamische Programmierung ein und beschreibt die allgemeine Form von diskreten dynamischen Programmen. Es werden die wichtigsten Konzepte, wie das Optimalitätsprinzip von Bellman und die Rückwärts-Vorwärts-Rekursion, vorgestellt. Das Kapitel erläutert auch die Klassifizierung von dynamischen Programmen anhand verschiedener Kriterien, wie z.B. Zeitabstände der Perioden, Informationsgrad über die Störgrößen und Ein- oder Mehrvertigkeit der Zustands- und Entscheidungsvariablen.
Das zweite Kapitel widmet sich der stochastischen dynamischen Programmierung und behandelt die Aufgabenstellung sowie die Herausforderungen, die durch stochastische Einflüsse entstehen. Anhand von Beispielen wird gezeigt, wie unbekannte Erträge und Zustände in der nächsten Periode in der Entscheidungsproblematik berücksichtigt werden können. Ein weiteres Beispiel illustriert die Maximierung der Wahrscheinlichkeit für das Eintreten eines Ereignisses mithilfe der stochastischen dynamischen Programmierung.
Das dritte Kapitel beschäftigt sich mit Markov-Entscheidungsprozessen, einem wichtigen Werkzeug zur Lösung von Optimierungsproblemen mit unendlich großem Horizont. Es werden die Übergangs- und Zustandswahrscheinlichkeiten sowie der Ertrag und Wert eines Prozesses erläutert. Anhand eines Beispiels wird die Anwendung von Markov-Entscheidungsprozessen in der Praxis dargestellt.
Schlüsselwörter
Die Schlüsselwörter und Schwerpunktthemen des Textes umfassen die dynamische Programmierung, stochastische Optimierung, Entscheidungsprozesse, Markov-Entscheidungsprozesse, Optimierungsprobleme mit unendlich großem Horizont, Bestellmengenproblem, Lagerhaltung, Wahrscheinlichkeit, Ertrag, Wert, Übergangs- und Zustandswahrscheinlichkeiten. Der Text beleuchtet die Anwendung der stochastischen dynamischen Programmierung in verschiedenen Bereichen und bietet einen umfassenden Überblick über die wichtigsten Konzepte und Methoden.
- Citar trabajo
- Dipl.-Winf. Anja Zschau (Autor), 2001, Grundzüge der stochastischen dynamischen Programmierung, Múnich, GRIN Verlag, https://www.grin.com/document/9069
-
¡Carge sus propios textos! Gane dinero y un iPhone X. -
¡Carge sus propios textos! Gane dinero y un iPhone X. -
¡Carge sus propios textos! Gane dinero y un iPhone X. -
¡Carge sus propios textos! Gane dinero y un iPhone X. -
¡Carge sus propios textos! Gane dinero y un iPhone X. -
¡Carge sus propios textos! Gane dinero y un iPhone X. -
¡Carge sus propios textos! Gane dinero y un iPhone X. -
¡Carge sus propios textos! Gane dinero y un iPhone X.