【正文】 uk)=g(uk)+h(xkuk) 目標(biāo)函數(shù)是 n個(gè)階段的總收益 ， 即階段效應(yīng)求和 。 已知對 A部門投入 uA臺機(jī)器時(shí)的年收益是g(uA)=4(uA)2（ 元 ） ， 機(jī)器完好率 a=， 相應(yīng)的 B部門的年收益是 h(uB)=2(uB)2 （ 元 ） ， 完好率 b= 。 解 以每年作為一個(gè)階段 ， 設(shè)狀態(tài)變量和決策變量都是連續(xù)取值的 。 K階段狀態(tài)變量 xk取為該年度初完好的設(shè)備數(shù) ， 決策變量取為該年度投入 A活動的設(shè)備數(shù) ， 則有 0≤xk≤1000， 0≤uk≤xk 狀態(tài)轉(zhuǎn)移方程為： xk+1=+(xkuk) 動態(tài)規(guī)劃基本方程 )}()(24{max)( 1122 ?????? kkkkkukkxfuxuxfk 資源的多段分配 逆序求條件最優(yōu)目標(biāo)函數(shù)值 fk(xk)和條件最優(yōu)決策 k=3時(shí) ， 0≤u3≤x3， 注意到 f4(x4)=0， 有 })(24{max)( 23323333uxuxf u ???2333 4)( xxf ? 333 )( xxu ??k=2時(shí) ， 0≤u2≤x2， 有 ))}((2)(24{max)( 22232222222uxufuxuxf u ?????? })]([42)(24{max 222222222uxuuxuu ?????? 2222 )( xxf ?0)( 22 ?xu 資源的多段分配 逆序求條件最優(yōu)目標(biāo)函數(shù)值 fk(xk)和條件最優(yōu)決策 k=1時(shí) ， 0≤u1≤x1， x2=+(x1u1)， f2(x2) ))}((2)(24{max)( 11121121111uxufuxuxf u ?????? })]([)(24{max 211111211uxuuxuu ?????? 2111 )( xxf ?0)( 1 ?xu 1000*1 ?x 0)1000(*1 ?u 900*2 ?x 0)900(*2 ?405*4 ?x 810)810(*3 ?u 810*3 ?x 串聯(lián)系統(tǒng)可靠性問題 系統(tǒng)可靠性是指系統(tǒng)在規(guī)定的條件下能正常工作的概率 ， 它是管理和工程技術(shù)設(shè)計(jì)中經(jīng)常要研究的問題 。 例如某種儀器設(shè)備由 N個(gè)部件串聯(lián)構(gòu)成 ， 凡其中有一個(gè)部件出現(xiàn)故障 ， 則整個(gè)系統(tǒng)便不能正常工作 。 自然備用元件越多 ， 系統(tǒng)的可靠性越高 ， 但也會相應(yīng)增加系統(tǒng)重量 、 體積和費(fèi)用 ， 有時(shí)也會降低工作精度 。 串聯(lián)系統(tǒng)可靠性問題 例 4－ 5 某電氣設(shè)備由三個(gè)部件串聯(lián)而成 ， 為提高該種設(shè)備在指定工作條件下正常工作的可靠性 ， 需在每個(gè)部件上安裝一個(gè) 、 兩個(gè)或三個(gè)主要元件的相同備件 。 則據(jù)題意有： x1=10千元 ， 且每個(gè)部件都最少有一個(gè)備件 ， 即uk≥1， 若令 sk表示為保障以后各部件均能獲得一個(gè)備件所需的資金數(shù) ， 則應(yīng)有： ???31kiik cs 串聯(lián)系統(tǒng)可靠性問題 例 4－ 5 ???31kiik cs且據(jù)此可得： s1=6， s2=5， s3=2。 串聯(lián)系統(tǒng)可靠性問題 例 4－ 5 根據(jù)上述分析可以寫出各階段的狀態(tài)可能集合和決策允許集合如下： x1=10 X2＝ {9， 7， 5} X3＝ {2， 3， 4， 5， 6} U1＝ {1， 2， 3} U2(9)＝ {1， 2， 3} U2(7)＝ {1， 2} U2(5)＝ {1} U3(2)＝ {1} U3(3)＝ {1， 2} U3(4)＝ {1， 2， 3} U3(5)＝ {1， 2， 3} U3(6)＝ {1， 2， 3} 串聯(lián)系統(tǒng)可靠性問題 例 4－ 5 狀態(tài)轉(zhuǎn)移方程為： 階段效應(yīng)為 kukkk cxx ,1 ??? kukkkk Ruxr ,),( ?目標(biāo)函數(shù)為是階段效應(yīng)乘積的形式 ),(31 kkkuxrR??? )}(),({max)(11 ???? kkkkkukk xfuxrxfk若以 fk(xk)表示在階段 k擁有資金 xk時(shí)采用最優(yōu)決策序列所得的 k階段往后的系統(tǒng)的可靠性，則動態(tài)規(guī)劃基本方程為： 串聯(lián)系統(tǒng)可靠性問題 例 4－ 5 )}(),({max)( 11 ???? kkkkkukk xfuxrxfk1/x32 2/x33 3/x34 f3() U3’ 2 1 1 3 1 1 2 4 1 1 1 3 6 1 1 1 3 1)( 44 ?xf 串聯(lián)系統(tǒng)可靠性問題 例 4－ 5 1/x23 2/x25 3/x26 f2() U2’ 9 3 7 1 5 1 1/x32 2/x33 3/x34 f3() U3’ 2 1 1 3 1 1 2 4 1 1 1 3 6 1 1 1 3 串聯(lián)系統(tǒng)可靠性問題 例 4－ 5 1/x23 2/x25 3/x26 f2() U2’ 9 3 7 1 5 1 1/9 2/7 3/5 f1() U1’ 10 1 1*1 ?u 3*2 ?u 2*3 ?u 生產(chǎn)－庫存問題 ? 生產(chǎn)計(jì)劃周期分為 n個(gè)階段 ， 即 k=1~n； ? 已知最初庫存量為 x1； ? 階段需求量為 dk； ? 單位產(chǎn)品的消耗費(fèi)用為 Lk； ? 單位產(chǎn)品的階段庫存費(fèi)用為 hk； ? 倉庫容量為 Mk； ? 階段生產(chǎn)能力為 Bk； ? 生產(chǎn)的準(zhǔn)備費(fèi)用為： ?????000產(chǎn)量產(chǎn)量kc 生產(chǎn)－庫存問題 問應(yīng)如何安排各階段產(chǎn)量 ， 使計(jì)劃期總費(fèi)用最小 。 關(guān)于狀態(tài) xk的約束條件是 ?即階段 k的庫存既不能超過庫存容量 ， 也不應(yīng)超過階段 k至階段 n的需求總量（ dk+dk+1+…+d n）， 否則將與 xn+1=0的假設(shè)相違背。 階段產(chǎn)量要在不超過生產(chǎn)能力 Bk的條件下 ， 充分滿足該階段的需求 dk， 同時(shí)還要滿足計(jì)劃末期的庫存量為 0的要求 。 已知其 n=3， ck=8，Lk=2， hk=， x1=1， Mk=4， x4=0（ 計(jì)劃周期末期的庫存量為 0） ， Bk＝ 6， d1=3， d2=4， d3=3。 已知其 n=3， ck=8，Lk=2， hk=， x1=1， Mk=4， x4=0（ 計(jì)劃周期末期的庫存量為 0） ， Bk＝ 6， d1=3， d2=4， d3=3。 已知其 n=3， ck=8，Lk=2， hk=， x1=1， Mk=4， x4=0（ 計(jì)劃周期末期的庫存量為 0） ， Bk＝ 6， d1=3， d2=4， d3=3。 這一類問題在海運(yùn) 、 航運(yùn)以及航天等領(lǐng)域都有應(yīng)用 。 ? 考慮有 N種物品需要裝船 。 最大的裝載重量為 W， 最大體積為 V。 二維背包問題 ? 例 4－ 6 已知貨物的單位重量 ωi， 單位體積 υi及價(jià)值 pi如表所示 ， 船的最大載重能力為 W＝ 5， 最大裝載體積為 V＝ 8， 求最優(yōu)裝載方案 。 k階段系統(tǒng)的狀態(tài)為在給第 k物品決定裝載數(shù)量時(shí) ，船上還剩余的載重能力 xk和剩余體積 yk， 因此狀態(tài)變量是二維的 ， 記為 （ xk, yk） 。 ????????kkkkkyxu?? ,min0 二維背包問題 ? 例 4－ 6 W＝ 5， V＝ 8 解 狀態(tài)轉(zhuǎn)移方程為： xk+1=xkukυk 階段效應(yīng)為 rk(xk, yk, uk)=pkωk yk+1=ykuk設(shè)備使用時(shí)間愈長，積累效益愈高，但隨著設(shè)備陳舊，維修使用費(fèi)用也會提高，而且，設(shè)備使用年限愈久，處理價(jià)格愈低，更新費(fèi)用也要增加。 由于每個(gè)階段都面臨著保留還是更新的兩種選擇，因此，它是一個(gè)多階段的決策過程，可以用動態(tài)規(guī)劃方法求解。 設(shè)備更新問題 狀態(tài)變量選為設(shè)備的役齡 t， 即 xk=t， 決策只有兩種可能，即保留或更新，記為 K（ 保留）或 P（ 更新）。 役齡為 t時(shí)的設(shè)備使用效益 γ(t)， 使用費(fèi)用 μ(t)和處理價(jià)格s(t)如下表所示 T 0 1 2 3 4 5 6 γ(t)萬元 27 26 26 24 22 20 18 μ(t)萬元 15 15 16 16 17 17 18 s(t)萬元 6 5 5 4 4 3 2 ????????????PutsPtsKuttutrkkkk 2)()0()0()()()(),(???? 設(shè)備更新問題 T 0 1 2 3 4 5 6 γ(t)萬元 27 26 26 24 22 20 18 μ(t)萬元 15 15 16 16 17 17 18 s(t)萬元 6 5 5 4 4 3 2 γ(t) μ(t) 12 11 10 8 5 3 0 s(t)+2 8 7 7 6 6 5 4 ??????????????)1(2)(:)1()()(:max)(11kkk ftsPtfttKtf ?? 設(shè)備更新問題 t 0 1 2 3 4 5 6 γ(t) μ(t) 12 11 10 8 5 3 0 s(t)+2 8 7 7 6 6 5 4 0)(7 ?tf ?????? ???2)(:)()(:max)(6 tsPttKtf ??t 0 1 2 3 4 5 6 f6(t) 12 11 10 8 6 5 4 設(shè)備更新問題 t 0 1 2 3 4 5 6 γ(t) μ(t) 12 11 10 8 5 3 0 s(t)+2 8 7 7 6 6 5 4 ????????????112)(:)1()()(:max)( 65 tsPtfttKtf ??t 0 1 2 3 4 5 6 f6(t) 12 11 10 8 6 5 4 f5(t) 23 21 18 17 17 16 15 γ(t) μ(t)+ f6(t+1) 23 21 18 14 10 7 s (t)+2+11 19 18 18 17 17 16 15 設(shè)備更新問題 t 0 1 2 3 4 5 6 γ(t) μ(t) 12 11 10 8 5 3 0 s(t)+2 8 7 7 6 6 5 4 ????????????212)(:)1()()(:max)( 54 tsPtfttKtf ??t 0 1 2 3 4 5 6 f6(t) 12 11 10 8 6 5 4 f5(t) 23 21 18 17 17 16 15 γ(t) μ(t)+ f5(t+1) 33 29 27 25 21 18 s (t)+2+11 29 28 28 27 27 26 25 設(shè)備更新問題 t 0 1 2 3 4 5 6 f6(t) 12 11 10 8 6 5 4 f5(t) 23 21 18 17 17 16 15 f4(t) 33 29 28 27 27 26 25 f3(t) 41 39 37 35 35 34 33 f2(t) 51 48 46 45 45 44 43 f1(t) 60 57 55 54 54 53 52 第一年役齡為一的產(chǎn)品的更新方案 設(shè)備更新問題 t 0 1 2 3 4 5 6 f6(t) 12 11 10 8 6 5 4 f5(t) 23 21 18 17 17 16 15 f4(t) 33 29 28 27 27 26 25 f3(t) 41 39 37 35 35 34 33 f2(t) 51 48 46 45 45 44 43 f1(t) 60 57 55 54 54 53 52 第一年役齡為 4的產(chǎn)品的更新方案 習(xí)題 P177 45 46