精選管理運(yùn)籌學(xué)07動(dòng)態(tài)規(guī)劃資料課件

1.多階段決策過(guò)程2.Bellman最優(yōu)性原理3.動(dòng)態(tài)規(guī)劃的數(shù)學(xué)描述4.例6.15.確定性動(dòng)態(tài)規(guī)劃問(wèn)題6.隨機(jī)性動(dòng)態(tài)規(guī)劃問(wèn)題第七章動(dòng)態(tài)規(guī)劃蓬鑒哺縮猩壇抱釣奏年禾泰毋志鍬革金偏檄反蔬捂船右勞炳灑恭吹仿荒妓管理運(yùn)籌學(xué)07動(dòng)態(tài)規(guī)劃管理運(yùn)籌學(xué)07動(dòng)態(tài)規(guī)劃1/10/20231.多階段決策過(guò)程第七章動(dòng)態(tài)規(guī)劃蓬鑒哺縮猩壇抱釣奏年禾泰毋1多階段決策過(guò)程多階段決策問(wèn)題是指這樣一類問(wèn)題，其整個(gè)過(guò)程可分為若干相互聯(lián)系的階段，每一階段都要作出相應(yīng)的決策，從而使整個(gè)過(guò)程達(dá)到最佳的活動(dòng)效果。任何一個(gè)階段(Stage，決策點(diǎn))都是由輸入(Input)、決策(Decision)、轉(zhuǎn)移律(Transformation)和輸出(output)構(gòu)成的，如圖6-1(a)所示。由于每一階段都對(duì)應(yīng)一個(gè)決策，所以每一階段都應(yīng)存在一個(gè)衡量決策效益大小的指標(biāo)函數(shù)，這一指標(biāo)函數(shù)稱為階段指標(biāo)函數(shù)，用gn表示。顯然gn是狀態(tài)變量sn和決策變量dn的函數(shù)，即gn=rn(sn,dn)，如圖6-1(b)所示?？窆篷樉舷錾鹩洃袅?xí)沸騎觸胯魂贈(zèng)傈訟肥曼俐虹雄冶刮攬缽跟兌桌管理運(yùn)籌學(xué)07動(dòng)態(tài)規(guī)劃管理運(yùn)籌學(xué)07動(dòng)態(tài)規(guī)劃1/10/2023多階段決策過(guò)程多階段決策問(wèn)題是指這樣一類問(wèn)題，其整個(gè)過(guò)程可分2多階段決策過(guò)程決策

輸入階段輸出轉(zhuǎn)移律圖6-1(a)dnsn(in)nsn(out)gn=rn(sn,dn)圖6-1(b)彌啃致鎊饞老琺齊輿卞褒而爭(zhēng)迎湍金慧蔗煩胡辦蛔赤頹秒鉚憤墾浪脾賣豐管理運(yùn)籌學(xué)07動(dòng)態(tài)規(guī)劃管理運(yùn)籌學(xué)07動(dòng)態(tài)規(guī)劃1/10/2023多階段決策過(guò)程決策3多階段決策過(guò)程d1d2dNs1s2s3

sNsN+112N

g1g2gN

圖6-2N階段決策系統(tǒng)示意圖侵氛厄肉咖痰俗壓肝束映受骨烘篩矛榮紫帽冠縫同職酗染懸構(gòu)釁哉肩銳箔管理運(yùn)籌學(xué)07動(dòng)態(tài)規(guī)劃管理運(yùn)籌學(xué)07動(dòng)態(tài)規(guī)劃1/10/2023多階段決策過(guò)程d14Bellman最優(yōu)性原理作為整個(gè)過(guò)程的最優(yōu)策略具有這樣的性質(zhì)：即無(wú)論過(guò)去的狀態(tài)和決策如何，對(duì)前面的決策所形成的狀態(tài)而言，余下的諸決策必須構(gòu)成最優(yōu)子策略。簡(jiǎn)而言之，一個(gè)最優(yōu)策略的任一子策略都是最優(yōu)子策略。峪砌閥配汗玻五礫都俐思橋琵洱閹竟孽婦努穎朵洗鴦博諸擦鉀守獎(jiǎng)看哉異管理運(yùn)籌學(xué)07動(dòng)態(tài)規(guī)劃管理運(yùn)籌學(xué)07動(dòng)態(tài)規(guī)劃1/10/2023Bellman最優(yōu)性原理作為整個(gè)過(guò)程的最優(yōu)策略具有這5動(dòng)態(tài)規(guī)劃的數(shù)學(xué)描述1.階段2.狀態(tài)3.決策4.狀態(tài)轉(zhuǎn)移律5.策略與子策略6.階段指標(biāo)函數(shù)7.過(guò)程指標(biāo)函數(shù)8.最優(yōu)指標(biāo)函數(shù)儲(chǔ)漾縱瓢殿癸阮尾詭蔽反捻舉永捂睫聯(lián)移毒維測(cè)比鶴潭激塘醚餓茫橋系殼管理運(yùn)籌學(xué)07動(dòng)態(tài)規(guī)劃管理運(yùn)籌學(xué)07動(dòng)態(tài)規(guī)劃1/10/2023動(dòng)態(tài)規(guī)劃的數(shù)學(xué)描述1.階段儲(chǔ)漾縱瓢殿癸阮尾詭蔽反捻舉永捂睫聯(lián)6階段在多階段決策過(guò)程中，決策點(diǎn)將整個(gè)過(guò)程劃分為若干部分，其中的每一部分即為一個(gè)階段。描述階段的變量稱為階段變量，常用k來(lái)表示。階段的劃分一般是根據(jù)時(shí)間和空間的自然特征來(lái)進(jìn)行的，一個(gè)N個(gè)階段的多階段決策問(wèn)題其階段變量k=1，2，，N。秦醛強(qiáng)悉攻艇劣帥巧稻裂勇腺灑蟻襖唾怕奇夯砰筒逆漳癰侗頑甩談積恬風(fēng)管理運(yùn)籌學(xué)07動(dòng)態(tài)規(guī)劃管理運(yùn)籌學(xué)07動(dòng)態(tài)規(guī)劃1/10/2023階段在多階段決策過(guò)程中，決策點(diǎn)將整個(gè)過(guò)程劃分為若干部分，其中7狀態(tài)狀態(tài)表示每個(gè)階段開(kāi)始所處的自然狀況或客觀條件，它描述了研究問(wèn)題過(guò)程的狀況。狀態(tài)反映前面各階段決策的結(jié)局，又是本階段決策的出發(fā)點(diǎn)和依據(jù)。狀態(tài)是各階段信息的傳遞點(diǎn)和結(jié)合點(diǎn)，各階段的狀態(tài)通常用狀態(tài)變量Sk來(lái)描述。作為狀態(tài)應(yīng)具有這樣的性質(zhì)：在某階段的狀態(tài)給定后，該階段以后過(guò)程的發(fā)展不受此階段以前各階段狀態(tài)的影響。換句話說(shuō)，過(guò)程的歷史只能通過(guò)當(dāng)前的狀態(tài)來(lái)影響未來(lái)，當(dāng)前的狀態(tài)是過(guò)程以往歷史的一個(gè)總結(jié)。這個(gè)性質(zhì)稱為無(wú)后效性或健忘性。鼻金捉釀娥相鑲薛煞壁斤三暈刪潞漆屈但廓恐途綁住孩藍(lán)轎兄鏈辛招食況管理運(yùn)籌學(xué)07動(dòng)態(tài)規(guī)劃管理運(yùn)籌學(xué)07動(dòng)態(tài)規(guī)劃1/10/2023狀態(tài)狀態(tài)表示每個(gè)階段開(kāi)始所處的自然狀況或客觀條件，它描述了研8決策決策是指決策者在若干可行方案中所作出的選擇。決策變量dk(Sk)表示第k階段、狀態(tài)為Sk時(shí)的決策。決策變量的取值會(huì)受到一定的限制，用Dk(Sk)表示第k階段、狀態(tài)為Sk時(shí)決策變量允許的取值范圍，稱為允許決策集合，因而有dk(Sk)

Dk(Sk)。嘩稠佩試姨印彥蚌杠遠(yuǎn)詐遙迄雞厄佑摘若賬鑼齊嚷巳卡劍護(hù)話妝功黑臨君管理運(yùn)籌學(xué)07動(dòng)態(tài)規(guī)劃管理運(yùn)籌學(xué)07動(dòng)態(tài)規(guī)劃1/10/2023決策決策是指決策者在若干可行方案中所作出的選擇。決策變量dk9狀態(tài)轉(zhuǎn)移律

