管理運(yùn)籌學(xué)_動態(tài)規(guī)劃

1、管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué)1第十章第十章 動態(tài)規(guī)劃動態(tài)規(guī)劃1多階段決策過程最優(yōu)化問題舉例多階段決策過程最優(yōu)化問題舉例2基本概念、基本方程與最優(yōu)化原理基本概念、基本方程與最優(yōu)化原理3動態(tài)規(guī)劃的應(yīng)用動態(tài)規(guī)劃的應(yīng)用(1)4動態(tài)規(guī)劃的應(yīng)用動態(tài)規(guī)劃的應(yīng)用(2)管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué)21 1多階段決策過程最優(yōu)化問題舉例多階段決策過程最優(yōu)化問題舉例例例1 最短路徑問題最短路徑問題 下圖表示從起點(diǎn)A到終點(diǎn)E之間各點(diǎn)的距離。求A到E的最短路徑。BACBDBCDEC4123123123221647248386756110643751管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué)31 1多階段決策過程最優(yōu)化問題舉例多階段決策

2、過程最優(yōu)化問題舉例用窮舉法的計(jì)算量用窮舉法的計(jì)算量: 如果從A到E的站點(diǎn)有k個(gè)，除A、E之外每站有3個(gè)位置則總共有3k-12條路徑； 計(jì)算各路徑長度總共要進(jìn)行 (k+1) 3k-12次加法以及3k-12-1次比較。隨著 k 的值增加時(shí)，需要進(jìn)行的加法和比較的次數(shù)將迅速增加； 例如當(dāng) k=20時(shí)，加法次數(shù)為 4.25508339662271015 次，比較 1.37260754729771014 次。若用1億次/秒的計(jì)算機(jī)計(jì)算需要約508天。管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué)41 1多階段決策過程最優(yōu)化問題舉例多階段決策過程最優(yōu)化問題舉例討論： 1、以上求從A到E的最短路徑問題，可以轉(zhuǎn)化為四個(gè)性質(zhì)完全

3、相同，但規(guī)模較小的子問題，即分別從Di 、Ci、Bi、A到E的最短路徑問題。 第四階段：兩個(gè)始點(diǎn)D1和D2，終點(diǎn)只有一個(gè)； 表10-1分析得知：從D1和D2到E的最短路徑唯一。 階段4本階段始點(diǎn)（狀態(tài)）本階段各終點(diǎn)（決策）到E的最短距離本階段最優(yōu)終點(diǎn)（最優(yōu)決策) E D1 D2 10* 6 10 6 E E管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué)5 第三階段：有三個(gè)始點(diǎn)C1，C2，C3，終點(diǎn)有D1，D2，對始點(diǎn)和終點(diǎn)進(jìn)行分析和討論分別求C1，C2，C3到D1，D2 的最短路徑問題： 表10-2分析得知：如果經(jīng)過C1，則最短路為C1-D2-E； 如果經(jīng)過C2，則最短路為C2-D2-E； 如果經(jīng)過C3，則最短

4、路為C3-D1-E。 1 1多階段決策過程最優(yōu)化問題舉例多階段決策過程最優(yōu)化問題舉例 階段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=11 6+6=12 12 11 11 D2 D2 D1管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué)6第二階段：有4個(gè)始點(diǎn)B1,B2,B3,B4，終點(diǎn)有C1,C2,C3。對始點(diǎn)和終點(diǎn)進(jìn)行分析和討論分別求B1,B2,B3,B4到C1,C2,C3 的最短路徑問題： 表10-3 分析得知：如果經(jīng)過B1，則走B1-C2-D2-E； 如果經(jīng)過B2，則走B

5、2-C3-D1-E； 如果經(jīng)過B3，則走B3-C3-D1-E； 如果經(jīng)過B4，則走B4-C3-D1-E。 1 1多階段決策過程最優(yōu)化問題舉例多階段決策過程最優(yōu)化問題舉例 階段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 C3管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué)7第一階段：只有1個(gè)始點(diǎn)A，終點(diǎn)有

6、B1,B2,B3,B4 。對始點(diǎn)和終點(diǎn)進(jìn)行分析和討論分別求A到B1,B2,B3,B4的最短路徑問題： 表10-4最后，可以得到：從A到E的最短路徑為A B4 C3 D1 E1 1多階段決策過程最優(yōu)化問題舉例多階段決策過程最優(yōu)化問題舉例 階段1本階段始點(diǎn)(狀態(tài)) 本階段各終點(diǎn)（決策）到E的最短距離本階段最優(yōu)終點(diǎn)(最優(yōu)決策) B1 B2 B3 B4 A 4+12=16 3+13=163+14=172+12=14 12 C2管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué)8 以上計(jì)算過程及結(jié)果，可用圖2表示，可以看到，以上方法不僅得到了從A到D的最短路徑，同時(shí)，也得到了從圖中任一點(diǎn)到E的最短路徑。 以上過程，僅用了22

7、次加法，計(jì)算效率遠(yuǎn)高于窮舉法。BACBDBCDEC412312312332164724838675161060106121111121314144B1275121 1多階段決策過程最優(yōu)化問題舉例多階段決策過程最優(yōu)化問題舉例管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué)9一、基本概念： 1、階段k：表示決策順序的離散的量，階段可以按時(shí)間或空間劃分。 2、狀態(tài)sk：能確定地表示決策過程當(dāng)前特征的量。狀態(tài)可以是數(shù)量，也可以是字符，數(shù)量狀態(tài)可以是連續(xù)的，也可以是離散的。 3、決策xk：從某一狀態(tài)向下一狀態(tài)過渡時(shí)所做的選擇。決策是所在狀態(tài)的函數(shù)，記為xk(sk)。 決策允許集合Dk(sk)：在狀態(tài)sk下，允許采取決策的全

