管理運籌學07動態(tài)規(guī)劃課件

1.多階段決策過程2.Bellman最優(yōu)性原理3.動態(tài)規(guī)劃的數(shù)學描述4.例6.15.確定性動態(tài)規(guī)劃問題6.隨機性動態(tài)規(guī)劃問題第七章動態(tài)規(guī)劃2023/2/6多階段決策過程多階段決策問題是指這樣一類問題，其整個過程可分為若干相互聯(lián)系的階段，每一階段都要作出相應的決策，從而使整個過程達到最佳的活動效果。任何一個階段(Stage，決策點)都是由輸入(Input)、決策(Decision)、轉移律(Transformation)和輸出(output)構成的，如圖6-1(a)所示。由于每一階段都對應一個決策，所以每一階段都應存在一個衡量決策效益大小的指標函數(shù)，這一指標函數(shù)稱為階段指標函數(shù)，用gn表示。顯然gn是狀態(tài)變量sn和決策變量dn的函數(shù)，即gn=rn(sn,dn)，如圖6-1(b)所示。2023/2/6多階段決策過程決策

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

dn

sn(in)

n

sn(out)

gn=rn(sn,dn)

圖6-1(b)2023/2/6Bellman最優(yōu)性原理作為整個過程的最優(yōu)策略具有這樣的性質：即無論過去的狀態(tài)和決策如何，對前面的決策所形成的狀態(tài)而言，余下的諸決策必須構成最優(yōu)子策略。簡而言之，一個最優(yōu)策略的任一子策略都是最優(yōu)子策略。2023/2/6動態(tài)規(guī)劃的數(shù)學描述1.階段2.狀態(tài)3.決策4.狀態(tài)轉移律5.策略與子策略6.階段指標函數(shù)7.過程指標函數(shù)8.最優(yōu)指標函數(shù)2023/2/6階段在多階段決策過程中，決策點將整個過程劃分為若干部分，其中的每一部分即為一個階段。描述階段的變量稱為階段變量，常用k來表示。階段的劃分一般是根據(jù)時間和空間的自然特征來進行的，一個N

個階段的多階段決策問題其階段變量k=1，2，，N。2023/2/6決策決策是指決策者在若干可行方案中所作出的選擇。決策變量dk(Sk)表示第k階段、狀態(tài)為Sk時的決策。決策變量的取值會受到一定的限制，用Dk(Sk)表示第k階段、狀態(tài)為Sk時決策變量允許的取值范圍，稱為允許決策集合，因而有dk(Sk)

Dk(Sk)。2023/2/6狀態(tài)轉移律

狀態(tài)轉移律是確定由一個狀態(tài)到另一個狀態(tài)演變過程的關系式，這種演變的對應關系記為Sk+1=Tk(Sk,dk)。2023/2/6策略與子策略各階段決策所組成的決策序列稱為一個策略，具有N個階段的動態(tài)規(guī)劃問題的策略可表示為{d1(S1),d2(S2),…,dN(SN)}。從某一階段開始到過程終點為止的決策序列，稱為子過程策略或子策略。從第k個階段起的子策略可表示為{dk(Sk),dk+1(Sk+1),…,dN(SN)}。2023/2/6過程指標函數(shù)過程指標函數(shù)是用來衡量所實現(xiàn)過程優(yōu)劣的數(shù)量指標，它是定義在全過程（策略）或后續(xù)子過程（子策略）上的數(shù)量函數(shù)。過程指標函數(shù)常用Rk,,N

來表示，構成動態(tài)規(guī)劃的過程指標函數(shù)應具有可分性并滿足遞推關系，即Rk,,N

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

=rk+Rk+1,N

2.過程指標函數(shù)是階段指標函數(shù)的積，此時Rk,,N

=rkRk+1,N2023/2/6最優(yōu)指標函數(shù)2023/2/6

ABCDB112

9C1156

A4B220D

81610C216

B39例12023/2/6例1的求解K=3時：f3(C1)=min{15}=15,C1Df3(C2)=min{16}=16,C2DK=2時：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時：f1(A)=min{6+25,4+32,8+25}=31,AB1C2D2023/2/6確定性動態(tài)規(guī)劃問題給出Sk和dk的取值后，狀態(tài)Sk+1的取值唯一確定的動態(tài)規(guī)劃問題稱為確定性動態(tài)規(guī)劃問題。確定性動態(tài)規(guī)劃有廣泛的應用領域，這些領域可概括為：1.最短路問題：見117頁例7-12.資源分配問題3.存貯控制問題4.非線性規(guī)劃問題2023/2/6資源分配問題[例7-2]:第119頁某公司擬將500萬元的資本投入所屬的甲、乙、丙三個工廠，各工廠獲得投資后年利潤將有相應的增長，一定投資下的利潤增長額如下表所示，試確定最優(yōu)的投資分配方案，使公司年利潤增長額最大。投資(百萬元)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

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

