第10章 動態(tài)規(guī)劃.ppt

1、1,第五章 動態(tài)規(guī)劃,1多階段決策過程最優(yōu)化問題舉例 2基本概念、基本方程與最優(yōu)化原理 3動態(tài)規(guī)劃的應用(1) 4動態(tài)規(guī)劃的應用(2),2,1多階段決策過程最優(yōu)化問題舉例,例1 最短路徑問題 下圖表示從起點A到終點E之間各點的距離。求A到E的最 短路徑。,B,C,B,D,B,C,D,E,C,4,1,2,3,1,2,3,1,2,3,2,2,1,6,4,7,2,4,8,3,8,6,7,5,6,1,10,6,3,7,5,1,3,1多階段決策過程最優(yōu)化問題舉例,用窮舉法的計算量: 如果從A到E的站點有k個，除A、E之外每站有3個位置則 總共有3k-12條路徑； 計算各路徑長度總共要進行 (k+1) 3

2、k-12次加法以及3k- 12-1次比較。隨著 k 的值增加時，需要進行的加法和比較的 次數(shù)將迅速增加； 例如當 k=20時，加法次數(shù)為 4.25508339662271015 次， 比較 1.37260754729771014 次。若用1億次/秒的計算機計算 需要約508天。,4,1多階段決策過程最優(yōu)化問題舉例,討論： 1、以上求從A到E的最短路徑問題，可以轉(zhuǎn)化為四個性質(zhì)完全相 同，但規(guī)模較小的子問題，即分別從Di 、Ci、Bi、A到E的最短路 徑問題。 第四階段：兩個始點D1和D2，終點只有一個； 表10-1 分析得知：從D1和D2到E的最短路徑唯一。,5,第三階段：有三個始點C1，C2，

3、C3，終點有D1，D2，對始點 和終點進行分析和討論分別求C1，C2，C3到D1，D2 的最短路 徑問題： 表10-2 分析得知：如果經(jīng)過C1，則最短路為C1-D2-E； 如果經(jīng)過C2，則最短路為C2-D2-E； 如果經(jīng)過C3，則最短路為C3-D1-E。,1多階段決策過程最優(yōu)化問題舉例,6,第二階段：有4個始點B1,B2,B3,B4，終點有C1,C2,C3。對始點和終點進行分 析和討論分別求B1,B2,B3,B4到C1,C2,C3 的最短路徑問題： 表10-3 分析得知：如果經(jīng)過B1，則走B1-C2-D2-E； 如果經(jīng)過B2，則走B2-C3-D1-E； 如果經(jīng)過B3，則走B3-C3-D1-E；

4、 如果經(jīng)過B4，則走B4-C3-D1-E。,1多階段決策過程最優(yōu)化問題舉例,7,第一階段：只有1個始點A，終點有B1,B2,B3,B4 。對始點和終 點進行分析和討論分別求A到B1,B2,B3,B4的最短路徑問題： 表10-4 最后，可以得到：從A到E的最短路徑為A B4 C3 D1 E,1多階段決策過程最優(yōu)化問題舉例,8,以上計算過程及結(jié)果，可用圖2表示，可以看到，以上方法不僅 得到了從A到D的最短路徑，同時，也得到了從圖中任一點到E的最 短路徑。 以上過程，僅用了22次加法，計算效率遠高于窮舉法。,B,C,B,D,B,C,D,E,C,4,1,2,3,1,2,3,1,2,3,3,2,1,6,

5、4,7,2,4,8,3,8,6,7,5,1,6,10,6,0,10,6,12,11,11,12,13,14,14,12,7,5,1,2,1多階段決策過程最優(yōu)化問題舉例,9,一、基本概念： 1、階段k：表示決策順序的離散的量，階段可以按時間或空間劃分。 2、狀態(tài)sk：能確定地表示決策過程當前特征的量。狀態(tài)可以是數(shù)量，也可以是字符，數(shù)量狀態(tài)可以是連續(xù)的，也可以是離散的。 3、決策xk：從某一狀態(tài)向下一狀態(tài)過渡時所做的選擇。決策是所在狀態(tài)的函數(shù)，記為xk(sk)。 決策允許集合Dk(sk)：在狀態(tài)sk下，允許采取決策的全體。 4、策略Pk,n(sk)：從第k階段開始到最后第n階段的決策序列，稱k子策

