4.3動(dòng)態(tài)規(guī)劃建模與求解ppt課件

1、4.3.1 建摸1、實(shí)際根據(jù)-最優(yōu)化原理最優(yōu)化原理： 一個(gè)過(guò)程的最優(yōu)戰(zhàn)略具有這樣的性質(zhì)，即無(wú)論初始形狀及初始決策如何，對(duì)于先前決策所構(gòu)成的形狀而言，其以后的一切決策必構(gòu)成最優(yōu)戰(zhàn)略2、動(dòng)態(tài)規(guī)劃模型的幾個(gè)要素：1)階段數(shù)k2)形狀變量sk3)決策變量uk sk 4)目的函數(shù)Vk,n形狀轉(zhuǎn)移方程kkkusTs,15)最優(yōu)值函數(shù)fk(sk)3、建立動(dòng)態(tài)規(guī)劃模型的根本要求：1所研討的問(wèn)題必需可以分成幾個(gè)相互聯(lián)絡(luò)的階段，而且在每一個(gè)階段都具有需求進(jìn)展決策的問(wèn)題。2在每一階段都必需有假設(shè)干個(gè)與該階段相關(guān)的形狀普通情況下，形狀是所研討系統(tǒng)在該階段能夠處于的情況或條件建模時(shí)總是從與決策有關(guān)的條件中，或是從問(wèn)題的

2、約束條件中去選擇形狀變量。3)具有明確的目的函數(shù)，且階段目的值可以計(jì)算4)能正確列出最優(yōu)值函數(shù)的遞推公式和邊境條件b能經(jīng)過(guò)現(xiàn)階段的決策，使當(dāng)前形狀轉(zhuǎn)移 成下一階段的形狀即 可以給出形狀轉(zhuǎn)移方程kkkusTs,1c形狀的無(wú)后效性之前的過(guò)程無(wú)關(guān)最優(yōu)策略應(yīng)與的為出發(fā)點(diǎn)的后部子過(guò)程階段的狀態(tài)即以第kkssk形狀的選取必需留意以下幾個(gè)要點(diǎn)：a在所研討問(wèn)題的各階段，都能直接或間 接確定形狀變量的取值例 資源分配問(wèn)題 某公司有資金a萬(wàn)元，擬投資于n個(gè)工程，知對(duì)第i個(gè)工程投資xi萬(wàn)元，收益為g i (xi)，問(wèn)應(yīng)如何分配資金可使總收益最大？解：階段k=1,2, ,n形狀變量sk決策變量uk：第k個(gè)工程的投資額

3、：在第k階段時(shí)可以用于投資 第k到第n個(gè)工程的資金數(shù)形狀轉(zhuǎn)移方程：sk+1 = sk -uk目的函數(shù)Vk,nnkiiiug：第k階段可分配的資金數(shù)為sk時(shí)，第k至第n個(gè)工程的最大總收益0|kkkksuuUkksf最優(yōu)值函數(shù) af1求kksf邊境條件：k=n,n-1, ,2,1011nnsf資源分配問(wèn)題的動(dòng)態(tài)規(guī)劃根本方程： 01 , 2 , 1,max11110nnkkkksukksfnnksfugsfkk建立遞推公式：kkug11kksfkksu0max：在第k階段分配的資金數(shù)為sk時(shí)，第k至第n個(gè)工程的最大總收益kksf最優(yōu)值函數(shù)某種機(jī)器的任務(wù)系統(tǒng)由n個(gè)部件串聯(lián)組成，只需有一個(gè)部件失靈，整個(gè)

4、系統(tǒng)就不能正常任務(wù)。為提高系統(tǒng)任務(wù)的可靠性，在每一個(gè)部件上均裝有主要元件的備用件，并設(shè)計(jì)了備用元件自動(dòng)投入安裝。顯然，備用元件越多，整個(gè)系統(tǒng)的可靠性越大，但備用元件增多也會(huì)導(dǎo)致系統(tǒng)的本錢(qián)、分量相應(yīng)增大。設(shè)部件i(i=1,2, ,n)上裝有xi個(gè)備用元件時(shí)，正常任務(wù)的概率為pi xi 。設(shè)裝一個(gè)i部件的設(shè)備元件費(fèi)用為ci ，分量wi為，要求整個(gè)系統(tǒng)所配備用元件的總費(fèi)用不超越C，總分量不超越W，問(wèn)如何選擇個(gè)部件的備用元件數(shù)，使整個(gè)系統(tǒng)的任務(wù)可靠性最大？例 復(fù)合系統(tǒng)任務(wù)可靠性問(wèn)題解：設(shè)A-整個(gè)系統(tǒng)正常任務(wù)，Ai部件i正常任務(wù)滿(mǎn)足：Cxcniii1Wxwniii1且為整數(shù)0ix非線性規(guī)劃問(wèn)題 nAPA

5、PAPAP21則,21nAAAA iinixp1 iinixpP1max數(shù)學(xué)模型為：求系統(tǒng)由n個(gè)部件串聯(lián)組成，每一個(gè)部件上裝有備用件，部件i(i=1,2, ,n)上裝有xi個(gè)備用元件時(shí)，正常任務(wù)的概率為pi xi 。設(shè)裝一個(gè)i部件的設(shè)備元件費(fèi)用為ci ，分量wi為，要求總費(fèi)用不超越C，總分量不超越W，問(wèn)如何選擇個(gè)部件的備用元件數(shù)，使整個(gè)系統(tǒng)的任務(wù)可靠性最大？例 復(fù)合系統(tǒng)任務(wù)可靠性問(wèn)題解： n個(gè)部件=n個(gè)階段決策變量uk = 部件k上所裝的備用元件數(shù)xk 形狀變量：sk=第k個(gè)到第n個(gè)部件可運(yùn)用的總費(fèi)用yk=第k個(gè)到第n個(gè)部件允許的總分量形狀轉(zhuǎn)移方程：kkkkucss1kkkkuwyy1目的函數(shù)

