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

第6章動(dòng)態(tài)規(guī)劃動(dòng)態(tài)規(guī)劃的基本理論（2學(xué)時(shí)）確定型動(dòng)態(tài)規(guī)劃（2學(xué)時(shí)）隨機(jī)型動(dòng)態(tài)規(guī)劃（1學(xué)時(shí)）動(dòng)態(tài)規(guī)劃的軟件求解簡介

（1學(xué)時(shí)）

第6章動(dòng)態(tài)規(guī)劃動(dòng)態(tài)規(guī)劃的基本理論一、離散隨機(jī)性動(dòng)態(tài)規(guī)劃

隨機(jī)型的動(dòng)態(tài)規(guī)劃是指狀態(tài)的轉(zhuǎn)移律是不確定的，即對給定的狀態(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+1c1c2cN12N第15講隨機(jī)型動(dòng)態(tài)規(guī)劃及軟件介紹一、離散隨機(jī)性動(dòng)態(tài)規(guī)劃sk狀態(tài)xk決策概率k階段的收益p

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

例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)用最?。浚惱滩?：例6-7）

例1某公司承擔(dān)一種新產(chǎn)品研制任務(wù)，合同要求三個(gè)

解：把三次試制當(dāng)作三個(gè)階段（k=1,2,3）,決策變量xk表示第k次生產(chǎn)的產(chǎn)品的件數(shù)；狀態(tài)變量sk表示第k次試制前是否已經(jīng)生產(chǎn)出合格品，如果有合格品，則sk=0；如果沒有合格品，記sk=1。最優(yōu)函數(shù)fk(sk)表示從狀態(tài)sk、決策xk出發(fā)的第k階段以后的最小期望費(fèi)用。故有fk(0)＝0。生產(chǎn)出一件合格品的概率為0.4，所以生產(chǎn)xk件產(chǎn)品都不合格的概率為，至少有一件合格品的概率為1-，故有狀態(tài)轉(zhuǎn)移方程為

解：把三次試制當(dāng)作三個(gè)階段（k=1,2,3）,決

用C(xk)表示第k階段的費(fèi)用，第k階段的費(fèi)用包括制造成本和裝配費(fèi)用，故有

根據(jù)狀態(tài)轉(zhuǎn)移方程以及C(xk)，可得到

如果3個(gè)月后沒有試制出一件合格品，則要承擔(dān)2000元的罰金，因此有f4(1)=20。

當(dāng)k=3時(shí)，計(jì)算如下表：

x3

s3

C(x3)+20×f3(s3)x3*012345600——————001201511.29.328.598.568.938.565x3C(x3)+20×

當(dāng)k=2時(shí)，計(jì)算如下表：

x2

s2

C(x2)+8.56×f2(s2)x2*0123400————0018.568.147.086.857.116.853x2C(x2)+8.56×0

當(dāng)k=1時(shí)，有

x1

s1

C(x1)+6.85×f1(s1)x1*012300

—

—

—0016.857.116.466.486.462x1C(x1)+6.85×0

上面三個(gè)表中并沒有列出xk取更大數(shù)值的情況，因?yàn)榭梢宰C明以后的C(xk)+fk+1(1)的值是對xk單調(diào)增加的。

因此得到的最優(yōu)策略是，在第1個(gè)階段試制2件產(chǎn)品；如果都不合格，在第2階段試制3件產(chǎn)品；如果仍都不合格，則在第3個(gè)階段試制5件產(chǎn)品。該策略得到的最小的期望費(fèi)用6.46。

上面三個(gè)表中并沒有列出xk取更大數(shù)值的情況例2不確定性采購問題（類例教材1：例6-8）某廠生產(chǎn)上需要在近五周內(nèi)必須采購一批原料,而估計(jì)在未來五周內(nèi)原材料的價(jià)格是波動(dòng)的，浮動(dòng)價(jià)格和概率已知。如何采購使其采購價(jià)格的數(shù)學(xué)期望最小，并求出期望值。單價(jià)概率5000.36000.37000.4單價(jià)概率5000.36000.37000.4動(dòng)態(tài)規(guī)劃的數(shù)學(xué)模型該問題分成五個(gè)階段，k表示周，k＝1，2，3，4，5設(shè)Sk表示為第k周的實(shí)際價(jià)格。決策變量Uk,Uk＝1表示為第k周決定采購，Uk＝0表示為第k周決定等待。XkE表示為第k周決定等待,而在以后采取最優(yōu)決策時(shí)采購價(jià)格的期望值。fk(Sk)表示第k周實(shí)際價(jià)格為Sk時(shí)，從第k周到第5周采取最優(yōu)策略所得的最小期望值。遞推關(guān)系式：fk(Sk)＝min{Sk，XkE}邊界條件：f5(S5)＝S5其中：XkE=0.3fk+1(500)+0.3fk+1(600)+0.4fk+1(700)Sk∈{500,600,700}動(dòng)態(tài)規(guī)劃的數(shù)學(xué)模型遞推關(guān)系式：f5(S5)＝S5S5∈{500,600,700}f5(500)＝500

