第七章 動態(tài)規(guī)劃

1、1 第七章 動態(tài)規(guī)劃 |多階段決策過程的最優(yōu)化 |動態(tài)規(guī)劃的基本概念和基本原理 |動態(tài)規(guī)劃模型的建立與求解 |動態(tài)規(guī)劃在經(jīng)濟(jì)管理中的應(yīng)用 |馬氏決策規(guī)劃簡介 美國數(shù)學(xué)家貝爾曼 （richard. bellman) 創(chuàng)始時間 上個世紀(jì)50年代 創(chuàng)始人 |是運籌學(xué)的一個主要分支 |是解決多階段決策過程的最優(yōu)化的一 種方法多階段決策過程： 資源分配問題 生產(chǎn)計劃與庫存問題 投資問題裝載問題排序問題 生產(chǎn)過程的最優(yōu)控制等 多階段決策過程的最優(yōu)化的目標(biāo)： 達(dá)到整個活動過程的總體效果最優(yōu) 主要用于解決： 最優(yōu)路徑問題 動態(tài)規(guī)劃 模型分類 離散確定型 離散隨機(jī)型 連續(xù)確定型 連續(xù)隨機(jī)型 多階段決策問題 (m

2、ulti-stage decision process) 狀態(tài) x1 階段1 t1 決策u1 狀態(tài) x2 決策u2 階段2 t2 狀態(tài) x3 . 狀態(tài) xk 決策uk 階段k tk 狀態(tài) xk+1 . 狀 態(tài) xn 決策un 階段n tn 狀 態(tài) xn+1 1.多階段決策過程的最優(yōu)化 動態(tài)規(guī)劃方法與“時間”關(guān)系很密切， 隨著時間過程的發(fā)展而決定各時段的決策， 產(chǎn)生一個決策序列，這就是“動態(tài)”的意思。 然而它也可以處理與時間無關(guān)的靜態(tài)問題， 只要在問題中人為地引入“時段”因素，就 可以將其轉(zhuǎn)化為一個多階段決策問題。在本 章中將介紹這種處理方法。 2.多階段決策問題舉例 屬于多階段決策類的問題很多

3、， 例如： 1)1)工廠生產(chǎn)過程工廠生產(chǎn)過程：由于市場需求 是一隨著時間而變化的因素，因此， 為了取得全年最佳經(jīng)濟(jì)效益，就要在 全年的生產(chǎn)過程中，逐月或者逐季度 地根據(jù)庫存和需求情況決定生產(chǎn)計劃 安排。 |例1：某廠與用戶簽訂了如表所示 的交貨合同，表中數(shù)字為月底的交 貨量。該廠的生產(chǎn)能力為每月400 件，該廠倉庫的存貨能力為300件。 已知每百件貨物的生產(chǎn)費用為 10000元。在進(jìn)行生產(chǎn)的月份，工 廠還要支付經(jīng)常費4000元。倉庫保 管費為每百件貨物每月1000元。假 設(shè)開始時及6月底交貨后無存貨。 月份 123456 交貨量 （百件） 125321 2) 2)設(shè)備更新問題：設(shè)備更新問題：一

4、般企業(yè) 用于生產(chǎn)活動的設(shè)備，剛買來時故障 少，經(jīng)濟(jì)效益高，即使進(jìn)行轉(zhuǎn)讓，處 理價值也高，隨著使用年限的增加， 就會逐漸變?yōu)楣收隙啵S修費用增加， 可正常使用的工時減少，加工質(zhì)量下 降，經(jīng)濟(jì)效益差，并且，使用的年限 越長、處理價值也越低，自然，如果 賣去舊的買新的，還需要付出更新 費因此就需要綜合權(quán)衡決定設(shè)備的 使用年限，使總的經(jīng)濟(jì)效益最好。 例2：下表給出了某單位的預(yù)測數(shù)據(jù)， 現(xiàn)決定考慮到1998年（n=5），試作5 年內(nèi)的設(shè)備更新計劃 產(chǎn)品年代機(jī)齡收入額維護(hù)費新設(shè)備購置費舊設(shè)備折價 1993 1 2 3 4 5 18 16 16 14 14 8 8 9 9 10 50 20 15 10 5

5、2 1994 0 1 2 3 4 22 21 20 18 16 6 6 8 8 10 50 30 25 20 15 10 1995 0 1 2 3 27 25 24 22 5 6 8 9 52 31 26 21 15 1996 0 1 2 29 26 24 5 5 6 52 33 28 20 1997 0 1 30 28 4 5 55 35 30 199803246040 3) 3)連續(xù)生產(chǎn)過程的控制連續(xù)生產(chǎn)過程的控制 問題問題：一般化工生產(chǎn)過程中， 常包含一系列完成生產(chǎn)過程的設(shè) 備，前一工序設(shè)備的輸出則是后 一工序設(shè)備的輸入，因此，應(yīng)該 如何根據(jù)各工序的運行工況，控 制生產(chǎn)過程中各設(shè)備的輸入

6、和輸 出，以使總產(chǎn)量最大。 以上所舉問題的發(fā)展過程都與時間 因素有關(guān)，因此在這類多階段決策問題 中，階段的劃分常取時間區(qū)段來表示， 并且各個階段上的決策往往也與時間因 素有關(guān)，這就使它具有了“動態(tài)”的含 義，所以把處理這類動態(tài)問題的方法稱 為動態(tài)規(guī)劃方法。 不過，實際中尚有許多不包含時間 因素的一類“靜態(tài)”決策問題，就其本 質(zhì)而言是一次決策問題，是非動態(tài)決策 問題，但是也可以人為地引入階段的概 念當(dāng)作多階段決策問題，應(yīng)用動態(tài)規(guī)劃 方法加以解決。 4 4）資源分配問題：）資源分配問題：便屬于這類靜 態(tài)問題。如：某工業(yè)部門或公司，擬對 其所屬企業(yè)進(jìn)行稀缺資源分配，為此需 要制定出收益最大的資源分配