6、略。P1,n(s1)即為全過程策略。 5、狀態(tài)轉(zhuǎn)移方程 sk+1=Tk(sk, xk)：某一狀態(tài)以及該狀態(tài)下的決策，與下一狀態(tài)之間的函數(shù)關(guān)系。,2基本概念、基本方程與最優(yōu)化原理,10,6、階段指標函數(shù)vk(sk, xk)：從狀態(tài)sk出發(fā)，選擇決策xk所產(chǎn)生的第k階段指標。 過程指標函數(shù)Vk,n(sk, xk, xk+1, xn)：從狀態(tài)sk出發(fā)，選擇決策xk, xk+1, , xn所產(chǎn)生的過程指標。動態(tài)規(guī)劃要求過程指標具有可分離 性，即 Vk,n(sk, xk, xk+1, , xn) = vk(sk, xk)+Vk+1(sk+1, xk+1, , xn) 稱指標具有可加性，或 Vk,n(sk

7、, xk, xk+1, , xn) = vk(sk, xk)Vk+1(sk+1, xk+1, , xn)稱指標具有可乘性。 二、基本方程： 最優(yōu)指標函數(shù)fk(sk)：從狀態(tài)sk出發(fā)，對所有的策略Pk,n，過程指 標Vk,n的最優(yōu)值，即,2基本概念、基本方程與最優(yōu)化原理,11,對于可加性指標函數(shù)，上式可以寫為 上式中“opt”表示“max”或“min”。對于可乘性指標函數(shù)，上式可以 寫為 以上式子稱為動態(tài)規(guī)劃最優(yōu)指標的遞推方程，是動態(tài)規(guī)劃的基本 方程。 終端條件：為了使以上的遞推方程有遞推的起點，必須要設定最 優(yōu)指標的終端條件，一般最后一個狀態(tài)n+1下最優(yōu)指標fn+1(sn+1) = 0。,2基

8、本概念、基本方程與最優(yōu)化原理,12,三、最優(yōu)化原理 作為整個過程的最優(yōu)策略具有如下性質(zhì)： 不管在此最優(yōu)策略上的某個狀態(tài)以前的狀 態(tài)和決策如何，對該狀態(tài)來說，以后的所有決 策必定構(gòu)成最優(yōu)子策略。就是說，最優(yōu)策略的 任意子策略都是最優(yōu)的。,2基本概念、基本方程與最優(yōu)化原理,13,一、資源分配問題 例2. 某公司擬將某種設備5臺，分配給所屬的甲、乙、丙三個工 廠。各工廠獲得此設備后，預測可創(chuàng)造的利潤如表10-5所示，問這 5臺設備應如何分配給這3個工廠，使得所創(chuàng)造的總利潤為最大？ 表10-5,3 動態(tài)規(guī)劃的應用(1),14,解：將問題按工廠分為三個階段，甲、乙、丙三個廠分別編號為1、2、3廠。設 s

9、k= 分配給第k個廠至第3個廠的設備臺數(shù)（k=1、2、 3）。 xk=分配給第k個設備臺數(shù)。 已知s1=5, 并有 從與的定義，可知 以下我們從第三階段開始計算。,3 動態(tài)規(guī)劃的應用(1),15,第三階段: 顯然將臺設備都分配給第3工廠時， 也就是時，第3階段的指標值（即第3廠的盈利） 為最大，即 由于第3階段是最后的階段，故有 其中可取值為0,1,2,3,4,5。其數(shù)值計算見表106。,3 動態(tài)規(guī)劃的應用(1),16,表106,3 動態(tài)規(guī)劃的應用(1),17,其中表示取3子過程上最優(yōu)指標值時的 決策，例如在表10-6中可知當=4時，有有 此時，即當時，此時取 （把4臺設備分配給第3廠）是最優(yōu)