f5(600)＝600

f5(700)＝700即在第五周，不論原材料的市場價(jià)格如何，都必須購買。當(dāng)k=5時(shí)f4(S4)＝min{S4，X4E}X4E=0.3f5(500)+0.3f5(600)+0.4f5(700)＝610f4(500)＝500f4(600)＝600f4(700)＝610當(dāng)k=4時(shí)U4＝1，當(dāng)S4＝500，600U4＝0，當(dāng)S4＝700即在第四周時(shí)，當(dāng)市場價(jià)格為500或600時(shí)，選擇購買原材料。若市場價(jià)格為700時(shí)，則繼續(xù)等待。f5(S5)＝S5S5∈{500,600,700}當(dāng)當(dāng)k=3時(shí)，f3(S3)＝min{S3，X3E}X3E=0.3f4(500)+0.3f4(600)+0.4f4(700)＝574f3(500)＝500f3(600)＝574

f3(700)＝574U3＝1，當(dāng)S3＝500U3＝0，當(dāng)S3＝600，700即在第三周時(shí)，當(dāng)市場價(jià)格為500時(shí)，選擇購買原材料。若市場價(jià)格為600或700時(shí)，則繼續(xù)等待。隨機(jī)型動(dòng)態(tài)規(guī)劃及軟件介紹課件當(dāng)k=2時(shí)，f2(S2)＝min{S2，X2E}X2E=0.3f3(500)+0.3f3(600)+0.4f3(700)＝551.8f3(500)＝500f3(600)＝551.8

f3(700)＝551.8U2＝1，當(dāng)S2＝500U2＝0，當(dāng)S2＝600，700即在第二周時(shí)，當(dāng)市場價(jià)格為500時(shí)，選擇購買原材料。若市場價(jià)格為600或700時(shí)，則繼續(xù)等待。當(dāng)k=1時(shí)，f1(S1)＝min{S1，X1E}X1E=0.3f2(500)+0.3f2(600)+0.4f2(700)＝536.26f1(500)＝500f1(600)＝536.26

f1(700)＝536.26當(dāng)k=2時(shí)，U1＝1，當(dāng)S1＝500U1＝0，當(dāng)S1＝600，700即在第一周時(shí)，當(dāng)市場價(jià)格為500時(shí)，選擇購買原材料。若市場價(jià)格為600或700時(shí)，則繼續(xù)等待。由上可知，在第1、2、3周時(shí)，當(dāng)價(jià)格為500時(shí)，選擇購買原材料，若價(jià)格為600或700，則繼續(xù)等待。在第4周時(shí)，當(dāng)價(jià)格為500或600時(shí)，選擇購買原材料，若價(jià)格為700，則繼續(xù)等待，在第5周，則無論時(shí)什么價(jià)格都購買。依照這樣的最優(yōu)策略，價(jià)格的數(shù)學(xué)期望值為：500×0.3+536.26×0.3+536.26×0.4=525.382U1＝1，當(dāng)S1＝500二、動(dòng)態(tài)規(guī)劃軟件求解簡介1使用Lingo求解最短路二、動(dòng)態(tài)規(guī)劃軟件求解簡介1使用Lingo求解最短路例6-9

求A到G的最短距離路線，各地間的距離如圖6-3所示。

