Grundzüge der stochastischen dynamischen Programmierung

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.