7、方案。這 種問題原本要求一次確定出對各企業(yè)的 資源分配量，它與時間因素?zé)o關(guān)，不屬 動態(tài)決策，但是，我們可以人為地規(guī)定 一個資源分配的階段和順序，從而使其 變成一個多階段決策問題( (后面我們將后面我們將 詳細(xì)討論這個問題詳細(xì)討論這個問題) )。 |例3：某工廠生產(chǎn)a、b、c三種產(chǎn)品， 都使用某種原材料，現(xiàn)有原材料4噸。 江不同數(shù)量的這種原料分配給各種 產(chǎn)品時產(chǎn)生的收益如表所示，試確 定使總收益最大的分配法。 abc 0 1 2 3 0 10 17 20 0 6 17 18 0 8 11 11 5 5）運輸網(wǎng)絡(luò)問題）運輸網(wǎng)絡(luò)問題：如圖7-1所 示的運輸網(wǎng)絡(luò)，點間連線上的數(shù)字 表示兩地距離(也可是

8、運費、時間 等)，要求從a至f的最短路線。 這種運輸網(wǎng)絡(luò)問題也是靜態(tài)決 策問題。但是，按照網(wǎng)絡(luò)中點的分 布，可以把它分為5個階段，而作 為多階段決策問題來研究。 |多階段決策過程的最優(yōu)化 |動態(tài)規(guī)劃的基本概念和基本原理 |動態(tài)規(guī)劃模型的建立與求解 |動態(tài)規(guī)劃在經(jīng)濟(jì)管理中的應(yīng)用 |馬氏決策規(guī)劃簡介 一、動態(tài)規(guī)劃的基本概念一、動態(tài)規(guī)劃的基本概念 使用動態(tài)規(guī)劃方法解決 多階段決策問題，首先要將實 際問題寫成動態(tài)規(guī)劃模型，同 時也為了今后敘述和討論方便， 這里需要對動態(tài)規(guī)劃的下述一 些基本術(shù)語進(jìn)一步加以說明和 定義： ( (一一) ) 階段和階段變量階段和階段變量 為了便于求解和表示決策及過程的 發(fā)展

9、順序，而把所給問題恰當(dāng)?shù)貏澐譃?若干個相互聯(lián)系又有區(qū)別的子問題，稱 之為多段決策問題的階段。一個階段， 就是需要作出一個決策的子問題，通常， 階段是按決策進(jìn)行的時間或空間上先后 順序劃分的。用以描述階段的變量叫作 階段變量，一般以k表示階段變量階 段數(shù)等于多段決策過程從開始到結(jié)束所 需作出決策的數(shù)目，圖71所示的最短 路問題就是一個四階段決策過程。 （二）狀態(tài)、狀態(tài)變量和可能狀態(tài)（二）狀態(tài)、狀態(tài)變量和可能狀態(tài) 集集 1.狀態(tài)與狀態(tài)變量。用以描述事 物(或系統(tǒng))在某特定的時間與空間域 中所處位置及運動特征的量，稱為狀 態(tài)。反映狀態(tài)變化的量叫做狀態(tài)變量。 狀態(tài)變量必須包含在給定的階段上確 定全部允

10、許決策所需要的信息。按照 過程進(jìn)行的先后，每個階段的狀態(tài)可 分為初始狀態(tài)和終止?fàn)顟B(tài)，或稱輸入 狀態(tài)和輸出狀態(tài)，階段k的初始狀態(tài)記 作sk，終止?fàn)顟B(tài)記為sk+1。但為了清楚 起見，通常定義階段的狀態(tài)即指其初 始狀態(tài)。 2可能狀態(tài)集 一般狀態(tài)變量的取值有一定的范圍或允許集 合，稱為可能狀態(tài)集，或可達(dá)狀態(tài)集?？赡軤顟B(tài) 集實際上是關(guān)于狀態(tài)的約束條件。通常可能狀態(tài) 集用相應(yīng)階段狀態(tài)sk的大寫字母sk表示，sksk， 可能狀態(tài)集可以是一離散取值的集合，也可以為 一連續(xù)的取值區(qū)間，視具體問題而定在圖71 所示的最短路問題中，第一階段狀態(tài)為a，狀態(tài) 變量s1的狀態(tài)集合s1=a；第二階段則有兩個狀 態(tài)：b1 ,

11、b2, 狀態(tài)變量s2的狀態(tài)集合s2=b1 ,b2 ； 第三階段有四個狀態(tài):c1 ,c2 ,c3 ,c4狀態(tài)變量s3 的狀態(tài)集合s3=c1 ,c2 ,c3 ,c4 ；第四階段則有 三個狀態(tài)： d1 ,d ,d3 , 狀態(tài)變量s4的狀態(tài)集合 s4=c1 ,c2 ,c3 ；第五階段則有兩個狀態(tài)e1 ,e2 狀態(tài)變量s5的狀態(tài)集合s5=e1 ,e2, （三）決策、決策變量和允許決策集合（三）決策、決策變量和允許決策集合 所謂決策，就是確定系統(tǒng)過程發(fā)展的方案。 決策的實質(zhì)是關(guān)于狀態(tài)的選擇，是決策者從給定 階段狀態(tài)出發(fā)對下一階段狀態(tài)作出的選擇。 用以描述決策變化的量稱之決策變量和狀態(tài) 變量一樣，決策變量可

