第五章動態(tài)規(guī)劃多階段決策過程動態(tài)規(guī)劃的基本概念和基本原理動態(tài)規(guī)劃方法的基本步驟動態(tài)規(guī)劃方法應(yīng)用舉例本章內(nèi)容重點(diǎn)1二．動態(tài)規(guī)劃方法的基本步驟為進(jìn)一步說明動態(tài)規(guī)劃模型建立的基本方法及其求解過程,下面通過實(shí)際例子用上述方法具體給出求解動態(tài)規(guī)劃方法的基本步驟：

3.動態(tài)規(guī)劃方法的基本步驟2例:有某種機(jī)床,可以在高低兩種不同的負(fù)荷下進(jìn)行生產(chǎn),在高負(fù)荷下生產(chǎn)時,產(chǎn)品的年產(chǎn)量為g,與年初投入生產(chǎn)的機(jī)床數(shù)量u1的關(guān)系為g=g(u1)=8u1,這時,年終機(jī)床完好臺數(shù)將為au1,(a為機(jī)床完好率，0<a<1,設(shè)a=0.7).在低負(fù)荷下生產(chǎn)時,產(chǎn)品的年產(chǎn)量為h,和投入生產(chǎn)的機(jī)床數(shù)量u2的關(guān)系為h=h(u2)=5u2,相應(yīng)的機(jī)床完好率為b(0<b<1,設(shè)b=0.9),一般情況下a<b。1.假設(shè)某廠開始有x=1000臺完好的機(jī)床，現(xiàn)要制定一個五年生產(chǎn)計劃，問每年開始時如何重新分配完好的機(jī)床在兩種不同的負(fù)荷下生產(chǎn)的數(shù)量，以使在5年內(nèi)產(chǎn)品的總產(chǎn)量為最高2.若規(guī)定在第五個年度結(jié)束時，完好的機(jī)床數(shù)量為500臺問應(yīng)該如何安排五年的生產(chǎn)，使之在滿足這一終端要求的情況下產(chǎn)量最高？返回31.假設(shè)某廠開始有x=1000臺完好的機(jī)床，現(xiàn)要制定一個五年生產(chǎn)計劃，問每年開始時如何重新分配完好的機(jī)床在兩種不同的負(fù)荷下生產(chǎn)的數(shù)量，以使在5年內(nèi)產(chǎn)品的總產(chǎn)量為最高。

3.動態(tài)規(guī)劃方法的基本步驟階段k：狀態(tài)變量xk：決策變量dk：決策允許集合：狀態(tài)轉(zhuǎn)移方程：階段指標(biāo)：遞推方程：終端條件：返回4解：首先構(gòu)造這個問題的動態(tài)規(guī)劃模型。1．變量設(shè)置(1)設(shè)階段變量k表示年度，因此，階段總數(shù)n=5。(2)狀態(tài)變量sk表示第k年度初擁有的完好機(jī)床臺數(shù)，同時也是第k-1年度末時的完好機(jī)床數(shù)量。5(3)決策變量uk，表示第k年度中分配于高負(fù)荷下生產(chǎn)的機(jī)床臺數(shù)。于是sk-uk便為該年度中分配于低負(fù)荷下生產(chǎn)的機(jī)床臺數(shù)．這里sk與uk均取連續(xù)變量，當(dāng)它們有非整數(shù)數(shù)值時．可以這樣理解：如sk＝0.6，就表示一臺機(jī)器在k年度中正常工作時間只占6/10；uk=0.4時，就表示一臺機(jī)床在k年度只有4/10的時間于高負(fù)荷下工作．2．狀態(tài)轉(zhuǎn)移方程為

k=1，2，…,53.動態(tài)規(guī)劃方法的基本步驟63．允許決策集合,在第k段為4．目標(biāo)函數(shù)。設(shè)gk(sk,uk)為第k年度的產(chǎn)量，則gk(sk,uk)=8uk+5(sk-uk),k＝1,2,．．．,5因此，目標(biāo)函數(shù)為

