




版權說明:本文檔由用戶提供并上傳,收益歸屬內容提供方,若內容存在侵權,請進行舉報或認領
文檔簡介
1、第第6章章 動態(tài)規(guī)劃動態(tài)規(guī)劃動態(tài)規(guī)劃的基本理論動態(tài)規(guī)劃的基本理論 (2學時)學時)確定型動態(tài)規(guī)劃確定型動態(tài)規(guī)劃 (2學時)學時)隨機型動態(tài)規(guī)劃隨機型動態(tài)規(guī)劃 (1學時)學時) 動態(tài)規(guī)劃的軟件求解簡介動態(tài)規(guī)劃的軟件求解簡介 (1學時)學時)一、離散隨機性動態(tài)規(guī)劃一、離散隨機性動態(tài)規(guī)劃 隨機型的動態(tài)規(guī)劃是指狀態(tài)的轉移律是不確定的,即對給定的狀態(tài)和決策,下一階段的到達狀態(tài)是具有確定概率分布的隨機變量,這個概率分布由本階段的狀態(tài)和決策完全確定。隨機型動態(tài)規(guī)劃的基本結構如下圖: 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、p pN 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轉移到轉移到k+1 k+1 階段狀態(tài)為階段狀態(tài)為i i時的指時的指標函數(shù)值。標函數(shù)值。 在隨機性的動態(tài)規(guī)劃問題中,由于下一階段到達的狀在隨機性的動態(tài)規(guī)劃問題中,由于下一階段到達的狀態(tài)和階段的效益值不確定,只能根據(jù)各階段的期望效益值態(tài)和階段的效益值不確定,只能根據(jù)各階段的期望效益值進行優(yōu)化。進行優(yōu)化。
3、 例例1 1 某公司承擔一種新產品研制任務,合同要求三個月內交出一件合格的樣品,否則將索賠2000元。根據(jù)有經驗的技術人員估計,試制品合格的概率為0.4,每次試制一批的裝配費為200元,每件產品的制造成本為100元。每次試制的周期為1個月。問該如何安排試制,每次生產多少件,才能使得期望費用最???(類例教材(類例教材1:例:例6-7) 解:把三次試制當作三個階段(解:把三次試制當作三個階段(k=1,2,3k=1,2,3), ,決策變量決策變量x xk k表示第表示第k k次生產的產品的件數(shù);狀態(tài)變量次生產的產品的件數(shù);狀態(tài)變量s sk k表示第表示第k k次試制前次試制前是否已經生產出合格品,如
4、果有合格品,則是否已經生產出合格品,如果有合格品,則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。 生產出一件合格品的概率為生產出一件合格品的概率為0.40.4,所以生產,所以生產x xk k件產品都不件產品都不合格的概率為合格的概率為 ,至少有一件合格品的概率為,至少有一件合格品的概率為1- 1- ,故,故有狀態(tài)轉移方程為有狀態(tài)轉移方程為 kx
5、6 . 0kkxkxkspsp6 . 01)0(6 . 0) 1(11kx6.0 用用C(xC(xk k) )表示第表示第k k階段的費用,第階段的費用,第k k階段的費用包階段的費用包括制造成本和裝配費用,故有括制造成本和裝配費用,故有 根據(jù)狀態(tài)轉移方程以及根據(jù)狀態(tài)轉移方程以及C(xC(xk k) ),可得到,可得到 0002)(kkkkxxxxC)1 (6 . 0)0()6 . 01 ()(min) 1 (11kxkxkxkffxcfkkk)1 (6 . 0)(min1kxkxfxckk 如果如果3 3個月后沒有試制出一件合格品,則要承擔個月后沒有試制出一件合格品,則要承擔20002000
6、元的罰金,因此有元的罰金,因此有f f4 4(1)=20(1)=20。 當當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 當當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 當當k=1k=1時,有時,有 x1 s1 C(x1)+6.85f1(s1) x1*
7、0 1 2 3 0 0 0 0 16.857.116.466.48 6.46 2 0.61x 上面三個表中并沒有列出上面三個表中并沒有列出x xk k取更大數(shù)值的情況,因取更大數(shù)值的情況,因為可以證明以后的為可以證明以后的C(xC(xk k)+ f)+ fk+1k+1(1)(1)的值是對的值是對x xk k單調單調增加的。增加的。 因此得到的最優(yōu)策略是,在第因此得到的最優(yōu)策略是,在第1 1個階段試制個階段試制2 2件產件產品;如果都不合格,在第品;如果都不合格,在第2 2階段試制階段試制3 3件產品;如果仍都件產品;如果仍都不合格,則在第不合格,則在第3 3個階段試制個階段試制5 5件產品。該
8、策略得到的最件產品。該策略得到的最小的期望費用小的期望費用6.466.46。 0.6kx例例2 不確定性采購問題(類例教材不確定性采購問題(類例教材1:例:例6-8)某廠生產上需要在近五周內必須采購一批原料,而估計在未來五周內原材料的價格是波動的,浮動價格和概率已知。如何采購使其采購價格的數(shù)學期數(shù)學期望最小望最小,并求出期望值。單價概率5000.36000.37000.4動態(tài)規(guī)劃的數(shù)學模型動態(tài)規(guī)劃的數(shù)學模型 該問題分成五個該問題分成五個階段階段,k表示周,表示周,k1,2,3,4,5 設設Sk表示為第表示為第k周的實際價格。周的實際價格。 決策變量決策變量Uk, ,Uk1表示為第表示為第k周決
9、定采購,周決定采購,Uk0表示為表示為第第k周決定等待。周決定等待。 XkE表示為第表示為第k周決定等待周決定等待,而在以后采取最優(yōu)決策時采購而在以后采取最優(yōu)決策時采購價格的期望值。價格的期望值。 fk(Sk)表示第表示第k周實際價格為周實際價格為Sk時,從第時,從第k周到第周到第5周采取周采取最優(yōu)策略所得的最小期望值。最優(yōu)策略所得的最小期望值。遞推關系式:遞推關系式: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,6
10、00,700f5(500)500 f5(600)600 f5(700)700即在第五周,不論原材料的市場價格如何,都必須購買。當當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當當k=4時時U U4 41 1 ,當,當S S4 4500500,600600U U4 40 0 ,當,當S S4 4700700即在第四周時,當市場價格為500或600時,選擇購買原材料。若市場價格為700時,則繼續(xù)等待。當k=3時,f3(S3)minS3,X3EX3E=
11、0.3 f4(500)+0.3 f4(600)+ 0.4f4(700)574f3(500)500 f3(600)574 f3(700)574U31 ,當S3500U30 ,當S3600,700即在第三周時,當市場價格為500時,選擇購買原材料。若市場價格為600或700時,則繼續(xù)等待。 當當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 ,當,當S2500U20 ,當,當S2600,700即在第二周時,當市場價格為500時,選擇購買原
12、材料。若市場價格為600或700時,則繼續(xù)等待。當當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 ,當,當S1500U10 ,當,當S1600,700即在第一周時,當市場價格為500時,選擇購買原材料。若市場價格為600或700時,則繼續(xù)等待。由上可知,在第1、2、3周時,當價格為500時,選擇購買原材料,若價格為600或700,則繼續(xù)等待。在第4周時,當價格為500或600時,選擇購買原材料,若價格為700,則繼續(xù)等待,在
13、第5周,則無論時什么價格都購買。依照這樣的最優(yōu)策略,價格的數(shù)學期望值為價格的數(shù)學期望值為: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】用用MatlabMatla
14、b求解圖求解圖6-76-7的最短路。的最短路。A2B3B1B1C2C3C1D2DE24374632462363333434圖圖6-7 6-7 上海至災區(qū)的公路網絡圖上海至災區(qū)的公路網絡圖解解: 計算機求解計算機求解 在該題中首先用在該題中首先用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ī)劃應用案例分析三、動態(tài)規(guī)劃應用案例分析(6.5)(6.5)論文論文1:1:基于基于MatlabMatlab的的0- 1 0- 1 背包問題的動態(tài)規(guī)劃方法求解背包問題的動態(tài)規(guī)劃方法求解論文論文2:2
溫馨提示
- 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網頁內容里面會有圖紙預覽,若沒有圖紙預覽就沒有圖紙。
- 4. 未經權益所有人同意不得將文件中的內容挪作商業(yè)或盈利用途。
- 5. 人人文庫網僅提供信息存儲空間,僅對用戶上傳內容的表現(xiàn)方式做保護處理,對用戶上傳分享的文檔內容本身不做任何修改或編輯,并不能對任何下載內容負責。
- 6. 下載文件中如有侵權或不適當內容,請與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。
最新文檔
- 2025屆四川省瀘州市五中學七年級英語第二學期期末預測試題含答案
- 2025年出入管理協(xié)議
- 2025年項目部環(huán)境保護與污染防治安全協(xié)議
- 2025年標準純凈水交易條款協(xié)議
- 2025年北京租賃住宅策劃協(xié)議版
- 2025年分校擴展與策劃管理協(xié)議
- 人防工程施工中與地方基礎設施的銜接問題
- 未來糧食儲備體系的技術革新與發(fā)展趨勢
- 商業(yè)空間節(jié)假日環(huán)境維護規(guī)劃基礎知識點歸納
- 理賠業(yè)務系統(tǒng)升級風險基礎知識點歸納
- 解讀《2023年中國血脂管理指南》
- 運用PDCA提高影像診斷與手術符合率演示文稿
- 公司聲譽風險管理辦法(2022年修訂)
- 700水平軋機主傳動系統(tǒng)設計
- 海南事業(yè)單位招聘2023年考試真題及答案解析
- 中職PLC期末考試試卷
- MT/T 699-1997煤礦采空區(qū)阻化汽霧防火技術規(guī)范
- GB/T 39655.2-2020造船船用螺旋槳制造公差第2部分:直徑在0.8 m至2.5 m的螺旋槳
- GB/T 33974-2017熱軋花紋鋼板及鋼帶
- GB/T 19363.1-2008翻譯服務規(guī)范第1部分:筆譯
- GB 2759-2015食品安全國家標準冷凍飲品和制作料
評論
0/150
提交評論