第10章動態(tài)規(guī)劃學(xué)習(xí)教案

1、會計學(xué)1第第10章動態(tài)章動態(tài)(dngti)規(guī)劃規(guī)劃第一頁，共76頁。2第1頁/共75頁第二頁，共76頁。3 階段4本階段始點（狀態(tài)）本階段各終點（決策）到E的最短距離本階段最優(yōu)終點（最優(yōu)決策) E D1 D2 10* 6 10 6 E E第2頁/共75頁第三頁，共76頁。4 第三階段：有三個始點C1，C2，C3，終點有D1，D2，對始點和終點進(jìn)行分析和討論(toln)分別求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 1 多階段多階段(jidu

2、n)(jidun)決策過程最優(yōu)化問題舉例決策過程最優(yōu)化問題舉例 階段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=12 12 11 11 D2 D2 D1第3頁/共75頁第四頁，共76頁。5第二階段：有4個始點B1,B2,B3,B4，終點有C1,C2,C3。對始點和終點進(jìn)行分析和討論分別求B1,B2,B3,B4到C1,C2,C3 的最短路徑問題： 表10-3 分析(fnx)得知：如果經(jīng)過B1，則走B1-C2-D2-E； 如果經(jīng)過B2，則走B2-C

3、3-D1-E； 如果經(jīng)過B3，則走B3-C3-D1-E； 如果經(jīng)過B4，則走B4-C3-D1-E。 1 1 多階段決策過程多階段決策過程(guchng)(guchng)最優(yōu)化問題舉例最優(yōu)化問題舉例 階段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 C3第4頁/共75頁第五頁，共76頁。

4、6第一階段：只有1個始點A，終點(zhngdin)有B1,B2,B3,B4 。對始點和終點進(jìn)行分析和討論分別求A到B1,B2,B3,B4的最短路徑問題： 表10-4最后，可以得到：從A到E的最短路徑為A B4 C3 D1 E1 1 多階段決策過程多階段決策過程(guchng)(guchng)最優(yōu)化問題舉例最優(yōu)化問題舉例 階段1本階段始點(狀態(tài)) 本階段各終點（決策）到E的最短距離本階段最優(yōu)終點(最優(yōu)決策) B1 B2 B3 B4 A 4+12=16 3+13=163+14=172+12=14 12 C2第5頁/共75頁第六頁，共76頁。7 以上計算過程及結(jié)果，可用圖以上計算過程及結(jié)果，可用圖2

5、表示，可以看到，以上方法不僅表示，可以看到，以上方法不僅得到了從得到了從A到到D的最短路徑，同時，也得到了從圖中任一點到的最短路徑，同時，也得到了從圖中任一點到E的最的最短路徑。短路徑。 以上過程，僅用了以上過程，僅用了22次加法次加法(jif)，計算效率遠(yuǎn)高于窮舉法。，計算效率遠(yuǎn)高于窮舉法。BACBDBCDEC412312312332164724838675161060106121111121314144B1275121 1 多階段決策過程多階段決策過程(guchng)(guchng)最優(yōu)化問題最優(yōu)化問題舉例舉例第6頁/共75頁第七頁，共76頁。8一、基本概念： 1、階段k：表示決策順序的離

6、散的量，階段可以按時間或空間劃分。 2、狀態(tài)sk：能確定地表示決策過程當(dāng)前特征的量。狀態(tài)可以是數(shù)量，也可以是字符，數(shù)量狀態(tài)可以是連續(xù)的，也可以是離散的。 3、決策xk：從某一狀態(tài)向下一狀態(tài)過渡時所做的選擇。決策是所在狀態(tài)的函數(shù)，記為xk(sk)。 決策允許集合(jh)Dk(sk)：在狀態(tài)sk下，允許采取決策的全體。 4、策略Pk,n(sk)：從第k階段開始到最后第n階段的決策序列，稱k子策略。P1,n(s1)即為全過程策略。 5、狀態(tài)轉(zhuǎn)移方程 sk+1=Tk(sk, xk)：某一狀態(tài)以及該狀態(tài)下的決策，與下一狀態(tài)之間的函數(shù)關(guān)系。2 2 基本概念、基本方程基本概念、基本方程(fngchng)(f

7、ngchng)與最優(yōu)化與最優(yōu)化原理原理第7頁/共75頁第八頁，共76頁。9 6、階段指標(biāo)函數(shù)、階段指標(biāo)函數(shù)vk(sk, xk)：從狀態(tài)：從狀態(tài)sk出發(fā)，選擇決策出發(fā)，選擇決策xk所產(chǎn)生的第所產(chǎn)生的第k階段指階段指標(biāo)。標(biāo)。 過程指標(biāo)函數(shù)過程指標(biāo)函數(shù)Vk,n(sk, xk, xk+1, xn)：從狀態(tài)：從狀態(tài)sk出發(fā)，選擇決策出發(fā)，選擇決策xk, xk+1, , xn所產(chǎn)生的過程指標(biāo)。動態(tài)規(guī)劃要求過程指標(biāo)具有可分離所產(chǎn)生的過程指標(biāo)。動態(tài)規(guī)劃要求過程指標(biāo)具有可分離性，即性，即 Vk,n(sk, xk, xk+1, , xn) = vk(sk, xk)+Vk+1(sk+1, xk+1, , xn)稱指