5．條件最優(yōu)目標(biāo)函數(shù)遞推方程。令fk(sk)表示由第k年的狀態(tài)sk出發(fā)，采取最優(yōu)分配方案到第5年度結(jié)束這段時間的產(chǎn)品產(chǎn)量，根據(jù)最優(yōu)化原理有以下遞推關(guān)系：

k=1,2,3,4,53.動態(tài)規(guī)劃方法的基本步驟76.邊界條件為下面采用逆序遞推計算法,從第5年度開始遞推計算。

k=5時有顯然，當(dāng)u5*=s5時，f5(s5)有最大值，相應(yīng)的有f5(s5)=8s5

k=4時有

3.動態(tài)規(guī)劃方法的基本步驟,=

=

因此，當(dāng)u4*=s4時，有最大值f4(s4)=13.6s48

k=3時有

可見，當(dāng)u3*=s3時，f3(s3)有最大值f3(s3)=17.55s3.

k=2時有

=+=此時，當(dāng)取u2*=0時有最大值，即f2(s2)=20.8s2，其中s2=0.7u1+0.9(s1-u1)3.動態(tài)規(guī)劃方法的基本步驟=9

k=1時有+

=當(dāng)取u1*=0時,f1(s1)有最大值，即f1(s1)=23.7s1,因?yàn)閟1=1000,故f1(s1)=23700個產(chǎn)品．按照上述計算順序?qū)ほ櫟玫较率鲇嬎憬Y(jié)果：3.動態(tài)規(guī)劃方法的基本步驟10上面所討論的最優(yōu)決策過程是所謂始端狀態(tài)s1固定，終端狀態(tài)s6自由．如果終端也附加上一定的約束條件，那么計算結(jié)果將會與之有所差別．例如，若規(guī)定在第五個年度結(jié)束時，完好的機(jī)床數(shù)量為500臺(上面只有278臺)，問應(yīng)該如何安排五年的生產(chǎn)，使之在滿足這一終端要求的情況下產(chǎn)量最高？3.動態(tài)規(guī)劃方法的基本步驟11解：由狀態(tài)轉(zhuǎn)移方程有得

顯而易見，由于固定了終端的狀態(tài)s6，第五年的決策變量U5的允許決策集合U5(s5)也有了約束，上式說明U5(s5)已退化為一個點(diǎn)，即第五年投入高負(fù)荷下生產(chǎn)的機(jī)床數(shù)只能由式U5=4.5s5-2500作出一種決策，故3.動態(tài)規(guī)劃方法的基本步驟＝50012當(dāng)k=5時有

當(dāng)k=4時有

顯然，只有取u4*=0，f4(s4)有最大值，即f4(s4)=21.7s4-7500。同理類推3.動態(tài)規(guī)劃方法的基本步驟====13k=3時有可知,當(dāng)u3*=0時,f3(s3)有最大值f4(s4)=24.5s3-7500.k=2時有此時,當(dāng)u2*=0時有最大值,即f2(s2)=27.1s2-75003.動態(tài)規(guī)劃方法的基本步驟

=

=

=

=

+14

k=1時有

只有取u1*=0時,f1(s1)有最大值，即

f1(s1)=29.4s1-7500。由此可見，為了使下一個五年計劃開始的一年有完好的機(jī)床500臺，其最優(yōu)策略應(yīng)該為：在前4年中，都應(yīng)該把全部機(jī)床投人低負(fù)荷下生產(chǎn)，在第5年，只能把部分完好機(jī)投入高負(fù)荷下生產(chǎn)。根據(jù)最優(yōu)策賂，從始端向終端遞推計算出各年的狀態(tài)，即算出每年年初的完好機(jī)床臺數(shù)，因?yàn)閟1＝1000臺，于是有3.動態(tài)規(guī)劃方法的基本步驟==15因此，u5*=4.5s5-2500=452(臺)，這就是說第5年里還有204臺投入低負(fù)荷下生產(chǎn)，否則不能保證s6=0.7u5+0.9(s5-u5)=500(臺)。在上述最優(yōu)決策下，5年里所得最高產(chǎn)量為：

