教案_動態(tài)規(guī)劃1_1

1、動態(tài)規(guī)劃動態(tài)規(guī)劃（Dynamic Programming） R. Bellman50年代執(zhí)教于普林斯頓和斯坦福大學(xué)，年代執(zhí)教于普林斯頓和斯坦福大學(xué)，后進(jìn)入蘭德（后進(jìn)入蘭德（Rand）研究所。）研究所。1957年發(fā)表年發(fā)表“Dynamic Programming”一書，標(biāo)識動態(tài)規(guī)劃的正式誕生。一書，標(biāo)識動態(tài)規(guī)劃的正式誕生。 動態(tài)規(guī)劃的研究對象和引例動態(tài)規(guī)劃的理論基礎(chǔ)和具體迭代方動態(tài)規(guī)劃的理論基礎(chǔ)和具體迭代方 法法動態(tài)規(guī)劃的基本思想和基本方程動態(tài)規(guī)劃的基本思想和基本方程動態(tài)規(guī)劃的基本概念和定義動態(tài)規(guī)劃的基本概念和定義 動態(tài)規(guī)劃是解決復(fù)雜系統(tǒng)優(yōu)化問題的一種方法。是動態(tài)規(guī)劃是解決復(fù)雜系統(tǒng)優(yōu)化問題的一種

2、方法。是解決解決動態(tài)系統(tǒng)多階段動態(tài)系統(tǒng)多階段決策過程的基本方法之一決策過程的基本方法之一。AB1B2C1C2C3C4D1D2D3E1E2E3F1F2G531368766835338422123335526643123456第一節(jié) 動態(tài)規(guī)劃的引例和研究對象引例引例1 最短路問題最短路問題一、一、 引例引例引例引例2：投資金額分配問題：投資金額分配問題投資項目投資額（百萬元）0 1 2 3 4ABC 41 48 60 66 42 50 60 6648 64 68 78 76 某公司有資金4百萬元，可以向 A、B、C三個項目追加投資，各項目可以有不同的投資額，相應(yīng)的效益值如表所示。如何分配資金使總效

3、益值最大？狀態(tài)（未分的資金額）決策（分配資金額） 0 1 2 3 4最優(yōu)決策最優(yōu)決策的效益值01234- - - -48 64 - - -48 64 68 - -48 64 68 78 -48 64 68 78 760123348646878781.對于項目C投資項目投資額（百萬元）0 1 2 3 4ABC 41 48 60 66 42 50 60 6648 64 68 78 76 求解過程2.對于項目B狀態(tài)對B的決策C的狀態(tài)B的效益值C的效益值最優(yōu)總效益值011222333344444001012012301234010210321043210404042404250404250604042

4、506066486448686448786864487878686448881049010810698118110114108118120118124114狀態(tài)（未分的資金額）決策（分配資金額） 0 1 2 3 4最優(yōu)決策最優(yōu)決策的效益值0123488 - - - -104 90 - - -108 106 98 - -118 110 114 103 -118 120 118 124 1140000388104108118124狀態(tài)（未分的資金額）決策（分配資金額） 0 1 2 3 4最優(yōu)決策最優(yōu)決策的效益值4162 159 156 164 15431643.對于A項目對于項目B最優(yōu)決策：A項目

5、3萬，B項目0萬，C項目1萬 包含包含隨時間變化隨時間變化的因素和變量的系統(tǒng)。的因素和變量的系統(tǒng)。系統(tǒng)在某個時刻的狀態(tài)，往往要依某系統(tǒng)在某個時刻的狀態(tài)，往往要依某種形式受過去某些決策的影響；種形式受過去某些決策的影響；將時間作為決策變量之一的決策問將時間作為決策變量之一的決策問題稱為動態(tài)決策問題。題稱為動態(tài)決策問題。如經(jīng)濟(jì)系統(tǒng)如經(jīng)濟(jì)系統(tǒng),生產(chǎn)系統(tǒng)等生產(chǎn)系統(tǒng)等。動態(tài)系統(tǒng)動態(tài)系統(tǒng)： 線性系統(tǒng)、非線性系統(tǒng)。線性系統(tǒng)、非線性系統(tǒng)。動態(tài)系統(tǒng)動態(tài)系統(tǒng)的特點：的特點： 動態(tài)決策動態(tài)決策 問題：問題：而系統(tǒng)的當(dāng)前狀態(tài)和決策又會影響而系統(tǒng)的當(dāng)前狀態(tài)和決策又會影響系統(tǒng)今后的發(fā)展。系統(tǒng)今后的發(fā)展。二、動態(tài)規(guī)劃的研究

