動態(tài)規(guī)劃的建模與求解

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