f1(s1)＝29.4s1-7500=29400-7500＝21900(個)?？梢?，附加了終端約束條件以后，其最高產(chǎn)量f1(s1)比終端自由時要低一些。3.動態(tài)規(guī)劃方法的基本步驟（臺）（臺）（臺）（臺）（臺）16

線性規(guī)劃問題：

某工廠現(xiàn)有資金30萬元，可用于生產(chǎn)兩種產(chǎn)品。已知生產(chǎn)1噸第一種產(chǎn)品需要資金3萬元，可獲利1.5萬元；生產(chǎn)1噸第二種產(chǎn)品需要資金5萬元，可獲利2萬元。問應(yīng)生產(chǎn)這兩種產(chǎn)品各多少噸，才能使獲得的利潤最大？3.動態(tài)規(guī)劃方法的基本步驟17

動態(tài)規(guī)劃模型建立后，對基本方程分段求解，不像線性規(guī)劃或非線性規(guī)劃那樣有固定的解法，必須根據(jù)具體問題的特點(diǎn)，結(jié)合數(shù)學(xué)技巧靈活求解，如動態(tài)規(guī)劃模型中的狀態(tài)變量與決策變量若被限定只能取離散值，則可采用離散變量的分段窮舉法。當(dāng)動態(tài)規(guī)劃模型中狀態(tài)變量與決策變量為連續(xù)變量，就要根據(jù)方程的具體情況靈活選取連續(xù)變量的求解方法。如經(jīng)典解析方法、線性規(guī)劃方法、非線性規(guī)劃法或其它數(shù)值計算方法等。還有連續(xù)變量的離散化解法和高維問題的降維法及疏密格子點(diǎn)法等等。3.動態(tài)規(guī)劃方法的基本步驟18學(xué)習(xí)方法建議：第一步先看問題，充分理解問題的條件、情況及求解目標(biāo)。第二步結(jié)合前面講到的理論和解題過程，考慮如何著手進(jìn)行求解該問題的工作。分析針對該動態(tài)規(guī)劃問題的“四大要素、一個方程”——這一步在開始時會感到困難，但是一定要下決心去思考，在思考過程中深入理解前文講到的概念和理論。4.動態(tài)規(guī)劃方法應(yīng)用舉例19第三步動手把求解思路整理出來，或者說，把該問題作為習(xí)題獨(dú)立的來做。第四步

把自己的求解放到一邊，看書中的求解方法，要充分理解教材中的論述。第五步對照自己的求解，分析成敗。4.動態(tài)規(guī)劃方法應(yīng)用舉例201.動態(tài)規(guī)劃的四大要素①狀態(tài)變量及其可能集合xk

Xk②決策變量及其允許集合ukUk

③狀態(tài)轉(zhuǎn)移方程

xk+1=Tk

(xk,uk

)④階段效應(yīng)rk

(xk,uk

)

4.動態(tài)規(guī)劃方法應(yīng)用舉例212.動態(tài)規(guī)劃基本方程

fn+1(xn+1)=0(邊界條件)

fk(xk)=opt

u{rk

(xk,uk

)+fk+1(xk+1)}

k=n,…,14.動態(tài)規(guī)劃方法應(yīng)用舉例22求最短路徑

23求最短路徑

例5.524

將問題分成五個階段，第k階段到達(dá)的具體地點(diǎn)用狀態(tài)變量xk表示，例如：x2=B3表示第二階段到達(dá)位置B3，等等。這里狀態(tài)變量取字符值而不是數(shù)值。

將決策定義為到達(dá)下一站所選擇的路徑，例如目前的狀態(tài)是x2=B3，這時決策允許集合包含三個決策，它們是D2(x2)=D2(B3)={B3C1,B3C2,B3C3}求最短路徑