8、體。 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基本概念、基本方程與最優(yōu)化原理基本概念、基本方程與最優(yōu)化原理管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué)10 6、階段指標(biāo)函數(shù)vk(sk, xk)：從狀態(tài)sk出發(fā)，選擇決策xk所產(chǎn)生的第k階段指標(biāo)。 過程指標(biāo)函數(shù)Vk,n(sk, xk, xk+1, xn)：從狀態(tài)sk出發(fā)，選擇決策xk, xk+1, , xn所產(chǎn)生的過程指標(biāo)。動態(tài)規(guī)劃要求過程指標(biāo)具有可分離性，即 Vk,n(sk, xk

9、, xk+1, , xn) = vk(sk, xk)+Vk+1(sk+1, xk+1, , xn)稱指標(biāo)具有可加性，或 Vk,n(sk, xk, xk+1, , xn) = vk(sk, xk)Vk+1(sk+1, xk+1, , xn)稱指標(biāo)具有可乘性。二、基本方程： 最優(yōu)指標(biāo)函數(shù)fk(sk)：從狀態(tài)sk出發(fā)，對所有的策略Pk,n，過程指標(biāo)Vk,n的最優(yōu)值，即 ),()(,)(nkknksDxkkPsVsfoptkkk2 2基本概念、基本方程與最優(yōu)化原理基本概念、基本方程與最優(yōu)化原理管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué)11 對于可加性指標(biāo)函數(shù)，上式可以寫為 上式中“opt”表示“max”或“min”

10、。對于可乘性指標(biāo)函數(shù)，上式可以寫為 以上式子稱為動態(tài)規(guī)劃最優(yōu)指標(biāo)的遞推方程，是動態(tài)規(guī)劃的基本方程。 終端條件：為了使以上的遞推方程有遞推的起點(diǎn)，必須要設(shè)定最優(yōu)指標(biāo)的終端條件，一般最后一個(gè)狀態(tài)n+1下最優(yōu)指標(biāo)fn+1(sn+1) = 0。nksfxsvsfkkkkksDxkkoptkkk, 2 , 1)(),()(11)(nksfxsvsfkkkkksDxkkoptkkk, 2 , 1)(),()(11)(2 2基本概念、基本方程與最優(yōu)化原理基本概念、基本方程與最優(yōu)化原理管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué)12三、最優(yōu)化原理三、最優(yōu)化原理 作為整個(gè)過程的最優(yōu)策略具有如下性質(zhì)： 不管在此最優(yōu)策略上的某個(gè)狀

11、態(tài)以前的狀態(tài)和決策如何，對該狀態(tài)來說，以后的所有決策必定構(gòu)成最優(yōu)子策略。就是說，最優(yōu)策略的任意子策略都是最優(yōu)的。2 2基本概念、基本方程與最優(yōu)化原理基本概念、基本方程與最優(yōu)化原理管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué)13一、資源分配問題一、資源分配問題 例2. 某公司擬將某種設(shè)備5臺，分配給所屬的甲、乙、丙三個(gè)工廠。各工廠獲得此設(shè)備后，預(yù)測可創(chuàng)造的利潤如表10-5所示，問這5臺設(shè)備應(yīng)如何分配給這3個(gè)工廠，使得所創(chuàng)造的總利潤為最大？ 表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

12、 動態(tài)規(guī)劃的應(yīng)用動態(tài)規(guī)劃的應(yīng)用(1)(1)管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué)14解：將問題按工廠分為三個(gè)階段，甲、乙、丙三個(gè)廠分別編號為1、2、3廠。設(shè) sk= 分配給第k個(gè)廠至第3個(gè)廠的設(shè)備臺數(shù)（k=1、2、3）。 xk=分配給第k個(gè)設(shè)備臺數(shù)。 已知s1=5, 并有 從與的定義，可知以下我們從第三階段開始計(jì)算。222223),(xsxsTskskx33xs 3 3 動態(tài)規(guī)劃的應(yīng)用動態(tài)規(guī)劃的應(yīng)用(1)111112),(xsxsTs管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué)15 第三階段: 顯然將臺設(shè)備都分配給第3工廠時(shí)，也就是時(shí)，第3階段的指標(biāo)值（即第3廠的盈利）為最大，即 由于第3階段是最后的階段，故有 其中可

13、取值為0,1,2,3,4,5。其數(shù)值計(jì)算見表106。 )5 , 4 , 3 , 2 , 1 , 0(33ss).,(),(max)(333333333ssrxsrsfx3x),(),(max3333333ssrxsrx3 3 動態(tài)規(guī)劃的應(yīng)用動態(tài)規(guī)劃的應(yīng)用(1)33xs 管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué)16 表表106 012345000014 4126623111134121245121253x3s),(333xsr)(33sf3*x3 3 動態(tài)規(guī)劃的應(yīng)用動態(tài)規(guī)劃的應(yīng)用(1)管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué)17 其中表示取3子過程上最優(yōu)指標(biāo)值時(shí)的決策，例如在表10-6中可知當(dāng)=4時(shí)，有有此時(shí)，即當(dāng)時(shí)，

14、此時(shí)?。ò?臺設(shè)備分配給第3廠）是最優(yōu)決策，此時(shí)階段指標(biāo)值（盈利）為12，最優(yōu)3子過程最優(yōu)指標(biāo)值也為12。 第二階段： 當(dāng)把臺設(shè)備分配給第2工廠和第3工廠時(shí)，則對每個(gè)值，有一種最優(yōu)分配方案，使最大盈利即最優(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ī)劃的應(yīng)用動態(tài)規(guī)劃的應(yīng)用(1)管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué)18因?yàn)樯鲜揭部蓪懗善鋽?shù)值計(jì)算如表107所示。表107 , 223xss0123450 00104 5

15、1206 54 1023011 56 110 1424012 114110 161,25012 512 116114 1102122x2s)(),(233222xsfxsr)(22sf2*x00050104101156101110)(),(max)(223222222xsfxsrsfx3 3 動態(tài)規(guī)劃的應(yīng)用動態(tài)規(guī)劃的應(yīng)用(1)管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué)19 其中在的這一行里，當(dāng)時(shí)，這里從表105中可知，把1臺設(shè)備交給乙廠所得盈利數(shù)即可，知，這里從表106查即可知=11。同樣可知當(dāng)時(shí)，可知 ;當(dāng)時(shí)，；當(dāng)時(shí)，；當(dāng)時(shí)， ；由于，不可能分2廠5臺設(shè)備，故時(shí)，欄空著不填。從這些數(shù)值中取得最大即得，即有

16、=16。在此行中我們在取最大值的 上面加一橫以示區(qū)別，也可知這時(shí)的最優(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 fr42x11011)44()4 , 4(32 fr42s52x)54()5 , 4(32 fr)4(2f)4(

17、2f)(),(223222xsfxsr2x3 3 動態(tài)規(guī)劃的應(yīng)用動態(tài)規(guī)劃的應(yīng)用(1)管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué)20第一階段：把臺設(shè)備分配給第1，第2，第3廠時(shí)，最大盈利為其中可取值0,1,2,3,4,5.數(shù)值計(jì)算見表108 表10-8 然后按計(jì)算表格的順序推算，可知最優(yōu)分配方案有兩個(gè)： 1.由于，根據(jù)，查表107可知，再由 ，求得。即分配給甲廠0臺，乙廠2臺，丙廠3臺。 2.由于，根據(jù) ，查表107可 )5(11ss),5(), 5(max)5(111111xfxrfx1x0123455 316 9+10 12+5 13+0 21 0,21x1s)5(), 5(1211xfxr210147)

18、(1xf1*x01*x5051*12xss02*x3252*23xss333* sx21*x3251*12xss3 3 動態(tài)規(guī)劃的應(yīng)用動態(tài)規(guī)劃的應(yīng)用(1)管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué)21知，再由 ,求得，即分配給甲廠2臺，乙廠2臺，丙廠1臺。這兩種分配方案都能得到最高的總盈利21萬元。 22*x1232*23xss133* sx3 3 動態(tài)規(guī)劃的應(yīng)用動態(tài)規(guī)劃的應(yīng)用(1)管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué)22二、背包問題二、背包問題 設(shè)有n種物品，每一種物品數(shù)量無限。第i種物品每件重量為wi公斤，每件價(jià)值ci元?，F(xiàn)有一只可裝載重量為W公斤的背包，求各種物品應(yīng)各取多少件放入背包，使背包中物品的價(jià)值最高。

19、 這個(gè)問題可以用整數(shù)規(guī)劃模型來描述。設(shè)xi為第i種物品裝入背包的件數(shù)（i =1, 2, , n），背包中物品的總價(jià)值為z，則 Max z = c1x1+c2x2+ +cnxn s.t. w1x1+w2x2+wnxnW x1, x2, , xn0 且為整數(shù)。3 3 動態(tài)規(guī)劃的應(yīng)用動態(tài)規(guī)劃的應(yīng)用(1)管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué)23 下面用動態(tài)規(guī)劃逆序解法求解它。設(shè)階段變量k：第k次裝載第k種物品（k=1, 2, , n）狀態(tài)變量sk：第k次裝載時(shí)背包還可以裝載的重量；決策變量uk = xk：第k次裝載第k種物品的件數(shù)；決策允許集合：Dk(sk) = xk | 0 xksk/wk，xk為整數(shù)；狀態(tài)

20、轉(zhuǎn)移方程： sk+1 = sk wkxk；階段指標(biāo)： vk = ckxk；最優(yōu)過程指標(biāo)函數(shù)fk(sk)：第k到n階段容許裝入物品的最大使用價(jià)值；遞推方程： 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)規(guī)劃的應(yīng)用動態(tài)規(guī)劃的應(yīng)用(1)管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué)24例3.某咨詢公司有10個(gè)工作日可以去處理四種類型的咨詢項(xiàng)目，每種類型的咨詢項(xiàng)目中待處理的客戶數(shù)量、處理每個(gè)客戶所需工作日數(shù)以及所獲得的利潤如表109所示。顯然該公司在10天內(nèi)不能處理完所有的客戶，它可以

21、自己挑選一些客戶，其余的請其他咨詢公司去做，應(yīng)如何選擇客戶使得在這10個(gè)工作日中獲利最大？ 表109 咨詢項(xiàng)目類型待處理客戶數(shù)處理每個(gè)客戶所需工作日數(shù)處理每個(gè)客戶所獲利潤1234432213472811203 3 動態(tài)規(guī)劃的應(yīng)用動態(tài)規(guī)劃的應(yīng)用(1)管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué)25解：用動態(tài)規(guī)劃來求解此題。我們把此問題分成四個(gè)階段，第一階段我們決策將處理多少個(gè)第一種咨詢項(xiàng)目類型中的客戶，第二階段決策將處理多少個(gè)第二種咨詢項(xiàng)目類型中的客戶，第三階段、第四階段我們也將作出類似的決策。我們設(shè)分配給第k種咨詢項(xiàng)目到第四種咨詢項(xiàng)目的所有客戶的總工作日（第k階段的狀態(tài)變量）。 =在第k種咨詢項(xiàng)目中處理客戶的

22、數(shù)量（第k階段的決策變量）。已知10并有 kx1s,),(111112xsxsTsks3 3 動態(tài)規(guī)劃的應(yīng)用動態(tài)規(guī)劃的應(yīng)用(1)管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué)26 并從與的定義可知從第四階段開始計(jì)算：顯然將個(gè)工作日盡可能分配給第四類咨詢項(xiàng)目，即時(shí)，第四階段的指標(biāo)值為最大，其中，表示取不大于的最大整數(shù)，符號為取整符號，故有由于第四階段是最后的階段，故有,3),(222223xsxsTs.4),(333334xsxsTskskx447xs 4s)10, 1 , 0(4s7/44sx 7/4s7/4s ).7/,(),(max4444444ssrxsrx),7/,(),(max)(4444*44444

23、ssrxsrsfx3 3 動態(tài)規(guī)劃的應(yīng)用動態(tài)規(guī)劃的應(yīng)用(1)管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué)27因?yàn)橹炼酁?0，其數(shù)值計(jì)算見表1010。 表表10104s01000100200300400500600702018020190201100114x4s),(444xsr)(44sf4*x0000000202020203 3 動態(tài)規(guī)劃的應(yīng)用動態(tài)規(guī)劃的應(yīng)用(1)管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué)28第三階段：當(dāng)把個(gè)工作日分配給第四類和第三類咨詢項(xiàng)目時(shí)，則對每個(gè)值，都有一種最優(yōu)分配方案，使其最大盈利即最優(yōu)3子過程最優(yōu)指標(biāo)函數(shù)值為 因?yàn)橐驗(yàn)橹炼酁?0，所以的取值可為0,1,2。其數(shù)值計(jì)算見表1011。)10, 3

24、, 2 , 1 , 0(33ss3s. )(),(max)(33222222sfxsrsfx2233xss. )4(),(max)(334333333xsfxsrsfx3s3x3 3 動態(tài)規(guī)劃的應(yīng)用動態(tài)規(guī)劃的應(yīng)用(1)管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué)29 表表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

25、動態(tài)規(guī)劃的應(yīng)用動態(tài)規(guī)劃的應(yīng)用(1)管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué)30 第二階段： 同樣以每個(gè)值都有一種最優(yōu)分配方案，使其最大盈利即最優(yōu)2子過程最優(yōu)指標(biāo)函數(shù)值為：因?yàn)?，故有因?yàn)橹炼酁?0，所以的取值為0,1,2,3。其數(shù)值計(jì)算見表1012。. )3(),(max)(223222222xsfxsrsfx2233xss. )3(),(max)(223222222xsfxsrsfx2s2x2s3 3動態(tài)規(guī)劃的應(yīng)用動態(tài)規(guī)劃的應(yīng)用(1)管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué)313 3動態(tài)規(guī)劃的應(yīng)用動態(tài)規(guī)劃的應(yīng)用(1) 表表10-12管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué)32 第一階段： 我們已知，又因?yàn)?，同樣有 因?yàn)?,故可

26、取值為0,1,2, ,10。其數(shù)值計(jì)算見表1013。 表1013101s. )(),(max)(112111111xsfxsrsfx112xss.)10(),10(max)10(121111xfxrfx101s1x3 3動態(tài)規(guī)劃的應(yīng)用動態(tài)規(guī)劃的應(yīng)用(1) 管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué)33 從表1013可知，從而得10010，在表1012的的這一行可知，由，查表1011的的這一行可知，最后由，查表10-10的的這一行得，綜上所述得最優(yōu)解為：此時(shí)最大盈利為28?，F(xiàn)在我們不妨假設(shè)該咨詢公司的工作計(jì)劃有所改變，只有8個(gè)工作日來處理這四類咨詢項(xiàng)目，那么該咨詢公司如何選擇客戶使得獲利最大呢？我們不必從頭開

27、始重做這個(gè)問題，而只要在第一階段上把改成8，重新計(jì)算就可得到結(jié)果，如表1014所示，這是動態(tài)規(guī)劃的一個(gè)好處。28)10(1f01*x1*210 xs102s12*x731032*23xss73s03*x7073*34xss74s14*x0, 1, 03*2*1*xxx, 14*x4s3 3動態(tài)規(guī)劃的應(yīng)用動態(tài)規(guī)劃的應(yīng)用(1) 管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué)34表1014如上一樣可從表1014,1012,1011,1010得到兩組最優(yōu)解如下：它們的最優(yōu)解（即最大盈利）都為22。一旦咨詢的工作日不是減少而是增加，那么我們不僅要重新計(jì)算第一階段，而且要在第二、第三、第四階段的計(jì)算表上補(bǔ)上增加的工作日的新

28、的信息，也可得到新的結(jié)果。3042)4321xxxx1001)4*3*2*1*xxxx3 3動態(tài)規(guī)劃的應(yīng)用動態(tài)規(guī)劃的應(yīng)用(1) 管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué)35 實(shí)際上，背包問題我們也可以用整數(shù)規(guī)劃來求解，如果背包攜帶物品重量的限制為W公斤，這N種物品中第i種物品的重量為，價(jià)值為，第i種物品的總數(shù)量的，我們可以設(shè)表示攜帶第i種物品的數(shù)量，則其數(shù)學(xué)模型為：S.T. 且為整數(shù)。 我們不妨用此模型去求解例3，也一定得出同樣的結(jié)果。iwicinix,max1Niiixcf0), 2 , 1(1iiiNiiixNinxWxw3 3動態(tài)規(guī)劃的應(yīng)用動態(tài)規(guī)劃的應(yīng)用(1) 管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué)36三、生

29、產(chǎn)與存貯問題 例4.某公司為主要電力公司生產(chǎn)大型變壓器，由于電力采取預(yù)訂方式購買，所以該公司可以預(yù)測未來幾個(gè)月的需求量。為確保需求，該公司為新的一年前四個(gè)月制定一項(xiàng)生產(chǎn)計(jì)劃，這四個(gè)月的需求如表1015所示。生產(chǎn)成本隨著生產(chǎn)數(shù)量而變化。調(diào)試費(fèi)為4，除了調(diào)度費(fèi)用外，每月生產(chǎn)的頭兩臺各花費(fèi)為2，后兩臺花費(fèi)為1。最大生產(chǎn)能力每月為4臺，生產(chǎn)成本如表1016所示。表10153 3動態(tài)規(guī)劃的應(yīng)用動態(tài)規(guī)劃的應(yīng)用(1) 管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué)37 表表1016每臺變壓器在倉庫中由這個(gè)月存到下個(gè)月的儲存費(fèi)為1，倉庫的最大儲存能力為3臺，另外，知道在1月1日時(shí)倉庫里存有一臺變壓器，要求在4月30日倉庫的庫存

30、量為零。試問該公司應(yīng)如何制定生產(chǎn)計(jì)劃，使得四個(gè)月的生產(chǎn)成本和儲存總費(fèi)用最少？解：我們按月份來劃分階段，第i個(gè)月為第i階段：（i=1,2,3,4). 設(shè) 為第k階段期初庫存量； k=1,2,3,4 ks3 3動態(tài)規(guī)劃的應(yīng)用動態(tài)規(guī)劃的應(yīng)用(1) 管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué)38為第k階段生產(chǎn)量； k=1,2,3,4為第k階段需求量； k=1,2,3,4，這已在表10-15中告訴我們。因?yàn)橄聜€(gè)月的庫存量等于上個(gè)月的庫存量加上上個(gè)月的產(chǎn)量減去上個(gè)月的需求量，我們就得到了如下狀態(tài)轉(zhuǎn)移方程：因?yàn)?，故有因?yàn)椋视衚xkd, 1112dxss11s, 1121dxs, 2223dxss, 3334dxss,

31、4445dxss05s, 4440dxs3 3動態(tài)規(guī)劃的應(yīng)用動態(tài)規(guī)劃的應(yīng)用(1) 管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué)39由于必須要滿足需求，則有通過移項(xiàng)得到 另一方面，第k階段的生產(chǎn)量必不大于同期的生產(chǎn)能力（4臺），也不大于第k階段至第四階段的需求之和與第k階段期初庫存量之差，否則第k階段的生產(chǎn)量就要超過從第k階段至第四階段的總需求，故有以下我們從第四階段開始計(jì)算：從以上的狀態(tài)轉(zhuǎn)移方程可知這樣就有),4, 3 ,2, 1(,kdxskkkkkksdxkx44 ,)(minkikiksdx,0444dxs,34444ssdx)3 ,(),(min)(444444444ssrxsrsfx3 3動態(tài)規(guī)劃的

32、應(yīng)用動態(tài)規(guī)劃的應(yīng)用(1) 管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué)40 這里的階段指標(biāo)可以分成兩部分，即生產(chǎn)成本與儲存費(fèi)，即為 由于第四階段末要求庫存為零，即有，這樣可得 對于每個(gè)的可行值，的值列于表1017。 表1017),(nnnxsr),()(),(nnnnnnnnxshxcxsr001),(444xsh)3()3 ,()3()3 ,()(444444444444scsshscssrsf4s)(44sf3 3動態(tài)規(guī)劃的應(yīng)用動態(tài)規(guī)劃的應(yīng)用(1) 管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué)41表中當(dāng)時(shí)，可知第四階段要生產(chǎn)臺，從表1016可知總成本為9，同樣可以算出當(dāng)為1,2,3時(shí)的情況，結(jié)果已列于表1017中。第三階