10、決策，此時階段指標值 （盈利）為12，最優(yōu)3子過程最優(yōu)指標值也為12。 第二階段： 當把臺設備分配給第2工廠和第3工 廠時，則對每個值，有一種最優(yōu)分配方案，使最大盈利 即最優(yōu)2子過程最優(yōu)指標函數(shù)值為,3 動態(tài)規(guī)劃的應用(1),18,因為上式也可寫成 其數(shù)值計算如表107所示。 表107,3 動態(tài)規(guī)劃的應用(1),19,其中在的這一行里，當時， 這里從表105中可知，把1臺設備交給乙廠所得盈 利數(shù)即可，知，這里從表106查 即可知=11。同樣可知當時，可知 ; 當時，；當時， ；當時， ；由于，不可能分2廠5 臺設備，故時，欄空著不填。從 這些數(shù)值中取得最大即得，即有=16。在此行中 我們在取最

11、大值的 上面加一橫以示 區(qū)別，也可知這時的最優(yōu)決策為1或2。,3 動態(tài)規(guī)劃的應用(1),20,第一階段： 把臺設備分配給第1，第2，第3廠時，最大 盈利為其中可取值0,1,2,3,4,5. 數(shù)值計算見表108 表10-8 然后按計算表格的順序推算，可知最優(yōu)分配方案有兩個： 1.由于，根據(jù)，查表107可 知，再由 ，求得。即分配 給甲廠0臺，乙廠2臺，丙廠3臺。 2.由于，根據(jù) ，查表107可,3 動態(tài)規(guī)劃的應用(1),21,知，再由 ,求得， 即分配給甲廠2臺，乙廠2臺，丙廠1臺。 這兩種分配方案都能得到最高的總盈利21萬元。,3 動態(tài)規(guī)劃的應用(1),22,二、背包問題 設有n種物品，每一種

12、物品數(shù)量無限。第i種物品每件 重量為wi公斤，每件價值ci元?，F(xiàn)有一只可裝載重量為W 公斤的背包，求各種物品應各取多少件放入背包，使背 包中物品的價值最高。 這個問題可以用整數(shù)規(guī)劃模型來描述。設xi為第i種 物品裝入背包的件數(shù)（i =1, 2, , n），背包中物品的總 價值為z，則 Max z = c1x1+c2x2+ +cnxn s.t. w1x1+w2x2+wnxnW x1, x2, , xn0 且為整數(shù)。,3 動態(tài)規(guī)劃的應用(1),23,下面用動態(tài)規(guī)劃逆序解法求解它。設 階段變量k：第k次裝載第k種物品（k=1, 2, , n） 狀態(tài)變量sk：第k次裝載時背包還可以裝載的重量； 決策變

13、量uk = xk：第k次裝載第k種物品的件數(shù)； 決策允許集合：Dk(sk) = xk | 0 xksk/wk，xk為整數(shù)； 狀態(tài)轉(zhuǎn)移方程： sk+1 = sk wkxk； 階段指標： vk = ckxk； 最優(yōu)過程指標函數(shù)fk(sk)：第k到n階段容許裝入物品的最大使 用價值； 遞推方程： fk(sk) = max ckxk+fk+1(sk+1) = max ckxk+fk+1(sk wkxk)； xDk(sk) 終端條件： fn+1(sn+1) = 0。,3 動態(tài)規(guī)劃的應用(1),24,例3.某咨詢公司有10個工作日可以去處理四種類型的咨 詢項目，每種類型的咨詢項目中待處理的客戶數(shù)量、處理每