25最優(yōu)指標(biāo)函數(shù)fk(xk)表示從目前狀態(tài)到E的最短路徑。終端條件為

f5(x5)=f5(E)=0

其含義是從E到E的最短路徑為0。

第四階段的遞推方程為

:

求最短路徑

26其中*表示最優(yōu)值，在上表中，由于決策允許集合D4(x4)中的決策是唯一的，因此這個值就是最優(yōu)值。

由此得到f4(x4)的表達(dá)式。由于這是一個離散的函數(shù)，取值用列表表示：求最短路徑

27第三階段的遞推方程為：

求最短路徑

28由此得到f3(x3)的表達(dá)式：

求最短路徑

29求最短路徑

30由此得到f2(x2)的表達(dá)式：求最短路徑

31第一階段的遞推方程為：求最短路徑

32由此得到f1(x1)的表達(dá)式求最短路徑

33資源分配問題34

例5.6:有資金4萬元，投資A、B、C三個項(xiàng)目，每個項(xiàng)目的投資效益與投入該項(xiàng)目的資金有關(guān)。三個項(xiàng)目A、B、C的投資效益（萬噸）和投入資金（萬元）關(guān)系見下表：求對三個項(xiàng)目的最優(yōu)投資分配，使總投資效益最大。

資源分配問題35階段k：每投資一個項(xiàng)目作為一個階段；狀態(tài)變量xk：投資第k個項(xiàng)目前的資金數(shù)；決策變量dk：第k個項(xiàng)目的投資；決策允許集合：0≤dk≤xk狀態(tài)轉(zhuǎn)移方程：xk+1=xk-dk階段指標(biāo)：vk(xk

,dk)見表中所示；遞推方程：fk(xk)=max{vk(xk

,dk)+fk+1(xk+1)}終端條件：f4(x4)=0資源分配問題36k=4，f4(x4)=0

k=3，0≤d3≤x3，x4=x3-d3

資源分配問題37k=2，0≤d2≤x2，x3=x2-d2資源分配問題38k=1，0≤d1≤x1，x2=x1-d1資源分配問題39背包問題40背包問題41則Max

z= c1x1+c2x2+…+cnxn

s.t.w1x1+w2x2+…+wnxn≤W

x1,x2,…,xn為正整數(shù)

階段k：第k次裝載第k種物品（k=1,2,…,n）狀態(tài)變量xk：第k次裝載時背包還可以裝載的重量；決策變量dk：第k次裝載第k種物品的件數(shù)；背包問題424.決策允許集合： Dk(xk)={dk|0

dkxk/wk，dk為整數(shù)}；5.狀態(tài)轉(zhuǎn)移方程：xk+1=xk-wkdk6.階段指標(biāo)：vk=ckdk7.遞推方程fk(xk)=max{ckdk+fk+1(xk+1)}=max{ckdk+fk+1(xk-wkdk)}8.終端條件：fn+1(xn+1)=0背包問題43例5.7:對于一個具體問題c1=65，c2=80，c3=30；w1=2，w2=3，w3=1；以及 W=5

用動態(tài)規(guī)劃求解f4(x4)=0

對于k=3背包問題4445464748生產(chǎn)庫存問題49

例5.9：一個工廠生產(chǎn)某種產(chǎn)品,1-

7月份生產(chǎn)成本和產(chǎn)品需求量的變化情

況如下表：

生產(chǎn)庫存問題50階段k：月份，k=1,2,…,7,8；狀態(tài)變量xk：第k個月初（發(fā)貨以前）的庫存量；決策變量dk：第k個月的生產(chǎn)量；狀態(tài)轉(zhuǎn)移方程：xk+1=xk-rk+dk；決策允許集合：Dk(xk)={dk

|dk0,rk+1xk+1H} ={dk

|dk0,rk+1xk-rk+dkH}；階段指標(biāo)：vk(xk,dk)=ckdk；終端條件：f8(x8)=0, x8=0；生產(chǎn)庫存問題51遞推方程：fk(xk)=min{vk(xk,dk)+fk+1(xk+1)}