33、段：此時(shí)有：因?yàn)橐约八杂欣?，?dāng)?shù)谌A段初庫存量時(shí)，生產(chǎn)量為2時(shí)，則所以生產(chǎn)成本為8，第三階段末庫存為2時(shí)，儲存費(fèi)為，而04s3344sx4s)(1)(),()(),(3333333333333dxsxcxshxcxsr,3334dxss, 13d)() 1(1)(min)(443333)4,4min(133333sfxsxcsfsxs) 1() 1(1)(min3343333)4,4min(1333xsfxsxcsxs13s3x2121333dxs221),2()()(4333444fdxsfsf3 3動態(tài)規(guī)劃的應(yīng)用動態(tài)規(guī)劃的應(yīng)用(1) 管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué)42查1017表可知，這

34、樣可知，填入表1018中的欄內(nèi)，其他結(jié)果如表1018所示 ： 表1018 第二階段：因?yàn)樗杂?) 2 (4f,16628)2()2 , 1 (43 fr2, 133xs, 422232dxssd3 3動態(tài)規(guī)劃的應(yīng)用動態(tài)規(guī)劃的應(yīng)用(1) 管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué)43 計(jì)算結(jié)果如表1019所示。 表1019 )(),(min)(33222)4,8min(422222sfxsrsfsxs)(),()(min3322222)4,8min(4222sfxshxcsxs)()(1)(min222322222)4,8min(4222dxsfdxsxcsxs)4()4(1)(min2232222)4,8

35、min(4222xsfxsxcsxs3 3動態(tài)規(guī)劃的應(yīng)用動態(tài)規(guī)劃的應(yīng)用(1) 管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué)44第一階段：因?yàn)楣视杏?jì)算結(jié)果見表1020。 表1020, 1, 2211111sdxssd)(),(min) 1 ()(22111411111sfxsrfsfx)21 ()21 (1)(min12111411xfxxcx3 3動態(tài)規(guī)劃的應(yīng)用動態(tài)規(guī)劃的應(yīng)用(1) 管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué)45利用遞推關(guān)系可以從表1020，表1019，表1018和表1017得到兩組最優(yōu)解： 這時(shí)有最低總成本29。0441)4321xxxx3042)4321xxxx3 3動態(tài)規(guī)劃的應(yīng)用動態(tài)規(guī)劃的應(yīng)用(1)

36、管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué)463 3動態(tài)規(guī)劃的應(yīng)用動態(tài)規(guī)劃的應(yīng)用(1) 四、系統(tǒng)可靠性問題 例例5.某科研項(xiàng)目組由三個(gè)小組用不同的手段分別研究，它們失敗的概率各為0.40，0.60，0.80。為了減少三個(gè)小組都失敗的可能性，現(xiàn)決定給三個(gè)小組中增派兩名高級科學(xué)家，到各小組后，各小組科研項(xiàng)目失敗概率如下表： 問如何分派科學(xué)家才能使三個(gè)小組都失敗的概率（即科研項(xiàng)目最終失敗的概率）最??？ 高級科學(xué)家小組12300.400.600.8010.200.400.5020.150.200.30管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué)473 3動態(tài)規(guī)劃的應(yīng)用動態(tài)規(guī)劃的應(yīng)用(1) 解：用逆序算法。設(shè) 階段：每個(gè)研究小組為一

37、個(gè)階段，且階段123小組123管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué)483 3動態(tài)規(guī)劃的應(yīng)用動態(tài)規(guī)劃的應(yīng)用(1) 計(jì)算當(dāng)n=3時(shí)，當(dāng)n=2時(shí)， s3 f3*(s3) x3*008001050120302 x2s2f2(s2,x2)=P2(x2) f3*(s2-x2) f2*(s2) x2*012004804801030032030020180200160162管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué)493 3動態(tài)規(guī)劃的應(yīng)用動態(tài)規(guī)劃的應(yīng)用(1) 當(dāng)n=1時(shí)， 最優(yōu)解為 x1*=1，x2*=0，x3*=1；科研項(xiàng)目最終失敗的概率為0.060。 x1s1f1(s1,x1)=P1(x1) f2*(s1-x1)f2*(s2)

38、x2*01220064 0060 0072 0060 1管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué)504 4動態(tài)規(guī)劃的應(yīng)用動態(tài)規(guī)劃的應(yīng)用(2)(2)* *一、一、連續(xù)連續(xù)確定性動態(tài)規(guī)劃確定性動態(tài)規(guī)劃 對于狀態(tài)變量和決策變量只取連續(xù)值，過程的演變方式為確定性時(shí)，這種動態(tài)規(guī)劃問題就稱為連續(xù)確定性動態(tài)規(guī)劃問題。管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué)514 4動態(tài)規(guī)劃的應(yīng)用動態(tài)規(guī)劃的應(yīng)用(2)(2)* *機(jī)器負(fù)荷分配問題機(jī)器負(fù)荷分配問題 例例1 一種機(jī)器能在高低兩種不同的負(fù)荷狀態(tài)下工作。設(shè)機(jī)器在高負(fù)荷下生產(chǎn)時(shí)，產(chǎn)量函數(shù)為P1=8u1，其中u1為在高負(fù)荷狀態(tài)下生產(chǎn)的機(jī)器數(shù)目，年完好率為a=0.7，即到年底有70的機(jī)器保持完好。

