最優(yōu)化原理與動態(tài)規(guī)劃實用教案

1、會計學1最優(yōu)化原理與動態(tài)最優(yōu)化原理與動態(tài)(dngti)規(guī)劃規(guī)劃第一頁，共31頁。2.“局部最優(yōu)路徑局部最優(yōu)路徑”法：選擇當前最短途徑法：選擇當前最短途徑(tjng)，“逢近便走逢近便走”。所取決策必是所取決策必是Q A1 B2 C2T，全程，全程長度是長度是13。QTA1A2A3B1B2B3C1C224374642442514633334第1頁/共31頁第二頁，共31頁。全枚舉法計算工作量將會十分龐大全枚舉法計算工作量將會十分龐大(pngd)(pngd)。局部最優(yōu)求出的解不一定是最優(yōu)解。局部最優(yōu)求出的解不一定是最優(yōu)解。第2頁/共31頁第三頁，共31頁。第3頁/共31頁第四頁，共31頁。第4頁/

2、共31頁第五頁，共31頁。二、動態(tài)二、動態(tài)(dngti)規(guī)劃解題規(guī)劃解題 標號法：標號法：最短路徑最短路徑(ljng)：Q A3 B1 C1TQTA1A2A3B1B2B3C1C224374642442514633334階段階段1階段階段2階段階段3階段階段40，T3,T4,T4,C17,C26,C111,B1 ,B28,B18,B111,A3 第5頁/共31頁第六頁，共31頁。三、動態(tài)三、動態(tài)(dngti)規(guī)劃的基本概念。規(guī)劃的基本概念。1.階段階段(stage)和階段變量。和階段變量。 把所給問題恰當地劃分把所給問題恰當地劃分(hu fn)為若干個相互聯為若干個相互聯系又有區(qū)別的子問題，稱之

3、為多段決策問題的階系又有區(qū)別的子問題，稱之為多段決策問題的階段。段。QTA1A2A3B1B2B3C1C224374642442514633334第6頁/共31頁第七頁，共31頁。用以描述階段的變量叫作階段變量，一般以用以描述階段的變量叫作階段變量，一般以k k表示表示(biosh)(biosh)階段量階段量階段數階段數k k的編號法有兩種：的編號法有兩種：(1)(1)順序編號；順序編號；(2)(2)逆序編號法。逆序編號法。QTA1A2A3B1B2B3C1C224374642442514633334第7頁/共31頁第八頁，共31頁。2.狀態(tài)狀態(tài)(state)、狀態(tài)變量和可能狀態(tài)集、狀態(tài)變量和可能

4、狀態(tài)集(1)狀態(tài)與狀態(tài)變量。表示狀態(tài)與狀態(tài)變量。表示(biosh)每個每個階段開始所處的自然狀況或客觀條件。階段開始所處的自然狀況或客觀條件。QTA1A2A3B1B2B3C1C224374642442514633334第8頁/共31頁第九頁，共31頁。(2)動態(tài)動態(tài)(dngti)規(guī)劃維數。規(guī)劃維數。(3)可能狀態(tài)可能狀態(tài)(zhungti)集：用集：用S(sk)表示。表示。QTA1A2A3B1B2B3C1C224374642442514633334第9頁/共31頁第十頁，共31頁。3.3.決策決策(decision)(decision)、決策變量和允許決策集合、決策變量和允許決策集合(1)(1)

5、決策。表示決策。表示(biosh)(biosh)當過程處于某一階段的當過程處于某一階段的某個狀態(tài)，可以作出不同的決定（選擇），從而某個狀態(tài)，可以作出不同的決定（選擇），從而確定下一階段的狀態(tài)。確定下一階段的狀態(tài)。QTA1A2A3B1B2B3C1C224374642442514633334第10頁/共31頁第十一頁，共31頁。(2)決策變量決策變量:xk=xk(sk)決策變量決策變量xk(sk)的允許決策集用的允許決策集用Dk(sk)表示表示(biosh), xk(sk)Dk(sk)允許決策集合實際是允許決策集合實際是決策的約束條件。決策的約束條件。QTA1A2A3B1B2B3C1C224374

6、642442514633334第11頁/共31頁第十二頁，共31頁。4.策略和子策略策略和子策略(Policy)（1）全過程策略指具有）全過程策略指具有n個階段全部個階段全部(qunb)過過程，簡稱策略。表示為程，簡稱策略。表示為 x1(s1),x2(s1),xn(sn)。 k后部子過程策略后部子過程策略,表示為表示為pk(xk)QTA1A2A3B1B2B3C1C224374642442514633334第12頁/共31頁第十三頁，共31頁。(2)允許策略集合記作允許策略集合記作P。 最優(yōu)策略最優(yōu)策略:從允許策略集中從允許策略集中(jzhng)，找出的具，找出的具有最優(yōu)效果的策略。有最優(yōu)效果的

