運(yùn)籌(第八章動(dòng)態(tài)規(guī)劃)

1、2022-4-211運(yùn)籌學(xué)運(yùn)籌學(xué)OPERATIONS RESEARCH2022-4-212第八章第八章 動(dòng)態(tài)規(guī)劃動(dòng)態(tài)規(guī)劃n 多階段決策最優(yōu)化問(wèn)題舉例多階段決策最優(yōu)化問(wèn)題舉例n基本概念、基本方程與最優(yōu)化原理基本概念、基本方程與最優(yōu)化原理n離散確定性動(dòng)態(tài)規(guī)劃求解離散確定性動(dòng)態(tài)規(guī)劃求解n離散隨機(jī)性動(dòng)態(tài)規(guī)劃求解離散隨機(jī)性動(dòng)態(tài)規(guī)劃求解n一般數(shù)學(xué)規(guī)劃模型的動(dòng)態(tài)規(guī)劃解法一般數(shù)學(xué)規(guī)劃模型的動(dòng)態(tài)規(guī)劃解法2022-4-2131 1多階段決策過(guò)程最優(yōu)化問(wèn)題舉例多階段決策過(guò)程最優(yōu)化問(wèn)題舉例例例1 1 最短路徑問(wèn)題最短路徑問(wèn)題下圖表示從起點(diǎn)下圖表示從起點(diǎn)A A到終點(diǎn)到終點(diǎn)E E之間各點(diǎn)的距離。求之間各點(diǎn)的距離。求A A

2、到到E E的最短路徑。的最短路徑。BACBDBCDEC41231231232216472483867561106437512022-4-214用窮舉法的計(jì)算量用窮舉法的計(jì)算量: :如果從如果從A A到到E E的站點(diǎn)有的站點(diǎn)有k k個(gè)，除個(gè)，除A A、E E之外每站有之外每站有3 3個(gè)位個(gè)位置則總共有置則總共有3 3k-1k-12 2條路徑；條路徑；計(jì)算各路徑長(zhǎng)度總共要進(jìn)行計(jì)算各路徑長(zhǎng)度總共要進(jìn)行 (k+1) 3(k+1) 3k-1k-12 2次加法次加法以及以及3 3k-1k-12-12-1次比較。隨著次比較。隨著 k k 的值增加時(shí)，需要的值增加時(shí)，需要進(jìn)行的加法和比較的次數(shù)將迅速增加；進(jìn)行

3、的加法和比較的次數(shù)將迅速增加；例如例如 k=20k=20時(shí)，加法次數(shù)為時(shí)，加法次數(shù)為 4.25508339662274.255083396622710101515 次，比較次，比較 1.37260754729771.372607547297710101414 次。次。若用若用1 1億次億次/ /秒的計(jì)算機(jī)計(jì)算需要約秒的計(jì)算機(jī)計(jì)算需要約508508天。天。2022-4-215討論：討論：1 1、以上求從、以上求從A A到到E E的最短路徑問(wèn)題，可以轉(zhuǎn)化為四個(gè)的最短路徑問(wèn)題，可以轉(zhuǎn)化為四個(gè) 性質(zhì)完全相同，但規(guī)模較小的子問(wèn)題，即分別從性質(zhì)完全相同，但規(guī)模較小的子問(wèn)題，即分別從 D Di i 、C C

4、i i、B Bi i、A A到到E E的最短路徑問(wèn)題。的最短路徑問(wèn)題。 第四階段：第四階段：兩個(gè)始點(diǎn)兩個(gè)始點(diǎn)D D1 1和和D D2 2，終點(diǎn)只有一個(gè)；，終點(diǎn)只有一個(gè)； 表表-1-1分析得知：從分析得知：從D D1 1和和D D2 2到到E E的最短路徑唯一。的最短路徑唯一。 階段4本階段始點(diǎn)（狀態(tài)）本階段各終點(diǎn)（決策）到E的最短距離本階段最優(yōu)終點(diǎn)（最優(yōu)決策) E D1 D2 10 6 10 6 E E2022-4-216 第三階段第三階段：有三個(gè)始點(diǎn)有三個(gè)始點(diǎn)C C1 1，C C2 2，C C3 3，終點(diǎn)有，終點(diǎn)有D D1 1，D D2 2，對(duì)始點(diǎn)和終點(diǎn)進(jìn)行分析和討論分別求對(duì)始點(diǎn)和終點(diǎn)進(jìn)行分