39、在低負(fù)荷下生產(chǎn)時(shí)，產(chǎn)量函數(shù)為P2=5u2，其中u2為在低負(fù)荷狀態(tài)下生產(chǎn)的機(jī)器數(shù)目，年完好率為b=0.9。設(shè)開始生產(chǎn)時(shí)共有1000臺完好的機(jī)器，請問每年應(yīng)該如何把完好機(jī)器分配給高、低兩種負(fù)荷下生產(chǎn)，才能使得5年內(nèi)生產(chǎn)的產(chǎn)品總產(chǎn)量最高。管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué)524 4動態(tài)規(guī)劃的應(yīng)用動態(tài)規(guī)劃的應(yīng)用(2)(2)* *解 建立動態(tài)規(guī)劃模型： 分為5個(gè)階段，每個(gè)階段為1年。設(shè)狀態(tài)變量sk表示在第k階段初擁有的完好機(jī)器數(shù)目；k=1,2,3,4,5。 決策變量xk表示第k階段中分配給高負(fù)荷狀態(tài)下生產(chǎn)的機(jī)器數(shù)目；k=1,2,3,4,5。顯然sk-xk為分配給低負(fù)荷狀態(tài)下生產(chǎn)的機(jī)器數(shù)目。 狀態(tài)轉(zhuǎn)移方程為 s

40、k+1=0.7xk+0.9(sk-xk) 階段指標(biāo) rk(sk,xk)=8xk+5(sk-xk) 最優(yōu)指標(biāo)函數(shù) ，其中k=1,2,3,4,5。 f6(s6)=0。)()58max)(11kkkkkkksfxsxsf（kksx 0管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué)534 4動態(tài)規(guī)劃的應(yīng)用動態(tài)規(guī)劃的應(yīng)用(2)(2)* *第5階段： 因?yàn)閒5(s5)是x5的線性單調(diào)增函數(shù)，故有x5* =s5，于是有f5(s5)=8s5。第4階段： )(2 .126 .13max)(9 . 07 . 0 8)(58max8)(58max)()(58max)(44404444440544405544404444444444x

41、sxxsxxsxsxsxsfxsxsfsxsxsxsx 管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué)544 4動態(tài)規(guī)劃的應(yīng)用動態(tài)規(guī)劃的應(yīng)用(2)(2)* * 同樣的，f4(s4)是x4的線性單調(diào)增函數(shù)，有x4*=s4 ，f4(s4)=13.6s4。 對前幾個(gè)階段依次類推，可得 f3(s3)=17.5s3， f2(s2)=20.75s2， f1(s1)=23.72s1。 因?yàn)槠诔豕灿型旰脵C(jī)器1000臺，故s1=1000。有f1(s1)=23.72s123720，即5年最大的產(chǎn)量為23720臺。得最優(yōu)解為 ， ， ， 。 這意味著前兩年應(yīng)把年初完好機(jī)器完全投入低負(fù)荷生產(chǎn)，后三年應(yīng)把年初完好機(jī)器完全投入高負(fù)荷生產(chǎn)。

42、0*1x0*2x3*3sx 4*4sx 5*5sx 管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué)554 4動態(tài)規(guī)劃的應(yīng)用動態(tài)規(guī)劃的應(yīng)用(2)(2)* * 下一步工作是確定每年初的狀態(tài)，按照從前向后的順序依次計(jì)算出每年年初完好的機(jī)器數(shù)目。已知s1=1000,根據(jù)狀態(tài)轉(zhuǎn)移方程，有:9009 . 0)(9 . 07 . 01*11*12sxsxs8109 . 0)(9 . 07 . 02*22*23sxsxs5677 . 0)(9 . 07 . 03*33*34sxsxs3977 . 0)(9 . 07 . 04*44*45sxsxs管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué)564 4動態(tài)規(guī)劃的應(yīng)用動態(tài)規(guī)劃的應(yīng)用(2)(2)*

43、* 上面所討論的最優(yōu)策略過程，初始端狀態(tài)s1=1000臺是固定的，終點(diǎn)狀態(tài)s6沒有要求。這種情況下得到最優(yōu)決策稱為初始端固定終點(diǎn)自由的最優(yōu)策略。 如果終點(diǎn)附加一定的條件，則問題就稱為“終端固定問題”。例如，規(guī)定在第5年度結(jié)束時(shí)仍要保持500臺機(jī)器完好（而不是278臺），應(yīng)如何安排生產(chǎn)才能使得總產(chǎn)量最大？ 下面來分析： 根據(jù)終點(diǎn)條件有 可得500)(9 . 07 . 05556xsxs25005 . 455sx管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué)574 4動態(tài)規(guī)劃的應(yīng)用動態(tài)規(guī)劃的應(yīng)用(2)(2)* * 顯然，由于固定了終點(diǎn)的狀態(tài)，x5的取值受到了約束。因此有 類似的， 容易解得 ，f4(s4)=21.7

44、s4-7500。75005 .18)25005 . 4(5)25005 . 4(8max)(555555sssssf75007 . 07 .21max75005 .18)(58max)()(58max)(4405444055444044444444xssxsxsfxsxsfsxsxsx0*4x管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué)584 4動態(tài)規(guī)劃的應(yīng)用動態(tài)規(guī)劃的應(yīng)用(2)(2)* * 依次類推，得 f3(s3)=24.5s3-7500 f2(s2)=27.1s2-7500 f1(s1)=29.4s1-7500 再采用順序方法遞推計(jì)算各年的狀態(tài)，有 s1=1000， 0*1*2*3xxx9009 . 0

