動(dòng)態(tài)規(guī)劃講義

1、第6章動(dòng)態(tài)規(guī)劃最優(yōu)化原理1951年美國(guó)數(shù)學(xué)家 R.Bellman等人，根據(jù)一類(lèi)多階段問(wèn)題的特點(diǎn)，把多階段決策問(wèn)題變換為一系列互相聯(lián)系的單階段問(wèn)題，然后逐個(gè)加以解決。一些靜態(tài)模型，只要人為地引進(jìn)“時(shí)間”因素，分成時(shí)段，就可以轉(zhuǎn)化成多階段的動(dòng)態(tài)模型，用動(dòng)態(tài)規(guī)劃方法去處理。與此同時(shí)，他提出了解決這類(lèi)問(wèn)題的"最優(yōu)化原理”(Principle of optimality ):上述程序?qū)崿F(xiàn)方法同樣適合于背包問(wèn)題，最優(yōu)庫(kù)存問(wèn)題等，只是針對(duì)具體情況，最優(yōu)決策表的表示和生成會(huì)有所不同。“一個(gè)過(guò)程的最優(yōu)決策具有這樣的性質(zhì)： 即無(wú)論其初始狀態(tài)和初始決策如何，其今后諸策略對(duì)以第一個(gè)決策所形成的狀態(tài)作為初始狀

2、態(tài)的過(guò)程而言，必須構(gòu)成最優(yōu)策略”。簡(jiǎn)言之,一個(gè)最優(yōu)策略的子策略，對(duì)于它的初態(tài)和終態(tài)而言也必是最優(yōu)的。這個(gè)“最優(yōu)化原理”如果用數(shù)學(xué)化一點(diǎn)的語(yǔ)言來(lái)描述的話，就是：假設(shè)為了解決某一優(yōu)化問(wèn)題，需要依次作出n個(gè)決策D1 , D2，Dn，如若這個(gè)決策序列是最優(yōu)的，對(duì)于任何一個(gè)整數(shù)k, 1 < k < n,不論前面 k個(gè)決策是怎樣的，以后的最優(yōu)決策只取決于由前面決策所確定的當(dāng)前狀態(tài)，即以后的決策 Dk+1 , Dk+2 ,，Dn也是最優(yōu)的。最優(yōu)化原理是動(dòng)態(tài)規(guī)劃的基礎(chǔ)。任何一個(gè)問(wèn)題，如果失去了這個(gè)最優(yōu)化原理的支持, 就不可能用動(dòng)態(tài)規(guī)劃方法計(jì)算。能采用動(dòng)態(tài)規(guī)劃求解的問(wèn)題都需要滿(mǎn)足一定的條件：(1 )

3、問(wèn)題中的狀態(tài)必須滿(mǎn)足最優(yōu)化原理；(2) 問(wèn)題中的狀態(tài)必須滿(mǎn)足無(wú)后效性。所謂的無(wú)后效性是指：“下一時(shí)刻的狀態(tài)只與當(dāng)前狀態(tài)有關(guān)，而和當(dāng)前狀態(tài)之前的狀態(tài)無(wú)關(guān)，當(dāng)前的狀態(tài)是對(duì)以往決策的總結(jié)”。問(wèn)題求解模式動(dòng)態(tài)規(guī)劃所處理的問(wèn)題是一個(gè)多階段決策問(wèn)題，一般由初始狀態(tài)開(kāi)始，通過(guò)對(duì)中間階 段決策的選擇，達(dá)到結(jié)束狀態(tài)。這些決策形成了一個(gè)決策序列，同時(shí)確定了完成整個(gè)過(guò)程 的一條活動(dòng)路線(通常是求最優(yōu)的活動(dòng)路線)。如圖所示。動(dòng)態(tài)規(guī)劃的設(shè)計(jì)都有著一定的 模式，一般要經(jīng)歷以下幾個(gè)步驟：初始狀態(tài)決策1 I宀丨決策2 | t I決策n|f結(jié)束狀態(tài)(1) 劃分階段：按照問(wèn)題的時(shí)間或空間特征，把問(wèn)題分為若干個(gè)階段。在劃分階段時(shí),

4、 注意劃分后的階段一定要是有序的或者是可排序的，否則問(wèn)題就無(wú)法求解。(2) 確定狀態(tài)和狀態(tài)變量： 將問(wèn)題發(fā)展到各個(gè)階段時(shí)所處于的各種客觀情況用不同的 狀態(tài)表示出來(lái)。當(dāng)然，狀態(tài)的選擇要滿(mǎn)足無(wú)后效性。(3) 確定決策并寫(xiě)出狀態(tài)轉(zhuǎn)移方程：因?yàn)闆Q策和狀態(tài)轉(zhuǎn)移有著天然的聯(lián)系，狀態(tài)轉(zhuǎn)移就是根據(jù)上一階段的狀態(tài)和決策來(lái)導(dǎo)出本階段的狀態(tài)。所以如果確定了決策，狀 態(tài)轉(zhuǎn)移方程也就可寫(xiě)出。但事實(shí)上常常是反過(guò)來(lái)做，根據(jù)相鄰兩段各狀態(tài)之間的關(guān)系 來(lái)確定決策。（4）尋找邊界條件：給出的狀態(tài)轉(zhuǎn)移方程是一個(gè)遞推式，需要一個(gè)遞推的終止條件或邊界條件。算法實(shí)現(xiàn)動(dòng)態(tài)規(guī)劃的主要難點(diǎn)在于理論上的設(shè)計(jì)，也就是上面4個(gè)步驟的確定，一旦設(shè)計(jì)完

5、成，實(shí)現(xiàn)部分就會(huì)非常簡(jiǎn)單。使用動(dòng)態(tài)規(guī)劃求解問(wèn)題，最重要的就是確定動(dòng)態(tài)規(guī)劃三要 素：?jiǎn)栴}的 階段,每個(gè)階段的 狀態(tài)以及從前一個(gè)階段轉(zhuǎn)化到后一個(gè)階段之間的遞推關(guān)系遞推關(guān)系必須是從次小的問(wèn)題開(kāi)始到較大的問(wèn)題之間的轉(zhuǎn)化，從這個(gè)角度來(lái)說(shuō)，動(dòng)態(tài)規(guī) 劃往往可以用遞歸程序來(lái)實(shí)現(xiàn)，不過(guò)因?yàn)檫f推可以充分利用前面保存的子問(wèn)題的解來(lái)減 少重復(fù)計(jì)算，所以對(duì)于大規(guī)模問(wèn)題來(lái)說(shuō)，有遞歸不可比擬的優(yōu)勢(shì)，這也是動(dòng)態(tài)規(guī)劃算法 的核心之處。動(dòng)態(tài)規(guī)劃算法將問(wèn)題的解決方案視為一系列決策的結(jié)果，與貪婪算法不同的是，貪婪算法中，每采用一次貪婪準(zhǔn)則，便做出一個(gè)不可撤回的決策；而在動(dòng)態(tài)規(guī)劃算法中，還要考察每個(gè)最優(yōu)決策序列中是否包含一個(gè)最優(yōu)決策子序列，即問(wèn)題是否具有最優(yōu)子結(jié)構(gòu)性質(zhì)。動(dòng)態(tài)規(guī)劃算法的有效性依賴(lài)于待求解問(wèn)題本身具有的兩個(gè)重要性質(zhì)：最優(yōu)子結(jié)構(gòu)性質(zhì) 和子問(wèn)題重疊性質(zhì)。（1 ）最優(yōu)子結(jié)