5、析和討論分別求C C1 1，C C2 2，C C3 3到到D D1 1，D D2 2 的最短路徑問(wèn)題：的最短路徑問(wèn)題： 表-2 分析得知：如果經(jīng)過(guò)分析得知：如果經(jīng)過(guò)C C1 1，則最短路為則最短路為C C1 1-D-D2 2-E-E； 如果經(jīng)過(guò)如果經(jīng)過(guò)C C2 2，則最短路為則最短路為C C2 2-D-D2 2-E-E； 如果經(jīng)過(guò)如果經(jīng)過(guò)C C3 3，則最短路為，則最短路為C C3 3-D-D1 1-E-E。 階段3本階段始點(diǎn)（狀態(tài)）本階段各終點(diǎn)（決策）到E的最短距離本階段最優(yōu)終點(diǎn)（最優(yōu)決策) D1 D2 C1 C2 C3 8+10=18 7+10=17 1+10=11 6+6=12 5+6=

6、11 6+6=12 12 11 11 D2 D2 D12022-4-217第二階段第二階段：有有4 4個(gè)始點(diǎn)個(gè)始點(diǎn)B B1 1,B,B2 2,B,B3 3,B,B4 4，終點(diǎn)有，終點(diǎn)有C C1 1,C,C2 2,C,C3 3。對(duì)始點(diǎn)和終點(diǎn)進(jìn)行分析和討論分別求對(duì)始點(diǎn)和終點(diǎn)進(jìn)行分析和討論分別求B B1 1,B,B2 2,B,B3 3,B,B4 4到到C C1 1,C,C2 2,C,C3 3 的最短路徑問(wèn)題：的最短路徑問(wèn)題： 表-3分析得知：如果經(jīng)過(guò)分析得知：如果經(jīng)過(guò)B B1 1，則走，則走B B1 1-C-C2 2-D-D2 2-E-E； 如果經(jīng)過(guò)如果經(jīng)過(guò)B B2 2，則走，則走B B2 2-C-

7、C3 3-D-D1 1-E-E； 如果經(jīng)過(guò)如果經(jīng)過(guò)B B3 3，則走，則走B B3 3-C-C3 3-D-D1 1-E-E； 如果經(jīng)過(guò)如果經(jīng)過(guò)B B4 4，則走，則走B B4 4-C-C3 3-D-D1 1-E-E。 階段2本階段始點(diǎn)（狀態(tài)） 本階段各終點(diǎn)（決策）到E的最短距離本階段最優(yōu)終點(diǎn)（最優(yōu)決策) C1 C2 C3 B1 B2 B3 B4 2+12=14 4+12=16 4+12=16 7+12=19 1+11=12 7+11=18 8+11=19 5+11=16 6+11=17 2+11=13 3+11=14 1+11=12 12 13 14 12 C2 C3 C3 C32022-4-

8、218第一階段：第一階段：只有只有1 1個(gè)始點(diǎn)個(gè)始點(diǎn)A A，終點(diǎn)有，終點(diǎn)有B B1 1,B,B2 2,B,B3 3,B,B4 4 。對(duì)。對(duì)始點(diǎn)和終點(diǎn)進(jìn)行分析和討論分別求始點(diǎn)和終點(diǎn)進(jìn)行分析和討論分別求A A到到B B1 1,B,B2 2,B,B3 3,B,B4 4的的最短路徑問(wèn)題：最短路徑問(wèn)題： 表10-4最后，可以得到：最后，可以得到：從從A A到到E E的最短路徑為的最短路徑為A A B B4 4 C C3 3 D D1 1 E E 階段1本階段始點(diǎn)(狀態(tài)) 本階段各終點(diǎn)（決策）到E的最短距離本階段最優(yōu)終點(diǎn)(最優(yōu)決策) B1 B2 B3 B4 A4+12=16 3+13=163+14=172

9、+12=14 12 B42022-4-219 以上計(jì)算過(guò)程及結(jié)果，可用圖以上計(jì)算過(guò)程及結(jié)果，可用圖2 2表示，可以看到，以表示，可以看到，以上方法不僅得到了從上方法不僅得到了從A A到到D D的最短路徑，同時(shí)，也得的最短路徑，同時(shí)，也得到了從圖中任一點(diǎn)到到了從圖中任一點(diǎn)到E E的最短路徑。的最短路徑。 以上過(guò)程，僅用了以上過(guò)程，僅用了2222次加法，計(jì)算效率遠(yuǎn)高于窮舉次加法，計(jì)算效率遠(yuǎn)高于窮舉法。法。BACBDBCDEC412312312332164724838675161060106121111121314144B1275122022-4-2110例例2 2 資源分配問(wèn)題資源分配問(wèn)題設(shè)有某種

10、機(jī)器數(shù)臺(tái)，用于完成兩類(lèi)工作設(shè)有某種機(jī)器數(shù)臺(tái)，用于完成兩類(lèi)工作A A，B B。由于。由于機(jī)器使用后有一定的損壞率，所以每年初的機(jī)器數(shù)機(jī)器使用后有一定的損壞率，所以每年初的機(jī)器數(shù)量是變化的；量是變化的；A A、B B兩項(xiàng)工作產(chǎn)生的收益也不同。如兩項(xiàng)工作產(chǎn)生的收益也不同。如何合理的分配機(jī)器的使用，可使得三年的總收益最何合理的分配機(jī)器的使用，可使得三年的總收益最大大? ? 假設(shè)第假設(shè)第k k年年初完好機(jī)器數(shù)是年年初完好機(jī)器數(shù)是S SK K，用于用于A A生產(chǎn)的生產(chǎn)的機(jī)器數(shù)是機(jī)器數(shù)是X XK K，則用于則用于B B生產(chǎn)的機(jī)器數(shù)是（生產(chǎn)的機(jī)器數(shù)是（S SK K- X- XK K）；）； 用于用于A A工作