45、)(9 . 07 . 01*11*12sxsxs8109 . 0)(9 . 07 . 02*22*23sxsxs7297 . 0)(9 . 07 . 03*33*34sxsxs6567 . 0)(9 . 07 . 04*44*45sxsxs管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué)594 4動態(tài)規(guī)劃的應(yīng)用動態(tài)規(guī)劃的應(yīng)用(2)(2)* * 可見，為了使終點(diǎn)完好的機(jī)器數(shù)量增加到500臺，需要安排前四年中全部完好機(jī)器都要投入低負(fù)荷生產(chǎn)，且在第5年，也只能全部投入高負(fù)荷。 相應(yīng)的最優(yōu)指標(biāo)為 f1(s1)=29.4s1-750021900。 可以看到，因?yàn)樵黾恿烁郊訔l件，總產(chǎn)量f1(s1)要比終點(diǎn)自由情況下的產(chǎn)量要低

46、。管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué)60二、離散隨機(jī)性動態(tài)規(guī)劃二、離散隨機(jī)性動態(tài)規(guī)劃 隨機(jī)型的動態(tài)規(guī)劃是指狀態(tài)的轉(zhuǎn)移律是不確定的，即對給定的狀態(tài)和決策，下一階段的到達(dá)狀態(tài)是具有確定概率分布的隨機(jī)變量，這個(gè)概率分布由本階段的狀態(tài)和決策完全確定。隨機(jī)型動態(tài)規(guī)劃的基本結(jié)構(gòu)如下圖： 4 4動態(tài)規(guī)劃的應(yīng)用動態(tài)規(guī)劃的應(yīng)用(2)(2)* * sk狀態(tài) xk決策概率k階段的收益p1p2pN.k+1階段的狀態(tài)sk+1c1c2cN 1 2N管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué)614 4動態(tài)規(guī)劃的應(yīng)用動態(tài)規(guī)劃的應(yīng)用(2)(2)* * 圖中N表示第k+1階段可能的狀態(tài)數(shù)，p1、p2、pN為給定狀態(tài)sk和決策xk的前提下，可能達(dá)到下

47、一個(gè)狀態(tài)的概率。ci為從k階段狀態(tài)sk轉(zhuǎn)移到k+1 階段狀態(tài)為i時(shí)的指標(biāo)函數(shù)值。 在隨機(jī)性的動態(tài)規(guī)劃問題中，由于下一階段到達(dá)的狀態(tài)和階段的效益值不確定，只能根據(jù)各階段的期望效益值進(jìn)行優(yōu)化。管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué)62離散隨機(jī)性動態(tài)規(guī)劃離散隨機(jī)性動態(tài)規(guī)劃 例例2 2 某公司承擔(dān)一種新產(chǎn)品研制任務(wù)，合同要求三個(gè)月內(nèi)交出一件合格的樣品，否則將索賠2000元。根據(jù)有經(jīng)驗(yàn)的技術(shù)人員估計(jì)，試制品合格的概率為0.4，每次試制一批的裝配費(fèi)為200元，每件產(chǎn)品的制造成本為100元。每次試制的周期為1個(gè)月。問該如何安排試制，每次生產(chǎn)多少件，才能使得期望費(fèi)用最小？ 管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué)63離散隨機(jī)性動態(tài)

48、規(guī)劃離散隨機(jī)性動態(tài)規(guī)劃 解：解：把三次試制當(dāng)作三個(gè)階段（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階段以后的最小期望費(fèi)用。故有fk(0)0。 生產(chǎn)出一件合格品的概率為0.4，所以生產(chǎn)xk件產(chǎn)品都不合格的概率為 ，至少有一件合格品的概率為1- ，故有狀態(tài)轉(zhuǎn)移方程為 kx6 . 0kkxkxkspsp6 . 01)0(6 . 0) 1(11kx6 . 0管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué)64離散隨機(jī)性動態(tài)規(guī)劃離散隨機(jī)性動態(tài)規(guī)劃 用C

49、(xk)表示第k階段的費(fèi)用，第k階段的費(fèi)用包括制造成本和裝配費(fèi)用，故有 根據(jù)狀態(tài)轉(zhuǎn)移方程以及C(xk)，可得到 0002)(kkkkxxxxC)1 (6 . 0)0()6 . 01 ()(min) 1 (11kxkxkxkffxcfkkk)1 (6 . 0)(min1kxkxfxckk管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué)65離散隨機(jī)性動態(tài)規(guī)劃離散隨機(jī)性動態(tài)規(guī)劃 如果3個(gè)月后沒有試制出一件合格品，則要承擔(dān)2000元的罰金，因此有f4(1)=20。 當(dāng)k=3時(shí)，計(jì)算如下表： x3 s3 C(x3)+20f3(s3) x3* 0 1 2 3 4 5 6 0 0 0 0 1 20 1511.2 9.32 8.59 8.56 8.93 8.56 5 0.63x管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué)66離散隨機(jī)性動態(tài)規(guī)劃離散隨機(jī)性動態(tài)規(guī)劃當(dāng)k=2時(shí)，計(jì)算如下表： x2 s2 C(x2)+8.56f2(s2) x2* 0 1 2 3 4 0 0 0 0 18.56 8.14 7.08 6.85 7.11 6.85 3 0.62x管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué)67離散隨機(jī)性動態(tài)規(guī)劃離散隨機(jī)性動態(tài)規(guī)劃當(dāng)k=1時(shí)，有 x1 s1 C(x1)+6.85f1(s1) x1* 0 1 2 3 0 0 0 0 16.857.116.466.48 6