2.x1=2，x2=2，x3=12023/2/6例7-3的求解構造動態(tài)規(guī)劃模型：設階段序數(shù)k表示年度，狀態(tài)變量Sk為第k年初擁有的完好機器數(shù)量，同時也是第k-1年度末時的完好機器數(shù)量。決策變量uk為第k年度中分配到高負荷下生產(chǎn)的機器數(shù)量，于是Sk-uk為第k年度中分配到低負荷下生產(chǎn)的機器數(shù)量。狀態(tài)轉移方程：Sk+1=auk+b(Sk-uk)=0.7uk+0.9(Sk-uk)允許決策集合：Dk(Sk)={0ukSk}設vk(Sk,uk)為第k年度的產(chǎn)量，則vk=8uk+5(Sk-uk)過程指標函數(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)是關于u5的單調增函數(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)是關于u4的單調增函數(shù)*u4=S4f4(S4)=13.6S42023/2/6例7-4的求解假設需求是按一定速度均勻發(fā)生的，訂貨不需要時間，但訂貨只能在月初辦理，每次訂貨的費用為10美元。月存貯費用是按每月底鞋的存量計算的，每雙0.2美元。由于訂貨不需要時間，所以銷售季節(jié)以外的月份無存貨。試確定最佳的進貨方案，以使總的銷售費用最小。階段：k=1,2,3,4,5,6狀態(tài)：Sk代表第k月初鞋的存量決策變量：dk代表第k月鞋的采購量狀態(tài)轉移律：Sk+1=Sk+dk-Dk，S1=S7=0費用函數(shù)：rk(Sk,dk)=(dk)+0.2(Sk+dk-Dk)，其中(dk)為訂貨費用，訂貨費用由兩部分構成，一部分是固定的采購費10美元，另一部分是貨款，dk=0時(dk)=0。最優(yōu)指標函數(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)轉移律，按上述計算的逆順序推算，可得如下最優(yōu)策略：十月份40雙十一月份50雙十二月份0雙一月份40雙二月份50雙三月份0雙最小的銷售費用為606美元。2023/2/6非線性規(guī)劃問題

2023/2/6例7-5的求解階段：按問題的變量個數(shù)劃分階段k=1，2，3狀態(tài)：S1=c，S2，S3決策變量：x1，x2，x3狀態(tài)轉移律：Sk+1=Sk-xk允許決策集合：0xkSk

最優(yōu)指標函數(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隨機性動態(tài)規(guī)劃問題給出Sk和dk的取值后，狀態(tài)Sk+1的取值不是唯一確定的，而是具有某種概率分布的隨機變量(此概率分布由狀態(tài)和決策唯一確定)，這類動態(tài)規(guī)劃問題稱為隨機性動態(tài)規(guī)劃問題。下面就通過三個例題來介紹一下隨機性動態(tài)規(guī)劃問題的應用。1.例12.例23.例32023/2/6例1

某公司承擔一種新產(chǎn)品試制任務，合同要求三個月內(nèi)交出一臺合格的樣品，否則將負擔1500元的經(jīng)濟賠償。據(jù)估計，試制時投產(chǎn)一臺得到合格樣品的概率是1/3，投產(chǎn)一批的準備結束費用為250元，每臺試制費用為100元。若投產(chǎn)一批全都不合格，可再投產(chǎn)一批，但每投一批的試制周期為一個月。要求確定每批投入的批量，使總的試制費用（包括可能的賠償損失）期望值最小。階段：k=1，2，3狀態(tài)：Sk=1表示第k個月初尚未得到合格樣品

Sk=0表示第k個月初已經(jīng)得到了合格樣品決策變量：dk表示第k個月初投產(chǎn)試制的臺數(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)采購一批原料，估計在未來五周內(nèi)價格會有一定的波動，各種價格及其出現(xiàn)的概率如下表所示，試確定在哪一周以什么價格購入原料，才能使采購價格的期望值最小。價格：500600700概率：0.30.30.42023/2/6例2的求解階段：k=1,2,3,4,5表示各周狀態(tài)：yk代表第k周的實際價格決策變量：xk=1代表第k周決定采購

xk=0代表第k周決定等待ykE：第k周決定等待，對應最優(yōu)子策略采購價格的期望值最優(yōu)指標函數(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時xk=1，代表以價格yk采購；fk(yk)=ykE時xk=0，代表等待。2023/2/6例2的求解k=5：

對于最后一周，如果所需的原料尚未買入，則無論市場價格如何都必須采購，因此有：

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(采購)

=600，y4=600(采購)=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(采購)

=574，y4=600(等待)=574，y4=700(等待)k=2：y2E=0.3f3(500)+0.3f3(600)+0.4f3(700)=55