第四章動態(tài)規(guī)劃問題天馬行空官方博客：/tmxk_docin

；QQ:1318241189；QQ群：175569632第四章動態(tài)規(guī)劃問題天馬行空官方博客：http://t.qq.1動態(tài)規(guī)劃的概念與模型靜態(tài)決策一次性決策動態(tài)決策多階段決策決策x1x2Zu輸入決策輸出決策效應(yīng)第一月x1x2r1u1第二月x3r2u2第三月x4r3u3動態(tài)規(guī)劃的概念與模型靜態(tài)決策一次性決策動態(tài)決策2多段決策過程T1x1x2r1u1T2x3r2u2Tkxkxk+!rkukTnxnxn+1rnun……n個決策子問題K稱為階段變量xk描述k階段初的狀態(tài)，稱為狀態(tài)變量一般把輸入狀態(tài)稱為該階段的階段狀態(tài)。uk的取值代表k階段對第k子問題所進(jìn)行的決策，稱為k階段的決策變量rk為k階段從狀況xk出發(fā),做決策uk之后的后果，稱為k階段的階段效應(yīng)。多段決策過程T1x1x2r1u1T2x3r2u2Tkxkxk3具有無后效性的多段決策過程Xk+1=Tk(xk,uk)系統(tǒng)從k階段往后的決策只與k階段系統(tǒng)的狀態(tài)xk有關(guān),而與系統(tǒng)以前的決策無關(guān)，則稱為具有無后效性的多段決策過程。T1x1x2r1(x1,u1)u1(x1)T2x3r2(x2,u2)u2(x2)Tkxkxk+!rk(xk,uk)uk(xk)Tnxnxn+1……rn(xn,un)un(xn)具有無后效性的多段決策過程4K后部子過程多段決策過程中從第k階段到最終階段的過程稱為k-后部子過程，簡稱k-子過程。Tkxkxk+!rk(xk,uk)uk(xk)Tnxnxn+1…rn(xn,un)un(xn)K后部子過程多段決策過程中從第k階段到最終階段的過程稱為k-5動態(tài)規(guī)劃模型Opt表示求優(yōu)Xk是一個集合，表示k階段狀態(tài)可能取值的范圍，稱為狀態(tài)可能集合。Uk是一個集合，表示k階段決策可能取值的范圍，稱為決策允許集合，一般來說對于不同狀態(tài)，可以作的決策的范圍是不同的。因此決策允許集合一般寫為Uk(xk)。

