【正文】 狀態(tài)轉(zhuǎn)移方程 ??? ??? PKxx kk 111相應的階段效應即階段的回收額也有兩種可能 ??????????PuPtsKuttutrkkkk )0()0()()()(),(????????????????????)1()0()0()(:)1()()(:max)(11kkk fPtsPtfttKtf???? 設備更新問題 例 4－ 7 假定 n＝ 6年 ， 新設備購買價格為 10萬元 。 設備更新問題 今有一設備更新問題如下： 已知 n為計算設備回收額的總期數(shù)； t為某個階段的設備役齡； γ(t)為從役齡為 t的設備得到的階段收益； μ(t)為役齡為 t的設備的階段使用費用； s(t)是役齡為 t的設備的處理價格； p為新設備的購置價格； 求 n期內(nèi)使回收額最大的設備更新政策 。 因此，處于某個階段的各種設備，總是面臨著保留還是更新的問題，這個問題應該從整個計劃期間的總回收額，而不應從局部的某個階段的回收額來考慮。υk 428,15min085),( 111 ?????????? uyx ），（)}0,1(),2,2(),4,3(),6,4(),8,5{(),( 222 ?? Xyx )}0,0(),2,1(),4,2(),0,1(),2,2(),4,3(),6,4(),8,5{(),( 333 ?? Xyx }1,0{22 ?? Uu }2,1,0{33 ? )},(),({max),( 111 ????? kkkkkkkukkk yxfuyxryxfk )},({max 111 ????? kkkkku yxfurk 二維背包問題 解 當 k＝ 3時 ， 由 f4(x4, y4)=0 0/(x3,y3) 1/(x32,y33) 2/(x34,y36) f3( ) u3 （ 5， 8） 0＋ 0 65＋ 0 2 65＋ 0 130 2 （ 4， 6） 0＋ 0 65＋ 0 2 65＋ 0 130 2 （ 3， 4） 0＋ 0 65＋ 0 65 1 （ 2， 2） 0＋ 0 0 0 （ 1， 0） 0＋ 0 0 0 （ 2， 4） 0＋ 0 65＋ 0 65 1 （ 1， 2） 0＋ 0 0 0 （ 0， 0） 0＋ 0 0 0 二維背包問題 解 當 k＝ 2時 ， 由 f3(x3, y3)已知 0/(x2,y2) 1/(x22,y24) f2( ) u2 （ 5， 8） 0＋ 130 80＋ 65 145 1 （ 4， 6） 0＋ 130 80＋ 0 130 0 （ 3， 4） 0＋ 65 80＋ 0 80 1 （ 2， 2） 0＋ 0 0 0 （ 1， 0） 0＋ 0 0 0 二維背包問題 解 當 k＝ 1時 ， W=5,V=8 0/(5,8) 1/(4,6) 2/(3,4) 3/(2,2) 4/(1,0) f1( ) u1 （ 5， 8） 0＋ 145 30＋ 130 60＋ 80 90＋ 0 120＋ 0 160 1 160)8,5(1 ?f )8,5(),( *1*1 ?yx 1)8,5(*1 ?u 06,4(*2u )6,4(),( *3*3 ?yx 2)6,4(*3 ?u )0,0(),( *4*4 ?yx )6,4(,( 2*2 yx 設備更新問題 設備更新問題的一般提法 隨著使用年限的增加，設備性能會變差，故障會增加，需要維修或更新。u k 各階段的狀態(tài)可能集與決策允許集為： 428,15min085),( 111 ?????????? uyx ），（)}0,1(),2,2(),4,3(),6,4(),8,5{(),( 222 ?? Xyx )}0,0(),2,1(),4,2(),0,1(),2,2(),4,3(),6,4(),8,5{(),( 333 ?? Xyx }1,0{22 ?? Uu }2,1,0{33 ? 二維背包問題 解 狀態(tài)轉(zhuǎn)移方程為： xk+1=xkukωk yk+1=ykuk 有 0≤xk≤5， 0≤yk≤8 決策變量 uk表示裝載第 k種物品的數(shù)量 。 i ωi υi pi 1 1 2 30 2 3 4 80 3 2 3 65 二維背包問題 ? 例 4－ 6 W＝ 5， V＝ 8 解 該問題中有三種物品需要裝載 ， 因此可以作為三段決策問題 ， 每階段為一個物品決定裝船的數(shù)量 。 現(xiàn)在要確定在不超過船的最大載重量和最大體積（ 不考慮貨物形狀 ） 的條件下 ， 使所載物品價值最大的裝載方案 。 第 i種物品單位的重量為 ωi， 單件體積為 υi， 而價值為 pi。 ? 若只考慮重量或體積限制 ， 則稱為一維背包問題 ， 若同時考慮重量和體積限制 ， 則稱為二維背包問題 。 kkkkduxx ???? 1 ????????????0)(0)(),(kkkkkkkkkkk uduxuudxuxr??????????????????0)()(0)()()(11kkkkkkkkkkkkkkkukk udxfdxuduxfduxuxfk 生產(chǎn)－庫存問題舉例 0 1 2 3 f3() U3’ 0 14 14 3 1 12 12 2 2 10 10 1 3 0 0 0 ??????????????????0)()(0)()()(11kkkkkkkkkkkkkkkukk udxfdxuduxfduxuxfkkkkk duxx ???? 1 33 3 xu ?? 生產(chǎn)－庫存問題舉例 0 1 2 3 4 5 6 f2() U2’ 0 16+14 +12 23+10 30 4 1 14+14 +12 21+10 +0 6 2 12+14 +12 19+10 +0 5 3 10+14 +12 17+10 +0 4 4 0+14 +12 15+10 +0 14 0 ??????????????????0)()(0)()()(11kkkkkkkkkkkkkkkukk udxfdxuduxfduxuxfkkkkk duxx ???? 1 )7,6min(4 222 xux ???? 生產(chǎn)－庫存問題舉例 2 3 4 5 6 f!() u1’ 1 12+30 + 19+ + 26+14 40 3或 6 ??????????????????0)()(0)()()(11kkkkkkkkkkkkkkkukk udxfdxuduxfduxuxfkkkkk duxx ???? 1 62 1 ?? u 40)(1 ?f 1*1 ?x 3)1(*1 ?u 1*2 ?x 6)1(*2 ?u 3*3 ?x 0)3(*3 ?u 0*4 ?x 生產(chǎn)－庫存問題舉例 2 3 4 5 6 f!() u1’ 1 12+30 + 19+ + 26+14 40 3或 6 40)(1 ?f 1*1 ?x 3)1(*1 ?u 1*2 ?x 6)1(*2 ?u 3*3 ?x 0)3(*3 ?u 0*4 ?x 6)1(*1 ?u 4*2 0)1(*2 ?u 0*3 3)3(*3 ?u 二維背包問題 ? 背包問題的特征類似于往旅行背包里面裝用品的問題 ， 要求在旅行袋容積和／或載重量的限制下 ， 所裝物品的總價值最大 。 ??? kkk uxd },0max{ },min{ 1 kkkknkkk dxMxdddB ?????? ? ?62 1 ?? u )7,6min(4222 xux ???? 33 3 xu ?? 生產(chǎn)－庫存問題舉例 ? 例 4－ 5 求解生產(chǎn)－庫存問題 。 3,2,1},min{0 1 ?????? ? kdddMx nkkkk ?11 ?x 04 ?x 40 2 ?? x 33 生產(chǎn)－庫存問題舉例 ? 例 4－ 5 求解生產(chǎn)－庫存問題 。 因此關(guān)于決策變量的約束條件就是 ??? kkk uxd },0max{ },min{ 1 kkkknkkk dxMxdddB ?????? ? ?kkkk duxx ???? 1期末庫存 =期初庫存 +生產(chǎn)量 本期需求 生產(chǎn)－庫存問題 階段 k的生產(chǎn)費用是 庫存費用按階段 k末期的庫存量 xk+1計算 ??????000kkkkkuuLcu)(1 kkkkkk duxhxh ???? ????????????0)(0)(0),(kkkkkkkkkkkkkkk uduxhuLcudxhuxr??????????????????0)()(0)()(min)(11kkkkkkkkkkkkkkkkkkkukk udxfdxhuduxfduxhuLcxfk 生產(chǎn)－庫存問題舉例 ? 例 4－ 5 求解生產(chǎn)－庫存問題 。 nkdddMx nkkkk ,2,1},min{0 1 ?? ?????? ? 庫容量限制 以后需求缺口 本期需求缺口 生產(chǎn)－庫存問題 決策變量 uk選為階段 k的生產(chǎn)量 。這里狀態(tài)變量 xk應選為階段 k的初始庫存量 ， 計劃初期的庫存量 x1是已知的 ， 末期的庫存量通常也是給定的 ， 為簡單起見這里假定 xn+1=0， 于是問題是始端末端固定的問題 。 從而可知：對 uk有 kkku xsc k ?? ? 1即當期所耗資金加上 k+1期往后所用資金 sk+1不超過當前擁有資金數(shù) 。 假設對部件 i(i=1， 2， 3)配備 j個備件后的可靠性 Rij和所需費用 cij均已知 ， 如表所示 ， 若可用的總資金數(shù)量為 1萬元 ， 問如何配備各部件的備用元件數(shù) ， 才能使該設備在給定工作條件下的可靠性最大 ？ 備件數(shù) 部件 j=1 j=2 j=3 Ci1 （ 千元 ) Ri1 Ci2 （ 千元） Ri2 Ci3 （ 千元） Ri3 1 1 3 5 2 3 5 6 3 2 3 4 串聯(lián)系統(tǒng)可靠性問題 例 4－ 5 解 以給不同的部件決定備件作為不同的階段 ， 則該問題是 3階段決策問題 設狀態(tài)變量 xk表示從第 k個部件到第 3個部件允許使用的總費用 （ k=1,2,3） 決策變量 uk為第 k部件配備的備用元件數(shù) （ k=1， 2， 3） 。 因此 ， 在成本 、 重量 、 體積等一定的條件限制下 ， 應如何選擇各部件的備用元件數(shù) ， 使得整個系統(tǒng)的可靠性最大 ， 就可以歸結(jié)為一個動態(tài)規(guī)劃問題 。 為了提高系統(tǒng)工作的可靠性 ， 一種方法是可以在每個部件上裝有主要元件的相同性能的備用件 ， 并且?guī)в袀溆迷詣油度胙b置 。 這兒要研究的是串聯(lián)系統(tǒng)可靠性問題 。 K階段狀態(tài)變量 xk取為該年度初完好的設備數(shù) ， 決策變量取為該年度投入 A活動的設備數(shù) ， 則有 0≤xk≤1000， 0≤uk≤xk 狀態(tài)轉(zhuǎn)移方程為： xk+1=+(xkuk) 資源的多段分配 例 4－ 4 解 以每年作為一個階段 ， 設狀態(tài)變量和決策變量都是連續(xù)取值的 。 試求使 3年間總收益最大的年度機器分配方案 。 資源的多段分配 例 4－ 4 今有 1000臺機床 ， 要投放到 A、 B兩個生產(chǎn)部門 ， 計劃連續(xù)使用 3年 。 求 n階段間總收益最大的資源分配計劃 。 已知在部門 A投入資源 uA時的階段收益是 g(uA)， 在部門 B投入資源 uB時的階段收益是 h(uB)。 設有某種資源 ， 初始的擁有量是 M。 當 k=1時