圖6-3例6-9的圖例6-9求A到G的最短距離路線，各地間的距離如圖6-3隨機(jī)型動(dòng)態(tài)規(guī)劃及軟件介紹課件隨機(jī)型動(dòng)態(tài)規(guī)劃及軟件介紹課件隨機(jī)型動(dòng)態(tài)規(guī)劃及軟件介紹課件二、動(dòng)態(tài)規(guī)劃軟件求解簡介2使用Matlab求解最短路二、動(dòng)態(tài)規(guī)劃軟件求解簡介2使用Matlab求解最短【例6-10】用Matlab求解圖6-7的最短路。圖6-7上海至災(zāi)區(qū)的公路網(wǎng)絡(luò)圖解:計(jì)算機(jī)求解在該題中首先用[1,2,3,4,5,6,7,8,9,10]來代表?！纠?-10】用Matlab求解圖6-7的最短路。圖6-7隨機(jī)型動(dòng)態(tài)規(guī)劃及軟件介紹課件隨機(jī)型動(dòng)態(tài)規(guī)劃及軟件介紹課件三、動(dòng)態(tài)規(guī)劃應(yīng)用案例分析(6.5)論文1:基于Matlab的0-1背包問題的動(dòng)態(tài)規(guī)劃方法求解論文2:基于MATLAB的動(dòng)態(tài)規(guī)劃常用算法的實(shí)現(xiàn)論文3:基于啟發(fā)式動(dòng)態(tài)規(guī)劃方法的發(fā)電商最優(yōu)競價(jià)策略論文4:基于自適應(yīng)動(dòng)態(tài)規(guī)劃的系統(tǒng)邊際電價(jià)預(yù)測1電廠內(nèi)部機(jī)組負(fù)荷的經(jīng)濟(jì)分配2電力企業(yè)購網(wǎng)電量分配案例分析四、動(dòng)態(tài)規(guī)劃文獻(xiàn)閱讀三、動(dòng)態(tài)規(guī)劃應(yīng)用案例分析(6.5)論文1:基于Matlab的第6章動(dòng)態(tài)規(guī)劃動(dòng)態(tài)規(guī)劃的基本理論（2學(xué)時(shí)）確定型動(dòng)態(tài)規(guī)劃（2學(xué)時(shí)）隨機(jī)型動(dòng)態(tài)規(guī)劃（1學(xué)時(shí)）動(dòng)態(tài)規(guī)劃的軟件求解簡介

（1學(xué)時(shí)）

第6章動(dòng)態(tài)規(guī)劃動(dòng)態(tài)規(guī)劃的基本理論一、離散隨機(jī)性動(dòng)態(tài)規(guī)劃

隨機(jī)型的動(dòng)態(tài)規(guī)劃是指狀態(tài)的轉(zhuǎn)移律是不確定的，即對給定的狀態(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+1c1c2cN12N第15講隨機(jī)型動(dòng)態(tài)規(guī)劃及軟件介紹一、離散隨機(jī)性動(dòng)態(tài)規(guī)劃sk狀態(tài)xk決策概率k階段的收益p

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

例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)用最?。浚惱滩?：例6-7）

例1某公司承擔(dān)一種新產(chǎn)品研制任務(wù)，合同要求三個(gè)

解：把三次試制當(dāng)作三個(gè)階段（k=1,2,3）,決策變量xk表示第k次生產(chǎn)的產(chǎn)品的件數(shù)；狀態(tài)變量sk表示第k次試制前是否已經(jīng)生產(chǎn)出合格品，如果有合格品，則sk=0；如果沒有合格品，記sk=1。最優(yōu)函數(shù)fk(sk)表示從狀態(tài)sk、決策xk出發(fā)的第k階段以后的最小期望費(fèi)用。故有fk(0)＝0。生產(chǎn)出一件合格品的概率為0.4，所以生產(chǎn)xk件產(chǎn)品都不合格的概率為，至少有一件合格品的概率為1-，故有狀態(tài)轉(zhuǎn)移方程為

解：把三次試制當(dāng)作三個(gè)階段（k=1,2,3）,決

用C(xk)表示第k階段的費(fèi)用，第k階段的費(fèi)用包括制造成本和裝配費(fèi)用，故有

根據(jù)狀態(tài)轉(zhuǎn)移方程以及C(xk)，可得到

如果3個(gè)月后沒有試制出一件合格品，則要承擔(dān)2000元的罰金，因此有f4(1)=20。

當(dāng)k=3時(shí)，計(jì)算如下表：

x3

s3

C(x3)+20×f3(s3)x3*012345600——————001201511.29.328.598.568.938.565x3C(x3)+20×

當(dāng)k=2時(shí)，計(jì)算如下表：

x2

s2

C(x2)+8.56×f2(s2)x2*0123400————0018.568.147.086.857.116.853x2C(x2)+8.56×0

