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
Anhang
Literaturverzeichnis
1 Einleitung - Dynamische Programmierung
Die dynamische Programmierung (DP) ist ein allgemeines Prinzip zur Lösung mehrstufiger oder sequentieller Entscheidungsprobleme.[1]
Sie bietet also 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.[2]
1.1 Allgemeine Form von (diskreten) dynamischen Programmen
- Das Optimierungsproblem kann in eine Sequenz zeitlich und / oder logisch geordneter Teilprobleme (Stufen) zerlegt werden. Pro Stufe ist dabei eine Entscheidung erforderlich, ein Entscheidungsprozess (EP) mit n < ¥ aufeinander folgenden Stufen stellt die Lösung des Gesamtproblems dar.
- Aus der Menge Zi wird jeder Stufe i (i = 1,...,n) ein Element zi zugeordnet.
zi kennzeichnet dabei den Zustand des EP in der i -ten Stufe.
- Die Entscheidungsalternativen einer Stufe i sind abhängig von der jeweiligen Stufe i und dem Zustand zi des EP.
Ei(zi) für alle zi Î Zi bezeichnet die Menge der zulässigen Entscheidungsalternativen.
ei Î Ei(zi) ist die zulässige Entscheidung in der Stufe i.
Trifft man in Stufe i im Zustand zi die Entscheidung ei Î Ei(zi), dann legt (zi,ei) den Zustand zi+1 in der nächsten Stufe fest:
Abbildung in dieser Leseprobe nicht enthalten
mit gi: Transformationsfunktion der Stufe i.
- Die Zielfunktion F des Gesamtproblems besitzt die Form:
Abbildung in dieser Leseprobe nicht enthalten
mit fi(zi,ei): additiver Beitrag zur Zielfunktion aus der Entscheidung ei im Zustand zi in
Stufe i.
Abbildung in dieser Leseprobe nicht enthalten
Eine zulässige Folge (e1,...,en) von Entscheidungen heißt Politik oder Strategie. Eine Politik (e1*,...,en*), die die Zielfunktion F optimiert, heißt optimale Politik oder optimale Strategie.
1.2 Diskrete deterministische Probleme
1.2.1 Klassifizierung von dynamischen Programmen
Modelle der DP lassen sich klassifizieren nach
- den Zeitabständen der Perioden bzw. Stufen:
kontinuierliche oder diskrete Modelle[3]
- dem Informationsgrad über die Störgrößen bi:
deterministische oder stochastische Modelle
- der Ein- oder Mehrwertigkeit der Zustands- und Entscheidungsvariablen:
uni- oder multivariate Modelle
- der Endlichkeit oder Unendlichkeit der Mengen Zi bzw. Ei möglicher Zustände
bzw. Entscheidungen:
endliche oder unendliche Mengen
1.2.2 Ein Bestellmengenproblem
Betrachtungsgegenstand ist ein einfaches Bestellmengenproblem. Die Stufen, in welche der EP unterteilt werden kann, entsprechen (Zeit-) Perioden.
Die Einkaufsabteilung eines Unternehmens muss für vier aufeinanderfolgende Perioden eine bestimmte Menge eines Rohstoffes bereitstellen, damit ein Produktionsprogramm erstellt werden kann. Die Rohstoffmenge ist dabei in jeder Periode gleich groß.
Die Einkaufspreise sind für jede Periode im voraus bekannt:
Abbildung in dieser Leseprobe nicht enthalten
(Quelle: Domschke / Drexl)
Der Lieferant kann (bei vernachlässigbarer Lieferzeit) in einer Periode maximal den Bedarf für zwei Perioden liefern.
Auch die Lagerkapazität ist auf den Bedarf zweier Perioden beschränkt.
Ferner gilt:
- Zu Beginn der 1. Periode ist das Lager leer (z0 = 0).
- Am Ende der 4. Periode soll der Bestand wieder auf 0 abgesunken sein (z4 = 0).
Auf die Erfassung von Lagerkosten soll vereinfachend verzichtet werden.
Welche Mengen xi sind zu den verschiedenen Zeitpunkten einzukaufen, so dass die Beschaffungskosten K möglichst gering bleiben?
Abbildung in dieser Leseprobe nicht enthalten
unter den Nebenbedingungen:
Abbildung in dieser Leseprobe nicht enthalten
1 2 3 4
Abb. 1: Zustände des Lagers in den Perioden i
(In Anlehnung an: Domschke / Drexl)
1.3 Lösungsansätze der dynamischen Programmierung
1.3.1 Das Optimalitätsprinzip von Bellman
Satz: Sei (e1*,..., ej-1*, ej*,..., en*) eine optimale Politik für das DP aus Definition[4]
(1) mit deterministischen Zuständen, dann gilt:
1) (e1*,..., ej-1*) ist eine optimale Politik für das Teil-DP:
Abbildung in dieser Leseprobe nicht enthalten
1.3.2 Rückwärts-Vorwärts-Rekursion ( <-- )
Für jede Stufe i und jeden Zustand zi Î Zi bezeichnet die Funktion [4]
Abbildung in dieser Leseprobe nicht enthalten
Iteration: i = n, n-1, n-2
Bestimme für ein gegebenes i und jedes zi Î Zi den Wert
Abbildung in dieser Leseprobe nicht enthalten
( sog. „Bellman’sche Funktionalgleichung“)
Vorwärtsrechnung: Nach der n -ten Iteration (i = 1) erhält man den Ziel-
funktionswert der optimalen Politik des DP:
F1*(z1) = F(e1*,..., en*)
Die optimale Politik kann in einer Vorwärtsrechnung explizit
ermittelt werden.
1.3.3 Vorwärts-Rückwärts-Rekursion ( --> )
Abbildung in dieser Leseprobe nicht enthalten
Rückwärtsiteration: i = n, n-1,...,1
Ermittle en*,e*n-1,...,e1*.
Sonderfälle: Probleme mit mehreren Start- und / oder Endzuständen.
Man führt dabei fiktive kosten- bzw. nutzenneutrale Anfangs-
und / oder Endzustände ein.
2 Stochastische Dynamische Programmierung
Bei vielen aus der Praxis stammenden dynamischen Optimierungsproblemen treten 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, oben bereits erläuterten deterministischen Probleme.[5]
[...]
[1] Vgl. Mitschrift zur Vorlesung „Standardmodelle des Operations Research“ im WS 2000/2001
[2] Vgl. Domschke, W.; Drexl, A.: Einführung in Operations Research, 3. Aufl., Springer-Verlag, Berlin u.a.,
1995, S. 143 ff.
[3] Vgl. Domschke, W.; Drexl, A.: Einführung in Operations Research, a.a.O., S. 145 ff.
[4] Vgl. Mitschrift zur Vorlesung „Standardmodelle des Operations Research“ im WS 2000/2001
[5] Vgl. Neumann, K.; Morlock, M.: Operations Research, Carl Hanser Verlag, München u.a., 1993, S. 615 ff.
-
Upload your own papers! Earn money and win an iPhone X. -
Upload your own papers! Earn money and win an iPhone X. -
Upload your own papers! Earn money and win an iPhone X. -
Upload your own papers! Earn money and win an iPhone X. -
Upload your own papers! Earn money and win an iPhone X. -
Upload your own papers! Earn money and win an iPhone X. -
Upload your own papers! Earn money and win an iPhone X. -
Upload your own papers! Earn money and win an iPhone X.