14、個 客戶所需工作日數(shù)以及所獲得的利潤如表109所示。顯然該公 司在10天內(nèi)不能處理完所有的客戶，它可以自己挑選一些客 戶，其余的請其他咨詢公司去做，應如何選擇客戶使得在這10 個工作日中獲利最大？ 表109,3 動態(tài)規(guī)劃的應用(1),25,解：用動態(tài)規(guī)劃來求解此題。 我們把此問題分成四個階段，第一階段我們決策將 處理多少個第一種咨詢項目類型中的客戶，第二階段決 策將處理多少個第二種咨詢項目類型中的客戶，第三階 段、第四階段我們也將作出類似的決策。我們設 分配給第k種咨詢項目到第四種咨詢項目的所 有客戶的總工作日（第k階段的狀態(tài)變量）。 =在第k種咨詢項目中處理客戶的數(shù)量（第k階段 的決策變量）

15、。 已知10 并有,3 動態(tài)規(guī)劃的應用(1),26,并從與的定義可知 從第四階段開始計算： 顯然將個工作日盡可能分配給第四 類咨詢項目，即時，第四階段的指標值為最大， 其中，表示取不大于的最大整數(shù)，符號為 取整符號，故有 由于第四階段是最后的階段，故有,3 動態(tài)規(guī)劃的應用(1),27,因為至多為10，其數(shù)值計算見表1010。 表1010,3 動態(tài)規(guī)劃的應用(1),28,第三階段： 當把個工作日分配給第四類和第 三類咨詢項目時，則對每個值，都有一種最優(yōu)分配方 案，使其最大盈利即最優(yōu)3子過程最優(yōu)指標函數(shù)值為 因為 因為至多為10，所以的取值可為0,1,2。其數(shù)值計算 見表1011。,3 動態(tài)規(guī)劃的

16、應用(1),29,表1011,3 動態(tài)規(guī)劃的應用(1),30,第二階段： 同樣以每個值都有一種最優(yōu)分配方案，使其最大盈利即 最優(yōu)2子過程最優(yōu)指標函數(shù)值為： 因為，故有 因為至多為10，所以的取值為0,1,2,3。其數(shù)值計算 見表1012。,3動態(tài)規(guī)劃的應用(1),31,3動態(tài)規(guī)劃的應用(1),表10-12,32,第一階段： 我們已知，又因為 ，同樣有 因為 ,故可取值為0,1,2, ,10。其數(shù)值計算 見表1013。 表1013,3動態(tài)規(guī)劃的應用(1),33,從表1013可知，從而得10 010，在表1012的的這一行可知，由 ，查表1011的的這一行可知 ，最后由，查表10-10的的這 一行

17、得，綜上所述得最優(yōu)解為： 此時最大盈利為28。 現(xiàn)在我們不妨假設該咨詢公司的工作計劃有所改變，只有 8個工作日來處理這四類咨詢項目，那么該咨詢公司如何選擇 客戶使得獲利最大呢？我們不必從頭開始重做這個問題，而只 要在第一階段上把改成8，重新計算就可得到結(jié)果，如表10 14所示，這是動態(tài)規(guī)劃的一個好處。,3動態(tài)規(guī)劃的應用(1),34,表1014 如上一樣可從表1014,1012,1011,1010得到兩組最優(yōu)解 如下： 它們的最優(yōu)解（即最大盈利）都為22。 一旦咨詢的工作日不是減少而是增加，那么我們不僅要重新計 算第一階段，而且要在第二、第三、第四階段的計算表上補上增加 的工作日的新的信息，也可

18、得到新的結(jié)果。,3動態(tài)規(guī)劃的應用(1),35,實際上，背包問題我們也可以用整數(shù)規(guī)劃來求解，如果背包攜帶物品重量的限制為W公斤，這N種物品中第i種物品的重量為，價值為，第i種物品的總數(shù)量的，我們可以設表示攜帶第i種物品的數(shù)量，則其數(shù)學模型為： S.T. 且為整數(shù)。 我們不妨用此模型去求解例3，也一定得出同樣的結(jié)果。,3動態(tài)規(guī)劃的應用(1),36,三、生產(chǎn)與存貯問題 例4.某公司為主要電力公司生產(chǎn)大型變壓器，由于電力 采取預訂方式購買，所以該公司可以預測未來幾個月的需求 量。為確保需求，該公司為新的一年前四個月制定一項生產(chǎn) 計劃，這四個月的需求如表1015所示。 生產(chǎn)成本隨著生產(chǎn)數(shù)量而變化。調(diào)試費

