1、第第6章章 動態(tài)規(guī)劃動態(tài)規(guī)劃動態(tài)規(guī)劃的基本理論動態(tài)規(guī)劃的基本理論 （2學(xué)時）學(xué)時）確定型動態(tài)規(guī)劃確定型動態(tài)規(guī)劃 （2學(xué)時）學(xué)時）隨機型動態(tài)規(guī)劃隨機型動態(tài)規(guī)劃 （1學(xué)時）學(xué)時） 動態(tài)規(guī)劃的軟件求解簡介動態(tài)規(guī)劃的軟件求解簡介 （1學(xué)時）學(xué)時）一、離散隨機性動態(tài)規(guī)劃一、離散隨機性動態(tài)規(guī)劃 隨機型的動態(tài)規(guī)劃是指狀態(tài)的轉(zhuǎn)移律是不確定的，即對給定的狀態(tài)和決策，下一階段的到達狀態(tài)是具有確定概率分布的隨機變量，這個概率分布由本階段的狀態(tài)和決策完全確定。隨機型動態(tài)規(guī)劃的基本結(jié)構(gòu)如下圖： sk狀態(tài) xk決策概率k階段的收益p1p2pN.k+1階段的狀態(tài)sk+1c1c2cN 1 2N第15講 隨機型動態(tài)規(guī)劃及軟件介

2、紹 圖中圖中N N表示第表示第k+1k+1階段可能的狀態(tài)數(shù)，階段可能的狀態(tài)數(shù)，p p1 1、p p2 2、ppN N為給定狀態(tài)為給定狀態(tài)s sk k和決策和決策x xk k的前提下，可能達到下一個狀態(tài)的的前提下，可能達到下一個狀態(tài)的概率。概率。c ci i為從為從k k階段狀態(tài)階段狀態(tài)s sk k轉(zhuǎn)移到轉(zhuǎn)移到k+1 k+1 階段狀態(tài)為階段狀態(tài)為i i時的指時的指標(biāo)函數(shù)值。標(biāo)函數(shù)值。 在隨機性的動態(tài)規(guī)劃問題中，由于下一階段到達的狀在隨機性的動態(tài)規(guī)劃問題中，由于下一階段到達的狀態(tài)和階段的效益值不確定，只能根據(jù)各階段的期望效益值態(tài)和階段的效益值不確定，只能根據(jù)各階段的期望效益值進行優(yōu)化。進行優(yōu)化。

3、例例1 1 某公司承擔(dān)一種新產(chǎn)品研制任務(wù)，合同要求三個月內(nèi)交出一件合格的樣品，否則將索賠2000元。根據(jù)有經(jīng)驗的技術(shù)人員估計，試制品合格的概率為0.4，每次試制一批的裝配費為200元，每件產(chǎn)品的制造成本為100元。每次試制的周期為1個月。問該如何安排試制，每次生產(chǎn)多少件，才能使得期望費用最小？（類例教材（類例教材1：例：例6-7） 解：把三次試制當(dāng)作三個階段（解：把三次試制當(dāng)作三個階段（k=1,2,3k=1,2,3）, ,決策變量決策變量x xk k表示第表示第k k次生產(chǎn)的產(chǎn)品的件數(shù)；狀態(tài)變量次生產(chǎn)的產(chǎn)品的件數(shù)；狀態(tài)變量s sk k表示第表示第k k次試制前次試制前是否已經(jīng)生產(chǎn)出合格品，如果

4、有合格品，則是否已經(jīng)生產(chǎn)出合格品，如果有合格品，則s sk k=0=0；如果沒有；如果沒有合格品，記合格品，記s sk k=1=1。最優(yōu)函數(shù)。最優(yōu)函數(shù)f fk k(s(sk k) )表示從狀態(tài)表示從狀態(tài)s sk k、決策、決策x xk k出發(fā)出發(fā)的第的第k k階段以后的最小期望費用。故有階段以后的最小期望費用。故有f fk k(0)(0)0 0。 生產(chǎn)出一件合格品的概率為生產(chǎn)出一件合格品的概率為0.40.4，所以生產(chǎn)，所以生產(chǎn)x xk k件產(chǎn)品都不件產(chǎn)品都不合格的概率為合格的概率為 ，至少有一件合格品的概率為，至少有一件合格品的概率為1- 1- ，故，故有狀態(tài)轉(zhuǎn)移方程為有狀態(tài)轉(zhuǎn)移方程為 kx6