6、對象每個階段都要進(jìn)行每個階段都要進(jìn)行決策決策,目的是使整個過程的決策目的是使整個過程的決策 達(dá)到最優(yōu)效果。達(dá)到最優(yōu)效果。多階段決策問題：多階段決策問題：是動態(tài)決策問題的一種特殊形式；是動態(tài)決策問題的一種特殊形式；在多階段決策過程中在多階段決策過程中,系統(tǒng)的動態(tài)過程可以按照時間系統(tǒng)的動態(tài)過程可以按照時間進(jìn)程分為進(jìn)程分為狀態(tài)狀態(tài)相互相互聯(lián)系聯(lián)系而又相互而又相互區(qū)別區(qū)別的各個的各個階段階段；多階段決策問題的典型例子：多階段決策問題的典型例子： 12n狀態(tài)狀態(tài)決策決策狀態(tài)狀態(tài)決策決策狀態(tài)狀態(tài)狀態(tài)狀態(tài)決策決策生產(chǎn)存貯決策問題生產(chǎn)存貯決策問題最短路問題最短路問題機器負(fù)荷分配問題機器負(fù)荷分配問題資源分配問題

7、資源分配問題 但要便于把問題的過程能轉(zhuǎn)化為多階段決策但要便于把問題的過程能轉(zhuǎn)化為多階段決策 的過程。的過程。 狀態(tài)變量的取值有一定的允許集合或范圍，此集狀態(tài)變量的取值有一定的允許集合或范圍，此集合稱為合稱為狀態(tài)允許集合狀態(tài)允許集合。 第二節(jié)第二節(jié) 動態(tài)規(guī)劃的基本概念和定義動態(tài)規(guī)劃的基本概念和定義 1. 階段、階段變量階段、階段變量 把所給問題的過程，適當(dāng)?shù)胤譃槿舾蓚€相互聯(lián)系把所給問題的過程，適當(dāng)?shù)胤譃槿舾蓚€相互聯(lián)系的的階段階段; 描述階段的變量稱為描述階段的變量稱為階段變量階段變量，常用，常用k表示；表示； 階段的劃分，一般是按時間和空間的自然特征來階段的劃分，一般是按時間和空間的自然特征來劃

8、分劃分 ；2. 狀態(tài)、狀態(tài)變量狀態(tài)、狀態(tài)變量每個階段開始所處的自然狀態(tài)或客觀條件。每個階段開始所處的自然狀態(tài)或客觀條件。通常一個階段有若干個狀態(tài)。通常一個階段有若干個狀態(tài)。 描述過程狀態(tài)的變量稱為描述過程狀態(tài)的變量稱為狀態(tài)變量狀態(tài)變量，常用，常用sk表示表示第第k階段的狀態(tài)。階段的狀態(tài)。年、月、年、月、路段路段一個數(shù)、一個數(shù)、一組數(shù)、一組數(shù)、一個向量一個向量 在實際問題中決策變量的取值往往在某一范圍在實際問題中決策變量的取值往往在某一范圍之內(nèi)，此范圍稱為之內(nèi)，此范圍稱為允許決策集合允許決策集合。常用。常用Dk(sk)表示第表示第k階段從狀態(tài)階段從狀態(tài)sk出發(fā)的允許決策集合，顯然有出發(fā)的允許決策

9、集合，顯然有 一個數(shù)一個數(shù)一組數(shù)一組數(shù)一個向量一個向量決定下一階段的狀態(tài)，這種決定稱為決定下一階段的狀態(tài)，這種決定稱為決策決策。在最優(yōu)控制中也稱為在最優(yōu)控制中也稱為控制控制。描述決策的變量，稱為描述決策的變量，稱為決策變量。決策變量。決策變量是狀態(tài)變量的函數(shù)。決策變量是狀態(tài)變量的函數(shù)。常用常用uk(sk) 表示第表示第k階段當(dāng)狀態(tài)為階段當(dāng)狀態(tài)為 sk時的決策變量。時的決策變量。3. 決策、決策變量決策、決策變量 過程的某一階段、過程的某一階段、 某個狀態(tài)某個狀態(tài), 可以做出不同的決可以做出不同的決定定(選擇選擇),uk(sk) Dk(sk) 系統(tǒng)在某一階段的狀態(tài)轉(zhuǎn)移不但與系統(tǒng)的當(dāng)前的系統(tǒng)在某一