當(dāng)k=1時(shí)，有

x1

s1

C(x1)+6.85×f1(s1)x1*012300

—

—

—0016.857.116.466.486.462x1C(x1)+6.85×0

上面三個(gè)表中并沒有列出xk取更大數(shù)值的情況，因?yàn)榭梢宰C明以后的C(xk)+fk+1(1)的值是對xk單調(diào)增加的。

因此得到的最優(yōu)策略是，在第1個(gè)階段試制2件產(chǎn)品；如果都不合格，在第2階段試制3件產(chǎn)品；如果仍都不合格，則在第3個(gè)階段試制5件產(chǎn)品。該策略得到的最小的期望費(fèi)用6.46。

上面三個(gè)表中并沒有列出xk取更大數(shù)值的情況例2不確定性采購問題（類例教材1：例6-8）某廠生產(chǎn)上需要在近五周內(nèi)必須采購一批原料,而估計(jì)在未來五周內(nèi)原材料的價(jià)格是波動(dòng)的，浮動(dòng)價(jià)格和概率已知。如何采購使其采購價(jià)格的數(shù)學(xué)期望最小，并求出期望值。單價(jià)概率5000.36000.37000.4單價(jià)概率5000.36000.37000.4動(dòng)態(tài)規(guī)劃的數(shù)學(xué)模型該問題分成五個(gè)階段，k表示周，k＝1，2，3，4，5設(shè)Sk表示為第k周的實(shí)際價(jià)格。決策變量Uk,Uk＝1表示為第k周決定采購，Uk＝0表示為第k周決定等待。XkE表示為第k周決定等待,而在以后采取最優(yōu)決策時(shí)采購價(jià)格的期望值。fk(Sk)表示第k周實(shí)際價(jià)格為Sk時(shí)，從第k周到第5周采取最優(yōu)策略所得的最小期望值。遞推關(guān)系式：fk(Sk)＝min{Sk，XkE}邊界條件：f5(S5)＝S5其中：XkE=0.3fk+1(500)+0.3fk+1(600)+0.4fk+1(700)Sk∈{500,600,700}動(dòng)態(tài)規(guī)劃的數(shù)學(xué)模型遞推關(guān)系式：f5(S5)＝S5S5∈{500,600,700}f5(500)＝500

f5(600)＝600

f5(700)＝700即在第五周，不論原材料的市場價(jià)格如何，都必須購買。當(dāng)k=5時(shí)f4(S4)＝min{S4，X4E}X4E=0.3f5(500)+0.3f5(600)+0.4f5(700)＝610f4(500)＝500f4(600)＝600f4(700)＝610當(dāng)k=4時(shí)U4＝1，當(dāng)S4＝500，600U4＝0，當(dāng)S4＝700即在第四周時(shí)，當(dāng)市場價(jià)格為500或600時(shí)，選擇購買原材料。若市場價(jià)格為700時(shí)，則繼續(xù)等待。f5(S5)＝S5S5∈{500,600,700}當(dāng)當(dāng)k=3時(shí)，f3(S3)＝min{S3，X3E}X3E=0.3f4(500)+0.3f4(600)+0.4f4(700)＝574f3(500)＝500f3(600)＝574

f3(700)＝574U3＝1，當(dāng)S3＝500U3＝0，當(dāng)S3＝600，700即在第三周時(shí)，當(dāng)市場價(jià)格為500時(shí)，選擇購買原材料。若市場價(jià)格為600或700時(shí)，則繼續(xù)等待。隨機(jī)型動(dòng)態(tài)規(guī)劃及軟件介紹課件當(dāng)k=2時(shí)，f2(S2)＝min{S2，X2E}X2E=0.3f3(500)+0.3f3(600)+0.4f3(700)＝551.8f3(500)＝500f3(600)＝551.8

f3(700)＝551.8U2＝1，當(dāng)S2＝500U2＝0，當(dāng)S2＝600，700即在第二周時(shí)，當(dāng)市場價(jià)格為500時(shí)，選擇購買原材料。若市場價(jià)格為600或700時(shí)，則繼續(xù)等待。當(dāng)k=1時(shí)，f1(S1)＝min{S1，X1E}X1E=0.3f2(500)+0.3f2(600)+0.4f2(700)＝536.26f1(500)＝500f1(600)＝536.26

f1(700)＝536.26當(dāng)k=2時(shí)，U1＝1，當(dāng)S1＝500U1＝0