6、Vk,n iinkiup最優(yōu)目的函數(shù)fk(sk， yk = 在部件k，可運(yùn)用 的總費(fèi)用為sk，總分量為yk 時(shí)，從部件k 到部件n的系統(tǒng)任務(wù)可靠性的最大值kumax111,kkkkkysfupKU復(fù)合系統(tǒng)任務(wù)可靠性的動(dòng)態(tài)規(guī)劃根本方程為：kkkysf,1,111nnnysf與問(wèn)題無(wú)關(guān)WCf,1求1 , 2 , 1,nnk動(dòng)態(tài)規(guī)劃根本方程： 01 , 2 , 1,1111nnkkkkukksfnnksfugoptsfk 11 , 2 , 1,1111nnkkkkukksfnnksfugoptsfk或4.4.2 動(dòng)態(tài)規(guī)劃模型的求解解法離散型延續(xù)型：分段窮舉法：利用解析方法或線性規(guī)劃方法沒(méi)有固定的方法

7、詳細(xì)模型詳細(xì)分析要求：閱歷 、技巧、靈敏難！投資額收益工廠 12314.525274.57397.58410.511105121513一、離散變量的分段窮舉法例資源分配問(wèn)題某有色金屬公司擬撥出50萬(wàn)元對(duì)所屬三家冶煉廠進(jìn)展技術(shù)改造，假設(shè)以十萬(wàn)元為最少分割單位，各廠收益與投資的關(guān)系如下表：?jiǎn)枺簩?duì)三個(gè)工廠如何分配，才干使總收益到達(dá)最大？形狀變量sk：階段k=1，2，3決策變量uk：給工廠k的投資額在第k階段時(shí)可供工廠k到工廠3分配的資金數(shù)kksu 0形狀轉(zhuǎn)移方程：sk+1 = sk -ukg k (uk)=給工廠k投資 uk十萬(wàn)元的收益目的函數(shù)Vk,n3kiiiug 110maxkkkksukksf

8、ugsfkkfk 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.529.5450 1 2 3 4 101011.512.

9、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 4 517 16.5 16 15.5 12117最大

10、總收益：十萬(wàn)元）(17)5(1f最優(yōu)戰(zhàn)略：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é)工問(wèn)題某工廠的消費(fèi)義務(wù)隨季節(jié)動(dòng)搖，為降低本錢(qián)宜用季節(jié)暫時(shí)工，但熟練的消費(fèi)工人暫時(shí)難以聘到，培訓(xùn)新手費(fèi)用又高，各季節(jié)工人需用量如下表所示，每季節(jié)超越需用量聘用，每人浪費(fèi)2000元，聘用或解聘費(fèi)為200元乘上兩個(gè)季節(jié)聘用人數(shù)之差的平方，問(wèn)廠長(zhǎng)

11、一年中應(yīng)如何聘用工人可使總破費(fèi)最小？假定工資按實(shí)踐任務(wù)時(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，形狀變量sk第k-1季度聘用人數(shù)決策變量uk第k季度聘用人數(shù)形狀轉(zhuǎn)移方程： sk+1 = uk fksk=第k-1季度聘用人數(shù)為sk人時(shí)，第k季度到 第4季度的最小總費(fèi)

12、用 ,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+1sk+1+2000(uk gk)gkuk255200(uk uk-1)2求f1255 =min +fk+1uk+2000(uk gk)gkuk255200(uk sk)2根本方程：fksk=min +fk+1ukf5s5=0求f1255+2000(uk gk)gkuk255200(uk sk)2m

13、in f4s4=+2000(u4 g4)g4u4255200(u4 s4)2u*4=255=200(255 s4)2,200s4255當(dāng)k=4時(shí)min f3s3=+f4u3+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,1f3s3 =min +2000(u3 200)200(u3 s3)2200u3255+200(255 u3)22332332552002002000200uusuh令33332554002000400usududh則100

14、0040080033su03dudh令1252133su得0800232duhd且12521*33su為最小值點(diǎn)即1252133su所以f3s3=23323211302007521200021125200sss2332326050150100025050sss當(dāng)k=3時(shí),240s3255255,2003umin min f2s2=+f3u2+2000(u2 g2)200(u2 s2)2g2u2255fksk=+fk+1uk+2000(uk gk)gkuk255200(uk sk)2知：f3s32332326050150100025050sss當(dāng)k=2時(shí),220s2255=min +2000(u

15、2 240)200(u2 s2)2240u2255+f3u2=min 587500048000400200300222222ussu240u2255形狀轉(zhuǎn)移方程： sk+1 = uk f2s2當(dāng)k=2時(shí),220s2255=min 587500048000400200300222222ussu240u22552dudh4800040060022su02dudh令803222su得0600222duhd且8032*,22su所以f2s2=587500048000400200300222222ussuh令5875000)8032(48000400200)8032(300222222ssss39550

16、00320003200222ss255,2402u為最小值點(diǎn)即803222sumin fksk=+fk+1uk+2000(uk gk)gkuk255200(uk sk)2知：f2s23955000320003200222ss當(dāng)k=1時(shí)，s1=255min f1255=+f2u1+2000(u1 g1)g1u1255200(u1 s1)2=min +2000(u1 220)220u1255200(u1 255)23955000320003200121uu形狀轉(zhuǎn)移方程： sk+1 = uk 3200034002000)255(400111uududh132000316001u01dudh令5 .2471u得031600212duhd且為最小值點(diǎn)即5 .2471uf1255=1850005