11、的設(shè)備的完好率是：工作的設(shè)備的完好率是：a%a%，用于，用于B B工作工作的設(shè)備的完好率是：的設(shè)備的完好率是：b%b%。則下一年初的完好機(jī)器數(shù)。則下一年初的完好機(jī)器數(shù)是是 S SK+1K+1= a% X= a% XK K+ b% + b% （S SK K- X- XK K）第第k k年的收益：年的收益： h(X h(XK K)+ g(S)+ g(SK K- X- XK K) )2022-4-2111例例3 3 背包問(wèn)題背包問(wèn)題設(shè)有設(shè)有n n種物品，每一種物品數(shù)量無(wú)限。第種物品，每一種物品數(shù)量無(wú)限。第i i種物品每種物品每件重量為件重量為w wi i公斤，每件價(jià)值公斤，每件價(jià)值c ci i元?，F(xiàn)

12、有一只可裝載重元。現(xiàn)有一只可裝載重量為量為W W公斤的背包，求各種物品應(yīng)各取多少件放入背公斤的背包，求各種物品應(yīng)各取多少件放入背包，使背包中物品的價(jià)值最高。包，使背包中物品的價(jià)值最高。 這個(gè)問(wèn)題可以用整數(shù)規(guī)劃模型來(lái)描述。設(shè)這個(gè)問(wèn)題可以用整數(shù)規(guī)劃模型來(lái)描述。設(shè)x xi i為第為第I I種物品裝入背包的件數(shù)（種物品裝入背包的件數(shù)（i i =1, 2, , =1, 2, , n n），背包），背包中物品的總價(jià)值為中物品的總價(jià)值為z z，則，則 Max z = cMax z = c1 1x x1 1+c+c2 2x x2 2+ +c+ +cn nx xn n s.t. w s.t. w1 1x x1

13、1+w+w2 2x x2 2+w+wn nx xn nW W x x1 1, x, x2 2, , x, , xn n 0 0 且為整數(shù)。且為整數(shù)。2022-4-2112動(dòng)態(tài)規(guī)劃動(dòng)態(tài)規(guī)劃是用來(lái)解決是用來(lái)解決多階段決策多階段決策過(guò)程最優(yōu)化的一種過(guò)程最優(yōu)化的一種方法。方法。多階段決策：多階段決策：是動(dòng)態(tài)決策問(wèn)題的一種特殊形式；是動(dòng)態(tài)決策問(wèn)題的一種特殊形式； 系統(tǒng)的動(dòng)態(tài)過(guò)程可以按照時(shí)間等進(jìn)程分為狀態(tài)系統(tǒng)的動(dòng)態(tài)過(guò)程可以按照時(shí)間等進(jìn)程分為狀態(tài)相互聯(lián)系相互聯(lián)系 而又相互區(qū)別的各個(gè)階段；而又相互區(qū)別的各個(gè)階段； 每個(gè)階段都要進(jìn)行決策每個(gè)階段都要進(jìn)行決策, ,目的是使整個(gè)過(guò)程的目的是使整個(gè)過(guò)程的決策達(dá)到最優(yōu)效