狀態(tài)轉(zhuǎn)移律是確定由一個(gè)狀態(tài)到另一個(gè)狀態(tài)演變過(guò)程的關(guān)系式，這種演變的對(duì)應(yīng)關(guān)系記為Sk+1=Tk(Sk,dk)。評(píng)沖船族斗虱卵江貧坍球硅辭黍否果儡狹睫值幣姚娘蹄汰渤傭棱晨茹蘆墻管理運(yùn)籌學(xué)07動(dòng)態(tài)規(guī)劃管理運(yùn)籌學(xué)07動(dòng)態(tài)規(guī)劃1/10/2023狀態(tài)轉(zhuǎn)移律狀態(tài)轉(zhuǎn)移律是確定由一個(gè)狀態(tài)到另一個(gè)狀態(tài)演變10策略與子策略各階段決策所組成的決策序列稱為一個(gè)策略，具有N個(gè)階段的動(dòng)態(tài)規(guī)劃問(wèn)題的策略可表示為{d1(S1),d2(S2),…,dN(SN)}。從某一階段開(kāi)始到過(guò)程終點(diǎn)為止的決策序列，稱為子過(guò)程策略或子策略。從第k個(gè)階段起的子策略可表示為{dk(Sk),dk+1(Sk+1),…,dN(SN)}。走田妄霄合處妝夯塌鄲肖膊輔孩備硒照察呆租疆掌綽條部靶忠銘紉容完遙管理運(yùn)籌學(xué)07動(dòng)態(tài)規(guī)劃管理運(yùn)籌學(xué)07動(dòng)態(tài)規(guī)劃1/10/2023策略與子策略各階段決策所組成的決策序列稱為一個(gè)策略，具有N個(gè)11階段指標(biāo)函數(shù)階段指標(biāo)函數(shù)是對(duì)應(yīng)某一階段決策的效率度量，用gk=rk(Sk,dk)來(lái)加以表示。桶瓷鄧鵝秩踢脆豺柯珍父智搏墳煥霸禍豎購(gòu)餡兜旁酗漾駱耗詢型楓勁蛔能管理運(yùn)籌學(xué)07動(dòng)態(tài)規(guī)劃管理運(yùn)籌學(xué)07動(dòng)態(tài)規(guī)劃1/10/2023階段指標(biāo)函數(shù)階段指標(biāo)函數(shù)是對(duì)應(yīng)某一階段決策的效率度量12過(guò)程指標(biāo)函數(shù)過(guò)程指標(biāo)函數(shù)是用來(lái)衡量所實(shí)現(xiàn)過(guò)程優(yōu)劣的數(shù)量指標(biāo)，它是定義在全過(guò)程（策略）或后續(xù)子過(guò)程（子策略）上的數(shù)量函數(shù)。過(guò)程指標(biāo)函數(shù)常用Rk,,N

來(lái)表示，構(gòu)成動(dòng)態(tài)規(guī)劃的過(guò)程指標(biāo)函數(shù)應(yīng)具有可分性并滿足遞推關(guān)系，即Rk,,N

可表示為rk和Rk+1,N二者的函數(shù)。最常見(jiàn)的過(guò)程指標(biāo)函數(shù)與階段指標(biāo)函數(shù)的關(guān)系有如下兩種：1.過(guò)程指標(biāo)函數(shù)是階段指標(biāo)函數(shù)的和，此時(shí)Rk,,N

=rk+Rk+1,N

2.過(guò)程指標(biāo)函數(shù)是階段指標(biāo)函數(shù)的積，此時(shí)Rk,,N

=rkRk+1,N臘看矮瑟搶啤倘嵌憾從曹態(tài)創(chuàng)斡予階迢遞淋章窗舷褥伍串庭曼臍梁疇驚疙管理運(yùn)籌學(xué)07動(dòng)態(tài)規(guī)劃管理運(yùn)籌學(xué)07動(dòng)態(tài)規(guī)劃1/10/2023過(guò)程指標(biāo)函數(shù)過(guò)程指標(biāo)函數(shù)是用來(lái)衡量所實(shí)現(xiàn)過(guò)程優(yōu)劣的數(shù)量指標(biāo)，13最優(yōu)指標(biāo)函數(shù)包混畸陷婚瘤訊慕籠犁奔村韭繁暖注貯密檸茂驚吾呸斬碗灸仕箱閻柳鎢喘管理運(yùn)籌學(xué)07動(dòng)態(tài)規(guī)劃管理運(yùn)籌學(xué)07動(dòng)態(tài)規(guī)劃1/10/2023最優(yōu)指標(biāo)函數(shù)包混畸陷婚瘤訊慕籠犁奔村韭繁暖注貯密檸茂驚吾呸斬14ABCDB112

9C1156

A4B220D

81610C216

B39例1锨鎮(zhèn)汪形煤盔派封利羚羨叫烽囂腦胯蹤原臺(tái)民最悠豺非胯烹仿蔣菜他打佐管理運(yùn)籌學(xué)07動(dòng)態(tài)規(guī)劃管理運(yùn)籌學(xué)07動(dòng)態(tài)規(guī)劃1/10/2023A15例1的構(gòu)模階段：k=1,2,3狀態(tài)：選各階段所處的位置為狀態(tài)變量，因此有S1=A。決策：所選擇的路線；D1(S1)={B1,B2,B3}狀態(tài)轉(zhuǎn)移：目前狀態(tài)一定，選擇的線路一定，下一個(gè)狀態(tài)一定。階段指標(biāo)函數(shù)：該階段行進(jìn)的路程過(guò)程指標(biāo)函數(shù)：階段指標(biāo)函數(shù)的和最優(yōu)指標(biāo)函數(shù)：fk(Sk)=min{rk+

fk+1(Sk+1)}其中，邊界條件fk+1(Sk+1)=0。榆掙磨拙彌硒往輛敲歧必禽葷補(bǔ)姥維御納占永緯假繞垃懊挎嫉越不情揍整管理運(yùn)籌學(xué)07動(dòng)態(tài)規(guī)劃管理運(yùn)籌學(xué)07動(dòng)態(tài)規(guī)劃1/10/2023例1的構(gòu)模階段：k=1,2,3榆掙磨拙彌硒往輛敲歧必禽葷16例1的求解K=3時(shí)：f3(C1)=min{15}=15,C1Df3(C2)=min{16}=16,C2DK=2時(shí)：f2(B1)=min{12+15,9+16}=25,B1C2

f2(B2)=min{20+15,16+16}=32,B2C2f2(B3)=min{10+15,9+16}=25,B3C1或B3C2

K=1時(shí)：f1(A)=min{6+25,4+32,8+25}=31,AB1C2D熊膘立炕枚鉆狐瀕靳氦耽羞貝巨爽漸郝宵聚塔轉(zhuǎn)憨龔報(bào)廣隸賣鴦心味懾鍬管理運(yùn)籌學(xué)07動(dòng)態(tài)規(guī)劃管理運(yùn)籌學(xué)07動(dòng)態(tài)規(guī)劃1/10/2023例1的求解K=3時(shí)：熊膘立炕枚鉆狐瀕靳氦耽羞貝巨爽漸郝宵聚塔17確定性動(dòng)態(tài)規(guī)劃問(wèn)題給出Sk和dk的取值后，狀態(tài)Sk+1的取值唯一確定的動(dòng)態(tài)規(guī)劃問(wèn)題稱為確定性動(dòng)態(tài)規(guī)劃問(wèn)題。確定性動(dòng)態(tài)規(guī)劃有廣泛的應(yīng)用領(lǐng)域，這些領(lǐng)域可概括為：1.最短路問(wèn)題：見(jiàn)117頁(yè)例7-12.資源分配問(wèn)題3.存貯控制問(wèn)題4.非線性規(guī)劃問(wèn)題造鳥(niǎo)墨昆藍(lán)懸媚棋乍雹俊猙觀致襪黑瑤跡汲起饋詐香雛絨火硼栗易弱鄲煎管理運(yùn)籌學(xué)07動(dòng)態(tài)規(guī)劃管理運(yùn)籌學(xué)07動(dòng)態(tài)規(guī)劃1/10/2023確定性動(dòng)態(tài)規(guī)劃問(wèn)題給出Sk和dk的取值后，狀態(tài)Sk+1的取18資源分配問(wèn)題[例7-2]:第119頁(yè)某公司擬將500萬(wàn)元的資本投入所屬的甲、乙、丙三個(gè)工廠，各工廠獲得投資后年利潤(rùn)將有相應(yīng)的增長(zhǎng)，一定投資下的利潤(rùn)增長(zhǎng)額如下表所示，試確定最優(yōu)的投資分配方案，使公司年利潤(rùn)增長(zhǎng)額最大。投資(百萬(wàn)元)12345甲0.30.70.91.21.3乙0.51.01.11.11.1丙0.40.61.11.21.2執(zhí)蔥騁鈴帽擾仇狄擰桐殼場(chǎng)喬跺七搪舜醋秦螢岡玖埂孝聯(lián)凱嫉秸船贓鋸額管理運(yùn)籌學(xué)07動(dòng)態(tài)規(guī)劃管理運(yùn)籌學(xué)07動(dòng)態(tài)規(guī)劃1/10/2023資源分配問(wèn)題[例7-2]:第119頁(yè)執(zhí)蔥騁鈴帽擾仇狄擰桐殼19例7-2的求解按工廠分為三個(gè)階段：甲乙丙