12、以用一個數(shù)，一組數(shù)或一 向量來描述，也可以是狀態(tài)變量的函數(shù)，記以 uk= uk(sk)，表示于階段k狀態(tài)sk時的決策變量。 決策變量的取值往往也有一定的允許范圍， 稱之允許決策集合。決策變量uk(sk)的允許決策 集用uk(sk)表示, uk(sk) uk(sk)允許決策集合 實際是決策的約束條件。 （四）策略和允許策略集合（四）策略和允許策略集合 策略(policy)也叫決策序列策略有全過 程策略和k部子策略之分，全過程策略是指具有 n個階段的全部過程，由依次進(jìn)行的n個階段決 策 構(gòu) 成 的 決 策 序 列 ， 簡 稱 策 略 ， 表 示 為 p1,nu1,u2,un。從k階段到第n階段，依

13、次進(jìn) 行的階段決策構(gòu)成的決策序列稱為k部子策略, 表示為pk,nuk,uk+1,un ，顯然當(dāng)k=1時的k部 子策略就是全過程策略。 在實際問題中，由于在各個階段可供選擇 的決策有許多個，因此，它們的不同組合就構(gòu) 成了許多可供選擇的決策序列(策略)，由它們 組成的集合，稱之允許策略集合，記作p1,n ， 從允許策略集中，找出具有最優(yōu)效果的策略稱 為最優(yōu)策略。 （五）狀態(tài)轉(zhuǎn)移方程（五）狀態(tài)轉(zhuǎn)移方程 系統(tǒng)在階段k處于狀態(tài)sk，執(zhí)行決策uk(sk) 的結(jié)果是系統(tǒng)狀態(tài)的轉(zhuǎn)移，即系統(tǒng)由階段k的 初始狀態(tài)sk轉(zhuǎn)移到終止?fàn)顟B(tài)sk+1 ，或者說，系 統(tǒng)由k階段的狀態(tài)sk轉(zhuǎn)移到了階段k+1的狀態(tài) sk+1，多階