10、階段的狀態(tài)轉(zhuǎn)移不但與系統(tǒng)的當(dāng)前的狀態(tài)和決策有關(guān)，而且還與系統(tǒng)過去的歷史狀態(tài)和決狀態(tài)和決策有關(guān)，而且還與系統(tǒng)過去的歷史狀態(tài)和決策有關(guān)。其策有關(guān)。其狀態(tài)轉(zhuǎn)移方程狀態(tài)轉(zhuǎn)移方程如下（一般形式）如下（一般形式）),(),(),(221112211231112kkkkusususTsususTsusTs 圖示如下：圖示如下：狀態(tài)轉(zhuǎn)移方程狀態(tài)轉(zhuǎn)移方程是確定是確定過程由一個狀態(tài)到另過程由一個狀態(tài)到另一個狀態(tài)的演變過程。一個狀態(tài)的演變過程。如果第如果第k階段狀態(tài)變量階段狀態(tài)變量sk的值、該階段的決策的值、該階段的決策變量一經(jīng)確定，第變量一經(jīng)確定，第k+1階段狀態(tài)變量階段狀態(tài)變量sk+1的值的值也就確定。也就確定

11、。4. 多階段決策過程多階段決策過程 可以在各個階段進(jìn)行決策，去控制過程發(fā)展的可以在各個階段進(jìn)行決策，去控制過程發(fā)展的多段過程；多段過程； 其發(fā)展是通過一系列的狀態(tài)轉(zhuǎn)移來實現(xiàn)的；其發(fā)展是通過一系列的狀態(tài)轉(zhuǎn)移來實現(xiàn)的；12ks1u1s2u2s3skukSk+1 能用動態(tài)規(guī)劃方法求解的多階段決策過程是一能用動態(tài)規(guī)劃方法求解的多階段決策過程是一類特殊的多階段決策過程，即類特殊的多階段決策過程，即具有無后效性具有無后效性的多階的多階段決策過程。段決策過程。 如果狀態(tài)變量不能滿足無后效性的要求，應(yīng)適當(dāng)如果狀態(tài)變量不能滿足無后效性的要求，應(yīng)適當(dāng)?shù)馗淖儬顟B(tài)的定義或規(guī)定方法。地改變狀態(tài)的定義或規(guī)定方法。),(

12、),(),(122231112kkkkusTsusTsusTs 動態(tài)規(guī)劃中能動態(tài)規(guī)劃中能處理的狀態(tài)轉(zhuǎn)移處理的狀態(tài)轉(zhuǎn)移方程的形式方程的形式。 狀態(tài)具有無后效性的多階段決策過程的狀態(tài)轉(zhuǎn)狀態(tài)具有無后效性的多階段決策過程的狀態(tài)轉(zhuǎn)移方程如下移方程如下無后效性無后效性(馬爾可夫性馬爾可夫性) 如果某階段狀態(tài)給定后，則在這個階段以后過程如果某階段狀態(tài)給定后，則在這個階段以后過程的發(fā)展不受這個階段以前各段狀態(tài)的影響；的發(fā)展不受這個階段以前各段狀態(tài)的影響； 過程的過去歷史只能通過當(dāng)前的狀態(tài)去影響它未過程的過去歷史只能通過當(dāng)前的狀態(tài)去影響它未來的發(fā)展；來的發(fā)展； 構(gòu)造動態(tài)規(guī)劃模型時，要充分注意是否滿足構(gòu)造動態(tài)規(guī)劃

13、模型時，要充分注意是否滿足無后效性的要求；無后效性的要求；狀態(tài)變量要滿足無后效性的要求狀態(tài)變量要滿足無后效性的要求； 由每段的決策按順序排列組成的決策函數(shù)序列由每段的決策按順序排列組成的決策函數(shù)序列稱為稱為k子過程策略，子過程策略， 當(dāng)當(dāng)k=1時，此決策函數(shù)序列成為全過程的一個時，此決策函數(shù)序列成為全過程的一個策略，簡稱策略，簡稱策略策略，記為，記為p1,n (s1).即即 可供選擇的策略有一定范圍，此范圍稱為可供選擇的策略有一定范圍，此范圍稱為允許策允許策略集合略集合，用，用p表示。從允許策略集合中找出達(dá)到最優(yōu)表示。從允許策略集合中找出達(dá)到最優(yōu)效果的策略稱為效果的策略稱為最優(yōu)策略最優(yōu)策略。)