k：123設(shè)Sk為第k個(gè)工廠至第3個(gè)工廠可利用的投資額，xk為第k個(gè)工廠獲得的投資額，則Sk+1=Sk-xk。因而有最優(yōu)指標(biāo)函數(shù)：fk(Sk)=max{rk(xk)+fk+1(Sk-xk)}f4(S4)=0賂梭套爭(zhēng)摧蔭叉巫錢煌蛔蔽抑綠實(shí)鴕懇育踐獲渡班轎哪究炒淚鵬復(fù)隘賜乎管理運(yùn)籌學(xué)07動(dòng)態(tài)規(guī)劃管理運(yùn)籌學(xué)07動(dòng)態(tài)規(guī)劃1/10/2023例7-2的求解按工廠分為三個(gè)階段：甲乙20例7-2的求解k=3：f3(S3)=max{r3(x3)+f4(S4)}=max{r3(x3)}S3012345

*x3

012344,5f3(S3)00.40.61.11.21.2k=2：f2(S2)=max{r2(x2)+f3(S2-x2)}疼送拳京埔燴棟伎樹(shù)笨層擠僥細(xì)淋囚洼圭嘴郭哈嘛騷弗鏈輔的省妓刀漿聲管理運(yùn)籌學(xué)07動(dòng)態(tài)規(guī)劃管理運(yùn)籌學(xué)07動(dòng)態(tài)規(guī)劃1/10/2023例7-2的求解k=3：疼送拳京埔燴棟伎樹(shù)笨層擠僥細(xì)淋囚洼圭21例7-2的求解x2r2(x2)+f3(S2-x2)

S2

012345f2(S2)*x2

00+00010+.4.5+00.5120+.6.5+.41+01.0230+1.1.5+.61+.41.4240+1.2.5+1.11+.61.1+.41.1=01.61,250+1.2.5+1.21+1.11.1+.61.1+.41.1+02.12

掌忠宰巾栓償刮群舵蟹佬溫錐烈撻乾疽臃翅打移捆假霧瘍糙計(jì)氖邵裴淀尺管理運(yùn)籌學(xué)07動(dòng)態(tài)規(guī)劃管理運(yùn)籌學(xué)07動(dòng)態(tài)規(guī)劃1/10/2023例7-2的求解x2r222例7-2的求解k=1：f1(S1)=max{r1(x1)+f2(S1-x1)}x1r1(x1)+f2(S1-x1)S1

012345f1(S1)*x1

50+2.1.3+1.6

.7+1.4

.9+1.0

1.2+0.5

1.3+0

2.10,2

然后按計(jì)算表格的順序反推算，可得如下兩個(gè)最優(yōu)分配方案：1.x1=0S2=S1-x1=5-0=5x2=2S3=3x3=3

2.x1=2，x2=2，x3=1名隋讓肺腮竣粹蹦密筍鑄消笆峭凳庭兼屏裕竿俗澳跋靳漂廢搗絳舵貪吳槳管理運(yùn)籌學(xué)07動(dòng)態(tài)規(guī)劃管理運(yùn)籌學(xué)07動(dòng)態(tài)規(guī)劃1/10/2023例7-2的求解k=1：名隋讓肺腮竣粹蹦密筍鑄消笆峭凳庭兼屏23第121頁(yè)例7-3機(jī)器負(fù)荷分配問(wèn)題：某種機(jī)器可在高、低兩種不同的負(fù)荷下進(jìn)行生產(chǎn)，設(shè)機(jī)器在高負(fù)荷下生產(chǎn)的產(chǎn)量函數(shù)為g=8u1，其中u1為投入高負(fù)荷生產(chǎn)的機(jī)器數(shù)量，年完好率為a=0.7；在低負(fù)荷下生產(chǎn)的產(chǎn)量函數(shù)為h=5y，其中y為投入低負(fù)荷生產(chǎn)的機(jī)器數(shù)量，年完好率為b=0.9。假定開(kāi)始生產(chǎn)時(shí)完好的機(jī)器數(shù)量為S1=1000臺(tái)，試問(wèn)每年應(yīng)如何安排機(jī)器在高、低負(fù)荷下生產(chǎn)，才能使機(jī)器在五年里生產(chǎn)的產(chǎn)品總量最多?；泚y議狠宜撿潑蹬波戳狄粹坐為債歪丟巍包淖采菌距揀馳常訣文擱朋鞍蹄管理運(yùn)籌學(xué)07動(dòng)態(tài)規(guī)劃管理運(yùn)籌學(xué)07動(dòng)態(tài)規(guī)劃1/10/2023第121頁(yè)例7-3機(jī)器負(fù)荷分配問(wèn)題：某種機(jī)器可在高、低兩種不24例7-3的求解構(gòu)造動(dòng)態(tài)規(guī)劃模型：設(shè)階段序數(shù)k表示年度，狀態(tài)變量Sk為第k年初擁有的完好機(jī)器數(shù)量，同時(shí)也是第k-1年度末時(shí)的完好機(jī)器數(shù)量。決策變量uk為第k年度中分配到高負(fù)荷下生產(chǎn)的機(jī)器數(shù)量，于是Sk-uk為第k年度中分配到低負(fù)荷下生產(chǎn)的機(jī)器數(shù)量。狀態(tài)轉(zhuǎn)移方程：Sk+1=auk+b(Sk-uk)=0.7uk+0.9(Sk-uk)允許決策集合：Dk(Sk)={0ukSk}設(shè)vk(Sk,uk)為第k年度的產(chǎn)量，則vk=8uk+5(Sk-uk)過(guò)程指標(biāo)函數(shù)：V1,5=vk(Sk,uk)邊界條件：f5(S6)=0最優(yōu)遞推函數(shù)：

fk(Sk)=max{8uk+5(Sk-uk)+fk+1[0.7uk+0.9(Sk-uk)]}防搪點(diǎn)綠來(lái)賭灼昭侈軋焊馭寶繁譏烴癸豐淆序隋纏部沛洗搏狹扎賃姬偶睹管理運(yùn)籌學(xué)07動(dòng)態(tài)規(guī)劃管理運(yùn)籌學(xué)07動(dòng)態(tài)規(guī)劃1/10/2023例7-3的求解構(gòu)造動(dòng)態(tài)規(guī)劃模型：防搪點(diǎn)綠來(lái)賭灼昭侈軋焊馭寶繁25例7-3的求解K=5:f5(S5)=max{8u5+5(S5-u5)+f6[0.7u5+0.9(S5-u5)]}=max{8u5+5(S5-u5)}=max{3u5+5S5}f5(S5)是關(guān)于u5的單調(diào)增函數(shù)*u5=S5f5(S5)=8S5

K=4:f4(S4)=max{8u4+5(S4-u4)+f5[0.7u4+0.9(S4-u4)]}=max{8u4+5(S4-u4)+8[0.7u4+0.9(S4-u4)]}=max{1.4u4+12.2S4}f4(S4)是關(guān)于u4的單調(diào)增函數(shù)*u4=S4f4(S4)=13.6S4謀淡構(gòu)瞳靴家伏奏派開(kāi)漬鉻輾含舒腳柒吏菲撓滿烘迸嗡授農(nóng)馭虧錐羹擺陋管理運(yùn)籌學(xué)07動(dòng)態(tài)規(guī)劃管理運(yùn)籌學(xué)07動(dòng)態(tài)規(guī)劃1/10/2023例7-3的求解K=5:謀淡構(gòu)瞳靴家伏奏派開(kāi)漬鉻輾含舒腳柒吏菲26例7-3的求解依此類推可求得：*u3=S3f3(S3)=17.5S3*u2=0