dkDk(xk)

=min{ckdk+fk+1(xk-rk+dk)}

dkDk(xk)

對于k=7因?yàn)閤8=0有d7=0遞推方程為f7(x7)=min{c7d7+f8(x8)}=0d7=0生產(chǎn)庫存問題52對于k=6

因?yàn)?/p>

d7=0，所以 x7=r7=4

而

x6-r6+d6=x7=4

因此有

d6=x7+r6-x6=4+7-x6=11-x6

也是唯一的決策。因此遞推方程為：

f6(x6)=min{c6d6+f7(x7)}

d6=11-x6

=10d6=10(11-x6)=110-10x6

生產(chǎn)庫存問題53對于k=5f5(x5)=min{c5d5+f6(x6)}d5D5(x5) =min{20d5+110-10x6}d5D5(x5) =min{20d5+110-10(x5-r5+d5)}

d5D5(x5) =min{20d5+110-10(x5-2+d5)}

d5D5(x5) =min{10d5-10x5+130}

d5D5(x5)D5(x5)={d5|d50,r6x5-r5+d5H}={d5|d50,r6+r5-x5d5H+r5-x5} ={d5|d50,9-x5d511-x5}生產(chǎn)庫存問題54因?yàn)閤5H=9，因此9-x50，決策允許集合可以簡化為

D5(x5)={d5|9-x5d511-x5}

遞推方程成為

f5(x5)=min{10d5-10x5+130}

9-x5d511-x5

=10(9-x5)-10x5+130

=220-20x5

d5*=9-x5

生產(chǎn)庫存問題55對于k=4

f4(x4)=min{c4d4+f5(x5)}

d4D4(x4)

=min{17d4+220-20x5}

d4D4(x4)

=min{17d4+220-20(x4-r4+d4)}

d4D4(x4)

=min{17d4+220-20(x4-3+d4)}

d4D4(x4)

=min{-3d4-20x4+280}

d4D4(x4)

生產(chǎn)庫存問題56D4(x4)={d4|d40,r5x4-r4+d4H}

={d4|d40,r5+r4-x4d4H+r4-x4}

={d4|d40,5-x4d412-x4}

={d4|max[0,5-x4]d412-x4}

由于在f4(x4)的表達(dá)式中d4的系數(shù)是-3，

因此d4在決策允許集合中應(yīng)取集合中的最大值，即d4=12-x4由此f4(x4)=-3(12-x4)-20x4+280 =-17x4+244

生產(chǎn)庫存問題57對于k=3

f3(x3)=min{c3d3+f4(x4)} d3D3(x3)

=min{13d3+244-17x4}d3D3(x3)

=min{13d3+244-17(x3-r3+d3)}

d3D3(x3)

=min{-4d3-17x3+329}d3D3(x3)

D3(x3)={d3|d30,r4x3-r3+d3H}

={d3|d30,r4+r3-x3d3H+r3-x3}

={d3|d30,8-x3d314-x3}

={d3|max[0,8-x3]d314-x3}

由此

f3(x3)=-4(14-x3)-17x3+329

=-13x3+273, d3*=14-x3

生產(chǎn)庫存問題58對于k=2

f2(x2)=min{c2d2+f3(x3)}d2D2(x2)

=min{18d2+273-13x3}d2D2(x2)

=min{18d2+273-13(x2-r2+d2)}

d2D2(x2)

=min{18d2+273-13(x2-8+d2)}

d2D2(x2)

=min{5d2-13x2+377}d2D2(x2)

D2(x2)={d2|d20,r3x2-r2+d2H}

={d2|d20,r3+r2-x2d2H+r2-x2}

={d2|d20,13-x2d217-x2