第15講隨機(jī)型動(dòng)態(tài)規(guī)劃及軟件介紹

1、第第6章章 動(dòng)態(tài)規(guī)劃動(dòng)態(tài)規(guī)劃動(dòng)態(tài)規(guī)劃的基本理論動(dòng)態(tài)規(guī)劃的基本理論 （2學(xué)時(shí)）學(xué)時(shí)）確定型動(dòng)態(tài)規(guī)劃確定型動(dòng)態(tài)規(guī)劃 （2學(xué)時(shí)）學(xué)時(shí)）隨機(jī)型動(dòng)態(tài)規(guī)劃隨機(jī)型動(dòng)態(tài)規(guī)劃 （1學(xué)時(shí)）學(xué)時(shí)） 動(dòng)態(tài)規(guī)劃的軟件求解簡(jiǎn)介動(dòng)態(tài)規(guī)劃的軟件求解簡(jiǎn)介 （1學(xué)時(shí)）學(xué)時(shí)）一、離散隨機(jī)性動(dòng)態(tài)規(guī)劃一、離散隨機(jī)性動(dòng)態(tài)規(guī)劃 隨機(jī)型的動(dòng)態(tài)規(guī)劃是指狀態(tài)的轉(zhuǎn)移律是不確定的，即對(duì)給定的狀態(tài)和決策，下一階段的到達(dá)狀態(tài)是具有確定概率分布的隨機(jī)變量，這個(gè)概率分布由本階段的狀態(tài)和決策完全確定。隨機(jī)型動(dòng)態(tài)規(guī)劃的基本結(jié)構(gòu)如下圖： sk狀態(tài) xk決策概率k階段的收益p1p2pN.k+1階段的狀態(tài)sk+1c1c2cN 1 2N第15講 隨機(jī)型動(dòng)態(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的前提下，可能達(dá)到下一個(gè)狀態(tài)的的前提下，可能達(dá)到下一個(gè)狀態(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時(shí)的指時(shí)的指標(biāo)函數(shù)值。標(biāo)函數(shù)值。 在隨機(jī)性的動(dòng)態(tài)規(guī)劃問題中，由于下一階段到達(dá)的狀在隨機(jī)性的動(dòng)態(tài)規(guī)劃問題中，由于下一階段到達(dá)的狀態(tài)和階段的效益值不確定，只能根據(jù)各階段的期望效益值態(tài)和階段的效益值不確定，只能根據(jù)各階段的期望效益值進(jìn)行優(yōu)化。進(jìn)行優(yōu)化。

3、例例1 1 某公司承擔(dān)一種新產(chǎn)品研制任務(wù)，合同要求三個(gè)月內(nèi)交出一件合格的樣品，否則將索賠2000元。根據(jù)有經(jīng)驗(yàn)的技術(shù)人員估計(jì)，試制品合格的概率為0.4，每次試制一批的裝配費(fèi)為200元，每件產(chǎn)品的制造成本為100元。每次試制的周期為1個(gè)月。問該如何安排試制，每次生產(chǎn)多少件，才能使得期望費(fèi)用最??？（類例教材（類例教材1：例：例6-7） 解：把三次試制當(dāng)作三個(gè)階段（解：把三次試制當(dāng)作三個(gè)階段（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èi)用。故有階段以后的最小期望費(fèi)用。故有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階段的費(fèi)用，第階段的費(fèi)用，第k k階段的費(fèi)用包階段的費(fèi)用包括制造成本和裝配費(fèi)用，故有括制造成本和裝配費(fèi)用，故有 根據(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個(gè)月后沒有試制出一件合格品，則要承擔(dān)個(gè)月后沒有試制出一件合格品，則要承擔(dān)20002000元

6、的罰金，因此有元的罰金，因此有f f4 4(1)=20(1)=20。 當(dāng)當(dāng)k=3k=3時(shí)，計(jì)算如下表：時(shí)，計(jì)算如下表： 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時(shí)，計(jì)算如下表：時(shí)，計(jì)算如下表： 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時(shí)，有時(shí)，有 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 上面三個(gè)表中并沒有列出上面三個(gè)表中并沒有列出x xk k取更大數(shù)值的情況，因取更大數(shù)值的情況，因?yàn)榭梢宰C明以后的為可以證明以后的C(xC(xk k)+ f)+ fk+1k+1(1)(1)的值是對(duì)的值是對(duì)x xk k單調(diào)單調(diào)增加的。增加的。 因此得到的最優(yōu)策略是，在第因此得到的最優(yōu)策略是，在第1 1個(gè)階段試制個(gè)階段試制2 2件產(chǎn)件產(chǎn)品；如果都不合格，在第品；如果都不合格，在第2 2階段試制階段試制3 3件產(chǎn)品；如果仍都件產(chǎn)品；如果仍都不合格，則在第不合格，則在第3 3個(gè)階段試制個(gè)階段試制5 5件產(chǎn)品

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

9、周決定采購(gòu)，周決定采購(gòu)，Uk0表示為表示為第第k周決定等待。周決定等待。 XkE表示為第表示為第k周決定等待周決定等待,而在以后采取最優(yōu)決策時(shí)采購(gòu)而在以后采取最優(yōu)決策時(shí)采購(gòu)價(jià)格的期望值。價(jià)格的期望值。 fk(Sk)表示第表示第k周實(shí)際價(jià)格為周實(shí)際價(jià)格為Sk時(shí)，從第時(shí)，從第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即在第五周，不論原材料的市場(chǎng)價(jià)格如何，都必須購(gòu)買。當(dāng)當(dāng)k=5k=5時(shí)時(shí)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時(shí)時(shí)U U4 41 1 ，當(dāng)，當(dāng)S S4 4500500，600600U U4 40 0 ，當(dāng)，當(dāng)S S4 4700700即在第四周時(shí)，當(dāng)市場(chǎng)價(jià)格為500或600時(shí)，選擇購(gòu)買原材料。若市場(chǎng)價(jià)格為700時(shí)，則繼續(xù)等待。當(dāng)k=3時(shí)，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即在第三周時(shí)，當(dāng)市場(chǎng)價(jià)格為500時(shí)，選擇購(gòu)買原材料。若市場(chǎng)價(jià)格為600或700時(shí)，則繼續(xù)等待。 當(dāng)當(dāng)k=2時(shí)時(shí)，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即在第二周時(shí)，當(dāng)市場(chǎng)價(jià)格為500時(shí)，選擇購(gòu)

12、買原材料。若市場(chǎng)價(jià)格為600或700時(shí)，則繼續(xù)等待。當(dāng)當(dāng)k=1時(shí)，時(shí)，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即在第一周時(shí)，當(dāng)市場(chǎng)價(jià)格為500時(shí)，選擇購(gòu)買原材料。若市場(chǎng)價(jià)格為600或700時(shí)，則繼續(xù)等待。由上可知，在第1、2、3周時(shí)，當(dāng)價(jià)格為500時(shí)，選擇購(gòu)買原材料，若價(jià)格為600或700，則繼續(xù)等待。在第4周時(shí)，當(dāng)價(jià)格為500或600時(shí)，選擇購(gòu)買原材料，若價(jià)格為700，則繼續(xù)等待

13、，在第5周，則無論時(shí)什么價(jià)格都購(gòu)買。依照這樣的最優(yōu)策略，價(jià)格的數(shù)學(xué)期望值為價(jià)格的數(shù)學(xué)期望值為：5000.3+536.260.3+ 536.260.4=525.382二、動(dòng)態(tài)規(guī)劃軟件求解簡(jiǎn)介二、動(dòng)態(tài)規(guī)劃軟件求解簡(jiǎn)介 1 1 使用使用LingoLingo求解最短路求解最短路例例6-9 6-9 求求A A到到G G的最短距離路線，各地間的距離如圖的最短距離路線，各地間的距離如圖6-36-3所示。所示。 圖圖6-3 6-3 例例6-96-9的圖的圖二、動(dòng)態(tài)規(guī)劃軟件求解簡(jiǎn)介二、動(dòng)態(tài)規(guī)劃軟件求解簡(jiǎn)介 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ò)圖解解: 計(jì)算機(jī)求解計(jì)算機(jī)求解 在該題中首先用在該題中首先用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。三、動(dòng)態(tài)規(guī)劃應(yīng)用案例分析三、動(dòng)態(tài)規(guī)劃應(yīng)用案例分析(6.5)(6.5)論文論文1:1:基于基于MatlabMatlab的的0- 1 0- 1 背包問題的動(dòng)態(tài)規(guī)劃方法求解背包問題的動(dòng)態(tài)規(guī)劃方法求解論文論文2:2:基于基于MAT LAB MAT LAB 的動(dòng)態(tài)