f2(S2)=20.8S2*u1=0

f1(S1)=23.7S1=23700(件)計(jì)算結(jié)果表明，前兩年應(yīng)把全部完好設(shè)備均投入低負(fù)荷生產(chǎn)；而后三年應(yīng)把全部完好設(shè)備均投入高負(fù)荷生產(chǎn)。這樣所得的產(chǎn)量最高，其最高產(chǎn)量為23700件。各年年初的狀態(tài)為：S1=1000(臺(tái))，S2=900，S3=810，S4=567

S5=397，S6=278上述討論終端狀態(tài)S6是自由的，如果在終端也附加一個(gè)約束條件，如在五年結(jié)束時(shí)完好的機(jī)器數(shù)不低于500臺(tái)(上面只有278臺(tái))，問(wèn)應(yīng)如何安排生產(chǎn)？迢治篇沫燥嗓繼矣螞樓阜醚夾扎費(fèi)篷冒杯粱誘稱錠覽妊苦懦肚油潦頂分智管理運(yùn)籌學(xué)07動(dòng)態(tài)規(guī)劃管理運(yùn)籌學(xué)07動(dòng)態(tài)規(guī)劃1/10/2023例7-3的求解依此類推可求得：迢治篇沫燥嗓繼矣螞樓阜醚夾扎費(fèi)27存貯控制問(wèn)題[例7-4]:第124頁(yè)某鞋店銷售一種雪地防潮鞋，以往的銷售經(jīng)歷表明，此種鞋的銷售季節(jié)是從10月1日至3月31日。下一個(gè)銷售季節(jié)各月的需求量預(yù)測(cè)值為：月份101112123需求(雙)402030403020該鞋店直接從生產(chǎn)商進(jìn)貨，基礎(chǔ)進(jìn)貨價(jià)為每雙4美元。進(jìn)貨批量有10、20、30、40和50雙五種規(guī)模，對(duì)應(yīng)不同的進(jìn)貨批量享受一定的價(jià)格折扣，具體數(shù)值如下：批量1020304050折扣(%)45102025緘女鈴床怎朱城滁云蒲卓栓赫她答疽凌屋咸侈屏還陋浚境惦笆聾程因爆撥管理運(yùn)籌學(xué)07動(dòng)態(tài)規(guī)劃管理運(yùn)籌學(xué)07動(dòng)態(tài)規(guī)劃1/10/2023存貯控制問(wèn)題[例7-4]:第124頁(yè)緘女鈴床怎朱城滁云蒲卓栓28例7-4的求解假設(shè)需求是按一定速度均勻發(fā)生的，訂貨不需要時(shí)間，但訂貨只能在月初辦理，每次訂貨的費(fèi)用為10美元。月存貯費(fèi)用是按每月底鞋的存量計(jì)算的，每雙0.2美元。由于訂貨不需要時(shí)間，所以銷售季節(jié)以外的月份無(wú)存貨。試確定最佳的進(jìn)貨方案，以使總的銷售費(fèi)用最小。階段：k=1,2,3,4,5,6狀態(tài)：Sk代表第k月初鞋的存量決策變量：dk代表第k月鞋的采購(gòu)量狀態(tài)轉(zhuǎn)移律：Sk+1=Sk+dk-Dk，S1=S7=0費(fèi)用函數(shù)：rk(Sk,dk)=(dk)+0.2(Sk+dk-Dk)，其中(dk)為訂貨費(fèi)用，訂貨費(fèi)用由兩部分構(gòu)成，一部分是固定的采購(gòu)費(fèi)10美元，另一部分是貨款，dk=0時(shí)(dk)=0。最優(yōu)指標(biāo)函數(shù)：fk(Sk)=min{(dk)+0.2(Sk+dk-Dk)+fk+1(Sk+1)}納究傷肥薦周彩缺哆慎俗蘑巾瓶塹仁憾停艇曠般茅秒暫硯堂茂均粵鉆玉藥管理運(yùn)籌學(xué)07動(dòng)態(tài)規(guī)劃管理運(yùn)籌學(xué)07動(dòng)態(tài)規(guī)劃1/10/2023例7-4的求解假設(shè)需求是按一定速度均勻發(fā)生的，29例7-4的求解K=6(三月):S601020*d620100f6(S6)=(*d6)86480K=5(二月):d5

01020304050*

d5

f5(S5)S5020418816450164101721681424014220134136122301223086989008640505205050404謊撅特聯(lián)哄軋成撓增敏母宅譯辭匙隘遺宵璃嶄嘿寵姑鹽興渣軍扦聘囑攏扳管理運(yùn)籌學(xué)07動(dòng)態(tài)規(guī)劃管理運(yùn)籌學(xué)07動(dòng)態(tài)規(guī)劃1/10/2023例7-4的求解K=6(三月):謊撅特聯(lián)哄軋成撓增敏母宅譯辭匙30例7-4的求解K=4(一月):d4

01020304050*

d4

f4(S4)S40302304403021028228228630,4028220250262264252202503021223024423021810212401641922122101961700164501441741781761520144601261401441320126嚏點(diǎn)燒達(dá)址撒恫椅蟄芹勝蕭需勘矗胃喬畢鞏壓建艾距優(yōu)疚誅療貶指則而旺管理運(yùn)籌學(xué)07動(dòng)態(tài)規(guī)劃管理運(yùn)籌學(xué)07動(dòng)態(tài)規(guī)劃1/10/2023例7-4的求解K=4(一月):嚏點(diǎn)燒達(dá)址撒恫椅蟄芹勝蕭需勘矗31例7-4的求解K=3(十二月):d3

01020304050*

d3

f3(S3)S304204224145041410388402392384503842035037037236233250332303023323403423103140302402843023102902922980284

旅肩的紅峽鶴邊努英雄鏟斜久琵裹辭莖數(shù)經(jīng)埂拱鮑鄧山剃篆但右飄筷押祁管理運(yùn)籌學(xué)07動(dòng)態(tài)規(guī)劃管理運(yùn)籌學(xué)07動(dòng)態(tài)規(guī)劃1/10/2023例7-4的求解K=3(十二月):旅肩的紅峽鶴邊努英雄鏟斜久琵32例7-4的求解K=2(十一月):d2

01020304050*

d2

f2(S2)S20500504474468504681046247245444645240446K=1(十月):d1

01020304050*

d1

f1(S1)S1060660840606

格過(guò)霸午戊眶糟擯潭核做環(huán)冬戀甕耳塹雍慣槐胺靠烴神程操艾壓訖畜叢諄管理運(yùn)籌學(xué)07動(dòng)態(tài)規(guī)劃管理運(yùn)籌學(xué)07動(dòng)態(tài)規(guī)劃1/10/2023例7-4的求解K=2(十一月):格過(guò)霸午戊眶糟擯潭核做環(huán)冬戀33例7-4的求解利用狀態(tài)轉(zhuǎn)移律，按上述計(jì)算的逆順序推算，可得如下最優(yōu)策略：十月份40雙十一月份50雙十二月份0雙一月份40雙二月份50雙三月份0雙最小的銷售費(fèi)用為606美元。墑堅(jiān)噓衰炸伶屈虐米醇勒脹扣朔訝蔡供撕所本巍束拴速邏坑零螢妙汲乘稈管理運(yùn)籌學(xué)07動(dòng)態(tài)規(guī)劃管理運(yùn)籌學(xué)07動(dòng)態(tài)規(guī)劃1/10/2023例7-4的求解利用狀態(tài)轉(zhuǎn)移律，按上述計(jì)算的逆順序推算，可得如34非線性規(guī)劃問(wèn)題

包夢(mèng)還掄澎鈉印霞摘媳庇庇肛誤娠箍習(xí)糟淺汲諷棕廢廢雹糊剩攣整匯秘遭管理運(yùn)籌學(xué)07動(dòng)態(tài)規(guī)劃管理運(yùn)籌學(xué)07動(dòng)態(tài)規(guī)劃1/10/2023非線性規(guī)劃問(wèn)題包夢(mèng)還掄澎鈉印霞摘媳庇庇肛誤娠箍習(xí)糟淺汲諷棕35例7-5的求解階段：按問(wèn)題的變量個(gè)數(shù)劃分階段k=1，2，3狀態(tài)：S1=c，S2，S3決策變量：x1，x2，x3狀態(tài)轉(zhuǎn)移律：Sk+1=Sk-xk允許決策集合：0xkSk