7、策略。 QTA1A2A3B1B2B3C1C224374642442514633334第13頁/共31頁第十四頁，共31頁。5.狀態(tài)轉移方程狀態(tài)轉移方程(狀態(tài)轉移律狀態(tài)轉移律) ：多階段決策過程：多階段決策過程的發(fā)展就是用階段狀態(tài)的相繼的發(fā)展就是用階段狀態(tài)的相繼(xingj)演變來描演變來描述的。述的。或簡寫為或簡寫為),(1kkkxsTs kkkkkksxsxsTs)(,(1從上階段從上階段(jidun)的某一狀態(tài)值到下階段的某一狀態(tài)值到下階段(jidun)某一狀態(tài)值的轉移規(guī)律成為狀態(tài)轉移律某一狀態(tài)值的轉移規(guī)律成為狀態(tài)轉移律第14頁/共31頁第十五頁，共31頁。6.指標指標(zhbio)函數函

8、數(1)階段指標函數階段指標函數(也稱階段收益也稱階段收益)（是對應某一（是對應某一階段狀態(tài)和從該狀態(tài)出發(fā)階段狀態(tài)和從該狀態(tài)出發(fā)(chf)的一個階段的一個階段的決策的某種效益度量。）的決策的某種效益度量。）vk(sk,xk) 簡記為簡記為vk 。(2)過程指標函數過程指標函數(指標函數指標函數)。(它所包含它所包含(bohn)的各階段指標函數的函數。）的各階段指標函數的函數。）Vk,n(sk,xk, sk+1,xk+1, sn,xn)。簡記為。簡記為Vk,n 。第15頁/共31頁第十六頁，共31頁。動態(tài)規(guī)劃求解的問題的過程指標動態(tài)規(guī)劃求解的問題的過程指標(zhbio)(zhbio)函函數數(

9、(指標指標(zhbio)(zhbio)函數函數) )，必須具有關于階段指，必須具有關于階段指標標(zhbio)(zhbio)的可分離形式的可分離形式( (和、積或其他形式和、積或其他形式) ) ： ),(),(),(),(11111,nnnkkkkkknnkkkknknkxsvxsvxsvxsxsxsVV 表示表示(biosh)(biosh)某種運算，可為加、減、乘、除、某種運算，可為加、減、乘、除、開方等。開方等。第16頁/共31頁第十七頁，共31頁。常見常見(chn jin)(chn jin)有有: : nkiiiinkxsvV),(,nkiiiinkxsvV),(,和和第17頁/共31頁

10、第十八頁，共31頁。相應的子策略稱為相應的子策略稱為sk狀態(tài)下的最優(yōu)子策略，狀態(tài)下的最優(yōu)子策略，記為記為pk*(sk) ；而構成該子策略的各段決策；而構成該子策略的各段決策稱為該過程上的最優(yōu)決策，記為稱為該過程上的最優(yōu)決策，記為)(,),(),(11nnkkkksxsxsx 7.最優(yōu)指標函數：最優(yōu)指標函數：fk(sk) nkVsfnkkk, 2 , 1,opt)(, 有有簡記為簡記為nksxsxsxspnnkkkkkk, 2 , 1),(,),(),()(11nkxxxpnkkk, 2 , 1,1第18頁/共31頁第十九頁，共31頁。8. 概念概念(ginin)的關系。的關系。狀態(tài)狀態(tài)sk階段

11、階段(jidun)kT(sk,xk)決策決策xk(sk)vk(sk,xk)狀態(tài)狀態(tài)sk+1階段階段(jidun)k+1T(sk+1,xk+1)決策決策xk+1(sk+1)vk+1(sk+1,xk+1)狀態(tài)狀態(tài)sk+2第19頁/共31頁第二十頁，共31頁。四、最優(yōu)化原理與動態(tài)規(guī)劃四、最優(yōu)化原理與動態(tài)規(guī)劃(guhu)的數學的數學模型模型 1.最優(yōu)化原理最優(yōu)化原理 (貝爾曼最優(yōu)化原理貝爾曼最優(yōu)化原理) 若某一全過程最優(yōu)策略為：若某一全過程最優(yōu)策略為：)(),(,),(),()(221111nnkksxsxsxsxsp 則則)(,),(),()(11nnkkkkkksxsxsxsp最優(yōu)化原理最優(yōu)化原理

12、 ：作為整個過程的最優(yōu)策略具有這樣：作為整個過程的最優(yōu)策略具有這樣的性質，無論過去的狀態(tài)和決策如何，對先前的性質，無論過去的狀態(tài)和決策如何，對先前(xinqin)(xinqin)決策決策所形成的狀態(tài)而言，余下的諸決策必構成最優(yōu)決策所形成的狀態(tài)而言，余下的諸決策必構成最優(yōu)決策。 第20頁/共31頁第二十一頁，共31頁。2.動態(tài)動態(tài)(dngti)規(guī)劃的數學模型規(guī)劃的數學模型(逆序法時逆序法時) 01 ,),(opt),(1111,csfnksfxsvsfxsvVnnkkkkksDxkknkiiiinkkkk(8.3a)(8.3b)第21頁/共31頁第二十二頁，共31頁。 01 ,),(opt),(

13、1111,csfnksfxsvsfxsvVnnkkkkksDxkknkiiiinkkkk(8.3c)(8.3d)或或(8.3b)和和(8.3d)稱為稱為(chn wi)邊界條件。邊界條件。第22頁/共31頁第二十三頁，共31頁。五、動態(tài)規(guī)劃方法的基本五、動態(tài)規(guī)劃方法的基本(jbn)步驟步驟1. 階段階段(jidun)的劃分的劃分2.正確正確(zhngqu)地定義狀態(tài)變量地定義狀態(tài)變量sk第23頁/共31頁第二十四頁，共31頁。( 1 ) 要 能 夠 正 確 地 描 述 受 控 過 程 的 變 化要 能 夠 正 確 地 描 述 受 控 過 程 的 變 化(binhu)特征。特征。 (2)包含到達

14、這個狀態(tài)前的足夠信息，且滿足無包含到達這個狀態(tài)前的足夠信息，且滿足無后效性。后效性。 (3)要滿足可知性。要滿足可知性。第24頁/共31頁第二十五頁，共31頁。3.正確正確(zhngqu)地定義決策變量及各階段的地定義決策變量及各階段的允許決策集合允許決策集合Dk(sk) 4. 能夠正確能夠正確(zhngqu)地寫出狀態(tài)轉移方程，地寫出狀態(tài)轉移方程，至少要能正確至少要能正確(zhngqu)反映狀態(tài)轉移規(guī)律。反映狀態(tài)轉移規(guī)律。第25頁/共31頁第二十六頁，共31頁。5.根據題意根據題意(t y),正確地構造出指標函數，應滿足正確地構造出指標函數，應滿足下列性質：下列性質：(1)可分性，可分性，(

15、2)為了進行動態(tài)規(guī)劃計算滿足遞推性，為了進行動態(tài)規(guī)劃計算滿足遞推性，nkkkknkVxsvV, 1,),(或或nkkkknkVxsvV, 1,),(6.確立邊界條件寫出動態(tài)規(guī)劃函數基本確立邊界條件寫出動態(tài)規(guī)劃函數基本(jbn)方方程。程。第26頁/共31頁第二十七頁，共31頁。階段階段(jidun)1階段階段(jidun)2階段階段(jidun)k階段階段k+1階段階段n狀態(tài)狀態(tài)S1決決策策x1狀態(tài)狀態(tài)S2v1決決策策x2狀態(tài)狀態(tài)S3v2決決策策xk狀態(tài)狀態(tài)Sk+1vk決決策策xk+1vk+1決決策策xnvn尋求最優(yōu)解的方向尋求最優(yōu)解的方向第27頁/共31頁第二十八頁，共31頁。六、動態(tài)規(guī)劃六

16、、動態(tài)規(guī)劃(guhu)的分類的分類離散離散決策決策(juc)(juc)過程過程連續(xù)連續(xù)(linx)(linx)決策過程決策過程根據多階段決策過程的根據多階段決策過程的時間參量時間參量根據決策過程的根據決策過程的演變演變確定性確定性決策過程決策過程隨機性隨機性決策過程決策過程離散確定性離散確定性決策過程決策過程連續(xù)連續(xù)確定性確定性決策過程決策過程離散隨機離散隨機性性決策過程決策過程連續(xù)隨機性連續(xù)隨機性決策過程決策過程第28頁/共31頁第二十九頁，共31頁。七、學習方法建議七、學習方法建議(jiny)第一步第一步 先看問題，充分理解問題的條件、先看問題，充分理解問題的條件、情況及求解目標。情況及求解目標。第二步第二步 分析針對該動態(tài)規(guī)劃問題的分析針對該動態(tài)規(guī)劃問題的“四大四大要素、一個方程要素、一個方程”。第三步第三步 動手把求解思路整理出來，或者說動手把求解思路整理出來，或者說，把該問題作為習題獨立的來做。，把該問題作為習題獨立的來做。第29頁/共31頁第三十頁，共31頁。第四步第四步 把自己的求解把自己的求解(qi ji)(qi ji)放到一邊，放到一邊，看書中的求解看書中的求解(qi ji)(qi ji)方法，要充分理解教