14、(,),(),()(11,nnkkkkknksusususp)(,),(),()(22111, 1nnnsusususp 5. 策略策略: 按順序排列的決策組成的集合；按順序排列的決策組成的集合； 由第由第k n(終止?fàn)顟B(tài)終止?fàn)顟B(tài))為止的過程，稱為問題的為止的過程，稱為問題的后部子過程后部子過程（k子過程）。子過程）。簡稱簡稱子策略子策略，記為，記為pk,n(sk)，即，即 它是定義在全過程或所有后部子過程它是定義在全過程或所有后部子過程上確定的數(shù)量函數(shù)。上確定的數(shù)量函數(shù)。 動態(tài)規(guī)劃模型的指標(biāo)函數(shù)，應(yīng)具有可分離性，動態(tài)規(guī)劃模型的指標(biāo)函數(shù)，應(yīng)具有可分離性，并滿足并滿足遞推遞推關(guān)系。關(guān)系。常見的指

15、標(biāo)函數(shù)的形式是：常見的指標(biāo)函數(shù)的形式是： 費用、成本、利潤、路長等費用、成本、利潤、路長等 。nknkkkknknksususVV, 2 , 1111,),( 用用Vk, n 表示之。表示之。6. 指標(biāo)函數(shù)和最優(yōu)值函數(shù)指標(biāo)函數(shù)和最優(yōu)值函數(shù) 用來衡量所實現(xiàn)過程優(yōu)劣的一種數(shù)量指標(biāo)，稱用來衡量所實現(xiàn)過程優(yōu)劣的一種數(shù)量指標(biāo)，稱為指標(biāo)函數(shù)；為指標(biāo)函數(shù)；即即V Vk k, ,n n可以表示為可以表示為s sk k,u,uk k, ,V Vk+1,nk+1,n的函數(shù)。的函數(shù)。常見的指標(biāo)函數(shù)的形式是：常見的指標(biāo)函數(shù)的形式是： 過程和它的任一子過程的指標(biāo)是它所包含的各過程和它的任一子過程的指標(biāo)是它所包含的各階段

16、的指標(biāo)和。即階段的指標(biāo)和。即usvsusVjjnkjjnkknk,1,無后效性的結(jié)果。無后效性的結(jié)果。 其中其中vj( (s sj ) ) 表示第表示第 j 階段的階段的階段指標(biāo)階段指標(biāo)。這時上式。這時上式可寫成可寫成),(),(),(111, 11,susVusvsusVnkknkkkknkknk 過程和它的任意子過程的指標(biāo)是它所包含的各階段過程和它的任意子過程的指標(biāo)是它所包含的各階段的指標(biāo)的的指標(biāo)的 乘乘 積積。即。即),(),(1,usvsusVjjjnkjnkknk則可改寫成則可改寫成),(),(),(111, 11,susVusvsusVnkknkkkknkknk),(,),(111

17、, 1111,nkknkkkknkkkknksusVussususV 多階段決策過程的數(shù)學(xué)模型：（具有無后效性的多階段決策過程的數(shù)學(xué)模型：（具有無后效性的多階段決策過程）多階段決策過程） 第第k階段階段 第第n階段階段 狀態(tài)狀態(tài)sk 終止?fàn)顟B(tài)終止?fàn)顟B(tài)采取最優(yōu)策略所得采取最優(yōu)策略所得到的指標(biāo)函數(shù)值。到的指標(biāo)函數(shù)值。最優(yōu)值函數(shù)最優(yōu)值函數(shù)：),()(1,susVoptsfnkknkkkuunk即即可遞推可遞推nkUuSsusTstsusvsusVoptkkkkkkkknjjjjnkknkuuun, 2 , 1),(. .),(),(111,21 多階段決策過程的數(shù)學(xué)模型：（具有無后效性）多階段決策過

18、程的數(shù)學(xué)模型：（具有無后效性）小結(jié)小結(jié):),()(1,susVoptsfnkknkkkuunk),(,111,1nkknkkkksusVus方程方程 : 狀態(tài)轉(zhuǎn)移方程狀態(tài)轉(zhuǎn)移方程),(1kkkkusTs概念概念 : 階段變量階段變量k狀態(tài)變量狀態(tài)變量sk決策變量決策變量uk;指標(biāo)指標(biāo): ),(111,nkkkknknksususVV動態(tài)規(guī)劃本質(zhì)上是多階段決策過程動態(tài)規(guī)劃本質(zhì)上是多階段決策過程; 效益效益指標(biāo)函數(shù)形式指標(biāo)函數(shù)形式: 和、和、 積積無后效性無后效性),(111,nkkkknksususV可遞推可遞推,*2*1nuuu,*2*1nsss解多階段決策過程問題，求出解多階段決策過程問題，

19、求出 最優(yōu)策略最優(yōu)策略，即最優(yōu)，即最優(yōu)決策序列決策序列susvoptsfnkknkkkuunk1,f1(s1) 最優(yōu)軌線最優(yōu)軌線，即執(zhí)行最優(yōu)策略時的即執(zhí)行最優(yōu)策略時的狀態(tài)序列狀態(tài)序列 最優(yōu)目標(biāo)函數(shù)值最優(yōu)目標(biāo)函數(shù)值),(*1*1*,1*,1nnnnususVV從從k到終點最優(yōu)策略到終點最優(yōu)策略子策略的最優(yōu)目標(biāo)函數(shù)值子策略的最優(yōu)目標(biāo)函數(shù)值第三節(jié)：動態(tài)規(guī)劃的基本思想和基本方程第三節(jié)：動態(tài)規(guī)劃的基本思想和基本方程AB1B2C1C2C3C4D1D2D3E1E2E3F1F2G531368766835338422123335526643123456375976713109111316 18 最短路的特性最短

20、路的特性：如果已有從起點到終點的一條如果已有從起點到終點的一條最短路，那么從最短路線上中間任何一點出發(fā)到終最短路，那么從最短路線上中間任何一點出發(fā)到終點的路線仍然是最短路。（證明用反證法）點的路線仍然是最短路。（證明用反證法）4AB1B2C1C2C3C4D1D2D3E1E2E3F1F2G5313687668353384221233355 26631234564k=5k=5，出發(fā)點，出發(fā)點E1E1、E2E2、E3E3 73543min,min2621516115FfFEdFfFEdu5(E1)=F1E1 F1 G 53245min,min262251612525FfFEdFfFEdfEAB1B2

21、C1C2C3C4D1D2D3E1E2E3F1F2G531368766835338422123335526643)(15Efu5(E2)=F2E2 F2 G 93646min,min262351613535FfFEdFfFEdfEu5(E3)=F2E3 F2 Gk=6k=6,F1 G f f6 6(F1)=4(F1)=4F F2 2 G ,f,f6 6(F2)=3(F2)=3k=4，f4(D4)=7 u4(D1)=E2f4(D2)=6 u4(D2)=E2f4(D3)=8 u4(D3)=E2k=2, f2(B1)=13 u2(B1)=C2 f2(B2)=16 u2(B2)=C3f3(C1)=13

22、u3(C1)=D1f3(C2)=10 u3(C2)=D1f3(C3)=9 u3(C3)=D1f3(C4)=12 u3(C4)=D3k=3,= minf1(A)= mind1(A,B1)+ f2(B1) d1(A,B2)+ f2(B2)5+133+16=18k=1,u1(A)=B1u2(B1)=C2u3(C2)=D1u4(D1)=E2AB1B2C1C2C3C4D1D2D3E1E2E3F1F2G531368766835338422123335526643u1(A)=B1u2(B1)=C2u3(C2)=D1u4(D1)=E2u5(E1)=F1E1 F1 Gu5(E2)=F2E2 F2 Gu5(E3)

23、=F2E3 F2 G7 5 9 u5(E2)=F2u6(F2)=G最優(yōu)策略最優(yōu)策略用動態(tài)規(guī)劃（逆序法求解的）基本特性：用動態(tài)規(guī)劃（逆序法求解的）基本特性： 動態(tài)規(guī)劃方法是既把當(dāng)前一段和未來各段分開，動態(tài)規(guī)劃方法是既把當(dāng)前一段和未來各段分開，又把當(dāng)前效益和未來效益結(jié)合起來考慮的一種最優(yōu)又把當(dāng)前效益和未來效益結(jié)合起來考慮的一種最優(yōu)化方法?；椒?。每段決策的選取都是從全局考慮的每段決策的選取都是從全局考慮的, ,與該段與該段的最優(yōu)選擇答案一般是不同的。的最優(yōu)選擇答案一般是不同的。 求解時求解時從邊界條件開始從邊界條件開始，逆逆（或順）過程行進(jìn)方（或順）過程行進(jìn)方向，逐段向，逐段遞推遞推尋優(yōu)。在每個問

24、題求解時，都要使用它尋優(yōu)。在每個問題求解時，都要使用它前面已求出的子問題的最優(yōu)結(jié)果，最后問題的最優(yōu)解，前面已求出的子問題的最優(yōu)結(jié)果，最后問題的最優(yōu)解，就是整個問題的最優(yōu)解。就是整個問題的最優(yōu)解。 將多階段決策過程將多階段決策過程劃分階段劃分階段，恰當(dāng)?shù)剡x取，恰當(dāng)?shù)剡x取狀態(tài)變狀態(tài)變量量、決策變量決策變量、及定義、及定義最優(yōu)指標(biāo)函數(shù)，最優(yōu)指標(biāo)函數(shù)，正確寫出基本正確寫出基本的的遞推關(guān)系式遞推關(guān)系式和恰當(dāng)?shù)暮颓‘?dāng)?shù)倪吔鐥l件邊界條件（簡言之為基本方（簡言之為基本方程）。從而把問題化成一族同類的子問題；程）。從而把問題化成一族同類的子問題； 求解的各個階段求解的各個階段, ,我們利用了我們利用了k k階段