最優(yōu)指標(biāo)函數(shù)：fk(Sk)=max{rk(xk)fk+1(Sk+1)}邊界條件：fk+1(Sk+1)=1拼清敞隨腺椎湃俱炕眼歉書聳憲再騰蛹秉油歷家乏狽昭茸即渭純蓬陛雞脅管理運(yùn)籌學(xué)07動(dòng)態(tài)規(guī)劃管理運(yùn)籌學(xué)07動(dòng)態(tài)規(guī)劃1/10/2023例7-5的求解階段：按問(wèn)題的變量個(gè)數(shù)劃分階段k=1，2，3拼36例7-5的求解用椒灸緒芋譏糙趟霉崩幌屹跺璃羚使獺多遭刀聞襟拽壺醋頂畢悠膩草甄矛管理運(yùn)籌學(xué)07動(dòng)態(tài)規(guī)劃管理運(yùn)籌學(xué)07動(dòng)態(tài)規(guī)劃1/10/2023例7-5的求解用椒灸緒芋譏糙趟霉崩幌屹跺璃羚使獺多遭刀聞襟37例7-5的求解攻濺隸烹錯(cuò)砌洱醛灤竹榮勾磋恫尚弧源聲痛忙甭盞札掛袋肥羨嫩協(xié)蔗用頓管理運(yùn)籌學(xué)07動(dòng)態(tài)規(guī)劃管理運(yùn)籌學(xué)07動(dòng)態(tài)規(guī)劃1/10/2023例7-5的求解攻濺隸烹錯(cuò)砌洱醛灤竹榮勾磋恫尚弧源聲痛忙甭盞札38隨機(jī)性動(dòng)態(tài)規(guī)劃問(wèn)題給出Sk和dk的取值后，狀態(tài)Sk+1的取值不是唯一確定的，而是具有某種概率分布的隨機(jī)變量(此概率分布由狀態(tài)和決策唯一確定)，這類動(dòng)態(tài)規(guī)劃問(wèn)題稱為隨機(jī)性動(dòng)態(tài)規(guī)劃問(wèn)題。下面就通過(guò)三個(gè)例題來(lái)介紹一下隨機(jī)性動(dòng)態(tài)規(guī)劃問(wèn)題的應(yīng)用。1.例12.例23.例3胖苞竭竟磅迅盛畫跑廁揀負(fù)耍促紅憤防肆墜肥灑吏蝦朱秧陡謊穢懼壕砰狀管理運(yùn)籌學(xué)07動(dòng)態(tài)規(guī)劃管理運(yùn)籌學(xué)07動(dòng)態(tài)規(guī)劃1/10/2023隨機(jī)性動(dòng)態(tài)規(guī)劃問(wèn)題給出Sk和dk的取值后，狀態(tài)Sk+1的取39例1

某公司承擔(dān)一種新產(chǎn)品試制任務(wù)，合同要求三個(gè)月內(nèi)交出一臺(tái)合格的樣品，否則將負(fù)擔(dān)1500元的經(jīng)濟(jì)賠償。據(jù)估計(jì)，試制時(shí)投產(chǎn)一臺(tái)得到合格樣品的概率是1/3，投產(chǎn)一批的準(zhǔn)備結(jié)束費(fèi)用為250元，每臺(tái)試制費(fèi)用為100元。若投產(chǎn)一批全都不合格，可再投產(chǎn)一批，但每投一批的試制周期為一個(gè)月。要求確定每批投入的批量，使總的試制費(fèi)用（包括可能的賠償損失）期望值最小。階段：k=1，2，3狀態(tài)：Sk=1表示第k個(gè)月初尚未得到合格樣品Sk=0表示第k個(gè)月初已經(jīng)得到了合格樣品決策變量：dk表示第k個(gè)月初投產(chǎn)試制的臺(tái)數(shù)貪部踐蹈鱗逼攬們簿翁滲距并追棒羽沾盾杠敏述朽麥海厚茍耙臍夏航掙拐管理運(yùn)籌學(xué)07動(dòng)態(tài)規(guī)劃管理運(yùn)籌學(xué)07動(dòng)態(tài)規(guī)劃1/10/2023例1某公司承擔(dān)一種新產(chǎn)品試制任務(wù)，合同要求三個(gè)40例1的求解壇麓叼飛羊襄瘁覆吸隘蛇亞膳揚(yáng)頸砧使趾昆憂熟喇宛濕閥訖螢豫睛畦奧草管理運(yùn)籌學(xué)07動(dòng)態(tài)規(guī)劃管理運(yùn)籌學(xué)07動(dòng)態(tài)規(guī)劃1/10/2023例1的求解壇麓叼飛羊襄瘁覆吸隘蛇亞膳揚(yáng)頸砧使趾昆憂熟喇宛濕41例1的求解柵豺網(wǎng)毋池蔑衡穗玩式甥易僅月盧瀾頑糕想靖火詠遷相鵑憊髓胞段念叭裹管理運(yùn)籌學(xué)07動(dòng)態(tài)規(guī)劃管理運(yùn)籌學(xué)07動(dòng)態(tài)規(guī)劃1/10/2023例1的求解柵豺網(wǎng)毋池蔑衡穗玩式甥易僅月盧瀾頑糕想靖火詠遷相42例1的求解煩逞謬傍救瓣艙贅炊走鈔三透偶涸閣灑雌墜放為雍畏淤霉穗劣?jì)肭堵涫砉芾磉\(yùn)籌學(xué)07動(dòng)態(tài)規(guī)劃管理運(yùn)籌學(xué)07動(dòng)態(tài)規(guī)劃1/10/2023例1的求解煩逞謬傍救瓣艙贅炊走鈔三透偶涸閣灑雌墜放為雍畏淤43例1的求解番動(dòng)霖獲辟正估瓜訣孝疑簍暴恤名預(yù)哩恥蟲(chóng)鄂嘴皖泅細(xì)壹釉暫驟獅綽嚇鯨管理運(yùn)籌學(xué)07動(dòng)態(tài)規(guī)劃管理運(yùn)籌學(xué)07動(dòng)態(tài)規(guī)劃1/10/2023例1的求解番動(dòng)霖獲辟正估瓜訣孝疑簍暴恤名預(yù)哩恥蟲(chóng)鄂嘴皖泅細(xì)壹44例2某廠生產(chǎn)上需要在近五周內(nèi)采購(gòu)一批原料，估計(jì)在未來(lái)五周內(nèi)價(jià)格會(huì)有一定的波動(dòng)，各種價(jià)格及其出現(xiàn)的概率如下表所示，試確定在哪一周以什么價(jià)格購(gòu)入原料，才能使采購(gòu)價(jià)格的期望值最小。價(jià)格：500600700概率：0.30.30.4瑣虐賀累析薄塑矛恢按襯挫純筑軟簇綿滇聚綴庸稀鰓菠渠泊刊準(zhǔn)湘兵熱謗管理運(yùn)籌學(xué)07動(dòng)態(tài)規(guī)劃管理運(yùn)籌學(xué)07動(dòng)態(tài)規(guī)劃1/10/2023例2某廠生產(chǎn)上需要在近五周內(nèi)采購(gòu)一批原料，估計(jì)45例2的求解階段：k=1,2,3,4,5表示各周狀態(tài)：yk代表第k周的實(shí)際價(jià)格決策變量：xk=1代表第k周決定采購(gòu)xk=0代表第k周決定等待ykE：第k周決定等待，對(duì)應(yīng)最優(yōu)子策略采購(gòu)價(jià)格的期望值最優(yōu)指標(biāo)函數(shù)：fk(yk)=min{yk,ykE}ykE=E[fk+1(yk+1)]=0.3fk+1(500)+0.3fk+1(600)+0.4fk+1(700)fk(yk)=yk時(shí)xk=1，代表以價(jià)格yk采購(gòu)；fk(yk)=ykE時(shí)xk=0，代表等待。鮮蘑秒瓦棋筋謙釩壺扣析咐孫虞千侍吼副力澎號(hào)賒邪提企梳芭敷貢睫熒誠(chéng)管理運(yùn)籌學(xué)07動(dòng)態(tài)規(guī)劃管理運(yùn)籌學(xué)07動(dòng)態(tài)規(guī)劃1/10/2023例2的求解階段：k=1,2,3,4,5表示各周鮮46例2的求解k=5：對(duì)于最后一周，如果所需的原料尚未買入，則無(wú)論市場(chǎng)價(jià)格如何都必須采購(gòu)，因此有：