14、段決策過程的發(fā)展就是用階段狀態(tài) 的相繼演變來描述的。 對于具有無后效性的多階段決策過程,系 統(tǒng)由階段k到階段k+1的狀態(tài)轉(zhuǎn)移完全由階段k 的狀態(tài)sk和決策uk(sk)所確定，與系統(tǒng)過去的 狀態(tài)s1,s2, ,sk-1及其決策u1(s1), u2(s2)uk- 1(sk-1)無關(guān)。系統(tǒng)狀態(tài)的這種轉(zhuǎn)移，用數(shù)學(xué)公 式描述即有： (7-1)(,( 1k s k u k s k t k s 通常稱式(7-1)為多階段決策過程的狀 態(tài)轉(zhuǎn)移方程。有些問題的狀態(tài)轉(zhuǎn)移方程 不一定存在數(shù)學(xué)表達(dá)式，但是它們的狀 態(tài)轉(zhuǎn)移，還是有一定規(guī)律可循的。 ( (六六) ) 指標(biāo)函數(shù)指標(biāo)函數(shù) 用來衡量策略或子策略或決策的效 果的

15、某種數(shù)量指標(biāo)，就稱為指標(biāo)函數(shù)。 它是定義在全過程或各子過程或各階段 上的確定數(shù)量函數(shù)。對不同問題，指標(biāo) 函數(shù)可以是諸如費用、成本、產(chǎn)值、利 潤、產(chǎn)量、耗量、距離、時間、效用， 等等。例如：圖71的指標(biāo)就是運費。 (1)階段指標(biāo)函數(shù)（也稱階段效應(yīng)）。用 gk(sk,uk)表示第k段處于sk狀態(tài)且所作決策為 uk(sk)時的指標(biāo)，則它就是第k段指標(biāo)函數(shù)， 簡記為gk 。圖7-1的gk值就是從狀態(tài)sk到狀態(tài) sk+1的距離。譬如，gk(a,b1)=4,即a到b1的距 離為3。 (2)過程指標(biāo)函數(shù)（也稱目標(biāo)函數(shù)）。用 rk(sk,uk)表示第k子過程的指標(biāo)函數(shù)。如圖7- 1的rk(sk,uk)表示處于

16、第k段sk狀態(tài)且所作決 策為uk時，從sk點到終點f的距離。由此可見， rk(sk,uk)不僅跟當(dāng)前狀態(tài)sk有關(guān)，還跟該子 過程策略pk(sk)有關(guān)，因此它是sk和pk(sk)的 函數(shù)，嚴(yán)格說來，應(yīng)表示為:)(,( kkkk spsr 不 過 實 際 應(yīng) 用 中 往 往 表 示 為 rk(sk,uk)或rk(sk)。還跟第k子過程上 各段指標(biāo)函數(shù)有關(guān)，過程指標(biāo)函數(shù) rk(sk)通常是描述所實現(xiàn)的全過程或k 后部子過程效果優(yōu)劣的數(shù)量指標(biāo)，它 是由各階段的階段指標(biāo)函數(shù)gk(sk,uk) 累積形成的，適于用動態(tài)規(guī)劃求解的 問題的過程指標(biāo)函數(shù)（即目標(biāo)函數(shù)）， 必須具有關(guān)于階段指標(biāo)的可分離形 式對于部子

17、過程的指標(biāo)函數(shù)可以表 示為： 式中，表示某種運算，可以是加、減、乘、 除、開方等。 (7-2) ),() 1 , 1 ( 1 ),( ), 1 , 1 ,( , n u n s n g k u k s k g k u k s k g n u n s k u k s k u k s nk r nk r 多階段決策問題中，常見的目標(biāo)函 數(shù)形式之一是取各階段效應(yīng)之和的形式， 即: (7-3) 有些問題，如系統(tǒng)可靠性問題，其 目標(biāo)函數(shù)是取各階段效應(yīng)的連乘積形式， 如： (7-4) 總之，具體問題的目標(biāo)函數(shù)表達(dá)形 式需要視具體問題而定。 n ki i u i s i g k r),( n ki iiik

18、 usgr),( ( (七七) ) 最優(yōu)解最優(yōu)解 用fk(sk)表示第k子過程指標(biāo)函數(shù) 在狀態(tài)sk下的最優(yōu)值,即 稱fk(sk)為第k子過程上的最優(yōu)指標(biāo)函數(shù)； nkspsroptsf kkkk spp kk kkk , 2 , 1),(,()( )( 式中“opt”表示最優(yōu)化，視具體問題取max 或min。 )(,( kkkk spsr 最優(yōu)化原理 （貝爾曼最優(yōu)化原理） 作為一個全過程的最優(yōu)策略具有這樣 的性質(zhì)：對于最優(yōu)策略過程中的任意狀態(tài) 而言，無論其過去的狀態(tài)和決策如何，余 下的諸決策必構(gòu)成一個最優(yōu)子策略。該原 理的具體解釋是，若某一全過程最優(yōu)策略 為： )(),(,),(),()( 22

19、1111nnkk sususususp 則對上述策略中所隱含的任一狀態(tài)而 言，第k子過程上對應(yīng)于該狀態(tài)的最優(yōu)策 略必然包含在上述全過程最優(yōu)策略p1*中， 即為 )(,),(),()( 11nnkkkkkk susususp 二二. .動態(tài)規(guī)劃求解的多階段決策問題的特點動態(tài)規(guī)劃求解的多階段決策問題的特點 通常多階段決策過程的發(fā)展是通過狀 態(tài)的一系列變換來實現(xiàn)的。一般情況下， 系統(tǒng)在某個階段的狀態(tài)轉(zhuǎn)移除與本階段的 狀態(tài)和決策有關(guān)外，還可能與系統(tǒng)過去經(jīng) 歷的狀態(tài)和決策有關(guān)。因此，問題的求解 就比較困難復(fù)雜。而適合于用動態(tài)規(guī)劃方 法求解的只是一類特殊的多階段決策問題， 即具有“無后效性”的多階段決策過

20、程。 所謂無后效性，又稱馬爾柯夫性，是指系 統(tǒng)從某個階段往后的發(fā)展，僅由本階段所 處的狀態(tài)及其往后的決策所決定，與系統(tǒng) 以前經(jīng)歷的狀態(tài)和決策(歷史)無關(guān)。 例例4 4：為了說明動態(tài)規(guī)劃的基本思想方法和特 點，下面以圖7-1所示為例討論的求最短路問題 的方法。 第一種方法稱做全枚舉法或窮舉法。它的 基本思想是列舉出所有可能發(fā)生的方案和結(jié)果， 再對它們一一進(jìn)行比較，求出最優(yōu)方案。這里 從a到f的路程可以分為5個階段。第一段的走法 有兩種，第二段的走法有三種，第三四段的走 法 各 兩 種 ， 第 五 段 走 法 一 種 ， 因 此 共 有 2322124條可能的路線，分別算出各 條路線的距離，最后進(jìn)

21、行比較，可知最優(yōu)路線。 顯然，當(dāng)組成交通網(wǎng)絡(luò)的節(jié)點很 多時，用窮舉法求最優(yōu)路線的計算工作 量將會十分龐大，而且其中包含著許多 重復(fù)計算 第二種方法即所謂“局部最優(yōu)路徑” 法，是說某人從k出發(fā)，他并不顧及全 線是否最短，只是選擇當(dāng)前最短途徑， “逢近便走”，錯誤地以為局部最優(yōu)會 致整體最優(yōu)，在這種想法指導(dǎo)下，所取 決策必是ab1c1d1e1f，全程 長度是18；顯然，這種方法的結(jié)果常是 錯誤的 第三種方法是動態(tài)規(guī)劃方法。動 態(tài)規(guī)劃方法尋求該最短路問題的基本 思想是，首先將問題劃分為5個階段， 每次的選擇總是綜合后繼過程的一并 最優(yōu)進(jìn)行考慮，在各段所有可能狀態(tài) 的最優(yōu)后繼過程都已求得的情況下， 全

22、程的最優(yōu)路線便也隨之得到。 為了找出所有可能狀態(tài)的最優(yōu)后 繼過程，動態(tài)規(guī)劃方法總是從過程的 最后階段開始考慮，然后逆著實際過 程發(fā)展的順序，逐段向前遞推計算直 至始點。 具體說，此問題先從f開始，因為f是 終點。再無后繼過程，故可以接著考慮 第5階段上所有可能狀態(tài)e1，e2的最優(yōu)后 續(xù)過程。因為從e1 ,e2到f的路線是唯一 的，所以e1，e2的最優(yōu)決策和最優(yōu)后繼過 程就是到f，它們的最短距離分別是4和 3。 接著考慮階段4上可能的狀態(tài)d1，d2， d3 到f的最優(yōu)決策和最優(yōu)后繼過程在 狀態(tài)d1上，到e1是3，到e2是5，綜合考 慮后繼過程整體最優(yōu)，取最優(yōu)決策是到 e1,最優(yōu)后繼過程是d1e1

23、f ，最短距 離是7。同理，狀態(tài)d2的最優(yōu)決策是至 e2 ；d3的最優(yōu)決策是到e1。 同樣，當(dāng)階段4上所有可能狀態(tài)的最 優(yōu)后繼過程都已求得后，便可以開始考 慮階段3上所有可能狀態(tài)的最優(yōu)決策和最 優(yōu)后繼過程，如c1的最優(yōu)決策是到d1,最 優(yōu)路線是c1d1e1f ，最短距離是12 依此類推，最后可以得到從初始狀態(tài)a的 最 優(yōu) 決 策 是 到f最 優(yōu) 路 線 是 ab1c2d2e2 f ，全程的最短距離是 17。圖71中粗實線表示各點到的最優(yōu)路 線，每點上方括號內(nèi)的數(shù)字表示該點到 終點的最短路距離。 的距離到表示從 的最短距離到表示從 令 ykyk kk vvg fvf , 5 32 46 minm

24、in 7 35 43 minmin 303 404 0 22,2 11,2 2 22, 1 11, 1 1 10,22 10, 11 eed eed d eed eed d fee fee f fg fg f fg fg f fgf fgf f 8 54 53 minmin 10 55 74 minmin 12 58 75 minmin 5 33 41 minmin 33, 3 22, 3 3 22,2 11,2 2 22, 1 11, 1 1 22, 3 11, 3 3 ddc ddc c ddc ddc c ddc ddc c eed eed d fg fg f fg fg f fg fg

25、 f fg fg f 17 155 134 min 22, 11, min 15 97 87 108 min 34,2 23,2 12,2 min 2 13 86 103 122 min 33, 1 22, 1 11, 1 min 1 9 54 58 min 33,4 22,4 min 4 b f ba g b f ba g a f c f cb g c f cb g c f cb g b f c f cb g c f cb g c f cb g b f d f dc g d f dc g c f 綜上所述可見，全枚舉法雖可找出最 優(yōu)方案，但不是個好算法，局部最優(yōu)法 則完全是個錯誤方法，只有動

26、態(tài)規(guī)劃方 法屬較科學(xué)有效的算法。它的基本思想 是，把一個比較復(fù)雜的問題分解為一系 列同類型的更易求解的子問題，便于應(yīng) 用計算機(jī)。整個求解過程分為兩個階段， 先按整體最優(yōu)的思想逆序地求出各個子 問題中所有可能狀態(tài)的最優(yōu)決策與最優(yōu) 路線值，然后再順序地求出整個問題的 最優(yōu)策略和最優(yōu)路線。計算過程中，系 統(tǒng)地刪去了所有中間非最優(yōu)的方案組合， 從而使計算工作量比窮舉法大為減少。 |多階段決策過程的最優(yōu)化 |動態(tài)規(guī)劃的基本概念和基本原理 |動態(tài)規(guī)劃模型的建立與求解 |動態(tài)規(guī)劃在經(jīng)濟(jì)管理中的應(yīng)用 |馬氏決策規(guī)劃簡介 1應(yīng)將實際問題恰當(dāng)?shù)胤指畛蒼個子問題 (n個階段)。通常是根據(jù)時間或空間而劃 分的，或者在

27、經(jīng)由靜態(tài)的數(shù)學(xué)規(guī)劃模型 轉(zhuǎn)換為動態(tài)規(guī)劃模型時，常取靜態(tài)規(guī)劃 中變量的個數(shù)n，即k=n。 2正確地定義狀態(tài)變量sk，使它既能正 確地描述過程的狀態(tài)，又能滿足無后效 性動態(tài)規(guī)劃中的狀態(tài)與一般控制系統(tǒng) 中和通常所說的狀態(tài)的概念是有所不同 的，動態(tài)規(guī)劃中的狀態(tài)變量必須具備以 下三個特征： (1)要能夠正確地描述受控過程的變化特征。 (2)要滿足無后效性。即如果在某個階段狀態(tài)已經(jīng) 給定，那么在該階段以后，過程的發(fā)展不受前 面各段狀態(tài)的影響，如果所選的變量不具備無 后效性，就不能作為狀態(tài)變量來構(gòu)造動態(tài)規(guī)劃 的模型。 (3)要滿足可知性。即所規(guī)定的各段狀態(tài)變量的值， 可以直接或間接地測算得到。一般在動態(tài)規(guī)劃

28、 模型中，狀態(tài)變量大都選取那種可以進(jìn)行累計 的量。此外，在與靜態(tài)規(guī)劃模型的對應(yīng)關(guān)系上， 通常根據(jù)經(jīng)驗，線性與非線性規(guī)劃中約束條件 的個數(shù)，相當(dāng)于動態(tài)規(guī)劃中狀態(tài)變量sk的維 數(shù)而前者約束條件所表示的內(nèi)容，常就是狀 態(tài)變量sk所代表的內(nèi)容。 3正確地定義決策變量及各階段的允許 決策集合uk(sk)，根據(jù)經(jīng)驗，一般將問 題中待求的量，選作動態(tài)規(guī)劃模型中的 決策變量?；蛘咴诎鸯o態(tài)規(guī)劃模型(如 線性與非線性規(guī)劃)轉(zhuǎn)換為動態(tài)規(guī)劃模 型時，常取前者的變量xj為后者的決策 變量uk。 4. 能夠正確地寫出狀態(tài)轉(zhuǎn)移方程，至少 要能正確反映狀態(tài)轉(zhuǎn)移規(guī)律。如果給定 第k階段狀態(tài)變量sk的值，則該段的決策 變量uk一

29、經(jīng)確定，第k+1段的狀態(tài)變量 s k+ 1 的 值 也 就 完 全 確 定 ， 即 有 sk+1=tk(sk ,uk) 5根據(jù)題意,正確地構(gòu)造出目標(biāo)與變量的函 數(shù)關(guān)系目標(biāo)函數(shù)，目標(biāo)函數(shù)應(yīng)滿足下 列性質(zhì)： (1)可分性，即對于所有k后部子過程， 其目標(biāo)函數(shù)僅取決于狀態(tài)sk及其以后的決 策uk ,uk+1,un,就是說它是定義在全過 程和所有后部子過程上的數(shù)量函數(shù)。 (2)要滿足遞推關(guān)系，即 (3)函數(shù) 對其變元 rk+1來說要嚴(yán)格單調(diào)。 ),(, 111nkkkkk ssrus ),(,),( 111111, nkkkkknkkkknk ssrussususr 6寫出動態(tài)規(guī)劃函數(shù)基本方程 例如常

30、見的指標(biāo)函數(shù)是取各段 指標(biāo)和的形式 其中 表示第i階段的指標(biāo)， 它顯然是滿足上述三個性質(zhì)的。所 以上式可以寫成 ： n ki iiikk usgsr),()( ),(),( 111 nkkkkkk ssrusgr ),( iii usg 例5 （資源分配問題）某公司有資金10萬元，擬 投資于3個項目，已知對第i個項目投資xi萬元，收 益為g i (xi)，問應(yīng)如何分配資金可使總收益最大？ 其中， 解：階段k=1,2, 3 決策變量uk ：第k個項目的投資額 狀態(tài)變量sk：在第k階段時可以用于投資 第k到第3個項目的資金數(shù) 指標(biāo)函數(shù)vk,n 3 ki ii ug： ：第k階段可分配的資金 數(shù)為s

31、k時，第k至第3個項 目的最大總收益 狀態(tài)轉(zhuǎn)移方程： sk+1 = sk -uk 0| kkkk suuu kk sf最優(yōu)值函數(shù) af1求 邊界條件：0 44 sf 資源分配問題的動態(tài)規(guī)劃基本方程： 0 1 , 2 , 3max 44 11 0 sf ksfugsf kkkk su kk kk 建立遞推公式： kk su 0max kk sf k=3,2,1 kk ug 11 kk sf ：在第k階段分配的資金 數(shù)為sk時，第k至第3個項目 的最大總收益 kk sf最優(yōu)值函數(shù) 順序解法(前向動態(tài)規(guī)劃方法) 動態(tài)規(guī)劃的求解有兩種基本方法： 逆序解法(后向動態(tài)規(guī)劃方法) 順序解法的尋優(yōu)方向與過程的

32、行進(jìn)方向相同， 計算時從第一段開始逐段向后遞推，計算后一 階段要用到前一階段的求優(yōu)結(jié)果，最后一段計 算的結(jié)果就是全過程的最優(yōu)結(jié)果。 順序解法與逆序解法本質(zhì)上并無區(qū)別，一般地 說，當(dāng)初始狀態(tài)給定時可用逆序解法，當(dāng)終止 狀態(tài)給定時可用順序解法。 |兩種解法區(qū)別 1.狀態(tài)轉(zhuǎn)移方式不同 2.指標(biāo)函數(shù)的定義不同 逆序： 順序： sk+1=tk(sk ,uk) sk=tk(sk+1,uk) 3.基本方程形式不同 當(dāng)指標(biāo)函數(shù)為階段指標(biāo)和形式， 逆序解法 順序解法 解法 離散型 連續(xù)型 ：分段窮舉法 ：解析方法或線性規(guī)劃方法 沒有固定的方法 具體模型具體分析 要求：經(jīng)驗 、技巧、靈活 難！ 連續(xù)變量的離散化解

33、法 高維問題的降維法及疏密格子點法 |用逆序解法解例5 2 3 2 3 x0 33 22max)( 33 sxsf s k=3時 k=2時 )(*29max )(9max)( 2 222 x0 332 x0 22 22 22 xsx sfxsf s s 令 2 222222 )(*29)x,(shxsx 由 0) 1(*)(*49 dx dh 22 2 2 xs 解得）是極小點（因為04 4 9 2 2 2 2 22 dx hd sx 2 2 2s 極大值只可能在0,s2端點取得，f2(0)= f2(s2)=9s2 2 2 2s k=1時 2 3221 x0 11 2)(4max)( 11 s

34、sfxsf s 2 * 22222 * 22222 2222 x),()0(2/9 0 x),()0(2/9 2/9)()0( ssffs sffs ssff 此時，時， 此時，時，當(dāng) 時，解得當(dāng) 同理可求出x1=s1-1是極小點 20010010, 0 11 ）（時，兩個端點，比較fx 0 401010 * 1 11 1 x fx）（時， )2/9(10 2 * 112 sxss再由狀態(tài)轉(zhuǎn)移方程順推 10100 3 * 3 * 223 * 2 sxxssx，所以 最優(yōu)投資方案為全部資金投于第三個項 目，可得最大收益200萬元。 |多階段決策過程的最優(yōu)化 |動態(tài)規(guī)劃的基本概念和基本原理 |動態(tài)

35、規(guī)劃模型的建立與求解 |動態(tài)規(guī)劃在經(jīng)濟(jì)管理中的應(yīng)用 |馬氏決策規(guī)劃簡介 學(xué)習(xí)方法建議： 第一步 先看問題，充分理解問題 的條件、情況及求解目標(biāo)。 第二步 結(jié)合前面講到的理論和解 題過程，考慮如何著手進(jìn)行求解該問題的 工作。分析針對該動態(tài)規(guī)劃問題的“四大 要素、一個方程”這一步在開始時會 感到困難，但是一定要下決心去思考，在 思考過程中深入理解前文講到的概念和理 論。 第三步 動手把求解思路整理出 來，或者說，把該問題作為習(xí)題獨立的 來做。 第四步 把自己的求解放到一邊， 看書中的求解方法，要充分理解教材中 的論述。 第五步 對照自己的求解，分析 成敗。 1.動態(tài)規(guī)劃的四大要素 狀態(tài)變量及其可能

36、集合xkxk 決策變量及其允許集合ukuk 狀態(tài)轉(zhuǎn)移方程xk+1=tk (xk,uk) 階段效應(yīng)rk (xk,uk) 2. 動態(tài)規(guī)劃基本方程 fn+1(xn+1) = 0 (邊界條件) fk(xk) = opt urk ( xk , uk ) + fk+1(xk+1) k = n,1 61 則 max z=c1x1+c2x2+cnxn . w1x1+w2x2+wnxnw x1,x2,xn為正整數(shù)(i=1,2,n) 1 .階段k：第k次裝載第k種物品 （k=1,2,n） 2.狀態(tài)變量sk+1：在第k次開始時，背 包中允許裝入前k種物品的重量； 3.決策變量xk：第k次裝載第k種物品 的件數(shù)； 采

37、用動態(tài)規(guī)劃順序解法建模求解 s.t 4. 決策允許集合： dk(xk)=dk|0dksk+1/wk,dk為整數(shù)； 5. 狀態(tài)轉(zhuǎn)移方程：sk=sk+1-wkxk 6. 階段指標(biāo)：vk=ckxk 7. 遞推方程 fk(sk)=maxckxk+fk-1(sk) =maxckxk+fk-1(sk+1-wkxk) 8. 終端條件：f0(s1)=0 例6:對于一個具體問題c1=4，c2=5， c3=6；w1=3，w2=4，w3=5；以及w=10 用動態(tài)規(guī)劃求解 f0(s1)=0 4max)( 4 30 21 21 xxf sx 對于k=1 33222111000 1212888444000f1(s2) 1

38、09876543210s2 * 1 x )4(5 0 max)( 2312 4/32 32 xsfx sx xf 對于k=2 10210110000 13121098554000f2(s3) 101312109121098985854544000c2+f2 210210210101010100000 x2 109876543210s3 * 2 x 13 012, 56 ,13max 0(5),126),10max 5-106max)10( 222 323 210 3 3 ）（ ）（ ， fff xfxf x對于k=3 , 0 x, 1x, 2x * 3 * 2 * 1 最大值為13 67 庫存

39、問題 例8 某工廠生產(chǎn)并銷售某種產(chǎn)品，已知 今后四個月市場需求預(yù)測如表7-7，又每 月生產(chǎn)j單位產(chǎn)品費用為： c(j)= 0(j=0) 3+j(j=1,2,，6)(千元) 每月庫存j單位產(chǎn)品的費用為e(j)=0.5j(千 元)，該廠最大庫存容量為3單位，每月最 大生產(chǎn)能力為6單位，計劃開始和計劃期 末庫存量都是零。試制定四個月的生產(chǎn) 計劃，在滿足用戶需求條件下總費用最 小。假設(shè)第i+1個月的庫存量是第i個月可 銷售量與該月用戶需求量之差；而第i個 月的可銷售量是本月初庫存量與產(chǎn)量之 和。 階段k 狀態(tài)變量sk 決策變量uk 狀態(tài)轉(zhuǎn)移方程 階段指標(biāo) 終端條件 月份，k=1,2,3,4； 第k個月

40、初（發(fā)貨以前）的庫存量； 第k個月的生產(chǎn)量； sk+1=sk+uk-gk； gk(sk ,dk)=ckuk； f8(s8)=0,x8=0； 最優(yōu)指標(biāo)函數(shù) fk(sk) fk(xk)=mingk(sk ,uk)+fk+1(sk+1) =minckuk+fk+1(sk-gk+uk) 12 5 . 58 ; 5u 67 ; 4u 5 . 66 ; 3u 75 ; 2u min )2(0*5 . 0)3(min)0(f 3 3 3 3 343 52 3 ufu s u整數(shù) )()()(min)(f 333433 52 33 gusfseucs s u 整數(shù) 遞推方程 對于u3 max(0,2-s3)u

41、3min(6,5-s3,6-s3),其中s3的 取值范圍為0,1,2,3 當(dāng)s3=0時 2)0(u * 3 對于k=3 u*3(s3) f3( s3) c+e+f4 u3(s3) 0012 8811.512 1211.5812.51211.581312.51211.513.51312.512 210321043215432 3210 s3 對于k=2 u*2(s2) f2( s2) c+e+f3 u2(s2) 3 4 5 13.5 15 15.5 16 14.51713.5161517.51716.515.51817.5171618.518 210432154326543 3 2 10 s2

42、3 15.5 0 u*1(s1) f1( s1) c+f2 u1(s1) 2 21.52221.521 5432 0 s1 21 對于k=1 得出最佳生產(chǎn)計劃為，第一個月生產(chǎn)2單位，第二個月生 產(chǎn)5單位，第三個月不生產(chǎn)，第四個月生產(chǎn)4個單位。 總結(jié)此類生產(chǎn)存貯問題的基本方程為： 0)( )()()(min)(f 11 1k nn kkkkkk u k sf gusfseucs k 1,.,1,nnk 若最大庫存量為q,每月最大生產(chǎn)能力為p.則狀 態(tài)集合為： )(,min k s0 1 1 n kj k j jj gpgq 允許決策集合為： ,min k u), 0(max n kj k sq

43、k g k s j gp k s k g 74 采購與銷售問題 例9某商店在未來的四個月里，準(zhǔn)備利用商店的一個 倉庫來專門經(jīng)銷某種商品，倉庫最大容量為這種商品 1000單位。假定商店每月只能賣出倉庫現(xiàn)有的貨物。 當(dāng)商店在某月購貨時，下月初才能到貨。預(yù)測該商店 未來四個月的買賣價格如 下表，假定商店在1月開始 經(jīng)銷時，倉庫貯有該商品500單位，試問，如何制定 這四個月的訂購與銷售計劃，使獲利最大（不計庫存 費）。 1 10 12 2 8 9 3 11 13 4 15 17 月份 （k） 購買單價 （ck） 銷售單價 （pk） 解： k=1，2，3，4 狀態(tài)變量sk xk第k月賣出的貨物數(shù)量 yk

44、第k月訂購的貨物數(shù)量 狀態(tài)轉(zhuǎn)移方程： sk+1 = sk + yk -xk pk xk +fk+1（sk+1） ，求f1（500） -ck yk 0 xk sk 0yk 1000-(sk -xk ) 已知：倉庫最大容量為1000單位。商店每月只賣出倉庫 現(xiàn)有的貨物。當(dāng)商店在某月購貨時，下月初才能到 貨。 1月開始經(jīng)銷 時，倉庫貯有該商品500單位，如何制定四個月的訂 購與銷售計劃，使獲利最大（不計庫存費）。 第k月的購買單價ck，銷售單價pk， fk（sk）=第k月初庫存為時sk ， 從第k月到第4月末所獲得的最大利潤 =max ,0 xk sk ,0yk 1000-(sk -xk ) （ s

45、k + yk xk） 決策變量： s1=500 ,0sk1000 k=2，3，4 第k個月的庫存量（含上月的定貨） 基本方程： f5（s5）=0 求f1（500） fk（sk）= max pk xk 0 xk sk -ck yk 0yk 1000-(sk -xk ) +fk+1 （sk+yk-xk) k=4，3，2，1 f4（s4）= maxp4 x4 0 x4 s4 -c4 y4 0y4 1000-(s4 x4 ) =p4 s4=17 s4 x*4= s4 y*4= 0 當(dāng)k=4時 當(dāng)k=3時 f3（s3）= maxp3 x3 0 x3 s3 -c3 y3 0y3 1000-(s3 x3 )

46、 +f4 （s3+y3-x3) =max13 x3 0 x3 s3 -11 y3 0y3 1000-(s3 x3 ) +17 （s3+y3-x3) ,0s41000 ,0s31000 當(dāng)k=3時 f3（s3）=max13 x3 0 x3 s3 -11 y3 0y3 1000-(s3 x3 ) +17 （s3+y3-x3) =max-4 x3 0 x3 s3 +6 y3 0y3 1000-(s3 x3 ) +17 s3 求maxz=-4 x3+6 y3 +17s3 0 x3 s3 0y3 1000-(s3 x3 ) 取z=-4 x3+6 y3 +17s3 x3 s3 - x3 +y3 1000-