8、標(biāo)具有可加性，或稱指標(biāo)具有可加性，或 Vk,n(sk, xk, xk+1, , xn) = vk(sk, xk)Vk+1(sk+1, xk+1, , xn)稱指標(biāo)具有可乘性。稱指標(biāo)具有可乘性。二、基本二、基本(jbn)方程：方程： 最優(yōu)指標(biāo)函數(shù)最優(yōu)指標(biāo)函數(shù)fk(sk)：從狀態(tài)：從狀態(tài)sk出發(fā)，對所有的策略出發(fā)，對所有的策略Pk,n，過程指，過程指標(biāo)標(biāo)Vk,n的最優(yōu)值，即的最優(yōu)值，即 ),()(,)(nkknksDxkkPsVsfoptkkk2 2 基本概念、基本方程基本概念、基本方程(fngchng)(fngchng)與最優(yōu)化原與最優(yōu)化原理理第8頁/共75頁第九頁，共76頁。10 對于可加性指

9、標(biāo)函數(shù)，上式可以寫為對于可加性指標(biāo)函數(shù)，上式可以寫為 上式中上式中“opt”表示表示“max”或或“min”。對于可乘性指標(biāo)。對于可乘性指標(biāo)函數(shù)，上式可以函數(shù)，上式可以寫為寫為 以上式子稱為動態(tài)規(guī)劃最優(yōu)指標(biāo)的遞推方程，是動態(tài)以上式子稱為動態(tài)規(guī)劃最優(yōu)指標(biāo)的遞推方程，是動態(tài)規(guī)劃的基本規(guī)劃的基本方程。方程。 終端條件：為了使以上的遞推方程有遞推的起點，必終端條件：為了使以上的遞推方程有遞推的起點，必須要設(shè)定須要設(shè)定(sh dn)最最優(yōu)指標(biāo)的終端條件，一般最后一個狀態(tài)優(yōu)指標(biāo)的終端條件，一般最后一個狀態(tài)n+1下最優(yōu)指標(biāo)下最優(yōu)指標(biāo)fn+1(sn+1) = 0。nksfxsvsfkkkkksDxkkoptk

10、kk, 2 , 1)(),()(11)(nksfxsvsfkkkkksDxkkoptkkk, 2 , 1)(),()(11)(2 2 基本基本(jbn)(jbn)概念、基本概念、基本(jbn)(jbn)方程與最方程與最優(yōu)化原理優(yōu)化原理第9頁/共75頁第十頁，共76頁。11三、最優(yōu)化原理三、最優(yōu)化原理(yunl) 作為整個過程的最優(yōu)策略具有如下性質(zhì)：作為整個過程的最優(yōu)策略具有如下性質(zhì)： 不管在此最優(yōu)策略上的某個狀態(tài)以前的狀不管在此最優(yōu)策略上的某個狀態(tài)以前的狀態(tài)和決策如何，對該狀態(tài)來說，以后的所有決態(tài)和決策如何，對該狀態(tài)來說，以后的所有決策必定構(gòu)成最優(yōu)子策略。就是說，最優(yōu)策略的策必定構(gòu)成最優(yōu)子策略

11、。就是說，最優(yōu)策略的任意子策略都是最優(yōu)的。任意子策略都是最優(yōu)的。2 2 基本基本(jbn)(jbn)概念、基本概念、基本(jbn)(jbn)方程與最優(yōu)化方程與最優(yōu)化原理原理第10頁/共75頁第十一頁，共76頁。12一、資源分配問題一、資源分配問題 例例2. 某公司擬將某種設(shè)備某公司擬將某種設(shè)備5臺，分配給所屬的甲、乙、丙三個臺，分配給所屬的甲、乙、丙三個工工廠。各工廠廠。各工廠(gngchng)獲得此設(shè)備后，預(yù)測可創(chuàng)造的利潤如表獲得此設(shè)備后，預(yù)測可創(chuàng)造的利潤如表10-5所示，問這所示，問這5臺設(shè)備應(yīng)如何分配給這臺設(shè)備應(yīng)如何分配給這3個工廠個工廠(gngchng)，使得所創(chuàng)造的總，使得所創(chuàng)造的總

12、利潤為最大？利潤為最大？ 表表10-5 盈利 工廠設(shè)備臺數(shù) 甲 廠 乙 廠 丙 廠 0 0 0 0 1 3 5 4 2 7 10 6 3 9 11 11 4 12 11 12 5 13 11 123 3 動態(tài)動態(tài)(dngti)(dngti)規(guī)劃的應(yīng)用規(guī)劃的應(yīng)用(1)(1)第11頁/共75頁第十二頁，共76頁。13解：將問題按工廠分為三個階段，甲、乙、丙三個廠分別編號為1、2、3廠。設(shè) sk= 分配給第k個廠至第3個廠的設(shè)備臺數(shù)（k=1、2、3）。 xk=分配給第k個設(shè)備臺數(shù)。 已知s1=5, 并有 從與的定義，可知以下(yxi)我們從第三階段開始計算。222223),(xsxsTskskx33

13、xs 3 3 動態(tài)動態(tài)(dngti)(dngti)規(guī)劃的應(yīng)用規(guī)劃的應(yīng)用(1)(1)111112),(xsxsTs第12頁/共75頁第十三頁，共76頁。14 第三階段第三階段: 顯然將臺設(shè)備都分配給第顯然將臺設(shè)備都分配給第3工廠時工廠時，也就是時，第也就是時，第3階段的指標(biāo)值（即第階段的指標(biāo)值（即第3廠的盈利）廠的盈利）為最大，即為最大，即 由于第由于第3階段是最后的階段，故有階段是最后的階段，故有 其中可取值為其中可取值為0,1,2,3,4,5。其數(shù)值。其數(shù)值(shz)計算見表計算見表106。 )5 , 4 , 3 , 2 , 1 , 0(33ss).,(),(max)(333333333ss

14、rxsrsfx3x),(),(max3333333ssrxsrx3 3 動態(tài)規(guī)劃動態(tài)規(guī)劃(guhu)(guhu)的應(yīng)用的應(yīng)用(1)(1)33xs 第13頁/共75頁第十四頁，共76頁。15 表表106 012345000014 4126623111134121245121253x3s),(333xsr)(33sf3*x3 3 動態(tài)規(guī)劃動態(tài)規(guī)劃(guhu)(guhu)的應(yīng)用的應(yīng)用(1)(1)第14頁/共75頁第十五頁，共76頁。16 其中表示取3子過程上最優(yōu)指標(biāo)值時的決策，例如在表10-6中可知當(dāng)=4時，有有此時，即當(dāng)時，此時取（把4臺設(shè)備分配給第3廠）是最優(yōu)決策，此時階段指標(biāo)值（盈利(yn l

15、)）為12，最優(yōu)3子過程最優(yōu)指標(biāo)值也為12。 第二階段： 當(dāng)把臺設(shè)備分配給第2工廠和第3工廠時，則對每個值，有一種最優(yōu)分配方案，使最大盈利(yn l)即最優(yōu)2子過程最優(yōu)指標(biāo)函數(shù)值為 3*x)(33sf3x3s;12)4 , 4(3r,12)4(3f43*x43s43x)5 , 4 , 3 , 2 , 1 , 0(22ss2s)(),(max)(33222222sfxsrsfx3 3 動態(tài)規(guī)劃動態(tài)規(guī)劃(guhu)(guhu)的應(yīng)用的應(yīng)用(1)(1)第15頁/共75頁第十六頁，共76頁。17因為上式也可寫成其數(shù)值(shz)計算如表107所示。表107 , 223xss0123450 00104 5

16、1206 54 1023011 56 110 1424012 114110 161,25012 512 116114 1102122x2s)(),(233222xsfxsr)(22sf2*x00050104101156101110)(),(max)(223222222xsfxsrsfx3 3 動態(tài)規(guī)劃動態(tài)規(guī)劃(guhu)(guhu)的應(yīng)用的應(yīng)用(1)(1)第16頁/共75頁第十七頁，共76頁。18 其中在的這一行里，當(dāng)時，這里從表105中可知(k zh)，把1臺設(shè)備交給乙廠所得盈利數(shù)即可，知，這里從表106查即可知(k zh)=11。同樣可知(k zh)當(dāng)時，可知(k zh) ;當(dāng)時，；當(dāng)時，

17、；當(dāng)時， ；由于，不可能分2廠5臺設(shè)備，故時，欄空著不填。從這些數(shù)值中取得最大即得，即有=16。在此行中我們在取最大值的 上面加一橫以示區(qū)別，也可知(k zh)這時的最優(yōu)決策為1或2。42s12x16115) 3() 1 , 4() 14() 1 , 4()(),(3232223222frfrxsfxsr) 1 , 4(2r5) 1 , 4(2r)3()14(33ff) 3(3f)3(3f22x16610)2()2 , 4()24()2 , 4()(),(3232223222frfrxsfxsr02x12120)04()0 , 4(32 fr32x411)34()3 , 4(32 fr42x1

18、1011)44()4 , 4(32 fr42s52x)54()5 , 4(32 fr)4(2f)4(2f)(),(223222xsfxsr2x3 3 動態(tài)動態(tài)(dngti)(dngti)規(guī)劃的應(yīng)用規(guī)劃的應(yīng)用(1)(1)第17頁/共75頁第十八頁，共76頁。19第一階段：第一階段：把臺設(shè)備把臺設(shè)備(shbi)分配給第分配給第1，第，第2，第，第3廠時廠時，最大，最大盈利為其中可取值盈利為其中可取值0,1,2,3,4,5.數(shù)值計算見表數(shù)值計算見表108 表表10-8 然后按計算表格的順序推算，可知最優(yōu)分配方案有兩個然后按計算表格的順序推算，可知最優(yōu)分配方案有兩個： 1.由于，根據(jù)，查表由于，根據(jù)，

19、查表107可可知，再由知，再由 ，求得。即，求得。即分配分配給甲廠給甲廠0臺，乙廠臺，乙廠2臺，丙廠臺，丙廠3臺。臺。 2.由于，根據(jù)由于，根據(jù) ，查表，查表107可可 )5(11ss),5(), 5(max)5(111111xfxrfx1x0123455 316 9+10 12+5 13+0 21 0,21x1s)5(), 5(1211xfxr210147)(1xf1*x01*x5051*12xss02*x3252*23xss333* sx21*x3251*12xss3 3 動態(tài)規(guī)劃動態(tài)規(guī)劃(guhu)(guhu)的應(yīng)用的應(yīng)用(1)(1)第18頁/共75頁第十九頁，共76頁。20知，再由 ,

20、求得，即分配給甲廠2臺，乙廠2臺，丙廠1臺。這兩種分配方案都能得到(d do)最高的總盈利21萬元。 22*x1232*23xss133* sx3 3 動態(tài)動態(tài)(dngti)(dngti)規(guī)劃的應(yīng)用規(guī)劃的應(yīng)用(1)(1)第19頁/共75頁第二十頁，共76頁。21二、背包問題二、背包問題 設(shè)有設(shè)有n種物品，每一種物品數(shù)量無限。第種物品，每一種物品數(shù)量無限。第i種物品每種物品每件件重量為重量為wi公斤，每件價值公斤，每件價值ci元?，F(xiàn)有一只可裝載重量為元?，F(xiàn)有一只可裝載重量為W公斤的背包，求各種物品應(yīng)各取多少件放入背包，使背公斤的背包，求各種物品應(yīng)各取多少件放入背包，使背包中物品的價值最高。包中物

21、品的價值最高。 這個問題可以用整數(shù)規(guī)劃模型這個問題可以用整數(shù)規(guī)劃模型(mxng)來描述。來描述。設(shè)設(shè)xi為第為第i種種物品裝入背包的件數(shù)（物品裝入背包的件數(shù)（i =1, 2, , n），背包中物品的總），背包中物品的總價值為價值為z，則，則 Max z = c1x1+c2x2+ +cnxn s.t. w1x1+w2x2+wnxnW x1, x2, , xn0 且為整數(shù)。且為整數(shù)。3 3 動態(tài)規(guī)劃動態(tài)規(guī)劃(guhu)(guhu)的應(yīng)用的應(yīng)用(1)(1)第20頁/共75頁第二十一頁，共76頁。22 下面用動態(tài)規(guī)劃逆序解法求解它。設(shè)階段變量k：第k次裝載第k種物品（k=1, 2, , n）狀態(tài)變量s

22、k：第k次裝載時背包還可以裝載的重量；決策變量uk = xk：第k次裝載第k種物品的件數(shù)；決策允許集合：Dk(sk) = xk | 0 xksk/wk，xk為整數(shù)；狀態(tài)轉(zhuǎn)移(zhuny)方程： sk+1 = sk wkxk；階段指標(biāo)： vk = ckxk；最優(yōu)過程指標(biāo)函數(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 3 動態(tài)動態(tài)(dngti)(dngti)規(guī)劃的應(yīng)用規(guī)劃的應(yīng)用(1)(1)第21頁/共75頁

23、第二十二頁，共76頁。23例例3.某咨詢公司有某咨詢公司有10個工作日可以去處理四種類型個工作日可以去處理四種類型的咨的咨詢項目，每種類型的咨詢項目中待處理的客戶數(shù)量、處理詢項目，每種類型的咨詢項目中待處理的客戶數(shù)量、處理每個每個客戶所需工作日數(shù)以及所獲得的利潤如表客戶所需工作日數(shù)以及所獲得的利潤如表109所示。顯所示。顯然該公然該公司在司在10天內(nèi)不能處理完所有的客戶，它可以自己挑選一些天內(nèi)不能處理完所有的客戶，它可以自己挑選一些客客戶，其余的請其他咨詢公司去做，應(yīng)如何戶，其余的請其他咨詢公司去做，應(yīng)如何(rh)選擇客戶選擇客戶使得在這使得在這10個工作日中獲利最大？個工作日中獲利最大？ 表

24、表109 咨詢項目類型待處理客戶數(shù)處理每個客戶所需工作日數(shù)處理每個客戶所獲利潤1234432213472811203 3 動態(tài)規(guī)劃動態(tài)規(guī)劃(guhu)(guhu)的應(yīng)用的應(yīng)用(1)(1)第22頁/共75頁第二十三頁，共76頁。24解：用動態(tài)規(guī)劃來求解此題。解：用動態(tài)規(guī)劃來求解此題。我們把此問題分成四個階段我們把此問題分成四個階段(jidun)，第一階段，第一階段(jidun)我我們決策將們決策將處理多少個第一種咨詢項目類型中的客戶，第二階段處理多少個第一種咨詢項目類型中的客戶，第二階段(jidun)決決策將處理多少個第二種咨詢項目類型中的客戶，第三階策將處理多少個第二種咨詢項目類型中的客戶，第

25、三階段、第四階段段、第四階段(jidun)我們也將作出類似的決策。我們設(shè)我們也將作出類似的決策。我們設(shè)分配給第分配給第k種咨詢項目到第四種咨詢項目的所種咨詢項目到第四種咨詢項目的所有客戶的總工作日（第有客戶的總工作日（第k階段階段(jidun)的狀態(tài)變量）。的狀態(tài)變量）。 =在第在第k種咨詢項目中處理客戶的數(shù)量（第種咨詢項目中處理客戶的數(shù)量（第k階段階段(jidun)的決策變量）。的決策變量）。已知已知10并有并有 kx1s,),(111112xsxsTsks3 3 動態(tài)規(guī)劃動態(tài)規(guī)劃(guhu)(guhu)的應(yīng)用的應(yīng)用(1)(1)第23頁/共75頁第二十四頁，共76頁。25 并從與的定義可知并

26、從與的定義可知從第四階段開始從第四階段開始(kish)計算：計算：顯然將個工作日盡可能分配給第四顯然將個工作日盡可能分配給第四類咨詢項目，即時，第四階段的指標(biāo)值為最大，類咨詢項目，即時，第四階段的指標(biāo)值為最大，其中，表示取不大于的最大整數(shù)，符號為其中，表示取不大于的最大整數(shù)，符號為取整符號，故有取整符號，故有由于第四階段是最后的階段，故有由于第四階段是最后的階段，故有,3),(222223xsxsTs.4),(333334xsxsTskskx447xs 4s)10, 1 , 0(4s7/44sx 7/4s7/4s ).7/,(),(max4444444ssrxsrx),7/,(),(max)(

27、4444*44444ssrxsrsfx3 3 動態(tài)動態(tài)(dngti)(dngti)規(guī)劃的應(yīng)用規(guī)劃的應(yīng)用(1)(1)第24頁/共75頁第二十五頁，共76頁。26因為因為(yn wi)至多為至多為10，其數(shù)值計算見表，其數(shù)值計算見表1010。 表表10104s01000100200300400500600702018020190201100114x4s),(444xsr)(44sf4*x0000000202020203 3 動態(tài)規(guī)劃動態(tài)規(guī)劃(guhu)(guhu)的應(yīng)用的應(yīng)用(1)(1)第25頁/共75頁第二十六頁，共76頁。27第三階段：第三階段：當(dāng)把個工作日分配給第四類和第當(dāng)把個工作日分配給第

28、四類和第三類咨詢項目三類咨詢項目(xingm)時，則對每個值，都有一種時，則對每個值，都有一種最優(yōu)分配方最優(yōu)分配方案，使其最大盈利即最優(yōu)案，使其最大盈利即最優(yōu)3子過程最優(yōu)指標(biāo)函數(shù)值為子過程最優(yōu)指標(biāo)函數(shù)值為 因為因為因為至多為因為至多為10，所以的取值可為，所以的取值可為0,1,2。其數(shù)值。其數(shù)值計算計算見表見表1011。)10, 3 , 2 , 1 , 0(33ss3s. )(),(max)(33222222sfxsrsfx2233xss. )4(),(max)(334333333xsfxsrsfx3s3x3 3 動態(tài)規(guī)劃動態(tài)規(guī)劃(guhu)(guhu)的應(yīng)用的應(yīng)用(1)(1)第26頁/共75

29、頁第二十七頁，共76頁。28 表表1011 0 1 2000 1 00 200 300 40011 1 50011 1 60011 1 7 11+0 20 0 8020 11+0 22 2 9020 11+0 22 2 10020 11+0 22 23x3s)4(),(334333xsfxsr)(33sf3*x000000200011011011022022022003 3 動態(tài)規(guī)劃動態(tài)規(guī)劃(guhu)(guhu)的應(yīng)用的應(yīng)用(1)(1)第27頁/共75頁第二十八頁，共76頁。29 第二階段：第二階段： 同樣以每個值都有一種同樣以每個值都有一種(y zhn)最優(yōu)分配方案，使其最優(yōu)分配方案，使其

30、最大盈利即最大盈利即最優(yōu)最優(yōu)2子過程最優(yōu)指標(biāo)函數(shù)值為：子過程最優(yōu)指標(biāo)函數(shù)值為：因為，故有因為，故有因為至多為因為至多為10，所以的取值為，所以的取值為0,1,2,3。其數(shù)值計算。其數(shù)值計算見表見表1012。. )3(),(max)(223222222xsfxsrsfx2233xss. )3(),(max)(223222222xsfxsrsfx2s2x2s3 3 動態(tài)動態(tài)(dngti)(dngti)規(guī)劃的應(yīng)用規(guī)劃的應(yīng)用(1)(1)第28頁/共75頁第二十九頁，共76頁。30表表10-12第29頁/共75頁第三十頁，共76頁。31 第一階段：第一階段： 我們我們(w men)已知，又因為已知，又因

31、為 ，同，同樣有樣有 因為因為 ,故可取值為故可取值為0,1,2, ,10。其數(shù)值計算。其數(shù)值計算見表見表1013。 表表1013101s. )(),(max)(112111111xsfxsrsfx112xss.)10(),10(max)10(121111xfxrfx101s1x3 3 動態(tài)規(guī)劃動態(tài)規(guī)劃(guhu)(guhu)的應(yīng)用的應(yīng)用(1) (1) 第30頁/共75頁第三十一頁，共76頁。32 從 表 1 0 1 3 可 知 ， 從 而 得10010，在表1012的的這一行可知，由，查表1011的的這一行可知，最后由，查表10-10的的這一行得，綜上所述得最優(yōu)解為：此時最大盈利為28?，F(xiàn)在

32、我們不妨假設(shè)該咨詢公司的工作計劃有所改變，只有8個工作日來處理這四類咨詢項目，那么該咨詢公司如何選擇客戶使得獲利最大呢？我們不必從頭開始重做這個問題，而只要在第一階段上把改成8，重新(chngxn)計算就可得到結(jié)果，如表1014所示，這是動態(tài)規(guī)劃的一個好處。28)10(1f01*x1*210 xs102s12*x731032*23xss73s03*x7073*34xss74s14*x0, 1, 03*2*1*xxx, 14*x4s3 3 動態(tài)規(guī)劃動態(tài)規(guī)劃(guhu)(guhu)的應(yīng)用的應(yīng)用(1) (1) 第31頁/共75頁第三十二頁，共76頁。33表表1014如上一樣可從表如上一樣可從表101

33、4,1012,1011,1010得到兩組最優(yōu)解得到兩組最優(yōu)解如下：如下：它們的最優(yōu)解（即最大盈利）都為它們的最優(yōu)解（即最大盈利）都為22。一旦咨詢的工作日不是減少而是增加，那么我們不僅一旦咨詢的工作日不是減少而是增加，那么我們不僅(bjn)要重新計要重新計算第一階段，而且要在第二、第三、第四階段的計算表上補上增加算第一階段，而且要在第二、第三、第四階段的計算表上補上增加的工作日的新的信息，也可得到新的結(jié)果。的工作日的新的信息，也可得到新的結(jié)果。3042)4321xxxx1001)4*3*2*1*xxxx3 3 動態(tài)動態(tài)(dngti)(dngti)規(guī)劃的應(yīng)用規(guī)劃的應(yīng)用(1) (1) 第32頁/共