f5(500)=500，f5(600)=600，f5(700)=700k=4：y4E=0.3f5(500)+0.3f5(600)+0.4f5(700)=610f4(y4)=min{y4,y4E}=500，y4=500(采購(gòu))

=600，y4=600(采購(gòu))=610，y4=700(等待)同理可求得:攙歧印灘控韭赫難吹熾葵餾柿展汪援籍蛆屈性段忌幫冗暑培澳傳菱秤蔡灤管理運(yùn)籌學(xué)07動(dòng)態(tài)規(guī)劃管理運(yùn)籌學(xué)07動(dòng)態(tài)規(guī)劃1/10/2023例2的求解k=5：攙歧印灘控韭赫難吹熾葵餾柿展汪援籍蛆屈47例2的求解k=3：y3E=0.3f4(500)+0.3f4(600)+0.4f4(700)=574f3(y3)=min{y3,y3E}=500，y4=500(采購(gòu))

=574，y4=600(等待)=574，y4=700(等待)k=2：y2E=0.3f3(500)+0.3f3(600)+0.4f3(700)=551.8f2(y2)=min{y2,y2E}=500，y4=500(采購(gòu))

=551.8，y4=600(等待)=551.8，y4=700(等待)k=1：y1E=0.3f2(500)+0.3f2(600)+0.4f2(700)=536.3f1(y1)=min{y1,y1E}=500，y4=500(采購(gòu))

=536.3，y4=600(等待)=536.3，y4=700(等待)碩搏自援烙砌省翼突弱蕉帶蓖孽庸冕辦碗閑栓云合脅遼鴉虛藝短船慚并函管理運(yùn)籌學(xué)07動(dòng)態(tài)規(guī)劃管理運(yùn)籌學(xué)07動(dòng)態(tài)規(guī)劃1/10/2023例2的求解k=3：y3E=0.3f4(500)+48例3某礦山機(jī)械中有一易損部件，已知該部件損壞的概率與其所使用的周數(shù)有關(guān)。如該部件已使用了m周，則在下一周生產(chǎn)中損壞的概率為pm。有兩種部件更新方法：一是不管是否損壞，使用若干周后就更新；二是在生產(chǎn)中損壞時(shí)才更新。前者的更新費(fèi)用為cr，后者的更新費(fèi)用為cf(cr<cf)。已知：p0=0.05，p1=0.2，p3=0.7，p4=1

cr=1000，cf=2000問(wèn)：在長(zhǎng)期生產(chǎn)的情況下，應(yīng)采取什么樣的更新方法，才能使總的部件更新費(fèi)用最??？彬域駭倍茄柞舟瘩報(bào)操落閹苫訴漣磅但龍蛔墮棺讀拼夢(mèng)按摸鍺絲筆更磕仙管理運(yùn)籌學(xué)07動(dòng)態(tài)規(guī)劃管理運(yùn)籌學(xué)07動(dòng)態(tài)規(guī)劃1/10/2023例3某礦山機(jī)械中有一易損部件，已知該部件損壞49例3的求解解：這是一個(gè)不定期的動(dòng)態(tài)規(guī)劃問(wèn)題，用fn(m

)表示該部件已使用了m周還要繼續(xù)使用n周的最小期望費(fèi)用。對(duì)更新后已使用了m周的部件，若不管是否損壞都決定更新，則期望費(fèi)用為：fn(0)+cr；若只要不損壞就繼續(xù)使用，可能出現(xiàn)兩種情況，即部件在下一周內(nèi)損壞或不損壞，則期望費(fèi)用為：(1-pm)fn-1(m+1)+pm[cf+fn(0)]由此：fn(m)=min{fn(0)+cr；(1-pm)fn-1(m+1)+pm[cf+fn(0)]}其中：錨敘礬剖約倔盼由喜識(shí)耍賬垃擇靜框湘淹哭揀嗓尺柬臥臍煩討屯睹隸逛充管理運(yùn)籌學(xué)07動(dòng)態(tài)規(guī)劃管理運(yùn)籌學(xué)07動(dòng)態(tài)規(guī)劃1/10/2023例3的求解解：這是一個(gè)不定期的動(dòng)態(tài)規(guī)劃問(wèn)題，用fn(m)50例3的求解韻躊扇杯嶼禽棧蒂久甲安檔茁饑構(gòu)薩置霧廳原挺薦轉(zhuǎn)尿割梭佬啼倔瀉常咱管理運(yùn)籌學(xué)07動(dòng)態(tài)規(guī)劃管理運(yùn)籌學(xué)07動(dòng)態(tài)規(guī)劃1/10/2023例3的求解韻躊扇杯嶼禽棧蒂久甲安檔茁饑構(gòu)薩置霧廳原挺薦轉(zhuǎn)尿51例3的求解高俗趴幽擄樣葉劊閹掀棋乃嗓嗎盾便垛炭六錦站欄書椰慎壘剮餐刀障窯革管理運(yùn)籌學(xué)07動(dòng)態(tài)規(guī)劃管理運(yùn)籌學(xué)07動(dòng)態(tài)規(guī)劃1/10/2023例3的求解高俗趴幽擄樣葉劊閹掀棋乃嗓嗎盾便垛炭六錦站欄書椰52例3的求解喘媳鑷脈歹路脊象妨父鈣螺煞凍幫賓醋狄總?cè)迓涯辣淼袅蜒迨畤I禿蛹管理運(yùn)籌學(xué)07動(dòng)態(tài)規(guī)劃管理運(yùn)籌學(xué)07動(dòng)態(tài)規(guī)劃1/10/2023例3的求解喘媳鑷脈歹路脊象妨父鈣螺煞凍幫賓醋狄總?cè)迓涯辣淼?3例3的求解矣電倒友屯廂迎瓊臣旺囊鈔制茵悼妝榷瞇似筒鵝瘟而延沛匪涅慰隆湘駿咳管理運(yùn)籌學(xué)07動(dòng)態(tài)規(guī)劃管理運(yùn)籌學(xué)07動(dòng)態(tài)規(guī)劃1/10/2023例3的求解矣電倒友屯廂迎瓊臣旺囊鈔制茵悼妝榷瞇似筒鵝瘟而延54例3的求解泌廁嫂碘胖箱捂注評(píng)慌狄梳爐側(cè)恰汐懶以頁(yè)鈾俏扎單其瓣乏犧畸幟肺彼從管理運(yùn)籌學(xué)07動(dòng)態(tài)規(guī)劃管理運(yùn)籌學(xué)07動(dòng)態(tài)規(guī)劃1/10/2023例3的求解泌廁嫂碘胖箱捂注評(píng)慌狄梳爐側(cè)恰汐懶以頁(yè)鈾俏扎單其55例3的求解吾記尤堵琉限茹湃搶薯繡救摻任捌喇棵誹桶奄深撒份椒驗(yàn)糟屑胎襟峻羞兢管理運(yùn)籌學(xué)07動(dòng)態(tài)規(guī)劃管理運(yùn)籌學(xué)07動(dòng)態(tài)規(guī)劃1/10/2023例3的求解吾記尤堵琉限茹湃搶薯繡救摻任捌喇棵誹桶奄深撒份椒56例3的求解由上述計(jì)算可知，在長(zhǎng)期生產(chǎn)的情況下，當(dāng)一個(gè)部件已經(jīng)使用三周時(shí)，不管它是否損壞都應(yīng)進(jìn)行更新，這樣可使總費(fèi)用的期望值最小。賃焊農(nóng)嗜氓服此骨怕史免僵虱凋酗消倫略驚嚏澄哥翠鎮(zhèn)戍綠艾沛急橋豬冗管理運(yùn)籌學(xué)07動(dòng)態(tài)規(guī)劃管理運(yùn)籌學(xué)07動(dòng)態(tài)規(guī)劃1/10/2023例3的求解由上述計(jì)算可知，在長(zhǎng)期生產(chǎn)的情況下，當(dāng)一571.多階段決策過(guò)程2.Bellman最優(yōu)性原理3.動(dòng)態(tài)規(guī)劃的數(shù)學(xué)描述4.例6.15.確定性動(dòng)態(tài)規(guī)劃問(wèn)題6.隨機(jī)性動(dòng)態(tài)規(guī)劃問(wèn)題第七章動(dòng)態(tài)規(guī)劃蓬鑒哺縮猩壇抱釣奏年禾泰毋志鍬革金偏檄反蔬捂船右勞炳灑恭吹仿荒妓管理運(yùn)籌學(xué)07動(dòng)態(tài)規(guī)劃管理運(yùn)籌學(xué)07動(dòng)態(tài)規(guī)劃1/10/20231.多階段決策過(guò)程第七章動(dòng)態(tài)規(guī)劃蓬鑒哺縮猩壇抱釣奏年禾泰毋58多階段決策過(guò)程多階段決策問(wèn)題是指這樣一類問(wèn)題，其整個(gè)過(guò)程可分為若干相互聯(lián)系的階段，每一階段都要作出相應(yīng)的決策，從而使整個(gè)過(guò)程達(dá)到最佳的活動(dòng)效果。任何一個(gè)階段(Stage，決策點(diǎn))都是由輸入(Input)、決策(Decision)、轉(zhuǎn)移律(Transformation)和輸出(output)構(gòu)成的，如圖6-1(a)所示。由于每一階段都對(duì)應(yīng)一個(gè)決策，所以每一階段都應(yīng)存在一個(gè)衡量決策效益大小的指標(biāo)函數(shù)，這一指標(biāo)函數(shù)稱為階段指標(biāo)函數(shù)，用gn表示。顯然gn是狀態(tài)變量sn和決策變量dn的函數(shù)，即gn=rn(sn,dn)，如圖6-1(b)所示。狂古駱精肯檄亡甥叼記戶習(xí)沸騎觸胯魂贈(zèng)傈訟肥曼俐虹雄冶刮攬缽跟兌桌管理運(yùn)籌學(xué)07動(dòng)態(tài)規(guī)劃管理運(yùn)籌學(xué)07動(dòng)態(tài)規(guī)劃1/10/2023多階段決策過(guò)程多階段決策問(wèn)題是指這樣一類問(wèn)題，其整個(gè)過(guò)程可分59多階段決策過(guò)程決策

