運籌(第八章動態(tài)規(guī)劃)

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

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

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

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

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

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

7、D1 1-E-E； 如果經(jīng)過如果經(jīng)過B B3 3，則走，則走B B3 3-C-C3 3-D-D1 1-E-E； 如果經(jīng)過如果經(jīng)過B B4 4，則走，則走B B4 4-C-C3 3-D-D1 1-E-E。 階段2本階段始點（狀態(tài)） 本階段各終點（決策）到E的最短距離本階段最優(yōu)終點（最優(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-3-88第一階段：

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

9、2 B42022-3-89 以上計算過程及結(jié)果，可用圖以上計算過程及結(jié)果，可用圖2 2表示，可以看到，以表示，可以看到，以上方法不僅得到了從上方法不僅得到了從A A到到D D的最短路徑，同時，也得的最短路徑，同時，也得到了從圖中任一點到到了從圖中任一點到E E的最短路徑。的最短路徑。 以上過程，僅用了以上過程，僅用了2222次加法，計算效率遠(yuǎn)高于窮舉次加法，計算效率遠(yuǎn)高于窮舉法。法。BACBDBCDEC412312312332164724838675161060106121111121314144B1275122022-3-810例例2 2 資源分配問題資源分配問題設(shè)有某種機器數(shù)臺，用于完成兩

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

11、作的設(shè)備的完好率是：a%a%，用于，用于B B工作工作的設(shè)備的完好率是：的設(shè)備的完好率是：b%b%。則下一年初的完好機器數(shù)。則下一年初的完好機器數(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-3-811例例3 3 背包問題背包問題設(shè)有設(shè)有n n種物品，每一種物品數(shù)量無限。第種物品，每一種物品數(shù)量無限。第i i種物品每種物品每件重量為件重量為w wi i公斤，每件價值公斤，每件價值c ci i元?，F(xiàn)有一只可裝載重元。現(xiàn)有

12、一只可裝載重量為量為W W公斤的背包，求各種物品應(yīng)各取多少件放入背公斤的背包，求各種物品應(yīng)各取多少件放入背包，使背包中物品的價值最高。包，使背包中物品的價值最高。 這個問題可以用整數(shù)規(guī)劃模型來描述。設(shè)這個問題可以用整數(shù)規(guī)劃模型來描述。設(shè)x xi i為第為第I I種物品裝入背包的件數(shù)（種物品裝入背包的件數(shù)（i i =1, 2, , =1, 2, , n n），背包），背包中物品的總價值為中物品的總價值為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 1+w+w2 2x x

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

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

15、和出發(fā)點（能確定地表示決策過程當(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-3-8143 3、決策、決策x xk k：從某一狀態(tài)向下一狀態(tài)過渡時所做的選從某一狀態(tài)向下一狀態(tài)過渡時所做的選擇。決策是所在狀態(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階段開始到最后第階段開始到最后第n n階段的階段的決策序列，稱決策序列，稱k k子策略。子策略。P1,n(s1)P1,n(s1)即為全過程策略。即為全過程策略。2022-3-8155 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)從狀態(tài)S Sk k出發(fā)，選擇決

17、出發(fā)，選擇決策策X Xk k所產(chǎn)生的第所產(chǎn)生的第k k階段指標(biāo)。階段指標(biāo)。 過程指標(biāo)函數(shù)過程指標(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)生的過程指所產(chǎn)生的過程指標(biāo)。標(biāo)。2022-3-816動態(tài)規(guī)劃要求過程指標(biāo)具有可分離性動態(tài)規(guī)劃要求過程指標(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

18、)+Vk+1k+1(s(sk+1k+1, x, xk+1k+1, , x, , xn n) )稱指標(biāo)具有稱指標(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) )稱指標(biāo)具有稱指標(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ā)，對所有的策略出發(fā)，對所有的策略P Pk,nk,n，過程

19、指標(biāo)，過程指標(biāo)V Vk,nk,n的最優(yōu)值，即的最優(yōu)值，即 ),()(,)(nkknksDxkkPsVsfoptkkk2022-3-817對于可加性指標(biāo)函數(shù)，上式可以寫為對于可加性指標(biāo)函數(shù)，上式可以寫為 上式中上式中“opt”opt”表示表示“max”max”或或“min”min”。對于可乘性指標(biāo)函數(shù)，上式可以寫為對于可乘性指標(biāo)函數(shù)，上式可以寫為 以上式子稱為動態(tài)規(guī)劃最優(yōu)指標(biāo)的遞推方程，是動以上式子稱為動態(tài)規(guī)劃最優(yōu)指標(biāo)的遞推方程，是動態(tài)規(guī)劃的態(tài)規(guī)劃的基本方程基本方程。終端條件終端條件：為了使以上的遞推方程有遞推的起點，：為了使以上的遞推方程有遞推的起點，必須要設(shè)定最優(yōu)指標(biāo)的終端條件，一般最后一個

20、狀必須要設(shè)定最優(yōu)指標(biāo)的終端條件，一般最后一個狀態(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-3-8182.3 2.3 最優(yōu)化原理最優(yōu)化原理 作為整個過程的最優(yōu)策略具有如下性質(zhì)：作為整個過程的最優(yōu)策略具有如下性質(zhì)： 不管在此最優(yōu)策略上的某個狀態(tài)以前的狀不管在此最優(yōu)策略上的某個狀態(tài)以前的狀態(tài)和決策如何，對該狀態(tài)來說，以后的所有決態(tài)和決策如何，對該狀態(tài)來說

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

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

23、的預(yù)期損失； 過程指標(biāo)函數(shù)：過程指標(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-3-821逆序解法：逆序解法：邊界條件邊界條件 當(dāng)當(dāng)K=3K=3時，給時，給C C派巡邏隊，派巡邏隊， ， 0)(44sf5 , 4 , 3 , 2)(3sD4 , 3 , 23x 2342 24 -2423 24 22 -2234 24 22 212145 24 22 212143x3s)(33sf3*x)()(

24、min)(443333sfxpsf)x,s (v3332022-3-822當(dāng)當(dāng)K=2K=2時，給時，給B B派巡邏隊，派巡邏隊， 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-3-823當(dāng)當(dāng)K=1K=1時，給時，給A A派巡邏隊，派巡邏隊， )()(min)(1121111xsfxpsf 9)(1sD4 , 3 , 21x 23 4918+53 14+55

25、10+59693，41x1s)(11sf1*x)()(11211xsfxp最優(yōu)方案最優(yōu)方案： A A派派3 3支巡邏隊，支巡邏隊，B B派派4 4支巡邏隊，支巡邏隊，C C派派2 2支巡邏隊；支巡邏隊；或：或：A A派派4 4支巡邏隊，支巡邏隊，B B派派3 3支巡邏隊，支巡邏隊，C C派派2 2支巡邏隊支巡邏隊 2022-3-824解解2 2：順序解法：順序解法 設(shè)將向三個部位設(shè)將向三個部位A A，B B，C C派巡邏隊作派巡邏隊作為三個階段，為三個階段，K=1K=1，2 2，3 3。 決策變量決策變量 表示向第表示向第K K個部位派遣的巡邏隊數(shù)。個部位派遣的巡邏隊數(shù)。 狀態(tài)變量狀態(tài)變量 表

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

27、 234218182318 14143418 14 10104518 14 101041x2s)(21sf1*x)()(1011sfxp2022-3-826當(dāng)當(dāng)K=2K=2時，給時，給B B派巡邏隊，派巡邏隊，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-3-827當(dāng)當(dāng)K=3K=3時，給時，給C C派巡邏隊，派巡邏隊，)()(min)(2223343xsfxp

28、sf 9)(4sD4 , 3 , 23x 23 4924+45 22+48 21+526923x4s)(43sf3*x)()(3233sfxp最優(yōu)方案最優(yōu)方案： A A派派3 3支巡邏隊，支巡邏隊，B B派派4 4支巡邏隊，支巡邏隊，C C派派2 2支巡邏隊；支巡邏隊；或：或：A A派派4 4支巡邏隊，支巡邏隊，B B派派3 3支巡邏隊，支巡邏隊，C C派派2 2支巡邏隊支巡邏隊 2022-3-828例例2 2 資源分配問題資源分配問題 (P208(P208例例5 5）假設(shè)第假設(shè)第k k年年初完好機器數(shù)是年年初完好機器數(shù)是S SK K，用于用于A A生產(chǎn)的機器生產(chǎn)的機器數(shù)是數(shù)是X XK K，則

29、用于則用于B B生產(chǎn)的機器數(shù)是（生產(chǎn)的機器數(shù)是（S SK K - X- XK K）；）；用于用于A A工作的設(shè)備的完好率是：工作的設(shè)備的完好率是： ，用于，用于B B工作的工作的設(shè)備的完好率是：設(shè)備的完好率是：0.90.9。則下一年初的完好機器數(shù)。則下一年初的完好機器數(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邊界條件：邊界條件：)()(710max)(110kkkkksxkksfxsxsfkk

30、2022-3-8290)(44sf逆序解法：逆序解法：邊界條件邊界條件 當(dāng)當(dāng)K=3K=3時時，第三年初分配機器，第三年初分配機器 臺生產(chǎn)臺生產(chǎn)A A， 臺生臺生產(chǎn)產(chǎn)B B ， 3x33xs 3334433303310)()(710max)(33sxssfxsxsfsx當(dāng)當(dāng)K=2K=2時時，第二年初分配機器，第二年初分配機器 臺生產(chǎn)臺生產(chǎn)A A， 臺臺生產(chǎn)生產(chǎn)B B，2x22xs 22222sx0222222sx033222sx022sxs3216s16x32max)xs (109x3210)xs (7x10max)s (f)xs (7x10max)s (f2222222022-3-830當(dāng)當(dāng)K

31、=1K=1時時，第，第1 1年初分配機器年初分配機器 臺生產(chǎn)臺生產(chǎn)A A， 臺臺生產(chǎn)生產(chǎn)B B ，1x11xs 022009 . 02200max)(1093210)(710max)()(710max)(11100011111102211101111111xxxsxxsxsfxsxsfxsxsx1001s最優(yōu)方案最優(yōu)方案：第一年所有機器第一年所有機器100100臺用于生產(chǎn)臺用于生產(chǎn)B B， 第二年初完好機器第二年初完好機器9090臺；臺；第二年所有機器第二年所有機器9090臺用于生產(chǎn)臺用于生產(chǎn)A A， 第三年初完好機器第三年初完好機器6060臺；臺；第三年所有機器第三年所有機器6060臺用于生

32、產(chǎn)臺用于生產(chǎn)A A， 第四年初完好機器第四年初完好機器4040臺。臺。2022-3-8314 4離散隨機動態(tài)規(guī)劃模型求解離散隨機動態(tài)規(guī)劃模型求解隨機動態(tài)規(guī)劃：隨機動態(tài)規(guī)劃：狀態(tài)轉(zhuǎn)移規(guī)律不定，在給定的狀態(tài)狀態(tài)轉(zhuǎn)移規(guī)律不定，在給定的狀態(tài)和決策下，下一階段到達(dá)的狀態(tài)是具有確定概率分和決策下，下一階段到達(dá)的狀態(tài)是具有確定概率分布的隨機變量。布的隨機變量。第第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 Ci i：在決策：在決策X Xk k下出現(xiàn)狀態(tài)下出現(xiàn)狀態(tài)i i

33、時的指時的指標(biāo)函數(shù)標(biāo)函數(shù)2022-3-832隨機動態(tài)規(guī)劃中，對指標(biāo)函數(shù)進(jìn)行優(yōu)化時，要根據(jù)隨機動態(tài)規(guī)劃中，對指標(biāo)函數(shù)進(jìn)行優(yōu)化時，要根據(jù)各階段的各階段的期望效益期望效益進(jìn)行優(yōu)化。進(jìn)行優(yōu)化?；痉匠谈膶憺椋夯痉匠谈膶憺椋?(),()(11)(kkkkSDxkksfxsvEoptsfKk例：例：P210P210，例，例6 6 解：解：階段變量階段變量K K， 每月投產(chǎn)一批作為一個階段，每月投產(chǎn)一批作為一個階段，K=1K=1，2 2，3 3。 狀態(tài)變狀態(tài)變量量 ：表示第：表示第K K階段所擁有的合格樣品數(shù)，有兩階段所擁有的合格樣品數(shù)，有兩種可能狀態(tài)。種可能狀態(tài)。 表示有一臺以上的合格品；表示有一臺以上

34、的合格品； 表示沒有一臺合格品。表示沒有一臺合格品。ks0ks1ks2022-3-833決策變量決策變量 ：表示第：表示第K K個階段決定投產(chǎn)的數(shù)量個階段決定投產(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)下，做決策做決策 時，到最后一個階段的最小期望費用。時，到最后一個階段的最小期望費用。 )(kksfkskx2022-3-834Sk=1Xk第第k階段狀態(tài)階段狀態(tài)決策決策Sk=0Sk+1=1Sk+1=0K

35、X32KX321第第k+1階段狀態(tài)階段狀態(tài))(),()(11)(kkkkSDxkksfxscEoptsfKk易知：易知：4 , 3 , 2, 0)0(ksfkk)0(321 ) 1(32),(min) 1(1111)(kkxkkxkkSDxkksfsfxscsfkkKk2022-3-835逆序解法：逆序解法：邊界條件邊界條件 當(dāng)當(dāng)K=3K=3時，第三階段之后的最小期望費用時，第三階段之后的最小期望費用 0)0(33sf) 1(32),(min) 1(4433)(33333sfxscsfxSDx1500) 1(44sf 0 1 2 3 4 500 0011500 1350 1117 994 94

36、6 94894643x3s)(33sf3*x) 1(32),(44333sfxscx150032100250) 1(32),(3334433xxxsfxsc1500) 1(44sf2022-3-836當(dāng)當(dāng)K=2K=2時，第二階段之后的最小期望費用時，第二階段之后的最小期望費用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) 1(33sf94632100250) 1(32),(2223322xxxsfxsc2022-3-837當(dāng)當(dāng)K=1K=1時，第一階段之后的最小期望費用時，第一階段之后的最小期望費用) 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)方案：第