34、75頁第三十三頁，共76頁。34 實際上，背包問題實際上，背包問題(wnt)我們也可以用整數(shù)規(guī)劃來求解，如果背包攜帶物品重量的限制為我們也可以用整數(shù)規(guī)劃來求解，如果背包攜帶物品重量的限制為W公斤，這公斤，這N種物品中第種物品中第i種物品的重量為，價值為，第種物品的重量為，價值為，第i種物品的總數(shù)量的，我們可以設(shè)表示攜帶第種物品的總數(shù)量的，我們可以設(shè)表示攜帶第i種物品的數(shù)量，則其數(shù)學(xué)模型為：種物品的數(shù)量，則其數(shù)學(xué)模型為：S.T. 且為整數(shù)。且為整數(shù)。 我們不妨用此模型去求解例我們不妨用此模型去求解例3，也一定得出同樣的結(jié)果。，也一定得出同樣的結(jié)果。iwicinix,max1Niiixcf0),

35、2 , 1(1iiiNiiixNinxWxw3 3 動態(tài)規(guī)劃動態(tài)規(guī)劃(guhu)(guhu)的應(yīng)用的應(yīng)用(1) (1) 第33頁/共75頁第三十四頁，共76頁。35三、生產(chǎn)與存貯問題 例4.某公司為主要電力公司生產(chǎn)大型變壓器，由于電力采取預(yù)訂方式(fngsh)購買，所以該公司可以預(yù)測未來幾個月的需求量。為確保需求，該公司為新的一年前四個月制定一項生產(chǎn)計劃，這四個月的需求如表1015所示。生產(chǎn)成本隨著生產(chǎn)數(shù)量而變化。調(diào)試費為4，除了調(diào)度費用外，每月生產(chǎn)的頭兩臺各花費為2，后兩臺花費為1。最大生產(chǎn)能力每月為4臺，生產(chǎn)成本如表1016所示。表10153 3 動態(tài)規(guī)劃動態(tài)規(guī)劃(guhu)(guhu)的

36、應(yīng)用的應(yīng)用(1) (1) 第34頁/共75頁第三十五頁，共76頁。36 表表1016每臺變壓器在倉庫中由這個月存到下個月的儲存費為每臺變壓器在倉庫中由這個月存到下個月的儲存費為1，倉庫的最大儲存能力為倉庫的最大儲存能力為3臺，另外，知道在臺，另外，知道在1月月1日時倉庫里存日時倉庫里存有一臺變壓器，要求在有一臺變壓器，要求在4月月30日倉庫的庫存量為零。試問該公日倉庫的庫存量為零。試問該公司應(yīng)如何制定生產(chǎn)計劃司應(yīng)如何制定生產(chǎn)計劃(jhu)，使得四個月的生產(chǎn)成本和儲存總費，使得四個月的生產(chǎn)成本和儲存總費用最少？用最少？解：我們按月份來劃分階段，第解：我們按月份來劃分階段，第i個月為第個月為第i階

37、段：（階段：（i=1,2,3,4). 設(shè)設(shè) 為第為第k階段期初庫存量；階段期初庫存量； k=1,2,3,4 ks3 3 動態(tài)動態(tài)(dngti)(dngti)規(guī)劃的應(yīng)用規(guī)劃的應(yīng)用(1) (1) 第35頁/共75頁第三十六頁，共76頁。37為第為第k階段生產(chǎn)量階段生產(chǎn)量(chnling)； k=1,2,3,4為第為第k階段需求量；階段需求量； k=1,2,3,4，這已在表，這已在表10-15中告訴我們。中告訴我們。因為下個月的庫存量等于上個月的庫存量加上上個月的因為下個月的庫存量等于上個月的庫存量加上上個月的產(chǎn)量產(chǎn)量(chnling)減去上個月的需求量，我們就得到了如下狀態(tài)轉(zhuǎn)移方減去上個月的需求量