47、s3 x3, y30 求maxz=-4 x3+6 y3 +17s3 ,0s31000 x*3= s3 y*3=100 0 =6000+13s3 x3 + x1 =s3 - x3 +y3 + x2= 1000-s3 maxz=-4 x3+6 y3 +17s3 x1,x2,x3, y30 x3 y3 x1 x2 -4 6 0 0 z- 17s3 x1 1 0 1 0s3 x2 -1 1 0 1 1000-s3 x3 y3 x1 x2 2 0 0 -6 z-6000-11s3 x1 1 0 1 0s3 y3 -1 1 0 1 1000-s3 x3 y3 x1 x2 0 0 -2 -6 z-6000-

48、13s3 x3 1 0 1 0s3 y3 0 1 1 11000 x*3= s3 y*3=100 0 最優(yōu)值 z=6000+13s3 x3 s3 - x3 +y3 1000-s3 x3, y30 求maxz=-4 x3+6 y3 +17s3 標(biāo)準(zhǔn)型： 最優(yōu)解： fk（sk）= max pk xk 0 xk sk -ck yk 0yk 1000-(sk -xk ) +fk+1 （sk+yk-xk) f3（s3）=x*3= s3，y*3=100 06000+13s3 當(dāng)k=2時 f2（s2）= maxp2 x2 0 x2 s2 -c2 y2 0y2 1000-(s2 x2 ) +f3 （s2+y2