5、 . 0kkxkxkspsp6 . 01)0(6 . 0) 1(11kx6.0 用用C(xC(xk k) )表示第表示第k k階段的費用，第階段的費用，第k k階段的費用包階段的費用包括制造成本和裝配費用，故有括制造成本和裝配費用，故有 根據(jù)狀態(tài)轉(zhuǎn)移方程以及根據(jù)狀態(tài)轉(zhuǎn)移方程以及C(xC(xk k) )，可得到，可得到 0002)(kkkkxxxxC)1 (6 . 0)0()6 . 01 ()(min) 1 (11kxkxkxkffxcfkkk)1 (6 . 0)(min1kxkxfxckk 如果如果3 3個月后沒有試制出一件合格品，則要承擔(dān)個月后沒有試制出一件合格品，則要承擔(dān)20002000元

6、的罰金，因此有元的罰金，因此有f f4 4(1)=20(1)=20。 當(dāng)當(dāng)k=3k=3時，計算如下表：時，計算如下表： x3 s3 C(x3)+20f3(s3) x3* 0 1 2 3 4 5 6 0 0 0 0 1 20 1511.2 9.32 8.59 8.56 8.93 8.56 5 0.63x 當(dāng)當(dāng)k=2k=2時，計算如下表：時，計算如下表： x2 s2 C(x2)+8.56f2(s2) x2* 0 1 2 3 4 0 0 0 0 18.568.147.086.857.11 6.85 3 0.62x 當(dāng)當(dāng)k=1k=1時，有時，有 x1 s1 C(x1)+6.85f1(s1) x1* 0

7、 1 2 3 0 0 0 0 16.85 7.11 6.46 6.48 6.46 2 0.61x 上面三個表中并沒有列出上面三個表中并沒有列出x xk k取更大數(shù)值的情況，因取更大數(shù)值的情況，因為可以證明以后的為可以證明以后的C(xC(xk k)+ f)+ fk+1k+1(1)(1)的值是對的值是對x xk k單調(diào)單調(diào)增加的。增加的。 因此得到的最優(yōu)策略是，在第因此得到的最優(yōu)策略是，在第1 1個階段試制個階段試制2 2件產(chǎn)件產(chǎn)品；如果都不合格，在第品；如果都不合格，在第2 2階段試制階段試制3 3件產(chǎn)品；如果仍都件產(chǎn)品；如果仍都不合格，則在第不合格，則在第3 3個階段試制個階段試制5 5件產(chǎn)品

8、。該策略得到的最件產(chǎn)品。該策略得到的最小的期望費用小的期望費用6.466.46。 0.6kx例例2 不確定性采購問題（類例教材不確定性采購問題（類例教材1：例：例6-8）某廠生產(chǎn)上需要在近五周內(nèi)必須采購一批原料,而估計在未來五周內(nèi)原材料的價格是波動的，浮動價格和概率已知。如何采購使其采購價格的數(shù)學(xué)期數(shù)學(xué)期望最小望最小，并求出期望值。單價概率5000.36000.37000.4動態(tài)規(guī)劃的數(shù)學(xué)模型動態(tài)規(guī)劃的數(shù)學(xué)模型 該問題分成五個該問題分成五個階段階段，k表示周，表示周，k1，2，3，4，5 設(shè)設(shè)Sk表示為第表示為第k周的實際價格。周的實際價格。 決策變量決策變量Uk, ,Uk1表示為第表示為第k

9、周決定采購，周決定采購，Uk0表示為表示為第第k周決定等待。周決定等待。 XkE表示為第表示為第k周決定等待周決定等待,而在以后采取最優(yōu)決策時采購而在以后采取最優(yōu)決策時采購價格的期望值。價格的期望值。 fk(Sk)表示第表示第k周實際價格為周實際價格為Sk時，從第時，從第k周到第周到第5周采取周采取最優(yōu)策略所得的最小期望值。最優(yōu)策略所得的最小期望值。遞推關(guān)系式：遞推關(guān)系式：fk(Sk)minSk，XkE邊界條件：邊界條件：f5(S5)S5其中：其中：XkE=0.3 fk+1(500)+0.3 fk+1(600)+ 0.4fk+1(700) Sk500,600,700f5(S5)S5 S5500

10、,600,700f5(500)500 f5(600)600 f5(700)700即在第五周，不論原材料的市場價格如何，都必須購買。當(dāng)當(dāng)k=5k=5時時f4(S4)minS4，X4EX4E=0.3 f5(500)+0.3 f5(600)+ 0.4f5(700)610f4(500)500 f4(600)600 f4(700)610當(dāng)當(dāng)k=4時時U U4 41 1 ，當(dāng)，當(dāng)S S4 4500500，600600U U4 40 0 ，當(dāng)，當(dāng)S S4 4700700即在第四周時，當(dāng)市場價格為500或600時，選擇購買原材料。若市場價格為700時，則繼續(xù)等待。當(dāng)k=3時，f3(S3)minS3，X3EX3

11、E=0.3 f4(500)+0.3 f4(600)+ 0.4f4(700)574f3(500)500 f3(600)574 f3(700)574U31 ，當(dāng)S3500U30 ，當(dāng)S3600，700即在第三周時，當(dāng)市場價格為500時，選擇購買原材料。若市場價格為600或700時，則繼續(xù)等待。 當(dāng)當(dāng)k=2時時，f2(S2)minS2，X2EX2E=0.3 f3(500)+0.3 f3(600)+ 0.4f3(700)551.8f3(500)500 f3(600)551.8 f3(700)551.8U21 ，當(dāng)，當(dāng)S2500U20 ，當(dāng)，當(dāng)S2600，700即在第二周時，當(dāng)市場價格為500時，選擇購

12、買原材料。若市場價格為600或700時，則繼續(xù)等待。當(dāng)當(dāng)k=1時，時，f1(S1)minS1，X1EX1E=0.3 f2(500)+0.3 f2(600)+ 0.4f2(700)536.26f1(500)500 f1(600)536.26 f1(700)536.26U11 ，當(dāng)，當(dāng)S1500U10 ，當(dāng)，當(dāng)S1600，700即在第一周時，當(dāng)市場價格為500時，選擇購買原材料。若市場價格為600或700時，則繼續(xù)等待。由上可知，在第1、2、3周時，當(dāng)價格為500時，選擇購買原材料，若價格為600或700，則繼續(xù)等待。在第4周時，當(dāng)價格為500或600時，選擇購買原材料，若價格為700，則繼續(xù)等待

13、，在第5周，則無論時什么價格都購買。依照這樣的最優(yōu)策略，價格的數(shù)學(xué)期望值為價格的數(shù)學(xué)期望值為：5000.3+536.260.3+ 536.260.4=525.382二、動態(tài)規(guī)劃軟件求解簡介二、動態(tài)規(guī)劃軟件求解簡介 1 1 使用使用LingoLingo求解最短路求解最短路例例6-9 6-9 求求A A到到G G的最短距離路線，各地間的距離如圖的最短距離路線，各地間的距離如圖6-36-3所示。所示。 圖圖6-3 6-3 例例6-96-9的圖的圖二、動態(tài)規(guī)劃軟件求解簡介二、動態(tài)規(guī)劃軟件求解簡介 2 2 使用使用MatlabMatlab求解最短路求解最短路【例【例6-106-10】用】用MatlabM

14、atlab求解圖求解圖6-76-7的最短路。的最短路。A2B3B1B1C2C3C1D2DE24374632462363333434圖圖6-7 6-7 上海至災(zāi)區(qū)的公路網(wǎng)絡(luò)圖上海至災(zāi)區(qū)的公路網(wǎng)絡(luò)圖解解: 計算機求解計算機求解 在該題中首先用在該題中首先用1,2,3,4,5,6,7,8,9,101,2,3,4,5,6,7,8,9,10來代表來代表12312312 ,A B B B C C C D D E。三、動態(tài)規(guī)劃應(yīng)用案例分析三、動態(tài)規(guī)劃應(yīng)用案例分析(6.5)(6.5)論文論文1:1:基于基于MatlabMatlab的的0- 1 0- 1 背包問題的動態(tài)規(guī)劃方法求解背包問題的動態(tài)規(guī)劃方法求解論文論文2:2:基于基于MAT LAB MAT LAB 的動態(tài)