38、，我們就得到了如下狀態(tài)轉(zhuǎn)移方程：程：因為，故有因為，故有因為，故有因為，故有kxkd, 1112dxss11s, 1121dxs, 2223dxss, 3334dxss, 4445dxss05s, 4440dxs3 3 動態(tài)規(guī)劃動態(tài)規(guī)劃(guhu)(guhu)的應(yīng)用的應(yīng)用(1) (1) 第36頁/共75頁第三十七頁，共76頁。38由于必須要滿足由于必須要滿足(mnz)需求，則有需求，則有通過移項得到通過移項得到 另一方面，第另一方面，第k階段的生產(chǎn)量必不大于同期的生產(chǎn)能力階段的生產(chǎn)量必不大于同期的生產(chǎn)能力（4臺），也不大于第臺），也不大于第k階段至第四階段的需求之和與第階段至第四階段的需求之和

39、與第k階段階段期初庫存量之差，否則第期初庫存量之差，否則第k階段的生產(chǎn)量就要超過從第階段的生產(chǎn)量就要超過從第k階段階段至第四階段的總需求，故有至第四階段的總需求，故有以下我們從第四階段開始計算：以下我們從第四階段開始計算：從以上的狀態(tài)轉(zhuǎn)移方程可知從以上的狀態(tài)轉(zhuǎn)移方程可知這樣就有這樣就有),4, 3 ,2, 1(,kdxskkkkkksdxkx44 ,)(minkikiksdx,0444dxs,34444ssdx)3 ,(),(min)(444444444ssrxsrsfx3 3 動態(tài)規(guī)劃動態(tài)規(guī)劃(guhu)(guhu)的應(yīng)用的應(yīng)用(1) (1) 第37頁/共75頁第三十八頁，共76頁。39 這

40、里的階段指標(biāo)可以分成兩部分，即生產(chǎn)成本與這里的階段指標(biāo)可以分成兩部分，即生產(chǎn)成本與儲存費，即為儲存費，即為 由于第四階段末要求庫存為零，即有，由于第四階段末要求庫存為零，即有，這樣這樣(zhyng)可得可得 對于每個的可行值，的值列于表對于每個的可行值，的值列于表1017。 表表1017),(nnnxsr),()(),(nnnnnnnnxshxcxsr001),(444xsh)3()3 ,()3()3 ,()(444444444444scsshscssrsf4s)(44sf3 3 動態(tài)規(guī)劃動態(tài)規(guī)劃(guhu)(guhu)的應(yīng)用的應(yīng)用(1) (1) 第38頁/共75頁第三十九頁，共76頁。40表

41、中當(dāng)時，可知第四階段要生產(chǎn)表中當(dāng)時，可知第四階段要生產(chǎn)臺，從表臺，從表1016可知總成本為可知總成本為9，同樣可以算出當(dāng)為，同樣可以算出當(dāng)為1,2,3時時的情況的情況(qngkung)，結(jié)果已列于表，結(jié)果已列于表1017中。中。第三階段：第三階段：此時有：此時有：因為以及所以有因為以及所以有例如，當(dāng)?shù)谌A段初庫存量時，生產(chǎn)量為例如，當(dāng)?shù)谌A段初庫存量時，生產(chǎn)量為2時，時，則所以生產(chǎn)成本為則所以生產(chǎn)成本為8，第三階段末庫存，第三階段末庫存為為2時，儲存費為，而時，儲存費為，而04s3344sx4s)(1)(),()(),(3333333333333dxsxcxshxcxsr,3334dxss,

42、13d)() 1(1)(min)(443333)4,4min(133333sfxsxcsfsxs) 1() 1(1)(min3343333)4,4min(1333xsfxsxcsxs13s3x2121333dxs221),2()()(4333444fdxsfsf3 3 動態(tài)規(guī)劃動態(tài)規(guī)劃(guhu)(guhu)的應(yīng)用的應(yīng)用(1) (1) 第39頁/共75頁第四十頁，共76頁。41查1017表可知，這樣可知，填入表1018中的欄內(nèi)，其他結(jié)果(ji gu)如表1018所示 ： 表1018 第二階段：因為所以有6) 2 (4f,16628)2()2 , 1 (43 fr2, 133xs, 422232

43、dxssd3 3 動態(tài)規(guī)劃動態(tài)規(guī)劃(guhu)(guhu)的應(yīng)用的應(yīng)用(1) (1) 第40頁/共75頁第四十一頁，共76頁。42 計算結(jié)果如表1019所示。 表1019 )(),(min)(33222)4,8min(422222sfxsrsfsxs)(),()(min3322222)4,8min(4222sfxshxcsxs)()(1)(min222322222)4,8min(4222dxsfdxsxcsxs)4()4(1)(min2232222)4,8min(4222xsfxsxcsxs3 3 動態(tài)動態(tài)(dngti)(dngti)規(guī)劃的應(yīng)用規(guī)劃的應(yīng)用(1) (1) 第41頁/共75頁第四十

44、二頁，共76頁。43第一階段：第一階段：因為因為(yn wi)故有故有計算結(jié)果見表計算結(jié)果見表1020。 表表1020, 1, 2211111sdxssd)(),(min) 1 ()(22111411111sfxsrfsfx)21 ()21 (1)(min12111411xfxxcx3 3 動態(tài)規(guī)劃動態(tài)規(guī)劃(guhu)(guhu)的應(yīng)用的應(yīng)用(1) (1) 第42頁/共75頁第四十三頁，共76頁。44利用遞推關(guān)系利用遞推關(guān)系(gun x)可以從表可以從表1020，表，表1019，表，表1018和表和表1017得到兩組最優(yōu)解：得到兩組最優(yōu)解： 這時有最低總成本這時有最低總成本29。0441)43