49、-x2) ,0s21000 =max9 x2 0 x2 s2 -8 y2 0y2 1000-(s2 x2 ) +6000+13 （s2+y2-x2) =max-4 x2 0 x2 s2 +5 y2 0y2 1000-(s2 x2 ) +13 s2+6000 x*2= 0 =11000+8s2 ，y*2=1000-s2 fk（sk）= max pk xk 0 xk sk -ck yk 0yk 1000-(sk -xk ) +fk+1 （sk+yk-xk) 當(dāng)k=1時 f1（s1）= maxp1 x1 0 x1 s1 -c1 y1 0y1 1000-(s1 x1 ) +f2 （s1+y1-x1)

50、,s1=500 x*1= 500 =17000 ，y*1=0 f2（s2）=x*2= 011000+8s2，y*2=1000-s2 =max12 x1 0 x1 500 -10y1 0y1 1000-(500 x1 ) +11000+8（500+y1-x1) =max4 x1 0 x1 500 -2y1 0y1+ x1 500 +15000 . . 0 1 y . . . . . . 500 11 yx 1 x . f1（500）=17000 x*1= 500 ，y*1=0 f2（s2）=x*2= 011000+8s2，y*2=1000-s2 f3（s3）=x*3= s3 ，y*3=1000 6000+13s3 f4（s4）= 17 s4x*4= s4，y*4= 0 xk第k月賣出的貨物數(shù)量 yk第k月訂購的貨物數(shù)量 sk+1 = sk + yk -xk fk（sk）=第k月初庫存為時sk ， 從第k月到第4月末所獲得的最大利潤 結(jié)論：當(dāng)?shù)?個月初庫存為時500時， 4個月能獲