




版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進(jìn)行舉報(bào)或認(rèn)領(lǐng)
文檔簡介
1、4.3.1 建摸1、理論依據(jù)-最優(yōu)化原理最優(yōu)化原理: 一個(gè)過程的最優(yōu)策略具有這樣的性質(zhì),即無論初始狀態(tài)及初始決策如何,對于先前決策所形成的狀態(tài)而言,其以后的所有決策必構(gòu)成最優(yōu)策略2、動態(tài)規(guī)劃模型的幾個(gè)要素:1)階段數(shù)k2)狀態(tài)變量sk3)決策變量uk ( sk )4)指標(biāo)函數(shù)Vk,n狀態(tài)轉(zhuǎn)移方程kkkusTs,15)最優(yōu)值函數(shù)fk(sk)3、建立動態(tài)規(guī)劃模型的基本要求:1)所研究的問題必須能夠分成幾個(gè)相互聯(lián)系的階段,而且在每一個(gè)階段都具有需要進(jìn)行決策的問題。2)在每一階段都必須有若干個(gè)與該階段相關(guān)的狀態(tài)一般情況下,狀態(tài)是所研究系統(tǒng)在該階段可能處于的情況或條件建模時(shí)總是從與決策有關(guān)的條件中,或是
2、從問題的約束條件中去選擇狀態(tài)變量。3)具有明確的指標(biāo)函數(shù),且階段指標(biāo)值可以計(jì)算4)能正確列出最優(yōu)值函數(shù)的遞推公式和邊界條件(b)能通過現(xiàn)階段的決策,使當(dāng)前狀態(tài)轉(zhuǎn)移 成下一階段的狀態(tài)即 能夠給出狀態(tài)轉(zhuǎn)移方程kkkusTs,1(c)狀態(tài)的無后效性之前的過程無關(guān)最優(yōu)策略應(yīng)與的為出發(fā)點(diǎn)的后部子過程階段的狀態(tài)即以第kkssk狀態(tài)的選取必須注意以下幾個(gè)要點(diǎn):(a)在所研究問題的各階段,都能直接或間 接確定狀態(tài)變量的取值例 (資源分配問題) 某公司有資金a萬元,擬投資于n個(gè)項(xiàng)目,已知對第i個(gè)項(xiàng)目投資xi萬元,收益為g i (xi),問應(yīng)如何分配資金可使總收益最大?解:階段k=1,2, ,n狀態(tài)變量sk決策變
3、量uk:第k個(gè)項(xiàng)目的投資額:在第k階段時(shí)可以用于投資 第k到第n個(gè)項(xiàng)目的資金數(shù)狀態(tài)轉(zhuǎn)移方程:sk+1 = sk -uk指標(biāo)函數(shù)Vk,nnkiiiug:第k階段可分配的資金數(shù)為sk時(shí),第k至第n個(gè)項(xiàng)目的最大總收益0|kkkksuuUkksf最優(yōu)值函數(shù) af1求kksf邊界條件:k=n,n-1, ,2,1011nnsf資源分配問題的動態(tài)規(guī)劃基本方程: 01 , 2 , 1,max11110nnkkkksukksfnnksfugsfkk建立遞推公式:kkug11kksfkksu0max:在第k階段分配的資金數(shù)為sk時(shí),第k至第n個(gè)項(xiàng)目的最大總收益kksf最優(yōu)值函數(shù)某種機(jī)器的工作系統(tǒng)由n個(gè)部件串聯(lián)組成
4、,只要有一個(gè)部件失靈,整個(gè)系統(tǒng)就不能正常工作。為提高系統(tǒng)工作的可靠性,在每一個(gè)部件上均裝有主要元件的備用件,并設(shè)計(jì)了備用元件自動投入裝置。顯然,備用元件越多,整個(gè)系統(tǒng)的可靠性越大,但備用元件增多也會導(dǎo)致系統(tǒng)的成本、重量相應(yīng)增大。設(shè)部件i(i=1,2, ,n)上裝有xi個(gè)備用元件時(shí),正常工作的概率為pi ( xi )。設(shè)裝一個(gè)i部件的設(shè)備元件費(fèi)用為ci ,重量wi為,要求整個(gè)系統(tǒng)所裝備用元件的總費(fèi)用不超過C,總重量不超過W,問如何選擇個(gè)部件的備用元件數(shù),使整個(gè)系統(tǒng)的工作可靠性最大?例 復(fù)合系統(tǒng)工作可靠性問題解:設(shè)A-整個(gè)系統(tǒng)正常工作,Ai部件i正常工作滿足:Cxcniii1Wxwniii1且為整
5、數(shù)0ix非線性規(guī)劃問題 nAPAPAPAP21則,21nAAAA iinixp1 iinixpP1max數(shù)學(xué)模型為:求系統(tǒng)由n個(gè)部件串聯(lián)組成,每一個(gè)部件上裝有備用件,部件i(i=1,2, ,n)上裝有xi個(gè)備用元件時(shí),正常工作的概率為pi ( xi )。設(shè)裝一個(gè)i部件的設(shè)備元件費(fèi)用為ci ,重量wi為,要求總費(fèi)用不超過C,總重量不超過W,問如何選擇個(gè)部件的備用元件數(shù),使整個(gè)系統(tǒng)的工作可靠性最大?例 復(fù)合系統(tǒng)工作可靠性問題解: n個(gè)部件=n個(gè)階段決策變量uk = 部件k上所裝的備用元件數(shù)xk 狀態(tài)變量:sk=第k個(gè)到第n個(gè)部件可使用的總費(fèi)用yk=第k個(gè)到第n個(gè)部件容許的總重量狀態(tài)轉(zhuǎn)移方程:kkk
6、kucss1kkkkuwyy1指標(biāo)函數(shù)Vk,n iinkiup最優(yōu)指標(biāo)函數(shù)fk(sk, yk )= 在部件k,可使用 的總費(fèi)用為sk,總重量為yk 時(shí),從部件k 到部件n的系統(tǒng)工作可靠性的最大值kumax111,kkkkkysfupKU復(fù)合系統(tǒng)工作可靠性的動態(tài)規(guī)劃基本方程為:kkkysf,1,111nnnysf與問題無關(guān)WCf,1求1 , 2 , 1,nnk動態(tài)規(guī)劃基本方程: 01 , 2 , 1,1111nnkkkkukksfnnksfugoptsfk 11 , 2 , 1,1111nnkkkkukksfnnksfugoptsfk或4.4.2 動態(tài)規(guī)劃模型的求解解法離散型連續(xù)型:分段窮舉法:
7、利用解析方法或線性規(guī)劃方法沒有固定的方法具體模型具體分析要求:經(jīng)驗(yàn) 、技巧、靈活難!投資額收益工廠 12314.525274.57397.58410.511105121513一、離散變量的分段窮舉法例(資源分配問題)某有色金屬公司擬撥出50萬元對所屬三家冶煉廠進(jìn)行技術(shù)改造,若以十萬元為最少分割單位,各廠收益與投資的關(guān)系如下表:問:對三個(gè)工廠如何分配,才能使總收益達(dá)到最大?狀態(tài)變量sk:階段k=1,2,3決策變量uk:給工廠k的投資額在第k階段時(shí)可供工廠k到工廠3分配的資金數(shù)kksu 0狀態(tài)轉(zhuǎn)移方程:sk+1 = sk -ukg k (uk)=給工廠k投資 uk(十萬元)的收益指標(biāo)函數(shù)Vk,n3
8、kiiiug 110maxkkkksukksfugsfkkfk( sk )投資工廠k至工廠3所得的最大總收益求f1( 5 )=在工廠k,可供分配的資金數(shù)為sk時(shí),kumax11kkkksfugkksu 0 044sf基本方程:k=33s03u0112233)(33sf0 57845451013投資額收益工廠 12314.525274.57397.58410.5111051215131 , 2 , 3k 3303333maxugsfsu *3u012345k=22s2u)(22sf0032fg 001*2u020 15 2050 1 27 7 4.50或1730 1 2 38 9 9.5 7.5
9、29.5450 1 2 3 4 101011.512.511312.50 1 2 3 4 5131212.514.5 1615416 332202222maxsfugsfsu投資額收益工廠 12314.525274.57397.58410.511105121513sk+1 = sk -uk3s03u0112233)(33sf0 57845451013*3u012345k=1 221101111maxsfugsfsusk+1 = sk -uk投資額收益工廠 12314.525274.57397.58410.5111051215131s1u)(11sf 2211sfug*1u516 0 1 2 3
10、 4 517 16.5 16 15.5 12117最大總收益:十萬元)(17)5(1f最優(yōu)策略:1*1u3,*2u1,*3u2s2u)(22sf0032fg 001*2u020 15 2050 1 27 7 4.50或1730 1 2 38 9 9.5 7.529.5450 1 2 3 4 101011.512.511312.50 1 2 3 4 5131212.514.5 1615416二、連續(xù)變量的解法例(季節(jié)工問題)某工廠的生產(chǎn)任務(wù)隨季節(jié)波動,為降低成本宜用季節(jié)臨時(shí)工,但熟練的生產(chǎn)工人臨時(shí)難以聘到,培訓(xùn)新手費(fèi)用又高,各季節(jié)工人需用量如下表所示,每季節(jié)超過需用量聘用,每人浪費(fèi)2000元,聘
11、用或解聘費(fèi)為200元乘上兩個(gè)季節(jié)聘用人數(shù)之差的平方,問廠長一年中應(yīng)如何聘用工人可使總花費(fèi)最?。浚俣üべY按實(shí)際工作時(shí)間計(jì)算,則聘用人數(shù)可為分?jǐn)?shù))季度i 春 夏 秋 冬 春需用量gk 255 220 240 200 255方案1:255 220 240 200 255總費(fèi)用:+200352200552+200202+200402=1249000方案2:255 245 245 245 255總費(fèi)用:+200102200102+200025+20005 +200045 =190000解:階段1,狀態(tài)變量sk第k-1季度聘用人數(shù)決策變量uk第k季度聘用人數(shù)狀態(tài)轉(zhuǎn)移方程: sk+1 = uk fk(sk
12、)=第k-1季度聘用人數(shù)為sk人時(shí),第k季度到 第4季度的最小總費(fèi)用 ,220s2255gkuk255季度i 春 夏 秋 冬 春需用量gk 255 220 240 200 255234k=1,2,34s1=255,240s3255,200s4255已知:每季節(jié)超過需用量聘用,每人浪費(fèi)2000元,聘用 和解聘費(fèi)為200元乘上兩個(gè)季節(jié)聘用人數(shù)之差的平方=min +fk+1(sk+1)+2000(uk gk)gkuk255200(uk uk-1)2求f1(255) =min +fk+1(uk)+2000(uk gk)gkuk255200(uk sk)2基本方程:fk(sk)=min +fk+1(uk
13、)f5(s5)=0求f1(255)+2000(uk gk)gkuk255200(uk sk)2min f4(s4)=+2000(u4 g4)g4u4255200(u4 s4)2u*4=255=200(255 s4)2,200s4255當(dāng)k=4時(shí)min f3(s3)=+f4(u3)+2000(u3 g3)200(u3 s3)2g3u3255=min +2000(u3 200)200(u3 s3)2200u3255+200(255 u3)2當(dāng)k=3時(shí),240s3255k=4,3,2,1f3(s3) =min +2000(u3 200)200(u3 s3)2200u3255+200(255 u3)2
14、2332332552002002000200uusuh令33332554002000400usududh則1000040080033su03dudh令1252133su得0800232duhd且12521*33su為最小值點(diǎn)即1252133su所以f3(s3)=23323211302007521200021125200sss2332326050150100025050sss當(dāng)k=3時(shí),240s3255255,2003umin min f2(s2)=+f3(u2)+2000(u2 g2)200(u2 s2)2g2u2255fk(sk)=+fk+1(uk)+2000(uk gk)gkuk25520
15、0(uk sk)2已知:f3(s3)2332326050150100025050sss當(dāng)k=2時(shí),220s2255=min +2000(u2 240)200(u2 s2)2240u2255+f3(u2)=min 587500048000400200300222222ussu240u2255狀態(tài)轉(zhuǎn)移方程: sk+1 = uk f2(s2)當(dāng)k=2時(shí),220s2255=min 587500048000400200300222222ussu240u22552dudh4800040060022su02dudh令803222su得0600222duhd且8032*,22su所以f2(s2)=587500
16、048000400200300222222ussuh令5875000)8032(48000400200)8032(300222222ssss3955000320003200222ss255,2402u為最小值點(diǎn)即803222sumin fk(sk)=+fk+1(uk)+2000(uk gk)gkuk255200(uk sk)2已知:f2(s2)3955000320003200222ss當(dāng)k=1時(shí),s1=255min f1(255)=+f2(u1)+2000(u1 g1)g1u1255200(u1 s1)2=min +2000(u1 220)220u1255200(u1 255)23955000320003200121uu狀態(tài)轉(zhuǎn)移方程: sk+1 = uk 3200034002000)255(400111uududh132000316001u01dudh令5 .2471u得031600212duhd且為最小值點(diǎn)即5 .2471uf1(255)=1850005
溫馨提示
- 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 人人文庫網(wǎng)僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負(fù)責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。
最新文檔
- 生產(chǎn)經(jīng)營單位安全生產(chǎn)教育和培訓(xùn)
- 2020年安全月培訓(xùn)記錄
- 陜西省咸陽市百靈中學(xué)2025年物理高二第二學(xué)期期末調(diào)研試題含解析
- 上海市徐匯區(qū)市級名校2025年物理高一第二學(xué)期期末達(dá)標(biāo)測試試題含解析
- 銻揮發(fā)物減排方法-洞察及研究
- 體育教育課心得體會
- 企業(yè)老職工辭職報(bào)告
- 美容養(yǎng)生館管理規(guī)范
- 創(chuàng)傷性肌肉缺血查房
- 腎性骨軟化個(gè)案護(hù)理
- 2024年網(wǎng)格員考試題庫完美版
- 出入境交通運(yùn)輸工具檢查課件
- 2024年廣東省安全員C證(專職安全生產(chǎn)管理人員)考試試題題庫
- 防雨雪冰凍應(yīng)急演練
- GB/T 44536-2024CVD陶瓷涂層熱膨脹系數(shù)和殘余應(yīng)力試驗(yàn)方法
- 大疆在線測評題
- DB3402T 19-2021 汽車后市場 美容養(yǎng)護(hù)服務(wù)規(guī)范
- 化工公司安全知識競賽題庫(共1000題)
- 中國移動公開競聘考試題庫(含答案)
- DLT 572-2021 電力變壓器運(yùn)行規(guī)程
- HJ 636-2012 水質(zhì) 總氮的測定 堿性過硫酸鉀消解紫外分光光度法
評論
0/150
提交評論