45、21xxxx3042)4321xxxx3 3 動態(tài)規(guī)劃動態(tài)規(guī)劃(guhu)(guhu)的應(yīng)用的應(yīng)用(1) (1) 第43頁/共75頁第四十四頁，共76頁。45高級科學(xué)家小組12300.400.600.8010.200.400.5020.150.200.30第44頁/共75頁第四十五頁，共76頁。46階段123小組123第45頁/共75頁第四十六頁，共76頁。47 s3 f3*(s3) x3*008001050120302 x2s2f2(s2,x2)=P2(x2) f3*(s2-x2) f2*(s2) x2*012004804801030032030020180200160162第46頁/共75

46、頁第四十七頁，共76頁。48 x1s1f1(s1,x1)=P1(x1) f2*(s1-x1)f2*(s2)x2*01220064 0060 0072 0060 1第47頁/共75頁第四十八頁，共76頁。49第48頁/共75頁第四十九頁，共76頁。50第49頁/共75頁第五十頁，共76頁。51)()58max)(11kkkkkkksfxsxsf（kksx 0第50頁/共75頁第五十一頁，共76頁。52 )(2 .126 .13max)(9 . 07 . 0 8)(58max8)(58max)()(58max)(44404444440544405544404444444444xsxxsxxsxsx

47、sxsfxsxsfsxsxsxsx 第51頁/共75頁第五十二頁，共76頁。530*1x0*2x3*3sx 4*4sx 5*5sx 第52頁/共75頁第五十三頁，共76頁。549009 . 0)(9 . 07 . 01*11*12sxsxs8109 . 0)(9 . 07 . 02*22*23sxsxs5677 . 0)(9 . 07 . 03*33*34sxsxs3977 . 0)(9 . 07 . 04*44*45sxsxs第53頁/共75頁第五十四頁，共76頁。55500)(9 . 07 . 05556xsxs25005 . 455sx第54頁/共75頁第五十五頁，共76頁。5675005 .18)25005 . 4(5)25005 . 4(8max)(555555sssssf75007 . 07 .21max75005 .18)(58max)()(58max)(4405444055444044444444xssxsxsfxsxsfsxsxsx0*4x第55頁/共75頁第五十六頁，共76頁。570