Diskrete Dynamische Optimierung

Der Verfahren der diskreten dynamischen Optimierung basiert auf Bellmans Optimalitätsprinzip und wird genutzt um verschiedene Prozesse zu optimieren. Das Problem ist dabei wie folgt aufgebaut:

• Es gibt mehrere Stufen, in jeder Stufe gibt es
  • Eine Menge von möglichen Zuständen
  • Eine Menge von Entscheidungen
• Durch eine Entscheidung kann man von einer Stufe in die nächste übergehen
• Eine Entscheidung für eine Stufe hängt nur vom Zustand der Vorstufe ab

Modellierung als Graph

Solche Probleme lassen sich als Graph modellieren:

• Zustände, die das System einnehmen kann, werden als Knoten modelliert
• Entscheidungen, die man treffen kann, werden als Kanten modelliert

Beispiel Postkutschenproblem

Das Postkutschenproblem eignet sich gut zur Veranschaulichung solcher bisher nur abstrakter Probleme:

Ein Reisender will per Postkutsche vom Westen in den Osten der USA reisen. Dabei sucht er die sicherste Strecke. Jede Teilstrecke ist unterschiedlich gefährlich. Gesucht wird nun die sicherste Strecke.

Mathematisch könnte man die “Gefährlichkeit” einer Teilstrecke z.B. durch Lebensversicherungs-Kosten ausdrücken. Dann wäre die Gesamtstrecke mit den geringsten Kosten die sicherste Strecke.

Folgendes Beispiel zeigt ein Problem mit 5 Schichten als Graph modelliert:

graph LR
  subgraph Stufe 0
    A
  end

  subgraph Stufe 1
    B
    C
    D
  end

  subgraph Stufe 2
    E
    F
    G
  end

  subgraph Stufe 3
    H
    I
  end

  subgraph Stufe 4
    Z
  end

  A-- 2 -->B;
  A-- 4 -->C;
  A-- 3 -->D;
  B-- 7 -->E;
  B-- 4 -->F;
  B-- 6 -->G;
  C-- 3 -->E;
  C-- 2 -->F;
  C-- 4 -->G;
  D-- 4 -->E;
  D-- 1 -->F;
  D-- 5 -->G;
  E-- 1 -->H;
  E-- 4 -->I;
  F-- 6 -->H;
  F-- 3 -->I;
  G-- 3 -->H;
  G-- 3 -->I;
  H-- 3 -->Z;
  I-- 4 -->Z;

Definitionen

• Die Zustandsvariable repräsentiert den Zustand des Systems in einer Stufe (Im Beispiel oben wäre )
• Die Entscheidungsvariable repräsentiert die Entscheidung, die in Stufe getroffen wird (Im Beispiel oben wäre )
• Die Kosten- bzw. Entscheidungsfunktion gibt die Kosten für eine Entscheidung an, die im Zustand getroffen wird: (Im Beispiel oben wäre )
• Die Transformationsfunktion gibt an, in welchen Zustand das System in Stufe übergeht, wenn es sich in Stufe im Zustand befindet und die Entscheidung getroffen wird

Berechnung

Vorwärtsrechnung

Dabei wird an jeder Stufe der beste/günstigste Nachfolger gewählt.

Im Beispiel oben wäre das A —2-> B —4-> F —3-> I —4-> Z (insgesamte Kosten = 13)

Rückwärtsinduktion

Dabei wird die Lösung vom Ziel her in Stufen bis zum Start ermittelt. Formal wird dafür eine stufenbezogene Zielfunktion definiert. Diese addiert

• Die unmittelbaren Kosten beim Übergang von Zustand nach und
• Die mittelbaren Kosten vom Zustand bis zum Endpunkt

Im Beispiel wird bei angefangen, eine Stufe zurück gegangen und dabei die günstigsten Pfade notiert. So wird immer weiter verfahren.

Im Beispiel oben würde der erste Schritt Rückwärts so aussehen:

Von	Kosten
H	3
I	4

Der nächste Schritt:

Von	Kosten	Kosten	Minimum	Ergebnis
E	1+3=4	4+4=8	4	H
F	6+3=9	3+4=7	7	I
G	3+3=6	3+4=7	6	H

Allgemeine Formulierung

Probleme der DO lassen sich auch allgemein notieren. Dafür wird zusätzlich zu den Definitionen definiert:

• ist der Anfangszustand
• ist die Anzahl der Stufen
• ist die Zustandsmenge, also die Menge der Zustände, in denen sich das System in Stufe befinden kann
• ist die Entscheidungsmenge, also die Menge aller Entscheidungen, aus denen in Stufe , vom Zustand ausgehend, gewählt werden kann

Die Problemstellung lautet dann:

Unter den Nebenbedingungen: