【文章內(nèi)容簡(jiǎn)介】 4)(),()(00 ????? dfdbrbf 945)(),()( 00 ????? dfdaraf 1899)(),()( 00 ????? afasrsf 不定步數(shù)問(wèn)題 策略迭代法 例 4－ 2 )()}(),({min 10 iuufuirn 找出求 bsubfbsrafasr ??????????????????? )(168899min)(),()(),(min100 caudfdarcfcar ??????????????????? )(84526min)(),()(),(100cbudfdbcfcbrafabr????????????????????????????)(442294min)(),)(),()(),(min 1000tcutftcr dfdcr ??????????????????? )(20243min)(),()(),(min100? ? ? ? tdutftdr ????? )(404min)(),(min 10 不定步數(shù)問(wèn)題 策略迭代法 a c b d s t 6 9 5 2 4 4 8 4 2 3 圖 48 例 4－ 2 bsu ?)(1 cau ?)(1 cbu )(1 tcu ?)(1 tdu ?)(1 1248)(),()( 11 ????? bfbsrsf 0)(1 ?tf 2)(),()( 11 ??? tftcrcf 4)(),()( 11 ??? tftdrdf 422)(),()( 11 ????? cfcbrbf 826)(),()( 11 ????? cfaraf 不定步數(shù)問(wèn)題 策略迭代法 bsubfbsr afasr ??????????????????? )(124899min)(),()(),(min211 caudfdarcfcar ??????????????????? )(84526min)(),()(),(min211cbudfdbrcfcbrafabr?????????????????????????????)(4442284min)(),()(),()(),(min 2111tcutftcr dfdcr ??????????????????? )(20243min)(),()(),(min211? ? ? ? tdutftdr ????? )(404min)(),(min 21 不定步數(shù)問(wèn)題 策略迭代法 x u0 f0 u1 f1 u2 s a 18 b 12 b a d 9 c 8 c b d 8 c 4 c c t 2 t 2 t d t 4 t 4 t t 0 0 資源分配問(wèn)題 資源的多元分配 設(shè)有某種資源，總量為 M， 可以投入 n種生產(chǎn)活動(dòng)。已知用于活動(dòng) k的資源為 uk時(shí)的收益是 gk(uk)， 問(wèn)應(yīng)如何分配資源，使 n種生產(chǎn)活動(dòng)的總收益最大。這種問(wèn)題就是資源的多元分配問(wèn)題。 )()()(max 2211 nn ugugugZ ???? ?Muuuts n ???? ?21.. 0, 21 ?nuuu ? 資源分配問(wèn)題 資源的多元分配 如果將 n種活動(dòng)作為一個(gè)互相銜接的整體 ， 對(duì)一種活動(dòng)的資源分配作為一個(gè)階段 ， 每個(gè)階段確定對(duì)一種活動(dòng)的資源投放量 。 則該問(wèn)題成為一個(gè)多段決策問(wèn)題 。 狀態(tài)變量 xk的選取原則是要能夠據(jù)此確定決策 uk， 以及滿(mǎn)足狀態(tài)轉(zhuǎn)移方程所要求的無(wú)后效性 。 在資源分配問(wèn)題中 ， 決策變量選為對(duì)活動(dòng) k的資源投放量 ，因此狀態(tài)變量可以選擇為階段 k初所擁有的資源量 ， 即將要在第 k種到第 n種活動(dòng)間分配的資源量 。 資源的多元分配 關(guān)于狀態(tài)變量 xk的約束條件是 0≤xk≤M 關(guān)于決策變量 uk的約束條件是 0≤uk≤xk 狀態(tài)轉(zhuǎn)移方程為 xk+1=xkuk 顯然它滿(mǎn)足無(wú)后效性要求 。 階段效應(yīng)為對(duì)活動(dòng) k投放資源 uk時(shí)的收益 ， rk(xk, uk)=gk(uk) 目標(biāo)函數(shù)是為 n種活動(dòng)投放資源后的總收益 動(dòng)態(tài)規(guī)劃基本方程 ???nkkk ugR1)()}()({max)( 11 ???? kkkkukkxfugxfk 資源的多元分配 例 4－ 3 某公司擬將 50萬(wàn)元資金投放下屬 A、 B、 C三個(gè)部門(mén) ，各部門(mén)在獲得資金后的收益如表所示 ， 用動(dòng)態(tài)規(guī)劃方法求總收益最大的投資分配方案 （ 投資數(shù)以 10萬(wàn)元為單位 ） 。 投放資金（萬(wàn)元） 0 10 20 30 40 50 收 益 （萬(wàn)元） A 0 15 20 25 28 30 B 0 0 10 25 45 70 C 0 10 20 30 40 50 資源的多元分配 解 該問(wèn)題可以作為三段決策過(guò)程 。 對(duì) A、 B、 C三個(gè)部門(mén)分配資金分別形成 1， 2， 3三個(gè)階段 。 xk表示給部門(mén) k分配資金時(shí)擁有的資金數(shù) 。 uk表示給部門(mén) k分配的資金數(shù) （ 以 10萬(wàn)元為單位 ） 。 狀態(tài)轉(zhuǎn)移方程是 xk+1=xkuk。 階段效應(yīng)如表所示 。 目標(biāo)函數(shù)是階段效應(yīng)求和 。 投放資金（萬(wàn)元） 0 10 20 30 40 50 收 益 （萬(wàn)元） A 0 15 20 25 28 30 B 0 0 10 25 45 70 C 0 10 20 30 40 50 資源的多元分配 首先逆序求條件最優(yōu)目標(biāo)函數(shù)值集合和條件最優(yōu)決策集合 。 )}()({max)( 4433333xfugxf u ??0)(44 ?xf )}({max)( 33033 33 ugxf xu ??? )()(3333 ugxf ?從表可知 g3( )是單調(diào)遞增的函數(shù) ， 因此 ， 當(dāng) u3=x3時(shí)達(dá)到最大 。 即： 339。 x? 資源的多元分配 逆序求條件最優(yōu)目標(biāo)函數(shù)值集合和條件最優(yōu)決策集合 。 )()( 3333 ugxf ?339。 xu ? 0)0(,0)0()0( 333 ??? ugf 1)1(,10)1()1( 333 ??? ugf 2)2(,20)2()2(333 ??? ugf 3)3(,30)3()3( 333 ?? ugf 4)4(,40)4()4( 333 ??f 5)5(,50)5()5( 333 ?? ugf 資源的多元分配 逆序求條件最優(yōu)目標(biāo)函數(shù)值集合和條件最優(yōu)決策集合 。 )()( 3333 ugxf ?339。 xu ?x3 g3 f3 U3’ 0 0 0 0 1 10 10 1 2 20 20 2 3 30 30 3 4 40 40 4 5 50 50 5 資源的多元分配 逆序求條件最優(yōu)目標(biāo)函數(shù)值集合和條件最優(yōu)決策集合 。 k=2時(shí) ， 0≤x2≤5 0≤u2≤x2 )}()({max)( 332202322xfugxf xu ?? ?? )}()({max)0( 3322002 2 xfugf u ?? ?? 0)0(0)0()0( 232 ????? ufg )}()({max)1( 3322102 2 xfugf u ?? ??0)1(1000 100max)0()1( )1()0(max 23232 ????????????????????? ufgfg)}(){max)2( 33222022xfugf u? ??0)2(20010100200max)0()2()1()1()2()0(max 2323232??????????????????????????????? ufgfgfg 資源的多元分配 逆序求條件最優(yōu)目標(biāo)函數(shù)值集合和條件最優(yōu)決策集合 。 k=2時(shí) ， 0≤x2≤5 0≤u2≤x2 )}()({max)( 332202322xfugxf xu ?? ??0/x2 1/x21 2/x22 3/x23 4/x24 5/x25 f2() U2’ 0 0+0 0 0 1 0+10 0+0 10 0 2 0+20 0+10 10+0 20 0 3 0+30 0+20 10+10 25+0 30 0 4 0+40 0+30 10+20 25+10 45+0 45 4 5 0+50 0+40 10+30 25+20 45+10 70+0 70 5 資源的多元分配 逆序求條件最優(yōu)目標(biāo)函數(shù)值集合和條件最優(yōu)決策集合 。 當(dāng) k=1時(shí) ， 有 x1=5， 0≤u1≤x1=5 )}()({max)5( 22115011xfugf u ?? ?? ?????????????????????????????)0()5()1()4()2()3()3()2()4()1()5()0(max212121212121fgfgfgfgfgfg0)5(700301028202530204515700max1???????????????????????????????? u 資源的多元分配 逆序求條件最優(yōu)目標(biāo)函數(shù)值集合和條件最優(yōu)決策集合 。 當(dāng) k=1時(shí) ， 有 x1=5， 0≤u1≤x1=5 )}()({max)5( 22115011xfugf u ?? ??0/5 1/4 2/3 3/2 4/1 5/0 f1() U1’ 5 0+70 15+45 20+30 25+20 28+10 30+0 70 0 資源的多元分配 順序求最優(yōu)目標(biāo)函數(shù)值和最優(yōu)策略 、 最優(yōu)路線(xiàn) 0/5 1/4 2/3 3/2 4/1 5/0 f1() U1’ 5 0+70 15+45 20+30 25+20 28+10 30+0 70 0 5*1 ?x0)5(*1 ?u 5*2 ?x5)5(*2 ?u 0*4 ?x0)0(*3 ?u 0*3 ?x70)}({ 11*11???xfoptRXx 資源的多段分配 將一種有消耗性的資源 ， 多階段地在多種不同的生產(chǎn)活動(dòng)中投放的問(wèn)題稱(chēng)為資源的多段分配問(wèn)題 ， 下面討論其中包含有兩個(gè)生產(chǎn)活動(dòng)的簡(jiǎn)單情況 。 設(shè)有某種資源 ， 初始的擁有量是 M。 計(jì)劃在 A， B兩個(gè)生產(chǎn)部門(mén)連續(xù)使用 n個(gè)階段 。 已知在部門(mén) A投入資源 uA時(shí)的階段收益是 g(uA)， 在部門(mén) B投入資源 uB時(shí)的階段收益是 h(uB)。 又資源在生產(chǎn)中將有部分消耗 ， 已知每生產(chǎn)一個(gè)階段后部門(mén) A， B中的資源完好率分別為 a和 b， 0(a, b)1。 求 n階段間總收益最大的資源分配計(jì)劃 。 資源的多段分配 n段決策過(guò)程 狀態(tài)變量 xk為階段 k初擁有的資源量 ， 0≤xk≤M， x1=M 決策變量選為階段 k在部門(mén) A的資源投放量 ， 即 uA=uk， 這里顯然有 uB=xk uk， 決策變量的約束條件是 0≤uk≤xk 即最多將所擁有的資源都投入部門(mén) A， 其時(shí) uB=0 階段 k末部站 A的剩余資