19、為4，除了調(diào)度費 用外，每月生產(chǎn)的頭兩臺各花費為2，后兩臺花費為1。最大 生產(chǎn)能力每月為4臺，生產(chǎn)成本如表1016所示。 表1015,3動態(tài)規(guī)劃的應用(1),37,表1016 每臺變壓器在倉庫中由這個月存到下個月的儲存費為1， 倉庫的最大儲存能力為3臺，另外，知道在1月1日時倉庫里存 有一臺變壓器，要求在4月30日倉庫的庫存量為零。試問該公 司應如何制定生產(chǎn)計劃，使得四個月的生產(chǎn)成本和儲存總費 用最少？ 解：我們按月份來劃分階段，第i個月為第i階段：（i=1,2,3,4). 設 為第k階段期初庫存量； k=1,2,3,4,3動態(tài)規(guī)劃的應用(1),38,為第k階段生產(chǎn)量； k=1,2,3,4 為

20、第k階段需求量； k=1,2,3,4，這已在表10-15 中告訴我們。 因為下個月的庫存量等于上個月的庫存量加上上個月的 產(chǎn)量減去上個月的需求量，我們就得到了如下狀態(tài)轉(zhuǎn)移方 程： 因為，故有 因為，故有,3動態(tài)規(guī)劃的應用(1),39,由于必須要滿足需求，則有 通過移項得到 另一方面，第k階段的生產(chǎn)量必不大于同期的生產(chǎn)能力 （4臺），也不大于第k階段至第四階段的需求之和與第k階段 期初庫存量之差，否則第k階段的生產(chǎn)量就要超過從第k階段 至第四階段的總需求，故有 以下我們從第四階段開始計算： 從以上的狀態(tài)轉(zhuǎn)移方程可知 這樣就有,3動態(tài)規(guī)劃的應用(1),40,這里的階段指標可以分成兩部分，即生產(chǎn)成本

21、與 儲存費，即為 由于第四階段末要求庫存為零，即有， 這樣可得 對于每個的可行值，的值列于表1017。 表1017,3動態(tài)規(guī)劃的應用(1),41,表中當時，可知第四階段要生產(chǎn) 臺，從表1016可知總成本為9，同樣可以算出當為1,2,3時 的情況，結(jié)果已列于表1017中。 第三階段： 此時有： 因為以及所以有 例如，當?shù)谌A段初庫存量時，生產(chǎn)量為2時， 則所以生產(chǎn)成本為8，第三階段末庫存 為2時，儲存費為，而,3動態(tài)規(guī)劃的應用(1),42,查1017表可知，這樣可知， 填入表1018中的欄內(nèi)，其他結(jié)果如表1018所 示 ： 表1018 第二階段： 因為所以有,3動態(tài)規(guī)劃的應用(1),43,計算結(jié)

22、果如表1019所示。 表1019,3動態(tài)規(guī)劃的應用(1),44,第一階段： 因為故有 計算結(jié)果見表1020。 表1020,3動態(tài)規(guī)劃的應用(1),45,利用遞推關(guān)系可以從表1020，表1019，表1018和表10 17得到兩組最優(yōu)解： 這時有最低總成本29。,3動態(tài)規(guī)劃的應用(1),46,3動態(tài)規(guī)劃的應用(1),四、系統(tǒng)可靠性問題 例5.某科研項目組由三個小組用不同的手段分別研究，它們失敗的概率各為0.40，0.60，0.80。為了減少三個小組都失敗的可能性，現(xiàn)決定給三個小組中增派兩名高級科學家，到各小組后，各小組科研項目失敗概率如下表： 問如何分派科學家才能使三個小組都失敗的概率（即科研項目

