Es sei nun beliebig, und die Behauptung gelte für dieses . Nun ist nach der Induktionsannahme zu zeigen, daß die Beziehung in (4.1.35) auch für gilt, d.h.:
für
und jede beliebige zulässige Entscheidungspolitik . Mit (4.1.26) gilt nun
Im folgenden sei nun wieder Wir stellen uns weiter vor, daß beliebig aber fest gewählt wird. Dann gilt mithilfe der Induktionsannahme:
Diese Beziehung gilt für alle und alle zulässigen .[sic!] Wir bilden nun auf der linken Seite das Maximum hinsichtlich . [sic!]
Ein optimales wird dann wieder mit bezeichnet. Somit erhalten wir
Wenn wir wieder als variabel ansehen und dann bzw. setzen, dann bleibt die letzte Bedingung für alle gültig.
Da somit eine optimale Politik für einen Teilprozeß nur den von abhängigen Wert liefert, ist es möglich, den folgenden wichtigen Satz [uNS80] zu formulieren, der eine Form des Bellmannschen Optimalitätsprinzips darstellt:
Satz 4.1.6 Es seien (4.1.32) wieder die Bellmannschen Funktionalgleichungen. Dann gibt es eine optimale Strategie des erst auf der Stufe beginnenden Teilprozesses , die nur von dem Eingangszustand abhängt.
|
Wir nehmen nun an, der Satz gelte für beliebiges Dann ist zu zeigen, daß er auch für gilt. Die Induktionsannahme lautet
für und jede beliebige zulässige Entscheidungspolitik . Nun ist wegen (1.31)
Wir setzten wieder für festes und erhalten nach der Induktionsannahme
mit und für alle zulässigen
Auf der linken Seite dieser Ungleichung wird das Maximum bezüglich gebildet. Ein maximierendes wird wieder mit bezeichnet; dann gilt:
Für die linke Seite gilt laut Induktionsannahme und wegen (1.31) und (1.36):
Wenn wir wieder als variabel ansehen und dann bzw. setzen, bleibt die letzte Bedingung für gültig. Dann folgt aus (1.37)
für jede zulässige Entscheidungspolitik .
Somit ist der Induktionsnachweis erbracht und der Satz bewiesen. Die Bellmannschen Funktionalgleichungen können somit als hinreichende Bedingungen für optimale Entscheidungspolitiken angesehen werden.
Eine optimale Politik eines mit dem Anfangszustand beginnenden Teilprozesses liefert den nur von abhängigen Wert (1.34)
Eine Änderung der vorhergehenden Entscheidungsfunktionen des Gesamtprozesses , die den Zustand zu Beginn der -ten Stufe nicht ändert, beeinflußt den Wert von nicht. Somit gilt der
Satz 1.2: Es gibt eine optimale Politik eines auf der Stufe beginnenden -stufigen Teilprozesses , die nur von dem Eingangszustand und nicht von den vorhergehenden Entscheidungen abhängt.
|