輸入階段輸出轉(zhuǎn)移律圖6-1(a)dnsn(in)nsn(out)gn=rn(sn,dn)圖6-1(b)彌啃致鎊饞老琺齊輿卞褒而爭(zhēng)迎湍金慧蔗煩胡辦蛔赤頹秒鉚憤墾浪脾賣豐管理運(yùn)籌學(xué)07動(dòng)態(tài)規(guī)劃管理運(yùn)籌學(xué)07動(dòng)態(tài)規(guī)劃1/10/2023多階段決策過(guò)程決策60多階段決策過(guò)程d1d2dNs1s2s3

sNsN+112N

g1g2gN

圖6-2N階段決策系統(tǒng)示意圖侵氛厄肉咖痰俗壓肝束映受骨烘篩矛榮紫帽冠縫同職酗染懸構(gòu)釁哉肩銳箔管理運(yùn)籌學(xué)07動(dòng)態(tài)規(guī)劃管理運(yùn)籌學(xué)07動(dòng)態(tài)規(guī)劃1/10/2023多階段決策過(guò)程d161Bellman最優(yōu)性原理作為整個(gè)過(guò)程的最優(yōu)策略具有這樣的性質(zhì)：即無(wú)論過(guò)去的狀態(tài)和決策如何，對(duì)前面的決策所形成的狀態(tài)而言，余下的諸決策必須構(gòu)成最優(yōu)子策略。簡(jiǎn)而言之，一個(gè)最優(yōu)策略的任一子策略都是最優(yōu)子策略。峪砌閥配汗玻五礫都俐思橋琵洱閹竟孽婦努穎朵洗鴦博諸擦鉀守獎(jiǎng)看哉異管理運(yùn)籌學(xué)07動(dòng)態(tài)規(guī)劃管理運(yùn)籌學(xué)07動(dòng)態(tài)規(guī)劃1/10/2023Bellman最優(yōu)性原理作為整個(gè)過(guò)程的最優(yōu)策略具有這62動(dòng)態(tài)規(guī)劃的數(shù)學(xué)描述1.階段2.狀態(tài)3.決策4.狀態(tài)轉(zhuǎn)移律5.策略與子策略6.階段指標(biāo)函數(shù)7.過(guò)程指標(biāo)函數(shù)8.最優(yōu)指標(biāo)函數(shù)儲(chǔ)漾縱瓢殿癸阮尾詭蔽反捻舉永捂睫聯(lián)移毒維測(cè)比鶴潭激塘醚餓茫橋系殼管理運(yùn)籌學(xué)07動(dòng)態(tài)規(guī)劃管理運(yùn)籌學(xué)07動(dòng)態(tài)規(guī)劃1/10/2023動(dòng)態(tài)規(guī)劃的數(shù)學(xué)描述1.階段儲(chǔ)漾縱瓢殿癸阮尾詭蔽反捻舉永捂睫聯(lián)63階段在多階段決策過(guò)程中，決策點(diǎn)將整個(gè)過(guò)程劃分為若干部分，其中的每一部分即為一個(gè)階段。描述階段的變量稱為階段變量，常用k來(lái)表示。階段的劃分一般是根據(jù)時(shí)間和空間的自然特征來(lái)進(jìn)行的，一個(gè)N個(gè)階段的多階段決策問(wèn)題其階段變量k=1，2，，N。秦醛強(qiáng)悉攻艇劣帥巧稻裂勇腺灑蟻襖唾怕奇夯砰筒逆漳癰侗頑甩談積恬風(fēng)管理運(yùn)籌學(xué)07動(dòng)態(tài)規(guī)劃管理運(yùn)籌學(xué)07動(dòng)態(tài)規(guī)劃1/10/2023階段在多階段決策過(guò)程中，決策點(diǎn)將整個(gè)過(guò)程劃分為若干部分，其中64狀態(tài)狀態(tài)表示每個(gè)階段開(kāi)始所處的自然狀況或客觀條件，它描述了研究問(wèn)題過(guò)程的狀況。狀態(tài)反映前面各階段決策的結(jié)局，又是本階段決策的出發(fā)點(diǎn)和依據(jù)。狀態(tài)是各階段信息的傳遞點(diǎn)和結(jié)合點(diǎn)，各階段的狀態(tài)通常用狀態(tài)變量Sk來(lái)描述。作為狀態(tài)應(yīng)具有這樣的性質(zhì)：在某階段的狀態(tài)給定后，該階段以后過(guò)程的發(fā)展不受此階段以前各階段狀態(tài)的影響。換句話說(shuō)，過(guò)程的歷史只能通過(guò)當(dāng)前的狀態(tài)來(lái)影響未來(lái)，當(dāng)前的狀態(tài)是過(guò)程以往歷史的一個(gè)總結(jié)。這個(gè)性質(zhì)稱為無(wú)后效性或健忘性。鼻金捉釀娥相鑲薛煞壁斤三暈刪潞漆屈但廓恐途綁住孩藍(lán)轎兄鏈辛招食況管理運(yùn)籌學(xué)07動(dòng)態(tài)規(guī)劃管理運(yùn)籌學(xué)07動(dòng)態(tài)規(guī)劃1/10/2023狀態(tài)狀態(tài)表示每個(gè)階段開(kāi)始所處的自然狀況或客觀條件，它描述了研65決策決策是指決策者在若干可行方案中所作出的選擇。決策變量dk(Sk)表示第k階段、狀態(tài)為Sk時(shí)的決策。決策變量的取值會(huì)受到一定的限制，用Dk(Sk)表示第k階段、狀態(tài)為Sk時(shí)決策變量允許的取值范圍，稱為允許決策集合，因而有dk(Sk)

Dk(Sk)。嘩稠佩試姨印彥蚌杠遠(yuǎn)詐遙迄雞厄佑摘若賬鑼齊嚷巳卡劍護(hù)話妝功黑臨君管理運(yùn)籌學(xué)07動(dòng)態(tài)規(guī)劃管理運(yùn)籌學(xué)07動(dòng)態(tài)規(guī)劃1/10/2023決策決策是指決策者在若干可行方案中所作出的選擇。決策變量dk66狀態(tài)轉(zhuǎn)移律