14、果決策達(dá)到最優(yōu)效果多階段決策求解思路：多階段決策求解思路：將多階段決策問(wèn)題（將多階段決策問(wèn)題（n n階段）分解成階段）分解成n n個(gè)具有遞推關(guān)個(gè)具有遞推關(guān)系的單階段決策問(wèn)題，進(jìn)行正推或逆推計(jì)算。系的單階段決策問(wèn)題，進(jìn)行正推或逆推計(jì)算。2022-4-21132.1 2.1 基本概念基本概念 1 1、階段、階段k k：表示決策順序的離散的量，階段可以按表示決策順序的離散的量，階段可以按時(shí)間或空間劃分。時(shí)間或空間劃分。( (順序編號(hào)法、逆序編號(hào)法）順序編號(hào)法、逆序編號(hào)法） 2 2、狀態(tài)、狀態(tài)s sk k：反應(yīng)前一階段決策的結(jié)果，又是本階段反應(yīng)前一階段決策的結(jié)果，又是本階段作決策的依據(jù)和出發(fā)點(diǎn)（能確定

15、地表示決策過(guò)程作決策的依據(jù)和出發(fā)點(diǎn)（能確定地表示決策過(guò)程當(dāng)前特征的量）。狀態(tài)可以是數(shù)量，也可以是字當(dāng)前特征的量）。狀態(tài)可以是數(shù)量，也可以是字符，數(shù)量狀態(tài)可以是連續(xù)的，也可以是離散的。符，數(shù)量狀態(tài)可以是連續(xù)的，也可以是離散的。 2 2基本概念、基本方程與最優(yōu)化原理基本概念、基本方程與最優(yōu)化原理2022-4-21143 3、決策、決策x xk k：從某一狀態(tài)向下一狀態(tài)過(guò)渡時(shí)所做的選從某一狀態(tài)向下一狀態(tài)過(guò)渡時(shí)所做的選擇。決策是所在狀態(tài)的函數(shù)，記為擇。決策是所在狀態(tài)的函數(shù)，記為x xk k(s(sk k) )。 決策允許集合決策允許集合D Dk k(s(sk k) )：在狀態(tài)在狀態(tài)s sk k下，允許

16、采取決策下，允許采取決策的全體的全體4 4、策略、策略Pk,n(sk)Pk,n(sk)：從第從第k k階段開(kāi)始到最后第階段開(kāi)始到最后第n n階段的階段的決策序列，稱(chēng)決策序列，稱(chēng)k k子策略。子策略。P1,n(s1)P1,n(s1)即為全過(guò)程策略。即為全過(guò)程策略。2022-4-21155 5、狀態(tài)轉(zhuǎn)移方程、狀態(tài)轉(zhuǎn)移方程: : S Sk+1k+1=T=Tk k(S(Sk k, X, Xk k) )：某一狀態(tài)以及：某一狀態(tài)以及該狀態(tài)下的決策，與下一狀態(tài)之間的函數(shù)關(guān)系。該狀態(tài)下的決策，與下一狀態(tài)之間的函數(shù)關(guān)系。6 6、階段指標(biāo)函數(shù)、階段指標(biāo)函數(shù)V Vk k(S(Sk k, X, Xk k) )：從狀態(tài)

17、從狀態(tài)S Sk k出發(fā)，選擇決出發(fā)，選擇決策策X Xk k所產(chǎn)生的第所產(chǎn)生的第k k階段指標(biāo)。階段指標(biāo)。 過(guò)程指標(biāo)函數(shù)過(guò)程指標(biāo)函數(shù)V Vk,nk,n(S(Sk k；X Xk k, X, Xk+1k+1, X, Xn n) )：從狀態(tài)從狀態(tài)S Sk k出發(fā)，選擇決策出發(fā)，選擇決策X Xk k, X, Xk+1k+1, , Xn, , Xn所產(chǎn)生的過(guò)程指所產(chǎn)生的過(guò)程指標(biāo)。標(biāo)。2022-4-2116動(dòng)態(tài)規(guī)劃要求過(guò)程指標(biāo)具有可分離性動(dòng)態(tài)規(guī)劃要求過(guò)程指標(biāo)具有可分離性，即即 V Vk,nk,n(s(sk k, x, xk k, x, xk+1k+1, , x, , xn n) = V) = Vk k(s(

18、sk k, x, xk k)+V)+Vk+1k+1(s(sk+1k+1, x, xk+1k+1, , x, , xn n) )稱(chēng)指標(biāo)具有稱(chēng)指標(biāo)具有可加性可加性，或或 V Vk,nk,n(s(sk k, x, xk k, x, xk+1k+1, , x, , xn n) = v) = vk k(s(sk k, x, xk k) )V Vk+1k+1(s(sk+1k+1, x, xk+1k+1, , x, , xn n) )稱(chēng)指標(biāo)具有稱(chēng)指標(biāo)具有可乘性可乘性。2.2 2.2 基本方程基本方程最優(yōu)指標(biāo)函數(shù)最優(yōu)指標(biāo)函數(shù)f fk k(s(sk k) )：從狀態(tài)從狀態(tài)s sk k出發(fā)，對(duì)所有的策略出發(fā)，對(duì)所

19、有的策略P Pk,nk,n，過(guò)程指標(biāo)，過(guò)程指標(biāo)V Vk,nk,n的最優(yōu)值，即的最優(yōu)值，即 ),()(,)(nkknksDxkkPsVsfoptkkk2022-4-2117對(duì)于可加性指標(biāo)函數(shù)，上式可以寫(xiě)為對(duì)于可加性指標(biāo)函數(shù)，上式可以寫(xiě)為 上式中上式中“opt”opt”表示表示“max”max”或或“min”min”。對(duì)于可乘性指標(biāo)函數(shù)，上式可以寫(xiě)為對(duì)于可乘性指標(biāo)函數(shù)，上式可以寫(xiě)為 以上式子稱(chēng)為動(dòng)態(tài)規(guī)劃最優(yōu)指標(biāo)的遞推方程，是動(dòng)以上式子稱(chēng)為動(dòng)態(tài)規(guī)劃最優(yōu)指標(biāo)的遞推方程，是動(dòng)態(tài)規(guī)劃的態(tài)規(guī)劃的基本方程基本方程。終端條件終端條件：為了使以上的遞推方程有遞推的起點(diǎn)，：為了使以上的遞推方程有遞推的起點(diǎn)，必須要設(shè)

20、定最優(yōu)指標(biāo)的終端條件，一般最后一個(gè)狀必須要設(shè)定最優(yōu)指標(biāo)的終端條件，一般最后一個(gè)狀態(tài)態(tài)n+1n+1下最優(yōu)指標(biāo)下最優(yōu)指標(biāo)f fn+1n+1(s(sn+1n+1) = 0) = 0。n, 2 , 1k)s (f)x,s (v)s (f1k1kkkk)s (Dxkkoptkkkn, 2 , 1k)s (f)x,s (v)s (f1k1kkkk)s (Dxkkoptkkk2022-4-21182.3 2.3 最優(yōu)化原理最優(yōu)化原理 作為整個(gè)過(guò)程的最優(yōu)策略具有如下性質(zhì)：作為整個(gè)過(guò)程的最優(yōu)策略具有如下性質(zhì)： 不管在此最優(yōu)策略上的某個(gè)狀態(tài)以前的狀不管在此最優(yōu)策略上的某個(gè)狀態(tài)以前的狀態(tài)和決策如何，對(duì)該狀態(tài)來(lái)說(shuō)，以

21、后的所有決態(tài)和決策如何，對(duì)該狀態(tài)來(lái)說(shuō)，以后的所有決策必定構(gòu)成最優(yōu)子策略。就是說(shuō)策必定構(gòu)成最優(yōu)子策略。就是說(shuō)，最優(yōu)策略的最優(yōu)策略的任意子策略都是最優(yōu)的。任意子策略都是最優(yōu)的。2022-4-2119例例1 某警衛(wèi)部門(mén)共有某警衛(wèi)部門(mén)共有9支巡邏隊(duì)，負(fù)責(zé)三個(gè)要害部位支巡邏隊(duì)，負(fù)責(zé)三個(gè)要害部位A、B、C的警衛(wèi)巡邏。每個(gè)部位分別可派出的警衛(wèi)巡邏。每個(gè)部位分別可派出24支巡邏隊(duì)，并且支巡邏隊(duì)，并且由于派出的隊(duì)伍數(shù)量不同，各部位預(yù)期的損失有差別，由于派出的隊(duì)伍數(shù)量不同，各部位預(yù)期的損失有差別，詳見(jiàn)下表。各部位應(yīng)各分派多少支巡邏隊(duì)可是預(yù)期的總詳見(jiàn)下表。各部位應(yīng)各分派多少支巡邏隊(duì)可是預(yù)期的總損失最小。請(qǐng)用動(dòng)態(tài)規(guī)劃

22、方法求解。損失最小。請(qǐng)用動(dòng)態(tài)規(guī)劃方法求解。3 3離散確定性動(dòng)態(tài)規(guī)劃模型求解離散確定性動(dòng)態(tài)規(guī)劃模型求解部位巡邏隊(duì)數(shù) 預(yù)期損失ABC2183824314352241031212022-4-2120解：解：設(shè)將向三個(gè)部位設(shè)將向三個(gè)部位A A，B B，C C派巡邏隊(duì)作為三個(gè)階段，派巡邏隊(duì)作為三個(gè)階段，K=1K=1， 2 2，3 3。 決策變量決策變量 表示向第表示向第K K個(gè)部位派遣的巡邏隊(duì)數(shù)。個(gè)部位派遣的巡邏隊(duì)數(shù)。 狀態(tài)變量狀態(tài)變量 表示第表示第K K個(gè)階段時(shí)可供派遣的巡邏隊(duì)數(shù)量。個(gè)階段時(shí)可供派遣的巡邏隊(duì)數(shù)量。 狀態(tài)轉(zhuǎn)移方程：狀態(tài)轉(zhuǎn)移方程： 階段指標(biāo)函數(shù)：階段指標(biāo)函數(shù)： 派遣派遣 支巡邏隊(duì)時(shí)第支巡邏

23、隊(duì)時(shí)第K K階段產(chǎn)階段產(chǎn)生的預(yù)期損失；生的預(yù)期損失； 過(guò)程指標(biāo)函數(shù)：過(guò)程指標(biāo)函數(shù)： 第第K K階段到第階段到第3 3階段的預(yù)期損失。階段的預(yù)期損失。 最優(yōu)指標(biāo)函數(shù)：最優(yōu)指標(biāo)函數(shù)： kxkskkkxss1)(kkxpkx3 , 13 ,)(kkkkVxpV)()(min)(11)(kkKKSDxkksfXPsfKk2022-4-2121逆序解法：逆序解法：邊界條件邊界條件 當(dāng)當(dāng)K=3K=3時(shí)，給時(shí)，給C C派巡邏隊(duì)，派巡邏隊(duì)， ， 0)(44sf5 , 4 , 3 , 2)(3sD4 , 3 , 23x 2342 24 -2423 24 22 -2234 24 22 212145 24 22 2

24、12143x3s)(33sf3*x)()(min)(443333sfxpsf)x,s (v3332022-4-2122當(dāng)當(dāng)K=2K=2時(shí)，給時(shí)，給B B派巡邏隊(duì)，派巡邏隊(duì)， 23 4538+22 35+24 -593638+21 35+22 31+24554738+21 35+21 31+22534)()(min)(2232222xsfxpsf7 , 6 , 5)(2sD4 , 3 , 22x2x2s)(22sf2*x)()(22322xsfxp2022-4-2123當(dāng)當(dāng)K=1K=1時(shí)，給時(shí)，給A A派巡邏隊(duì)，派巡邏隊(duì)， )()(min)(1121111xsfxpsf 9)(1sD4 , 3

25、, 21x 23 4918+53 14+55 10+59693，41x1s)(11sf1*x)()(11211xsfxp最優(yōu)方案最優(yōu)方案： A A派派3 3支巡邏隊(duì)，支巡邏隊(duì)，B B派派4 4支巡邏隊(duì)，支巡邏隊(duì)，C C派派2 2支巡邏隊(duì)；支巡邏隊(duì)；或：或：A A派派4 4支巡邏隊(duì)，支巡邏隊(duì)，B B派派3 3支巡邏隊(duì)，支巡邏隊(duì)，C C派派2 2支巡邏隊(duì)支巡邏隊(duì) 2022-4-2124解解2 2：順序解法：順序解法 設(shè)將向三個(gè)部位設(shè)將向三個(gè)部位A A，B B，C C派巡邏隊(duì)作派巡邏隊(duì)作為三個(gè)階段，為三個(gè)階段，K=1K=1，2 2，3 3。 決策變量決策變量 表示向第表示向第K K個(gè)部位派遣的巡邏隊(duì)

26、數(shù)。個(gè)部位派遣的巡邏隊(duì)數(shù)。 狀態(tài)變量狀態(tài)變量 表示前表示前K-1K-1個(gè)階段可派遣的巡邏隊(duì)數(shù)個(gè)階段可派遣的巡邏隊(duì)數(shù)量。量。 狀態(tài)轉(zhuǎn)移方程：狀態(tài)轉(zhuǎn)移方程： ， 階段指標(biāo)函數(shù)：階段指標(biāo)函數(shù)： 派遣派遣 支巡邏隊(duì)時(shí)第支巡邏隊(duì)時(shí)第K K階段產(chǎn)生的預(yù)期損失；階段產(chǎn)生的預(yù)期損失； 最優(yōu)指標(biāo)函數(shù)：前最優(yōu)指標(biāo)函數(shù)：前K K個(gè)階段的最優(yōu)目標(biāo)個(gè)階段的最優(yōu)目標(biāo) kxkskkkxss1)(kkxpkx)()(min)(1)(1kkKKSDxkksfXPsfKk)(1kkkxss2022-4-2125順序解法：順序解法： 邊界條件邊界條件 當(dāng)當(dāng)K=1K=1時(shí)，給時(shí)，給A A派巡邏隊(duì)，派巡邏隊(duì)， ，0)(10sf5 ,

27、4 , 3 , 2)(2sD4 , 3 , 21x 234218182318 14143418 14 10104518 14 101041x2s)(21sf1*x)()(1011sfxp2022-4-2126當(dāng)當(dāng)K=2K=2時(shí)，給時(shí)，給B B派巡邏隊(duì)，派巡邏隊(duì)，7 , 6 , 5)(3sD4 , 3 , 22x 23 4538+14 35+18522638+10 35+14 31+18482738+10 35+10 31+14533，42x3s)(32sf2*x)()(23111xsfxp)()(min)(212232sfxpsf2022-4-2127當(dāng)當(dāng)K=3K=3時(shí)，給時(shí)，給C C派巡邏隊(duì)

28、，派巡邏隊(duì)，)()(min)(2223343xsfxpsf 9)(4sD4 , 3 , 23x 23 4924+45 22+48 21+526923x4s)(43sf3*x)()(3233sfxp最優(yōu)方案最優(yōu)方案： A A派派3 3支巡邏隊(duì)，支巡邏隊(duì)，B B派派4 4支巡邏隊(duì)，支巡邏隊(duì)，C C派派2 2支巡邏隊(duì)；支巡邏隊(duì)；或：或：A A派派4 4支巡邏隊(duì)，支巡邏隊(duì)，B B派派3 3支巡邏隊(duì)，支巡邏隊(duì)，C C派派2 2支巡邏隊(duì)支巡邏隊(duì) 2022-4-2128例例2 2 資源分配問(wèn)題資源分配問(wèn)題 (P208(P208例例5 5）假設(shè)第假設(shè)第k k年年初完好機(jī)器數(shù)是年年初完好機(jī)器數(shù)是S SK K，用

29、于用于A A生產(chǎn)的機(jī)器生產(chǎn)的機(jī)器數(shù)是數(shù)是X XK K，則用于則用于B B生產(chǎn)的機(jī)器數(shù)是（生產(chǎn)的機(jī)器數(shù)是（S SK K - X- XK K）；）；用于用于A A工作的設(shè)備的完好率是：工作的設(shè)備的完好率是： ，用于，用于B B工作的工作的設(shè)備的完好率是：設(shè)備的完好率是：0.90.9。則下一年初的完好機(jī)器數(shù)。則下一年初的完好機(jī)器數(shù)是是 S SK+1K+1= X= XK K+0.9+0.9（S SK K- X- XK K）第第k k年的收益：年的收益： 10X10XK K+ 7(S+ 7(SK K- X- XK K) )32a32,7)(10)(xxhxxg0)(44sf邊界條件：邊界條件：)()(7

30、10max)(110kkkkksxkksfxsxsfkk2022-4-21290)(44sf逆序解法：逆序解法：邊界條件邊界條件 當(dāng)當(dāng)K=3K=3時(shí)時(shí)，第三年初分配機(jī)器，第三年初分配機(jī)器 臺(tái)生產(chǎn)臺(tái)生產(chǎn)A A， 臺(tái)生臺(tái)生產(chǎn)產(chǎn)B B ， 3x33xs 3334433303310)()(710max)(33sxssfxsxsfsx當(dāng)當(dāng)K=2K=2時(shí)時(shí)，第二年初分配機(jī)器，第二年初分配機(jī)器 臺(tái)生產(chǎn)臺(tái)生產(chǎn)A A， 臺(tái)臺(tái)生產(chǎn)生產(chǎn)B B，2x22xs 22222sx0222222sx033222sx022sxs3216s16x32max)xs (109x3210)xs (7x10max)s (f)xs (7x

31、10max)s (f2222222022-4-2130當(dāng)當(dāng)K=1K=1時(shí)時(shí)，第，第1 1年初分配機(jī)器年初分配機(jī)器 臺(tái)生產(chǎn)臺(tái)生產(chǎn)A A， 臺(tái)臺(tái)生產(chǎn)生產(chǎn)B B ，1x11xs 022009 . 02200max)(1093210)(710max)()(710max)(11100011111102211101111111xxxsxxsxsfxsxsfxsxsx1001s最優(yōu)方案最優(yōu)方案：第一年所有機(jī)器第一年所有機(jī)器100100臺(tái)用于生產(chǎn)臺(tái)用于生產(chǎn)B B， 第二年初完好機(jī)器第二年初完好機(jī)器9090臺(tái)；臺(tái)；第二年所有機(jī)器第二年所有機(jī)器9090臺(tái)用于生產(chǎn)臺(tái)用于生產(chǎn)A A， 第三年初完好機(jī)器第三年初完好機(jī)器

32、6060臺(tái)；臺(tái)；第三年所有機(jī)器第三年所有機(jī)器6060臺(tái)用于生產(chǎn)臺(tái)用于生產(chǎn)A A， 第四年初完好機(jī)器第四年初完好機(jī)器4040臺(tái)。臺(tái)。2022-4-21314 4離散隨機(jī)動(dòng)態(tài)規(guī)劃模型求解離散隨機(jī)動(dòng)態(tài)規(guī)劃模型求解隨機(jī)動(dòng)態(tài)規(guī)劃：隨機(jī)動(dòng)態(tài)規(guī)劃：狀態(tài)轉(zhuǎn)移規(guī)律不定，在給定的狀態(tài)狀態(tài)轉(zhuǎn)移規(guī)律不定，在給定的狀態(tài)和決策下，下一階段到達(dá)的狀態(tài)是具有確定概率分和決策下，下一階段到達(dá)的狀態(tài)是具有確定概率分布的隨機(jī)變量。布的隨機(jī)變量。第第k+1階段階段可能狀態(tài)可能狀態(tài)SkXkn21第第k階段狀態(tài)階段狀態(tài)決策決策P1，C1P2，C2Pn，CnP Pi i：在決策：在決策X Xk k下出現(xiàn)狀態(tài)下出現(xiàn)狀態(tài)i i的概率的概率C

33、Ci i：在決策：在決策X Xk k下出現(xiàn)狀態(tài)下出現(xiàn)狀態(tài)i i時(shí)的指時(shí)的指標(biāo)函數(shù)標(biāo)函數(shù)2022-4-2132隨機(jī)動(dòng)態(tài)規(guī)劃中，對(duì)指標(biāo)函數(shù)進(jìn)行優(yōu)化時(shí)，要根據(jù)隨機(jī)動(dòng)態(tài)規(guī)劃中，對(duì)指標(biāo)函數(shù)進(jìn)行優(yōu)化時(shí)，要根據(jù)各階段的各階段的期望效益期望效益進(jìn)行優(yōu)化。進(jìn)行優(yōu)化。基本方程改寫(xiě)為：基本方程改寫(xiě)為：)(),()(11)(kkkkSDxkksfxsvEoptsfKk例：例：P210P210，例，例6 6 解：解：階段變量階段變量K K， 每月投產(chǎn)一批作為一個(gè)階段，每月投產(chǎn)一批作為一個(gè)階段，K=1K=1，2 2，3 3。 狀態(tài)變狀態(tài)變量量 ：表示第：表示第K K階段所擁有的合格樣品數(shù)，有兩階段所擁有的合格樣品數(shù)，有兩

34、種可能狀態(tài)。種可能狀態(tài)。 表示有一臺(tái)以上的合格品；表示有一臺(tái)以上的合格品； 表示沒(méi)有一臺(tái)合格品。表示沒(méi)有一臺(tái)合格品。ks0ks1ks2022-4-2133決策變量決策變量 ：表示第：表示第K K個(gè)階段決定投產(chǎn)的數(shù)量個(gè)階段決定投產(chǎn)的數(shù)量。kx狀態(tài)轉(zhuǎn)移律狀態(tài)轉(zhuǎn)移律：kkxkxkspsp321)0(32) 1(11階段指標(biāo)函數(shù)：階段指標(biāo)函數(shù)：0, 01,100250),(kkkkkssxxsc最優(yōu)指標(biāo)函數(shù)最優(yōu)指標(biāo)函數(shù) ：表示第表示第K K階段在階段在 狀態(tài)下，狀態(tài)下，做決策做決策 時(shí)，到最后一個(gè)階段的最小期望費(fèi)用。時(shí)，到最后一個(gè)階段的最小期望費(fèi)用。 )(kksfkskx2022-4-2134Sk=1

35、Xk第第k階段狀態(tài)階段狀態(tài)決策決策Sk=0Sk+1=1Sk+1=0KX32KX321第第k+1階段狀態(tài)階段狀態(tài))(),()(11)(kkkkSDxkksfxscEoptsfKk易知：易知：4 , 3 , 2, 0)0(ksfkk)0(321 ) 1(32),(min) 1(1111)(kkxkkxkkSDxkksfsfxscsfkkKk2022-4-2135逆序解法：逆序解法：邊界條件邊界條件 當(dāng)當(dāng)K=3K=3時(shí)，第三階段之后的最小期望費(fèi)用時(shí)，第三階段之后的最小期望費(fèi)用 0)0(33sf) 1(32),(min) 1(4433)(33333sfxscsfxSDx1500) 1(44sf 0 1

36、 2 3 4 500 0011500 1350 1117 994 946 94894643x3s)(33sf3*x) 1(32),(44333sfxscx150032100250) 1(32),(3334433xxxsfxsc1500) 1(44sf2022-4-2136當(dāng)當(dāng)K=2K=2時(shí)，第二階段之后的最小期望費(fèi)用時(shí)，第二階段之后的最小期望費(fèi)用0)0(22sf) 1(32),(min) 1(3322)(22222sfxscsfxSDx 0 1 2 3 4 500 001946 981 870 830 837 83032x2s)(22sf2*x) 1(32),(33222sfxscx946)

37、1(33sf94632100250) 1(32),(2223322xxxsfxsc2022-4-2137當(dāng)當(dāng)K=1K=1時(shí)，第一階段之后的最小期望費(fèi)用時(shí)，第一階段之后的最小期望費(fèi)用) 1(32),(min) 1(2211)(11111sfxscsfxSDx 0 1 2 3 4 51830 903 819 796 81479631x1s)(11sf1*x) 1(32),(22111sfxscx830) 1(22sf最優(yōu)方案最優(yōu)方案：第一期投產(chǎn)第一期投產(chǎn)3 3臺(tái)；第二期投產(chǎn)臺(tái)；第二期投產(chǎn)3 3臺(tái)；第三期投產(chǎn)臺(tái)；第三期投產(chǎn)4 4臺(tái)。臺(tái)。最小期望費(fèi)用最小期望費(fèi)用796796。2022-4-21385 5一般數(shù)學(xué)規(guī)劃模型的動(dòng)態(tài)規(guī)劃解法一般數(shù)學(xué)規(guī)劃模型的動(dòng)態(tài)規(guī)劃解法用動(dòng)態(tài)規(guī)劃的方法求解一般數(shù)學(xué)規(guī)劃模型思想用動(dòng)態(tài)規(guī)劃的方法求解一般數(shù)學(xué)規(guī)劃模型