23、最終失敗的概率）最??？,47,3動態(tài)規(guī)劃的應用(1),解：用逆序算法。設 階段：每個研究小組為一個階段，且,48,3動態(tài)規(guī)劃的應用(1),計算 當n=3時， 當n=2時，,49,3動態(tài)規(guī)劃的應用(1),當n=1時， 最優(yōu)解為 x1*=1，x2*=0，x3*=1；科研項目最終失敗的概率為0.060。,50,4動態(tài)規(guī)劃的應用(2)*,一、連續(xù)確定性動態(tài)規(guī)劃 對于狀態(tài)變量和決策變量只取連續(xù)值，過程的演變方式為確定性時，這種動態(tài)規(guī)劃問題就稱為連續(xù)確定性動態(tài)規(guī)劃問題。,51,4動態(tài)規(guī)劃的應用(2)*,機器負荷分配問題 例1 一種機器能在高低兩種不同的負荷狀態(tài)下工作。設機器在高負荷下生產(chǎn)時，產(chǎn)量函數(shù)為P1

24、=8u1，其中u1為在高負荷狀態(tài)下生產(chǎn)的機器數(shù)目，年完好率為a=0.7，即到年底有70的機器保持完好。在低負荷下生產(chǎn)時，產(chǎn)量函數(shù)為P2=5u2，其中u2為在低負荷狀態(tài)下生產(chǎn)的機器數(shù)目，年完好率為b=0.9。設開始生產(chǎn)時共有1000臺完好的機器，請問每年應該如何把完好機器分配給高、低兩種負荷下生產(chǎn)，才能使得5年內(nèi)生產(chǎn)的產(chǎn)品總產(chǎn)量最高。,52,4動態(tài)規(guī)劃的應用(2)*,解 建立動態(tài)規(guī)劃模型： 分為5個階段，每個階段為1年。設狀態(tài)變量sk表示在第k階段初擁有的完好機器數(shù)目；k=1,2,3,4,5。 決策變量xk表示第k階段中分配給高負荷狀態(tài)下生產(chǎn)的機器數(shù)目；k=1,2,3,4,5。顯然sk-xk為分

25、配給低負荷狀態(tài)下生產(chǎn)的機器數(shù)目。 狀態(tài)轉(zhuǎn)移方程為 sk+1=0.7xk+0.9(sk-xk) 階段指標 rk(sk,xk)=8xk+5(sk-xk) 最優(yōu)指標函數(shù) ，其 中k=1,2,3,4,5。 f6(s6)=0。,53,4動態(tài)規(guī)劃的應用(2)*,第5階段： 因為f5(s5)是x5的線性單調(diào)增函數(shù)，故有x5* =s5， 于是有f5(s5)=8s5。 第4階段：,54,4動態(tài)規(guī)劃的應用(2)*,同樣的，f4(s4)是x4的線性單調(diào)增函數(shù)，有x4*=s4 ， f4(s4)=13.6s4。 對前幾個階段依次類推，可得 f3(s3)=17.5s3， f2(s2)=20.75s2， f1(s1)=23

26、.72s1。 因為期初共有完好機器1000臺，故s1=1000。有f1(s1)=23.72s1 23720，即5年最大的產(chǎn)量為23720臺。得最優(yōu)解為 ， ， ， 。 這意味著前兩年應把年初完好機器完全投入低負荷生產(chǎn)， 后三年應把年初完好機器完全投入高負荷生產(chǎn)。,55,4動態(tài)規(guī)劃的應用(2)*,下一步工作是確定每年初的狀態(tài)，按照從前向后的順序依次計算出每年年初完好的機器數(shù)目。已知s1=1000,根據(jù)狀態(tài)轉(zhuǎn)移方程，有:,56,4動態(tài)規(guī)劃的應用(2)*,上面所討論的最優(yōu)策略過程，初始端狀態(tài)s1=1000臺是固定的，終點狀態(tài)s6沒有要求。這種情況下得到最優(yōu)決策稱為初始端固定終點自由的最優(yōu)策略。 如果