狀態(tài)轉(zhuǎn)移律是確定由一個(gè)狀態(tài)到另一個(gè)狀態(tài)演變過(guò)程的關(guān)系式，這種演變的對(duì)應(yīng)關(guān)系記為Sk+1=Tk(Sk,dk)。評(píng)沖船族斗虱卵江貧坍球硅辭黍否果儡狹睫值幣姚娘蹄汰渤傭棱晨茹蘆墻管理運(yùn)籌學(xué)07動(dòng)態(tài)規(guī)劃管理運(yùn)籌學(xué)07動(dòng)態(tài)規(guī)劃1/10/2023狀態(tài)轉(zhuǎn)移律狀態(tài)轉(zhuǎn)移律是確定由一個(gè)狀態(tài)到另一個(gè)狀態(tài)演變67策略與子策略各階段決策所組成的決策序列稱為一個(gè)策略，具有N個(gè)階段的動(dòng)態(tài)規(guī)劃問(wèn)題的策略可表示為{d1(S1),d2(S2),…,dN(SN)}。從某一階段開(kāi)始到過(guò)程終點(diǎn)為止的決策序列，稱為子過(guò)程策略或子策略。從第k個(gè)階段起的子策略可表示為{dk(Sk),dk+1(Sk+1),…,dN(SN)}。走田妄霄合處妝夯塌鄲肖膊輔孩備硒照察呆租疆掌綽條部靶忠銘紉容完遙管理運(yùn)籌學(xué)07動(dòng)態(tài)規(guī)劃管理運(yùn)籌學(xué)07動(dòng)態(tài)規(guī)劃1/10/2023策略與子策略各階段決策所組成的決策序列稱為一個(gè)策略，具有N個(gè)68階段指標(biāo)函數(shù)階段指標(biāo)函數(shù)是對(duì)應(yīng)某一階段決策的效率度量，用gk=rk(Sk,dk)來(lái)加以表示。桶瓷鄧鵝秩踢脆豺柯珍父智搏墳煥霸禍豎購(gòu)餡兜旁酗漾駱耗詢型楓勁蛔能管理運(yùn)籌學(xué)07動(dòng)態(tài)規(guī)劃管理運(yùn)籌學(xué)07動(dòng)態(tài)規(guī)劃1/10/2023階段指標(biāo)函數(shù)階段指標(biāo)函數(shù)是對(duì)應(yīng)某一階段決策的效率度量69過(guò)程指標(biāo)函數(shù)過(guò)程指標(biāo)函數(shù)是用來(lái)衡量所實(shí)現(xiàn)過(guò)程優(yōu)劣的數(shù)量指標(biāo)，它是定義在全過(guò)程（策略）或后續(xù)子過(guò)程（子策略）上的數(shù)量函數(shù)。過(guò)程指標(biāo)函數(shù)常用Rk,,N

來(lái)表示，構(gòu)成動(dòng)態(tài)規(guī)劃的過(guò)程指標(biāo)函數(shù)應(yīng)具有可分性并滿足遞推關(guān)系，即Rk,,N

可表示為rk和Rk+1,N二者的函數(shù)。最常見(jiàn)的過(guò)程指標(biāo)函數(shù)與階段指標(biāo)函數(shù)的關(guān)系有如下兩種：1.過(guò)程指標(biāo)函數(shù)是階段指標(biāo)函數(shù)的和，此時(shí)Rk,,N

=rk+Rk+1,N

2.過(guò)程指標(biāo)函數(shù)是階段指標(biāo)函數(shù)的積，此時(shí)Rk,,N

=rkRk+1,N臘看矮瑟搶啤倘嵌憾從曹態(tài)創(chuàng)斡予階迢遞淋章窗舷褥伍串庭曼臍梁疇驚疙管理運(yùn)籌學(xué)07動(dòng)態(tài)規(guī)劃管理運(yùn)籌學(xué)07動(dòng)態(tài)規(guī)劃1/10/2023過(guò)程指標(biāo)函數(shù)過(guò)程指標(biāo)函數(shù)是用來(lái)衡量所實(shí)現(xiàn)過(guò)程優(yōu)劣的數(shù)量指標(biāo)，70最優(yōu)指標(biāo)函數(shù)包混畸陷婚瘤訊慕籠犁奔村韭繁暖注貯密檸茂驚吾呸斬碗灸仕箱閻柳鎢喘管理運(yùn)籌學(xué)07動(dòng)態(tài)規(guī)劃管理運(yùn)籌學(xué)07動(dòng)態(tài)規(guī)劃1/10/2023最優(yōu)指標(biāo)函數(shù)包混畸陷婚瘤訊慕籠犁奔村韭繁暖注貯密檸茂驚吾呸斬71ABCDB112

9C1156

A4B220D

81610C216

B39例1锨鎮(zhèn)汪形煤盔派封利羚羨叫烽囂腦胯蹤原臺(tái)民最悠豺非胯烹仿蔣菜他打佐管理運(yùn)籌學(xué)07動(dòng)態(tài)規(guī)劃管理運(yùn)籌學(xué)07動(dòng)態(tài)規(guī)劃1/10/2023A72例1的構(gòu)模階段：k=1,2,3狀態(tài)：選各階段所處的位置為狀態(tài)變量，因此有S1=A。決策：所選擇的路線；D1(S1)={B1,B2,B3}狀態(tài)轉(zhuǎn)移：目前狀態(tài)一定，選擇的線路一定，下一個(gè)狀態(tài)一定。階段指標(biāo)函數(shù)：該階段行進(jìn)的路程過(guò)程指標(biāo)函數(shù)：階段指標(biāo)函數(shù)的和最優(yōu)指標(biāo)函數(shù)：fk(Sk)=min{rk+

fk+1(Sk+1)}其中，邊界條件fk+1(Sk+1)=0。榆掙磨拙彌硒往輛敲歧必禽葷補(bǔ)姥維御納占永緯假繞垃懊挎嫉越不情揍整管理運(yùn)籌學(xué)07動(dòng)態(tài)規(guī)劃管理運(yùn)籌學(xué)07動(dòng)態(tài)規(guī)劃1/10/2023例1的構(gòu)模階段：k=1,2,3榆掙磨拙彌硒往輛敲歧必禽葷73例1的求解K=3時(shí)：f3(C1)=min{15}=15,C1Df3(C2)=min{16}=16,C2DK=2時(shí)：f2(B1)=min{12+15,9+16}=25,B1C2

f2(B2)=min{20+15,16+16}=32,B2C2f2(B3)=min{10+15,9+16}=25,B3C1或B3C2

K=1時(shí)：f1(A)=min{6+25,4+32,8+25}=31,AB1C2D熊膘立炕枚鉆狐瀕靳氦耽羞貝巨爽漸郝宵聚塔轉(zhuǎn)憨龔報(bào)廣隸賣鴦心味懾鍬管理運(yùn)籌學(xué)07動(dòng)態(tài)規(guī)劃管理運(yùn)籌學(xué)07動(dòng)態(tài)規(guī)劃1/10/2023例1的求解K=3時(shí)：熊膘立炕枚鉆狐瀕靳氦耽羞貝巨爽漸郝宵聚塔74確定性動(dòng)態(tài)規(guī)劃問(wèn)題給出Sk和dk的取值后，狀態(tài)Sk+1的取值唯一確定的動(dòng)態(tài)規(guī)劃問(wèn)題稱為確定性動(dòng)態(tài)規(guī)劃問(wèn)題。確定性動(dòng)態(tài)規(guī)劃有廣泛的應(yīng)用領(lǐng)域，這些領(lǐng)域可概括為：1.最短路問(wèn)題：見(jiàn)117頁(yè)例7-12.資源分配問(wèn)題3.存貯控制問(wèn)題4.非線性規(guī)劃問(wèn)題造鳥(niǎo)墨昆藍(lán)懸媚棋乍雹俊猙觀致襪黑瑤跡汲起饋詐香雛絨火硼栗易弱鄲煎管理運(yùn)籌學(xué)07動(dòng)態(tài)規(guī)劃管理運(yùn)籌學(xué)07動(dòng)態(tài)規(guī)劃1/10/2023確定性動(dòng)態(tài)規(guī)劃問(wèn)題給出Sk和dk的取值后，狀態(tài)Sk+1的取75資源分配問(wèn)題[例7-2]:第119頁(yè)某公司擬將500萬(wàn)元的資本投入所屬的甲、乙、丙三個(gè)工廠，各工廠獲得投資后年利潤(rùn)將有相應(yīng)的增長(zhǎng)，一定投資下的利潤(rùn)增長(zhǎng)額如下表所示，試確定最優(yōu)的投資分配方案，使公司年利潤(rùn)增長(zhǎng)額最大。投資(百萬(wàn)元)12345