動態(tài)規(guī)劃模型Opt表示求優(yōu)6動態(tài)規(guī)劃的建模動態(tài)規(guī)劃建模①確定階段與階段變量②明確狀態(tài)變量和狀態(tài)可能集合。③確定決策變量和決策允許集合。④確定狀態(tài)轉(zhuǎn)移方程。⑤明確階段效應(yīng)和目標(biāo)。動態(tài)規(guī)劃的建模動態(tài)規(guī)劃建模7動態(tài)規(guī)劃的建模①確定階段與階段變量階段的劃分一般是按照決策進(jìn)行的時間或空間上的先后順序劃分的，階段數(shù)等于多段決策過程中從開始到結(jié)束所需要作出決策的數(shù)目，階段變量用k表示。②明確狀態(tài)變量和狀態(tài)可能集合。狀態(tài)變量必須包含在給定的階段上確定全部允許決策所需要的信息。狀態(tài)變量的確定決定了整個決策過程是不是具有無后效性，因而也決定著能不能用動態(tài)規(guī)劃方法來求解。狀態(tài)可能集是關(guān)于狀態(tài)的約束條件，因此為了求解必須正確地確定狀態(tài)可能集。動態(tài)規(guī)劃的建模①確定階段與階段變量8動態(tài)規(guī)劃的建模③確定決策變量和決策允許集合。與靜態(tài)問題相同，決策變量應(yīng)能夠反映對問題所作的決策，決策變量也應(yīng)有其相應(yīng)的約束條件，在建模時應(yīng)明確決策允許集合Uk(xk)。④確定狀態(tài)轉(zhuǎn)移方程。系統(tǒng)k階段從狀態(tài)xk出發(fā)作了決策uk(xk)之后的結(jié)果之一是系統(tǒng)狀態(tài)的轉(zhuǎn)移，這一結(jié)果直接影響系統(tǒng)往后的決策過程，因此必須明確狀態(tài)的轉(zhuǎn)移過程，即根據(jù)問題的內(nèi)在關(guān)系，明確xk+1=Tk(xk,uk)中的函數(shù)Tk（）。動態(tài)規(guī)劃的建模③確定決策變量和決策允許集合。9動態(tài)規(guī)劃的建模⑤明確階段效應(yīng)和目標(biāo)。階段效應(yīng)rk(xk,uk)是在階段k以xk出發(fā)作了決策uk之后所產(chǎn)生的后果，必須明確rk與xk，uk的關(guān)系，才能構(gòu)成目標(biāo)函數(shù)。目標(biāo)函數(shù)是由階段效應(yīng)經(jīng)過某種集結(jié)而得到的，如何集結(jié)視具體問題而定，同時還應(yīng)根據(jù)問題確定目標(biāo)是求最大還是最小。由于在經(jīng)濟(jì)系統(tǒng)中的大多數(shù)情況下，目標(biāo)的集結(jié)方法都是求和，因此，在不作說明的情況下，往后的討論都針對目標(biāo)為和的形式進(jìn)行。動態(tài)規(guī)劃的建模⑤明確階段效應(yīng)和目標(biāo)。10動態(tài)規(guī)劃解的概念多段決策過程中所要求解的是，從起始狀態(tài)x1開始，進(jìn)行一系列的決策，使目標(biāo)R達(dá)到最優(yōu)最優(yōu)目標(biāo)值R*最優(yōu)策略使得目標(biāo)達(dá)到最優(yōu)的決策序列。最優(yōu)路線在采取最優(yōu)策略時，系統(tǒng)從x1開始所經(jīng)過的狀態(tài)序列求解動態(tài)規(guī)劃模型找到最優(yōu)策略、最優(yōu)路線和最優(yōu)目標(biāo)值。動態(tài)規(guī)劃解的概念多段決策過程中所要求解的是，從起始狀態(tài)x1開11動態(tài)規(guī)劃最優(yōu)性原理多段決策過程的特點(diǎn)每個階段都要進(jìn)行決策相繼進(jìn)行的階段決策構(gòu)成的決策序列前一階段的終止?fàn)顟B(tài)又是后一階段的初始狀態(tài)階段最優(yōu)決策不能只從本階段的效應(yīng)出發(fā)，必須通盤考慮，整體規(guī)劃。階段k的最優(yōu)決策不應(yīng)該只是本階段效應(yīng)的最優(yōu)，而必須是本階段及其所有后續(xù)階段的總體最優(yōu)，即關(guān)于整個k后部子過程的最優(yōu)決策。動態(tài)規(guī)劃最優(yōu)性原理多段決策過程的特點(diǎn)12動態(tài)規(guī)劃最優(yōu)性原理最優(yōu)性原理“最優(yōu)策略具有的基本性質(zhì)是：無論初始狀態(tài)和初始決策如何，對于前面決策所造成的某一狀態(tài)而言，下余的決策序列必構(gòu)成最優(yōu)策略”。AMB動態(tài)規(guī)劃最優(yōu)性原理最優(yōu)性原理AMB13動態(tài)規(guī)劃最優(yōu)性原理最優(yōu)性原理的含意最優(yōu)策略的任何一部分子策略，也是相應(yīng)初始狀態(tài)的最優(yōu)策略。每個最優(yōu)策略只能由最優(yōu)子策略構(gòu)成。顯然，對于具有無后效性的多段決策過程而言，如果按照k后部子過程最優(yōu)的原則來求各階段狀態(tài)的最優(yōu)決策，那么這樣構(gòu)成的最優(yōu)決策序列或策略一定具有最優(yōu)性原理所提示的性質(zhì)。動態(tài)規(guī)劃最優(yōu)性原理最優(yōu)性原理的含意14貝爾曼函數(shù)貝爾曼函數(shù)fk(xk)：在階段k從初始狀態(tài)xk出發(fā)，執(zhí)行最優(yōu)決策序列或策略，到達(dá)過程終點(diǎn)時，整個k-子過程中的目標(biāo)函數(shù)取值，稱為條件最優(yōu)目標(biāo)函數(shù)，亦稱貝爾曼函數(shù)。條件最優(yōu)策略多段決策過程的任一階段狀態(tài)xk的最優(yōu)策略處于條件xk時的最優(yōu)策略。條件最優(yōu)決策構(gòu)成條件最優(yōu)策略的決策貝爾曼函數(shù)貝爾曼函數(shù)fk(xk)：條件最優(yōu)策略15貝爾曼函數(shù)條件最優(yōu)目標(biāo)函數(shù)值fk(xk)執(zhí)行條件最優(yōu)策略時的目標(biāo)函數(shù)值條件最優(yōu)路線執(zhí)行條件最優(yōu)策略時的階段狀態(tài)序列貝爾曼函數(shù)條件最優(yōu)目標(biāo)函數(shù)值fk(xk)條件最優(yōu)路線16貝爾曼函數(shù)條件最優(yōu)k-子策略系統(tǒng)從xk出發(fā)，在k-后部子過程中的最優(yōu)策略k-子過程條件最優(yōu)目標(biāo)函數(shù)fk(xk)是從xk出發(fā)系統(tǒng)在k-后部子過程中的最優(yōu)目標(biāo)值，多段決策問題所求解的最優(yōu)目標(biāo)函數(shù)值R*=f1(x1*)動態(tài)規(guī)劃基本方程fk(xk)與fk＋1(xk＋1)之間的遞推關(guān)系動態(tài)規(guī)劃方法的依據(jù)是最優(yōu)性原理貝爾曼函數(shù)條件最優(yōu)k-子策略17動態(tài)規(guī)劃基本方程設(shè)在階段k的狀態(tài)xk執(zhí)行了任意選定決策uk后的狀態(tài)是xk+1=Tk(xk,uk)。這時k-后部子過程就縮小為k+1后部子過程。根據(jù)最優(yōu)性原理，對k+1后部子過程應(yīng)采取最優(yōu)策略，由于無后效性，k后部子過程的目標(biāo)函數(shù)值為動態(tài)規(guī)劃基本方程設(shè)在階段k的狀態(tài)xk執(zhí)行了任意選定決策uk后18動態(tài)規(guī)劃基本方程動態(tài)規(guī)劃基本方程19動態(tài)規(guī)劃基本方程動態(tài)規(guī)劃基本方程20動態(tài)規(guī)劃方法基本原理動態(tài)規(guī)劃方法基本原理rk(xk,uk)和xk+1=Tk(xk,uk)都是已知的函數(shù)求fk(xk)需要首先求關(guān)于xk的所有k+1段狀態(tài)xk+1的fk+1(xk+1)逆序地求出條件最優(yōu)目標(biāo)函數(shù)值集合和條件最優(yōu)決策集合狀態(tài)xk+1是由前面階段的狀態(tài)決定的用問題給定的初始條件，即可順序地求出整個多段決策問題的最優(yōu)目標(biāo)函數(shù)值、最優(yōu)策略和最優(yōu)路線。動態(tài)規(guī)劃方法基本原理動態(tài)規(guī)劃方法基本原理rk(xk,uk21動態(tài)規(guī)劃問題求解的一般步驟

逆序地求出條件最優(yōu)目標(biāo)函數(shù)值集合和條件最優(yōu)決策集合k=n時，動態(tài)規(guī)劃基本方程是邊界條件k=n時的動態(tài)規(guī)劃基本方程成為動態(tài)規(guī)劃問題求解的一般步驟逆序地求出條件最優(yōu)目標(biāo)函數(shù)值集合22動態(tài)規(guī)劃問題求解的一般步驟

逆序地求出條件最優(yōu)目標(biāo)函數(shù)值集合和條件最優(yōu)決策集合k=n－1時，動態(tài)規(guī)劃的基本方程是所有的fn(xn)都已經(jīng)求出，因此可以根據(jù)xn=Tn-1(xn-1,un-1)就階段n-1每個可能狀態(tài)xn-1∈Xn-1求條件最優(yōu)決策及相應(yīng)的條件最優(yōu)目標(biāo)函數(shù)值fn－1(xn－1)動態(tài)規(guī)劃問題求解的一般步驟逆序地求出條件最優(yōu)目標(biāo)函數(shù)值集合23動態(tài)規(guī)劃問題求解的一般步驟

逆序地求出條件最優(yōu)目標(biāo)函數(shù)值集合和條件最優(yōu)決策集合k=1時，動態(tài)規(guī)劃的基本方程是所有的f2(x2)都已經(jīng)求出，因此可以根據(jù)x2=T1(x1,u1)就階段1每個可能狀態(tài)x1∈X1求條件最優(yōu)決策及相應(yīng)的條件最優(yōu)目標(biāo)函數(shù)值f1(x1)動態(tài)規(guī)劃問題求解的一般步驟逆序地求出條件最優(yōu)目標(biāo)函數(shù)值集合24動態(tài)規(guī)劃問題求解的一般步驟

逆序地求出條件最優(yōu)目標(biāo)函數(shù)值集合和條件最優(yōu)決策集合動態(tài)規(guī)劃問題求解的一般步驟逆序地求出條件最優(yōu)目標(biāo)函數(shù)值集合25動態(tài)規(guī)劃問題求解的一般步驟

順序地求出最優(yōu)目標(biāo)值、最優(yōu)策略和最優(yōu)路線若x1已知，則階段1的條件最優(yōu)決策就是階段1的關(guān)于整個過程的最優(yōu)決策若x1未知

動態(tài)規(guī)劃問題求解的一般步驟順序地求出最優(yōu)目標(biāo)值、最優(yōu)策略和26動態(tài)規(guī)劃問題求解的一般步驟順序地求出最優(yōu)目標(biāo)值、最優(yōu)策略和最優(yōu)路線動態(tài)規(guī)劃問題求解的一般步驟順序地求出最優(yōu)目標(biāo)值、最優(yōu)策略和最27

動態(tài)規(guī)劃四大要素、一個方程五個關(guān)鍵因素四大要素、一個方程：①狀態(tài)變量及其可能集合②決策變量及其允許集合③狀態(tài)轉(zhuǎn)移方程④階段效應(yīng)⑤動態(tài)規(guī)劃基本方程：動態(tài)規(guī)劃四大要素、一個方程五個關(guān)鍵因素四大要素、一28動態(tài)規(guī)劃應(yīng)用舉例----最短路問題例某旅行者希望從s地起到t地，其間的道路系統(tǒng)如圖4－1所示，圖上圓圈表示途徑的地方，稱為節(jié)點(diǎn)，連結(jié)兩地的箭線表示道路，其上的數(shù)字表示該段道路長度，箭頭表示通行的方向。試求s到t的最短路。adbetcfs9757845646547圖4--1動態(tài)規(guī)劃應(yīng)用舉例----最短路問題例某旅行者希望從s地起29動態(tài)規(guī)劃應(yīng)用舉例----最短路問題adbetcfs9757845646547第一階段第二階段第三階段劃分階段k=1,2,3代表三個階段動態(tài)規(guī)劃應(yīng)用舉例----最短路問題adbetcfs9757830動態(tài)規(guī)劃應(yīng)用舉例----最短路問題adbetcfs9757845646547狀態(tài)變量xk取為k階段所在地，則有：動態(tài)規(guī)劃應(yīng)用舉例----最短路問題adbetcfs9757831動態(tài)規(guī)劃應(yīng)用舉例----最短路問題adbetcfs9757845646547k階段決策是決定下一步走到哪里，uk(xk)取為下一步的所在點(diǎn)。動態(tài)規(guī)劃應(yīng)用舉例----最短路問題adbetcfs9757832動態(tài)規(guī)劃應(yīng)用舉例----最短路問題逆序求條件最優(yōu)目標(biāo)函數(shù)集和條件最優(yōu)決策集由于第3階段末已到達(dá)t，往后的距離自然是零，因此f4(t)=0對3階段所有可能的狀態(tài)X3={d,e,f}計算f3()如下動態(tài)規(guī)劃應(yīng)用舉例----最短路問題逆序求條件最優(yōu)目標(biāo)函數(shù)集和33動態(tài)規(guī)劃應(yīng)用舉例----最短路問題逆序求條件最優(yōu)目標(biāo)函數(shù)集和條件最優(yōu)決策集也可以用表格方法計算如下t/tF3()U3()def5+07+04+0574tttr3(x3,u3)+f4(x4)f3(x3)u3(x3)動態(tài)規(guī)劃應(yīng)用舉例----最短路問題逆序求條件最優(yōu)目標(biāo)函數(shù)集和34動態(tài)規(guī)劃應(yīng)用舉例----最短路問題逆序求條件最優(yōu)目標(biāo)函數(shù)集和條件最優(yōu)決策集對2階段所有可能的狀態(tài)X2={a,b,c}計算f2()如下動態(tài)規(guī)