管理運(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ī)劃2023/2/6多階段決策過(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)所示。2023/2/6多階段決策過(guò)程決策

輸入階段輸出轉(zhuǎn)移律圖6-1(a)

dn

sn(in)

n

sn(out)

gn=rn(sn,dn)

圖6-1(b)2023/2/6Bellman最優(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)子策略。2023/2/6動(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ù)2023/2/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。2023/2/6決策決策是指決策者在若干可行方案中所作出的選擇。決策變量dk(Sk)表示第k階段、狀態(tài)為Sk時(shí)的決策。決策變量的取值會(huì)受到一定的限制，用Dk(Sk)表示第k階段、狀態(tài)為Sk時(shí)決策變量允許的取值范圍，稱為允許決策集合，因而有dk(Sk)

Dk(Sk)。2023/2/6狀態(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)。2023/2/6策略與子策略各階段決策所組成的決策序列稱為一個(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)}。2023/2/6過(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,N2023/2/6最優(yōu)指標(biāo)函數(shù)2023/2/6

ABCDB112

9C1156

A4B220D

81610C216

B39例12023/2/6例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,AB1C2D2023/2/6確定性動(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)題2023/2/6資源分配問(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.22023/2/6例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)}2023/2/6例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

2023/2/6例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=12023/2/6例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)]}2023/2/6例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.6S42023/2/6例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)}2023/2/6例7-4的求解K=6(三月):

S601020*d620100f6(S6)=(*d6)86480K=5(二月):

d5

01020304050*

d5

f5(S5)S50204188164501641017216814240142201341361223012230869890086405052050504042023/2/6例7-4的求解K=4(一月):

d4

01020304050*

d4

f4(S4)S40302304403021028228228630,40282202502622642522025030212230244230218102124016419221221019617001645014417417817615201446012614014413201262023/2/6例7-4的求解K=3(十二月):

d3

01020304050*

d3

f3(S3)S304204224145041410388402392384503842035037037236233250332303023323403423103140302402843023102902922980284

2023/2/6例7-4的求解K=2(十一月):

d2

01020304050*

d2

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

d1

01020304050*

d1

f1(S1)S1060660840606

2023/2/6例7-4的求解利用狀態(tài)轉(zhuǎn)移律，按上述計(jì)算的逆順序推算，可得如下最優(yōu)策略：十月份40雙十一月份50雙十二月份0雙一月份40雙二月份50雙三月份0雙最小的銷售費(fèi)用為606美元。2023/2/6非線性規(guī)劃問(wèn)題

2023/2/6例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)=12023/2/6例7-5的求解2023/2/6例7-5的求解2023/2/6隨機(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.例32023/2/6例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ù)2023/2/6例1的求解2023/2/6例1的求解2023/2/6例1的求解2023/2/6例1的求解2023/2/6例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.42023/2/6例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，代表等待。2023/2/6例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(等待)同理可求得:2023/2/6例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)=55