25、與階段與k+1k+1階段階段之間的遞推關(guān)系之間的遞推關(guān)系: : 在求整個問題的最優(yōu)策略時，由于初始狀態(tài)是在求整個問題的最優(yōu)策略時，由于初始狀態(tài)是已知的，每段的決策是該段狀態(tài)的函數(shù)，故沿最優(yōu)已知的，每段的決策是該段狀態(tài)的函數(shù)，故沿最優(yōu)化策略所經(jīng)過的各段狀態(tài)便可確定了最優(yōu)路線?；呗运?jīng)過的各段狀態(tài)便可確定了最優(yōu)路線。fk(sk)=mindk(sk,uk(sk)+fk+1(uk(sk)uk Dk(sk)f7(s7)=0k=6,5,4,3,2,1 一般情況一般情況,k,k階段與階段與k+1k+1階段的遞推關(guān)系式（動態(tài)階段的遞推關(guān)系式（動態(tài)規(guī)劃基本方程）規(guī)劃基本方程） kkkkkkksDukksufs

26、usvsfoptkkk1,011nnsf邊界條件為邊界條件為練習(xí)：寫出乘積形式指標(biāo)函數(shù)的動態(tài)規(guī)劃基本方程。練習(xí)：寫出乘積形式指標(biāo)函數(shù)的動態(tài)規(guī)劃基本方程。 順序解法：實際上沒有順序法！順序解法：實際上沒有順序法！小結(jié)小結(jié): 要具有可分離性，并滿足遞推關(guān)系。即要具有可分離性，并滿足遞推關(guān)系。即,),(111, 11,nkknkkkknkknksusVussksV 函數(shù)函數(shù) k k（s sk k，u uk k，V Vk+1,nk+1,n）對于變量）對于變量V Vk+1k+1，n n要嚴(yán)格單調(diào)。要嚴(yán)格單調(diào)。將問題的過程劃分成恰當(dāng)?shù)碾A段；將問題的過程劃分成恰當(dāng)?shù)碾A段；選擇狀態(tài)變量選擇狀態(tài)變量s sk k