27、終點附加一定的條件，則問題就稱為“終端固定問題”。例如，規(guī)定在第5年度結(jié)束時仍要保持500臺機器完好（而不是278臺），應如何安排生產(chǎn)才能使得總產(chǎn)量最大？ 下面來分析： 根據(jù)終點條件有 可得,57,4動態(tài)規(guī)劃的應用(2)*,顯然，由于固定了終點的狀態(tài)，x5的取值受到了 約束。因此有 類似的， 容易解得 ，f4(s4)=21.7s4-7500。,58,4動態(tài)規(guī)劃的應用(2)*,依次類推，得 f3(s3)=24.5s3-7500 f2(s2)=27.1s2-7500 f1(s1)=29.4s1-7500 再采用順序方法遞推計算各年的狀態(tài)，有 s1=1000，,59,4動態(tài)規(guī)劃的應用(2)*,可見，

28、為了使終點完好的機器數(shù)量增加到500臺，需要安排前四年中全部完好機器都要投入低負荷生產(chǎn)，且在第5年，也只能全部投入高負荷。 相應的最優(yōu)指標為 f1(s1)=29.4s1-750021900。 可以看到，因為增加了附加條件，總產(chǎn)量f1(s1)要比終點自由情況下的產(chǎn)量要低。,60,二、離散隨機性動態(tài)規(guī)劃 隨機型的動態(tài)規(guī)劃是指狀態(tài)的轉(zhuǎn)移律是不確定的，即 對給定的狀態(tài)和決策，下一階段的到達狀態(tài)是具有確定概率 分布的隨機變量，這個概率分布由本階段的狀態(tài)和決策完全 確定。隨機型動態(tài)規(guī)劃的基本結(jié)構(gòu)如下圖：,4動態(tài)規(guī)劃的應用(2)*,sk,狀態(tài),xk,決策,概率,k階段的收益,p1,p2,pN,.,k+1階段

29、的狀態(tài)sk+1,c1,c2,cN,1,2,N,61,4動態(tài)規(guī)劃的應用(2)*,圖中N表示第k+1階段可能的狀態(tài)數(shù)，p1、p2、pN為給定狀態(tài)sk和決策xk的前提下，可能達到下一個狀態(tài)的概率。ci為從k階段狀態(tài)sk轉(zhuǎn)移到k+1 階段狀態(tài)為i時的指標函數(shù)值。 在隨機性的動態(tài)規(guī)劃問題中，由于下一階段到達的狀態(tài)和階段的效益值不確定，只能根據(jù)各階段的期望效益值進行優(yōu)化。,62,離散隨機性動態(tài)規(guī)劃,例2 某公司承擔一種新產(chǎn)品研制任務，合同要求三個月內(nèi)交出一件合格的樣品，否則將索賠2000元。根據(jù)有經(jīng)驗的技術(shù)人員估計，試制品合格的概率為0.4，每次試制一批的裝配費為200元，每件產(chǎn)品的制造成本為100元。每

30、次試制的周期為1個月。問該如何安排試制，每次生產(chǎn)多少件，才能使得期望費用最?。?63,離散隨機性動態(tài)規(guī)劃,解：把三次試制當作三個階段（k=1,2,3）,決策變量xk表示第k次生產(chǎn)的產(chǎn)品的件數(shù)；狀態(tài)變量sk表示第k次試制前是否已經(jīng)生產(chǎn)出合格品，如果有合格品，則sk=0；如果沒有合格品，記sk=1。最優(yōu)函數(shù)fk(sk)表示從狀態(tài)sk、決策xk出發(fā)的第k階段以后的最小期望費用。故有fk(0)0。 生產(chǎn)出一件合格品的概率為0.4，所以生產(chǎn)xk件產(chǎn)品都不合格的概率為 ，至少有一件合格品的概率為1- ，故有狀態(tài)轉(zhuǎn)移方程為,64,離散隨機性動態(tài)規(guī)劃,用C(xk)表示第k階段的費用，第k階段的費用包 括制造成本和裝配費用，故有 根據(jù)狀態(tài)轉(zhuǎn)移方程以及C(xk)，可得到,65,離散隨機性動態(tài)規(guī)劃,如果3個月后沒有試制出一件合格品，則要承擔 2000元的罰金，因此有f4(1)=20。 當k=3時，計算如下表：,6