1

Dynamic ProgrammingDynamic Programming

oder doch

Optimale Kontrolle?

2

EntscheidungsbaumEntscheidungsbaum

3

Entscheidungsbaum (Bsp)Entscheidungsbaum (Bsp)

4

DynamischDynamisch

Die Güte einer Entscheidung wird nicht nur an ihrer momentanten Wirkung, sondern auch an ihrem Einfluß auf den Prozeß (Ablauf eines Systems) als Ganzes gemessen.

5

Definition eines SystemsDefinition eines Systems

Eine Sammlung von Objekten, angeordnet in einer strukturierten Form, welche in einem gewissen Maße, Zweck oder Ziel orientiert ist

6

Charakterisierung eines Charakterisierung eines SystemsSystems

• Systemgrenzen, Systemelemente• Inputs/Outputs• Bezug innerhalb des Systems

7

Klassifikation von Klassifikation von SystemenSystemen

• Statisch oder dynamisch• Linear oder nicht linear• Zeit variant oder Zeit invariant• Deterministisch oder stochastisch• Zeit kontinuierlich oder (Zeit) diskret• Parameter konzentriert oder Parameter

verteilt

8

Das Konzept des Das Konzept des ZustandesZustandes

Zustandsvariablenmodellierung:

Der Zustand eines Systems wird durch einen Vektor explizit angegeben. Die Komponenten dieses Vektors sind Funktionen der Zeit.

9

Das Konzept des Das Konzept des ZustandesZustandes

Der Zustand eines Systems ist ein Maß für das Niveau der Aktivität in jeder Komponente des Systems und kann als Interface zwischen der Vergangenheit und der Zukunft der System-zeitgeschichte interpretiert werden.

10

OptimalesOptimales Kontrollproblem Kontrollproblem

• System, das über die Zeit kontrolliert werden soll.

• Gewünschter Output.• Zulässige Inputs, die über die Zeit

kontrolliert werden können.• Ein Performance Index (Kosten

Funktional).

11

Optimales KontrollmodellOptimales Kontrollmodell

• Zustandsgleichungen• Set von Randbedingungen der

Zustands- und Kontrollvariablen.• Restriktionen (Gleichheits;

Ungleichheit).

Optimale zulässige Kontrolle

12

Dynamische Dynamische ProgrammierungProgrammierung

Es existiert keine Standardform der Dynamischen Programmierung, in der sich jedes sequentielle Entscheidungsproblem schreiben läßt.

13

DP ModellDP Modell

Nnuxfx

xxts

xSuxFJ

nnnn

NNnn

N

n nun

,...,1),(

..

)(),(max

1

1

111

nn

nn

u

Xx

}),(|{)( 1 nnnnnnn XxfxIu

14

Dynamische Dynamische ProgrammierungProgrammierung

• Deterministische, mit endlich vielen Stufen

• Deterministische, mit abzählbar, unendlich vielen Stufen

• Kontinuierliche Deterministische• Stochastische

15

BspBsp

16

17

WertfunktionWertfunktion

)(),(max)( 11,...,);(

NN

N

nmmmm

xxNnmxIu

n xSuxFxV

n

mmm

)()( 1111 NNNN xSxV

18

BreakBreak