27、, , 既能描述過程的變化又滿足無既能描述過程的變化又滿足無后效性；后效性；確定決策變量確定決策變量u uk k及每一階段的允許決策集合及每一階段的允許決策集合D Dk k( (s sk k) )；正確寫出狀態(tài)轉(zhuǎn)移方程；正確寫出狀態(tài)轉(zhuǎn)移方程；正確寫出指標(biāo)函數(shù)正確寫出指標(biāo)函數(shù)V Vk,nk,n，它應(yīng)滿足下面三個性質(zhì)：，它應(yīng)滿足下面三個性質(zhì)： 是定義在全過程和所有后部子過程上的數(shù)量函數(shù)是定義在全過程和所有后部子過程上的數(shù)量函數(shù); ;第四節(jié)：第四節(jié)： 動態(tài)規(guī)劃的理論基礎(chǔ)和動態(tài)規(guī)劃的理論基礎(chǔ)和 具體迭代方具體迭代方 法法 多階段決策過程的特點：每個階段都要進(jìn)多階段決策過程的特點：每個階段都要進(jìn)行決策，

28、策略是由行決策，策略是由n個相繼進(jìn)行的決策構(gòu)成的個相繼進(jìn)行的決策構(gòu)成的決策序列。前一階段的終止?fàn)顟B(tài)又是下一階決策序列。前一階段的終止?fàn)顟B(tài)又是下一階段的初始狀態(tài)，因此，確定階段最優(yōu)決策不段的初始狀態(tài)，因此，確定階段最優(yōu)決策不能只從階段的效應(yīng)來考慮，必須是整個過程能只從階段的效應(yīng)來考慮，必須是整個過程通盤考慮，整體規(guī)劃。即階段通盤考慮，整體規(guī)劃。即階段k的最優(yōu)決策不的最優(yōu)決策不應(yīng)該只是本階段效應(yīng)的最優(yōu)，而必須是本階應(yīng)該只是本階段效應(yīng)的最優(yōu)，而必須是本階段及其所有后續(xù)階段的總體最優(yōu)。段及其所有后續(xù)階段的總體最優(yōu)。 動態(tài)規(guī)劃方法的理論基礎(chǔ)是基于動態(tài)規(guī)劃方法的理論基礎(chǔ)是基于R. Bellman提出的提出

29、的最優(yōu)性原理：最優(yōu)性原理：“一個過程的最優(yōu)策略具有這樣的性質(zhì)：一個過程的最優(yōu)策略具有這樣的性質(zhì)：即無論其初始狀態(tài)及初始決策如何，對于先前決策所形即無論其初始狀態(tài)及初始決策如何，對于先前決策所形成的狀態(tài)而言，余下的諸決策仍構(gòu)成最優(yōu)策略。成的狀態(tài)而言，余下的諸決策仍構(gòu)成最優(yōu)策略?！盇MB1 . 理論基礎(chǔ)理論基礎(chǔ) 適應(yīng)于用動態(tài)規(guī)劃方法求解的是具有無后效性的適應(yīng)于用動態(tài)規(guī)劃方法求解的是具有無后效性的多階段決策過程。多階段決策過程。 最優(yōu)性原理的含義是：最優(yōu)策略的任何一部分子最優(yōu)性原理的含義是：最優(yōu)策略的任何一部分子策略，也是它相應(yīng)初始狀態(tài)的最優(yōu)策略。每個最優(yōu)策策略，也是它相應(yīng)初始狀態(tài)的最優(yōu)策略。每個最

30、優(yōu)策略只能由最優(yōu)子策略構(gòu)成。略只能由最優(yōu)子策略構(gòu)成。),(),(),(1,1,)(1, 001, 0)(*1, 001, 01, 1,01, 01, 0psVoptpsVoptpsVnkknkkknnsPpsPpknknkkk),(),(1111,1, 01, 0kkkknkknusTsppp 動態(tài)規(guī)劃的最優(yōu)性定理：設(shè)階段數(shù)為動態(tài)規(guī)劃的最優(yōu)性定理：設(shè)階段數(shù)為n n的多階段的多階段決策過程，其階段編號為決策過程，其階段編號為k k=0,1,.,=0,1,.,n n-1-1。允許策略。允許策略),(*1*1*0*1,0nnuuup是最優(yōu)策略的充要條件是對任意一個是最優(yōu)策略的充要條件是對任意一個k k, 0, 0k k n n-1-1和和s s0 0 S S0 0，有，有 它是由給定的初始狀態(tài)它是由給定的初始狀態(tài)s s0 0和子策略和子策略p p0,0,k k-1-1所確定的所確定的k k段狀態(tài)。當(dāng)段狀態(tài)。當(dāng)V V是效益函數(shù)時，是效益函數(shù)時，optopt取取max;max;當(dāng)當(dāng)V V是損失函數(shù)是損失函數(shù)時，時，optopt取取min.min.證明：必要性（證明：必要性（ ）),(),()