管理運(yùn)籌學(xué)第10章動(dòng)態(tài)規(guī)劃ppt課件

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

2、 學(xué)學(xué)1 1多階段決策過程最優(yōu)化問題舉例多階段決策過程最優(yōu)化問題舉例用窮舉法的計(jì)算量用窮舉法的計(jì)算量: 從從A到到E的途徑有的途徑有432=24條，計(jì)算條，計(jì)算每條途徑的總長(zhǎng)度需求做每條途徑的總長(zhǎng)度需求做4次加法，那么次加法，那么計(jì)算各途徑長(zhǎng)度總共要進(jìn)展計(jì)算各途徑長(zhǎng)度總共要進(jìn)展244=96次次加法，做加法，做23次比較，才干得出結(jié)果。次比較，才干得出結(jié)果。管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué)1 1多階段決策過程最優(yōu)化問題舉例多階段決策過程最優(yōu)化問題舉例討論：討論： 1、以上求從、以上求從A到到E的最短途徑問題，可以轉(zhuǎn)化為四個(gè)性質(zhì)的最短途徑問題，可以轉(zhuǎn)化為四個(gè)性質(zhì)完全一樣，但規(guī)模較小的子問題，即分別從完

3、全一樣，但規(guī)模較小的子問題，即分別從Di 、Ci、Bi、A到到E的最短途徑問題。的最短途徑問題。 第四階段：兩個(gè)始點(diǎn)第四階段：兩個(gè)始點(diǎn)D1和和D2，終點(diǎn)只需一個(gè)；，終點(diǎn)只需一個(gè)； 階段階段4本階段始點(diǎn)本階段始點(diǎn)形狀形狀本階段各終點(diǎn)決策本階段各終點(diǎn)決策到到E的最短間隔的最短間隔本階段最優(yōu)終點(diǎn)本階段最優(yōu)終點(diǎn)最優(yōu)決策最優(yōu)決策) E D1 D2 10* 6 10 6 E E分析得知：從分析得知：從D1和和D2到到E的最短途徑獨(dú)一。的最短途徑獨(dú)一。管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué) 第三階段：有三個(gè)始點(diǎn)C1，C2，C3，終點(diǎn)有D1，D2，對(duì)始點(diǎn)和終點(diǎn)進(jìn)展分析和討論分別求C1，C2，C3到D1，D2 的最短途徑

4、問題： 1 1多階段決策過程最優(yōu)化問題舉例多階段決策過程最優(yōu)化問題舉例 階段階段3本階段始點(diǎn)本階段始點(diǎn)形狀形狀本階段各終點(diǎn)決策本階段各終點(diǎn)決策到到E的最短間隔的最短間隔本階段最優(yōu)終點(diǎn)本階段最優(yōu)終點(diǎn)最優(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分析得知：假設(shè)經(jīng)過分析得知：假設(shè)經(jīng)過C1，那么最短路為，那么最短路為C1-D2-E； 假設(shè)經(jīng)過假設(shè)經(jīng)過C2，那么最短路為，那么最短路為C2-D2-E； 假設(shè)經(jīng)過假設(shè)經(jīng)過C3，那么最短路為，那么最短路為C3-D1-E。管管 理理 運(yùn)

5、運(yùn) 籌籌 學(xué)學(xué)第二階段：有第二階段：有4個(gè)始點(diǎn)個(gè)始點(diǎn)B1,B2,B3,B4，終點(diǎn)有，終點(diǎn)有C1,C2,C3。對(duì)始。對(duì)始點(diǎn)和終點(diǎn)進(jìn)展分析和討論分別求點(diǎn)和終點(diǎn)進(jìn)展分析和討論分別求B1,B2,B3,B4到到C1,C2,C3 的最短途徑問題：的最短途徑問題： 1 1多階段決策過程最優(yōu)化問題舉例多階段決策過程最優(yōu)化問題舉例 階段階段2本階段始點(diǎn)本階段始點(diǎn)形狀形狀 本階段各終點(diǎn)決策本階段各終點(diǎn)決策到到E的最的最短間隔短間隔本階段最優(yōu)終本階段最優(yōu)終點(diǎn)最優(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

6、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分析得知：假設(shè)經(jīng)過分析得知：假設(shè)經(jīng)過B1，那么走，那么走B1-C2-D2-E； 假設(shè)經(jīng)過假設(shè)經(jīng)過B2，那么走，那么走B2-C3-D1-E； 假設(shè)經(jīng)過假設(shè)經(jīng)過B3，那么走，那么走B3-C3-D1-E； 假設(shè)經(jīng)過假設(shè)經(jīng)過B4，那么走，那么走B4-C3-D1-E。管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué)第一階段：只需第一階段：只需1個(gè)始點(diǎn)個(gè)始點(diǎn)A，終點(diǎn)有，終點(diǎn)有B1,B2,B3,B4 。對(duì)始點(diǎn)和。對(duì)始點(diǎn)和終點(diǎn)進(jìn)展分析和討論分別求終點(diǎn)進(jìn)展分析和討論分別求A到到B1,B2,B

7、3,B4的最短途徑問的最短途徑問題：題：1 1多階段決策過程最優(yōu)化問題舉例多階段決策過程最優(yōu)化問題舉例 階段階段1本階段始本階段始點(diǎn)點(diǎn)(形狀形狀) 本階段各終點(diǎn)決策本階段各終點(diǎn)決策到到E的最的最短間隔短間隔本階段最優(yōu)終本階段最優(yōu)終點(diǎn)點(diǎn)(最優(yōu)決策最優(yōu)決策) B1 B2 B3 B4 A 4+12=16 3+13=163+14=172+12=14 14 B4最后，可以得到：從最后，可以得到：從A到到E的最短途徑為的最短途徑為A B4 C3 D1 E管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué) 以上計(jì)算過程及結(jié)果，可用圖以上計(jì)算過程及結(jié)果，可用圖2表示，可以看到，以上方表示，可以看到，以上方法不僅得到了從法不僅得到了

8、從A到到D的最短途徑，同時(shí)，也得到了從圖中的最短途徑，同時(shí)，也得到了從圖中任一點(diǎn)到任一點(diǎn)到E的最短途徑。的最短途徑。BACBDBCDEC412312312332164724838675161060106121111121314144B1275121 1多階段決策過程最優(yōu)化問題舉例多階段決策過程最優(yōu)化問題舉例以上過程，僅用了以上過程，僅用了22次加法，計(jì)算效率遠(yuǎn)高于窮舉法。次加法，計(jì)算效率遠(yuǎn)高于窮舉法。管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué)一、根本概念：一、根本概念： 1、階段、階段k：表示決策順序的離散的量，階段可以按時(shí)間或空間劃：表示決策順序的離散的量，階段可以按時(shí)間或空間劃分。分。 2、形狀、形狀s

9、k：能確定地表示決策過程當(dāng)前特征的量。形狀可以是：能確定地表示決策過程當(dāng)前特征的量。形狀可以是數(shù)量，也可以是字符，數(shù)量形狀可以是延續(xù)的，也可以是離散數(shù)量，也可以是字符，數(shù)量形狀可以是延續(xù)的，也可以是離散的。的。 3、決策、決策xk：從某一形狀向下一形狀過渡時(shí)所做的選擇。決策是：從某一形狀向下一形狀過渡時(shí)所做的選擇。決策是所在形狀的函數(shù)，記為所在形狀的函數(shù)，記為xk(sk)。 決策允許集合決策允許集合Dk(sk)：在形狀：在形狀sk下，允許采取決策的全體。下，允許采取決策的全體。 4、戰(zhàn)略、戰(zhàn)略Pk,n(sk)：從第：從第k階段開場(chǎng)到最后第階段開場(chǎng)到最后第n階段的決策序列，稱階段的決策序列，稱k

10、子戰(zhàn)略。子戰(zhàn)略。P1,n(s1)即為全過程戰(zhàn)略。即為全過程戰(zhàn)略。 5、形狀轉(zhuǎn)移方程、形狀轉(zhuǎn)移方程 sk+1=Tk(sk, xk)：某一形狀以及該形狀下的決：某一形狀以及該形狀下的決策，與下一形狀之間的函數(shù)關(guān)系。策，與下一形狀之間的函數(shù)關(guān)系。2 2根本概念、根本方程與最優(yōu)化原理根本概念、根本方程與最優(yōu)化原理管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué) 6、階段目的函數(shù)、階段目的函數(shù)rk(sk, xk)：從形狀：從形狀sk出發(fā)，選擇決策出發(fā)，選擇決策xk所產(chǎn)生的所產(chǎn)生的第第k階段目的。階段目的。 過程目的函數(shù)過程目的函數(shù)Vk,n(sk, xk, xk+1, xn)：從形狀：從形狀sk出發(fā)，選擇出發(fā)，選擇決策決策x

11、k,xk+1, , xn所產(chǎn)生的過程目的。動(dòng)態(tài)規(guī)劃要求過程目的所產(chǎn)生的過程目的。動(dòng)態(tài)規(guī)劃要求過程目的具有可分別性，即具有可分別性，即 Vk,n(sk, xk, xk+1, , xn) = rk(sk, xk)+Vk+1,n(sk+1, xk+1, , xn)稱目的具有可加性，或稱目的具有可加性，或 Vk,n(sk, xk, xk+1, , xn) = rk(sk, xk)Vk+1,n(sk+1,xk+1, , xn)稱目的稱目的具有可乘性。具有可乘性。二、根本方程：二、根本方程： 最優(yōu)目的函數(shù)最優(yōu)目的函數(shù)fk(sk)：從形狀：從形狀sk出發(fā)，對(duì)一切的戰(zhàn)略出發(fā)，對(duì)一切的戰(zhàn)略Pk,n，過，過程目的

12、程目的Vk,n的最優(yōu)值，即的最優(yōu)值，即),()(,)(nkknksDxkkPsVsfoptkkk2 2根本概念、根本方程與最優(yōu)化原理根本概念、根本方程與最優(yōu)化原理管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué) 對(duì)于可加性目的函數(shù)，上式可以寫為對(duì)于可加性目的函數(shù)，上式可以寫為 上式中上式中“opt表示表示“max或或“min。對(duì)于可乘性目的。對(duì)于可乘性目的函數(shù)，上式可以寫為函數(shù)，上式可以寫為 以上式子稱為動(dòng)態(tài)規(guī)劃最優(yōu)目的的遞推方程，是動(dòng)態(tài)以上式子稱為動(dòng)態(tài)規(guī)劃最優(yōu)目的的遞推方程，是動(dòng)態(tài)規(guī)劃的根本方程。規(guī)劃的根本方程。 終端條件：為了使以上的遞推方程有遞推的起點(diǎn)，必終端條件：為了使以上的遞推方程有遞推的起點(diǎn)，必需求設(shè)

13、定最優(yōu)目的的終端條件，普通最后一個(gè)形狀需求設(shè)定最優(yōu)目的的終端條件，普通最后一個(gè)形狀n+1下下最優(yōu)目的最優(yōu)目的fn+1(sn+1) = 0。nksfxsrsfkkkkksDxkkoptkkk, 2 , 1)(),()(11)(nksfxsrsfkkkkksDxkkoptkkk, 2 , 1)(),()(11)(2 2根本概念、根本方程與最優(yōu)化原理根本概念、根本方程與最優(yōu)化原理管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué)三、最優(yōu)化原理三、最優(yōu)化原理 作為整個(gè)過程的最優(yōu)戰(zhàn)略具有如下性質(zhì)：作為整個(gè)過程的最優(yōu)戰(zhàn)略具有如下性質(zhì)： 不論在此最優(yōu)戰(zhàn)略上的某個(gè)形狀以前的狀不論在此最優(yōu)戰(zhàn)略上的某個(gè)形狀以前的狀態(tài)和決策如何，對(duì)該形

14、狀來說，以后的一切決態(tài)和決策如何，對(duì)該形狀來說，以后的一切決策必定構(gòu)成最優(yōu)子戰(zhàn)略。就是說，最優(yōu)戰(zhàn)略的策必定構(gòu)成最優(yōu)子戰(zhàn)略。就是說，最優(yōu)戰(zhàn)略的恣意子戰(zhàn)略都是最優(yōu)的。恣意子戰(zhàn)略都是最優(yōu)的。2 2根本概念、根本方程與最優(yōu)化原理根本概念、根本方程與最優(yōu)化原理管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué)一、資源分配問題一、資源分配問題 例例2. 某公司擬將某種設(shè)備某公司擬將某種設(shè)備5臺(tái)，分配給所屬的甲、乙、丙三個(gè)臺(tái)，分配給所屬的甲、乙、丙三個(gè)工廠。各工廠獲得此設(shè)備后，預(yù)測(cè)可發(fā)明的利潤(rùn)如下表所示，工廠。各工廠獲得此設(shè)備后，預(yù)測(cè)可發(fā)明的利潤(rùn)如下表所示，問這問這5臺(tái)設(shè)備應(yīng)如何分配給這臺(tái)設(shè)備應(yīng)如何分配給這3個(gè)工廠，使得所發(fā)明的

15、總利潤(rùn)為個(gè)工廠，使得所發(fā)明的總利潤(rùn)為最大？最大？ 工廠工廠盈利盈利設(shè)備臺(tái)數(shù)設(shè)備臺(tái)數(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 動(dòng)態(tài)規(guī)劃的運(yùn)用動(dòng)態(tài)規(guī)劃的運(yùn)用(1)(1)管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué)解：將問題按工廠分為三個(gè)階段，甲、乙、丙三個(gè)廠分解：將問題按工廠分為三個(gè)階段，甲、乙、丙三個(gè)廠分別編號(hào)為別編號(hào)為1、2、3廠。設(shè)廠。設(shè) sk= 分配給第分配給第k個(gè)廠至第個(gè)廠至第3個(gè)廠的設(shè)備臺(tái)數(shù)個(gè)廠的設(shè)備臺(tái)數(shù)k=1、2、3。 xk=分配給第分配給第k個(gè)設(shè)備臺(tái)數(shù)。個(gè)設(shè)備臺(tái)數(shù)。 知知s1=5,

16、并有并有 從從sk與與xk的定義，可知的定義，可知以下我們從第三階段開場(chǎng)計(jì)算。以下我們從第三階段開場(chǎng)計(jì)算。222223),(xsxsTs33xs 3 3 動(dòng)態(tài)規(guī)劃的運(yùn)用動(dòng)態(tài)規(guī)劃的運(yùn)用(1)(1)111112),(xsxsTs管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué)第三階段：第三階段：s3=x3012345000014 4126623111134121245121253x3s),(333xsr)(33sf3*x3 3 動(dòng)態(tài)規(guī)劃的運(yùn)用動(dòng)態(tài)規(guī)劃的運(yùn)用(1)(1)012345000014 4126623111134121245121253x3s管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué)0123450 0+0 001 0+45+

17、0 512 0+6 5+410+0 1023 0+11 5+6 10+4 11+0 1424 0+12 5+11 10+6 11+4 11+0 161,25 0+12 5+12 10+11 11+6 11+4 11+02122x2s)(),(223222xsfxsr)(22sf2*x3 3 動(dòng)態(tài)規(guī)劃的運(yùn)用動(dòng)態(tài)規(guī)劃的運(yùn)用(1)(1)第二階段：第二階段：S3=S2-X2管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué)第一階段：第一階段：s1=5,s2=s1-x1=5-x101234550+21 316 7+14 9+10 12+5 13+0 21 0,21x1s)5(), 5(1211xfxr)(11sf1*x3 3

18、 動(dòng)態(tài)規(guī)劃的運(yùn)用動(dòng)態(tài)規(guī)劃的運(yùn)用(1)(1)1x1=0 s2=s1-x1=5-0=5 x2=2 s3=s2-x2=5-2=3 x3=3。即分配給甲廠。即分配給甲廠0臺(tái)，乙廠臺(tái)，乙廠2臺(tái)，丙廠臺(tái)，丙廠3臺(tái)利臺(tái)利潤(rùn)最大，最大利潤(rùn)為潤(rùn)最大，最大利潤(rùn)為21萬元。萬元。2x1=2 s2=s1-x1=5-2=3 x2=2 s3=s2-x2=3-2=1 x3=1。即分配給甲廠。即分配給甲廠2臺(tái)，乙廠臺(tái)，乙廠2臺(tái)，丙廠臺(tái)，丙廠1臺(tái)利臺(tái)利潤(rùn)最大，最大利潤(rùn)為潤(rùn)最大，最大利潤(rùn)為21萬元。萬元。管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué)二、背包問題二、背包問題 設(shè)有設(shè)有n種物品，第種物品，第i種物品數(shù)量為種物品數(shù)量為ni，第，第i種

19、物品每件種物品每件分量為分量為wi公斤，第公斤，第i種物品每件價(jià)值為種物品每件價(jià)值為ci元?，F(xiàn)有一只元?，F(xiàn)有一只可裝載分量為可裝載分量為W公斤的背包，求各種物品應(yīng)各取多少公斤的背包，求各種物品應(yīng)各取多少件放入背包，使背包中物品的價(jià)值最高。件放入背包，使背包中物品的價(jià)值最高。 這個(gè)問題可以用整數(shù)規(guī)劃模型來描畫。設(shè)這個(gè)問題可以用整數(shù)規(guī)劃模型來描畫。設(shè)xi為第為第i種種物品裝入背包的件數(shù)物品裝入背包的件數(shù)i =1, 2, , n，背包中物品的，背包中物品的總價(jià)值為總價(jià)值為z，那么，那么 Max z = c1x1+c2x2+ +cnxn s.t. w1x1+w2x2+wnxnW xi ni (i=1,

20、2,n) x1, x2, , xn0 且為整數(shù)。且為整數(shù)。3 3 動(dòng)態(tài)規(guī)劃的運(yùn)用動(dòng)態(tài)規(guī)劃的運(yùn)用(1)(1)管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué) 下面用動(dòng)態(tài)規(guī)劃逆序解法求解它。設(shè) 階段變量k：裝載第k種物品k=1, 2, , n 形狀變量sk：裝載第k種物品到第n種物品的分量； 決策變量 xk：裝載第k種物品的件數(shù)； 決策允許集合：Dk(sk) = xk | 0 xksk/wk，xk為整數(shù)； 形狀轉(zhuǎn)移方程： sk+1 = sk wkxk； 階段目的： rk = ckxk； 最優(yōu)過程目的函數(shù)fk(sk)：第k到n階段允許裝入物品的最大運(yùn)用價(jià)值；遞推方程： fk(sk) = max ckxk+fk+1(sk

21、+1) = max ckxk+fk+1(sk wkxk)； xDk(sk) 終端條件： fn+1(sn+1) = 0。3 3 動(dòng)態(tài)規(guī)劃的運(yùn)用動(dòng)態(tài)規(guī)劃的運(yùn)用(1)(1)管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué)例例3.某咨詢公司有某咨詢公司有10個(gè)任務(wù)日可以去處置四種類型個(gè)任務(wù)日可以去處置四種類型的咨詢工程，每種類型的咨詢工程中待處置的客戶數(shù)量、的咨詢工程，每種類型的咨詢工程中待處置的客戶數(shù)量、處置每個(gè)客戶所需任務(wù)日數(shù)以及所獲得的利潤(rùn)如下表所處置每個(gè)客戶所需任務(wù)日數(shù)以及所獲得的利潤(rùn)如下表所示。顯然該公司在示。顯然該公司在10天內(nèi)不能處置完一切的客戶，它可天內(nèi)不能處置完一切的客戶，它可以本人挑選一些客戶，其他的

22、請(qǐng)其他咨詢公司去做，應(yīng)以本人挑選一些客戶，其他的請(qǐng)其他咨詢公司去做，應(yīng)如何選擇客戶使得在這如何選擇客戶使得在這10個(gè)任務(wù)日中獲利最大？個(gè)任務(wù)日中獲利最大？咨詢工程咨詢工程類型類型待處置客待處置客戶數(shù)戶數(shù)處置每個(gè)客戶所處置每個(gè)客戶所需任務(wù)日數(shù)需任務(wù)日數(shù)處置每個(gè)客戶處置每個(gè)客戶所獲利潤(rùn)所獲利潤(rùn)1234432213472811203 3 動(dòng)態(tài)規(guī)劃的運(yùn)用動(dòng)態(tài)規(guī)劃的運(yùn)用(1)(1)管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué)3動(dòng)態(tài)規(guī)劃的運(yùn)用動(dòng)態(tài)規(guī)劃的運(yùn)用(1) 解：用整數(shù)規(guī)劃來解有：解：用整數(shù)規(guī)劃來解有： 設(shè)設(shè)xi為處置第為處置第i種咨詢工程的客戶數(shù)，那么其整數(shù)種咨詢工程的客戶數(shù)，那么其整數(shù)規(guī)劃模型為：規(guī)劃模型為： M

23、ax z =2x1+8x2+11x3+20 x4 S.t. x1+3x2+4x3+7x4 10 x14 x2 3 x3 2 x4 2 x1,x2,x3,x40且為整數(shù)。且為整數(shù)。管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué)解：用動(dòng)態(tài)規(guī)劃來求解此題。解：用動(dòng)態(tài)規(guī)劃來求解此題。我們把此問題分成四個(gè)階段，第一階段我們決策將我們把此問題分成四個(gè)階段，第一階段我們決策將處置多少個(gè)第一種咨詢工程類型中的客戶，第二階段處置多少個(gè)第一種咨詢工程類型中的客戶，第二階段決策將處置多少個(gè)第二種咨詢工程類型中的客戶，第決策將處置多少個(gè)第二種咨詢工程類型中的客戶，第三階段、第四階段我們也將作出類似的決策。我們?cè)O(shè)三階段、第四階段我們也將

24、作出類似的決策。我們?cè)O(shè)sk：分配給第：分配給第k種咨詢工程到第四種咨詢工程的一切客種咨詢工程到第四種咨詢工程的一切客戶的總?cè)蝿?wù)日第戶的總?cè)蝿?wù)日第k階段的形狀變量。階段的形狀變量。xk：在第：在第k種咨詢工程中處置客戶的數(shù)量第種咨詢工程中處置客戶的數(shù)量第k階段的階段的決策變量。決策變量。知知s110并有并有s2=T1(s1,x1)=s1-x1, s3=T2(s2,x2)=s2-3x2 s4=T3(s3,x3)=s3-4x23 3 動(dòng)態(tài)規(guī)劃的運(yùn)用動(dòng)態(tài)規(guī)劃的運(yùn)用(1)(1)管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué)第四階段：第四階段：x4=s4/7=0,101000010002000300040005000600

25、070 2020 180 2020 190 2020 1100 2020 14x4s),(444xsr)(44sf4*x3 3 動(dòng)態(tài)規(guī)劃的運(yùn)用動(dòng)態(tài)規(guī)劃的運(yùn)用(1)(1)管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué)第三階段：第三階段：x3=s3/4=0,1,2,s4=s3-4x3 0 1 200+000 1 0+0 00 20+000 30+000 40+011+011 1 50+011+011 1 60+011+011 1 7 0+20 11+0 20 0 80+20 11+0 22+0 22 2 90+20 11+0 22+0 22 2 100+20 11+0 22+0 22 23x3s)4(),(3343

26、33xsfxsr)(33sf3*x3 3 動(dòng)態(tài)規(guī)劃的運(yùn)用動(dòng)態(tài)規(guī)劃的運(yùn)用(1)(1)管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué)3 3動(dòng)態(tài)規(guī)劃的運(yùn)用動(dòng)態(tài)規(guī)劃的運(yùn)用(1) (1) 第二階段：第二階段：x2=s2/3=0,1,2,3；s3=s2-3x2 0 1 2 300+0 00 1 0+0 00 20+0 00 30+0 8+0 81 40+118+0 11 0 50+118+0 11 0 60+118+016+0 16 2 7 0+20 8+11 16+0 20 0 80+22 8+11 16+0 22 0 90+22 8+11 16+0 24+0 24 3 100+22 8+20 16+11 24+0 28

27、 12x2s)3(),(223222xsfxsr)(22sf2*x管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué) 第一階段：第一階段：s2=s1-x1=10-x13 3動(dòng)態(tài)規(guī)劃的運(yùn)用動(dòng)態(tài)規(guī)劃的運(yùn)用(1) (1) 0 1 2 3 4 5 6 7 8 9 1000+ 2+ 4+ 6+ 8+ 10+ 12+ 14+ 16+ 18+ 20+28 24 22 20 16 11 11 8 0 0 0 28 01x1s)10(),(12111xfxsr)(11sf1*xx1= 0s2= s1-x1=10-0 =10 x2=1 s3= s2-3x2=10-31=7 x3= 0 s4= s3-4x3=7-40 =7 x4=1。即

28、第一個(gè)咨詢工程處置的客戶數(shù)為即第一個(gè)咨詢工程處置的客戶數(shù)為0戶，第二個(gè)咨詢工程處戶，第二個(gè)咨詢工程處置的客戶數(shù)為置的客戶數(shù)為1戶，第三個(gè)咨詢工程處置的客戶數(shù)為戶，第三個(gè)咨詢工程處置的客戶數(shù)為0戶，戶，第四個(gè)咨詢工程處置的客戶數(shù)為第四個(gè)咨詢工程處置的客戶數(shù)為1戶，獲得的利潤(rùn)最大，最戶，獲得的利潤(rùn)最大，最大利潤(rùn)為大利潤(rùn)為28。管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué)三、消費(fèi)與存貯問題三、消費(fèi)與存貯問題 例例4.某公司為主要電力公司消費(fèi)大型變壓器，由于電力某公司為主要電力公司消費(fèi)大型變壓器，由于電力公司采取預(yù)訂方式購(gòu)買，所以該公司可以預(yù)測(cè)未來幾個(gè)月公司采取預(yù)訂方式購(gòu)買，所以該公司可以預(yù)測(cè)未來幾個(gè)月的需求量。為確

29、保需求，該公司為新的一年前四個(gè)月制定的需求量。為確保需求，該公司為新的一年前四個(gè)月制定一項(xiàng)消費(fèi)方案，這四個(gè)月的需求如下表所示。一項(xiàng)消費(fèi)方案，這四個(gè)月的需求如下表所示。3 3動(dòng)態(tài)規(guī)劃的運(yùn)用動(dòng)態(tài)規(guī)劃的運(yùn)用(1) (1) 管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué) 3 3動(dòng)態(tài)規(guī)劃的運(yùn)用動(dòng)態(tài)規(guī)劃的運(yùn)用(1) (1) 每臺(tái)變壓器在倉(cāng)庫(kù)中由這個(gè)月存到下個(gè)月的儲(chǔ)存費(fèi)為每臺(tái)變壓器在倉(cāng)庫(kù)中由這個(gè)月存到下個(gè)月的儲(chǔ)存費(fèi)為1，倉(cāng)，倉(cāng)庫(kù)的最大儲(chǔ)存才干為庫(kù)的最大儲(chǔ)存才干為3臺(tái)，另外，知道在臺(tái)，另外，知道在1月月1日時(shí)倉(cāng)庫(kù)里存日時(shí)倉(cāng)庫(kù)里存有一臺(tái)變壓器，要求在有一臺(tái)變壓器，要求在4月月30日倉(cāng)庫(kù)的庫(kù)存量為零。試問該日倉(cāng)庫(kù)的庫(kù)存量為零。試問

30、該公司應(yīng)如何制定消費(fèi)方案，使得四個(gè)月的消費(fèi)本錢和儲(chǔ)存總公司應(yīng)如何制定消費(fèi)方案，使得四個(gè)月的消費(fèi)本錢和儲(chǔ)存總費(fèi)用最少？費(fèi)用最少？消費(fèi)本錢的調(diào)試費(fèi)為消費(fèi)本錢的調(diào)試費(fèi)為4，消費(fèi)本錢除了調(diào)試費(fèi)用外，每月消，消費(fèi)本錢除了調(diào)試費(fèi)用外，每月消費(fèi)的頭兩臺(tái)各破費(fèi)為費(fèi)的頭兩臺(tái)各破費(fèi)為2，后兩臺(tái)破費(fèi)為，后兩臺(tái)破費(fèi)為1。最大消費(fèi)才干每。最大消費(fèi)才干每月為月為4臺(tái)，消費(fèi)本錢如下表所示。臺(tái)，消費(fèi)本錢如下表所示。管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué)解：我們按月份來劃分階段，第解：我們按月份來劃分階段，第i個(gè)月為第個(gè)月為第i階段：階段：i=1,2,3,4). 設(shè)設(shè)sk為第為第k階段期初庫(kù)存量；階段期初庫(kù)存量； k=1,2,3,4 x

31、k為第為第k階段消費(fèi)量；階段消費(fèi)量； k=1,2,3,4dk為第為第k階段需求量；階段需求量； k=1,2,3,4， 由于下個(gè)月初的庫(kù)存量等于上個(gè)月初的庫(kù)存量加上上個(gè)由于下個(gè)月初的庫(kù)存量等于上個(gè)月初的庫(kù)存量加上上個(gè)月的產(chǎn)量減去上個(gè)月的需求量，我們就得到了如下形狀轉(zhuǎn)月的產(chǎn)量減去上個(gè)月的需求量，我們就得到了如下形狀轉(zhuǎn)移方程：移方程：11s121111112xxdxs4222223xsdxss1333334xsdxss30344444445sxxsdxss3 3動(dòng)態(tài)規(guī)劃的運(yùn)用動(dòng)態(tài)規(guī)劃的運(yùn)用(1) (1) 各月的消費(fèi)本錢和儲(chǔ)存費(fèi)用分別用各月的消費(fèi)本錢和儲(chǔ)存費(fèi)用分別用ck(xk)和和hk(sk,xk)表

32、示，表示，即階段目的函數(shù)為：即階段目的函數(shù)為：rk(sk,xk)=ck(xk)+hk(sk,xk)管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué) 第四階段：第四階段：r4(s4,x4)=c4(x4)+h4(s4,x4)=c4(3-s4)3 3動(dòng)態(tài)規(guī)劃的運(yùn)用動(dòng)態(tài)規(guī)劃的運(yùn)用(1) (1) 管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué)第三階段：第三階段：r3(s3,x3)=c(x3)+h(s3,x3),s4=s3+x3-13 3動(dòng)態(tài)規(guī)劃的運(yùn)用動(dòng)態(tài)規(guī)劃的運(yùn)用(1) (1) x3s3r3(s3,x3)+f4(s3+x3-1) 0 1 2 3 4f3(s3)x3*0 6+0+9 8+1+8 9+2+6 10+3+0 13410+0+9 6

33、+1+8 8+2+6 9+3+0 9020+1+8 6+2+6 8+3+0 9030+2+6 6+3+0 80管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué)第二階段：第二階段：r2(s2,x2)=c(x2)+h(s2,x2),s3=s2+x2-43 3動(dòng)態(tài)規(guī)劃的運(yùn)用動(dòng)態(tài)規(guī)劃的運(yùn)用(1) (1) x2s2r2(s2,x2)+f3(s2+x2-4) 0 1 2 3 4f2(s2)x2*0 10+0+13 2341 9+0+13 10+1+9 2242 8+0+13 9+1+9 10+2+9 1933 6+0+13 8+1+9 9+2+9 10+3+8 182管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué)第一階段：第一階段：r1(s1

34、,x1)=c(x1)+h(s1,x1),s2=s1+x1-2=x1-13 3動(dòng)態(tài)規(guī)劃的運(yùn)用動(dòng)態(tài)規(guī)劃的運(yùn)用(1) (1) x1s1r1(s1,x1)+f2(x1-1) 0 1 2 3 4f1(s1)x1*1 6+0+23 8+1+20 9+2+19 10+3+8 291,2利用遞推關(guān)系可以從得到兩組最優(yōu)解：利用遞推關(guān)系可以從得到兩組最優(yōu)解：x1=1s2=x1-1=1-1=0 x2=4 s3=s2+x2-4=0+4-4=0 x3=4 s4=s3+x3-1=0+4-1=3 x4=0，即，即1、2、3、4月份分別消費(fèi)月份分別消費(fèi)1、4、4、0臺(tái)變壓器，能使四個(gè)月的消臺(tái)變壓器，能使四個(gè)月的消費(fèi)本錢和存儲(chǔ)

35、總費(fèi)用最省，最小費(fèi)用為費(fèi)本錢和存儲(chǔ)總費(fèi)用最省，最小費(fèi)用為29 。x1=2s2=x1-1=2-1=1 x2=4 s3=s2+x2-4=1+4-4=1 x3=0 s4=s3+x3-1=1+0-1=0 x4=3，即，即1、2、3、4月份分別消費(fèi)月份分別消費(fèi)2、4、0、3臺(tái)變壓器，能使四個(gè)月的消臺(tái)變壓器，能使四個(gè)月的消費(fèi)本錢和存儲(chǔ)總費(fèi)用最省，最小費(fèi)用為費(fèi)本錢和存儲(chǔ)總費(fèi)用最省，最小費(fèi)用為29。管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué)3 3動(dòng)態(tài)規(guī)劃的運(yùn)用動(dòng)態(tài)規(guī)劃的運(yùn)用(1) (1) 四、系統(tǒng)可靠性問題 例5.某科研工程組由三個(gè)小組用不同的手段分別研討，它們失敗的概率各為0.40，0.60，0.80。為了減少三個(gè)小組都

36、失敗的能夠性，現(xiàn)決議給三個(gè)小組中增派兩名高級(jí)科學(xué)家，到各小組后，各小組科研工程失敗概率如下表： 高級(jí)科學(xué)家高級(jí)科學(xué)家小組小組12300.400.600.8010.200.400.5020.150.200.30問如何分派科學(xué)家才干使三個(gè)小組都失敗的概率即科研問如何分派科學(xué)家才干使三個(gè)小組都失敗的概率即科研工程最終失敗的概率最?。抗こ套罱K失敗的概率最??？管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué)3 3動(dòng)態(tài)規(guī)劃的運(yùn)用動(dòng)態(tài)規(guī)劃的運(yùn)用(1) (1) 解：用逆序算法。設(shè) 階段：每個(gè)研討小組為一個(gè)階段，共分為3個(gè)階段進(jìn)展，且階段階段123小組小組123決策變量決策變量xk：分配給第：分配給第k小組的高級(jí)科學(xué)家人數(shù)，相應(yīng)的

37、失小組的高級(jí)科學(xué)家人數(shù)，相應(yīng)的失敗概率為敗概率為rk(sk,xk)k=1,2,3，即為階段目的函數(shù)；，即為階段目的函數(shù)；形狀變量形狀變量sk：分配給第：分配給第k小組至第小組至第3小組的高級(jí)科學(xué)家人數(shù)小組的高級(jí)科學(xué)家人數(shù)k=1,2,3)。那么形狀轉(zhuǎn)移方程為：那么形狀轉(zhuǎn)移方程為： s1=1 s2=s1-x1 s3=s2-x2遞推方程為：遞推方程為：fk(sk)=minrk(sk,xk) fk+1(sk+1)管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué)3 3動(dòng)態(tài)規(guī)劃的運(yùn)用動(dòng)態(tài)規(guī)劃的運(yùn)用(1) (1) 第一階段：s3=x3 x2s2r2(s2,x2) f3(s2-x2) f2(s2) x2*01200.600.80

38、0.48010.600.500.400.800.30020.600.300.400.500.200.800.162 x3s3 r3(s3,x3) f3(s3) x3*0120 0.800.80010.500.50120.300.302第二階段：第二階段：s3=s2-x2管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué)3 3動(dòng)態(tài)規(guī)劃的運(yùn)用動(dòng)態(tài)規(guī)劃的運(yùn)用(1) (1) 第一階段：第一階段： x1s1r1(s1,x1) f2(2-x1)f1(s1)x1*01220.400.160.200.30 0.150.480.061最優(yōu)解為最優(yōu)解為 x1=1s2=s1-x1=2-1=1 x2=0 s3=s2-x2=1-0=1 x3

39、=1；即當(dāng)分配給第即當(dāng)分配給第1、2、3小組的高級(jí)科學(xué)家人數(shù)分別為小組的高級(jí)科學(xué)家人數(shù)分別為1、0、1人時(shí)，科研工程最終失敗的概率最小，最小概率為人時(shí)，科研工程最終失敗的概率最小，最小概率為0.060。管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué)4 4動(dòng)態(tài)規(guī)劃的運(yùn)用動(dòng)態(tài)規(guī)劃的運(yùn)用(2)(2)* *一、延續(xù)確定性動(dòng)態(tài)規(guī)劃一、延續(xù)確定性動(dòng)態(tài)規(guī)劃 對(duì)于形狀變量和決策變量只取延續(xù)值，對(duì)于形狀變量和決策變量只取延續(xù)值，過程的演化方式為確定性時(shí)，這種動(dòng)態(tài)規(guī)劃過程的演化方式為確定性時(shí)，這種動(dòng)態(tài)規(guī)劃問題就稱為延續(xù)確定性動(dòng)態(tài)規(guī)劃問題。問題就稱為延續(xù)確定性動(dòng)態(tài)規(guī)劃問題。管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué)4 4動(dòng)態(tài)規(guī)劃的運(yùn)用動(dòng)態(tài)規(guī)劃的運(yùn)

40、用(2)(2)* *機(jī)器負(fù)荷分配問題機(jī)器負(fù)荷分配問題 例例1 一種機(jī)器能在高低兩種不同的負(fù)荷形狀下任務(wù)。設(shè)一種機(jī)器能在高低兩種不同的負(fù)荷形狀下任務(wù)。設(shè)機(jī)器在高負(fù)荷下消費(fèi)時(shí)，產(chǎn)量函數(shù)為機(jī)器在高負(fù)荷下消費(fèi)時(shí)，產(chǎn)量函數(shù)為P1=8u1，其中，其中u1為在為在高負(fù)荷形狀下消費(fèi)的機(jī)器數(shù)目，年完好率為高負(fù)荷形狀下消費(fèi)的機(jī)器數(shù)目，年完好率為a=0.7，即到年，即到年底有底有70的機(jī)器堅(jiān)持完好。在低負(fù)荷下消費(fèi)時(shí)，產(chǎn)量函數(shù)的機(jī)器堅(jiān)持完好。在低負(fù)荷下消費(fèi)時(shí)，產(chǎn)量函數(shù)為為P2=5u2，其中，其中u2為在低負(fù)荷形狀下消費(fèi)的機(jī)器數(shù)目，年為在低負(fù)荷形狀下消費(fèi)的機(jī)器數(shù)目，年完好率為完好率為b=0.9。設(shè)開場(chǎng)消費(fèi)時(shí)共有。設(shè)開場(chǎng)

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

42、7xk+0.9(sk-xk) 階段目的 rk(sk,xk)=8xk+5(sk-xk) 最優(yōu)目的函數(shù))()58max)(11kkkkkkksfxsxsf（kksx 0(k=1,2,3,4,5 ) ,f6(s6)=0管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué)4 4動(dòng)態(tài)規(guī)劃的運(yùn)用動(dòng)態(tài)規(guī)劃的運(yùn)用(2)(2)* * 第第5階段：階段： 由于由于f5(s5)=max8x5+5(s5-x5)=max5s5+3x5, 而而0 x5s5, 故有故有x5* =s5，于是有，于是有f5(s5)=8s5。 第第4階段：階段： 4 . 12 .12max)(2 .126 .13max)(9 . 07 . 0 8)(58max8)(5

43、8max)()(58max)(4404440444444054440554440444444444444xsxsxxsxxsxsxsxsfxsxsfsxsxsxsxsx 管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué)4 4動(dòng)態(tài)規(guī)劃的運(yùn)用動(dòng)態(tài)規(guī)劃的運(yùn)用(2)(2)* * 故有故有x4*=s4 ，f4(s4)=13.6s4。 對(duì)前幾個(gè)階段依次類推，可得對(duì)前幾個(gè)階段依次類推，可得 f3(s3)=max17.24s3+0.28x3,而而0 x3s3，故當(dāng)，故當(dāng)x3*=s3時(shí)，時(shí)，有有f3(s3)=17.5s3， f2(s2)=max20.768s2-0.704x2,而而0 x2s2，故當(dāng)，故當(dāng)x2*=0時(shí)，時(shí)，有有f2

44、(s2)=20.768s2， f1(s1)=max23.6912s1-1.1236x1,而而0 x1s1，故當(dāng)，故當(dāng)x1*=0時(shí)，時(shí)，有有f1(s1)=23.6912s1。 綜上所述，得最優(yōu)解為綜上所述，得最優(yōu)解為x1*=0，x2*=0，x3*=s3 ，x4*= s4, x5*=s5。 由于期初共有完好機(jī)器由于期初共有完好機(jī)器1000臺(tái)，故臺(tái)，故s1=1000,有有f1(s1)=23.6912s123691.2，即，即5年最大的產(chǎn)量為年最大的產(chǎn)量為23691.2。而。而 s2=0.7x1*+0.9(s1-x1*)=0.9s1=0.91000=900, s3=0.7x2*+0.9(s2-x2*)

45、= 0.9s2=0.9900=810, s4= 0.7x3*+0.9(s3-x3*)= 0.7s3=0.7810=567 s5= 0.7x4*+0.9(s4-x4*)= 0.7s4=0.7567=397 s6= 0.7x5*+0.9(s5-x5*)= 0.7s5=0.7397=278 這意味著前兩年應(yīng)把年初完好機(jī)器完全投入低負(fù)荷消費(fèi)，這意味著前兩年應(yīng)把年初完好機(jī)器完全投入低負(fù)荷消費(fèi)，后三年應(yīng)把年初完好機(jī)器完全投入高負(fù)荷消費(fèi)。后三年應(yīng)把年初完好機(jī)器完全投入高負(fù)荷消費(fèi)。管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué)4 4動(dòng)態(tài)規(guī)劃的運(yùn)用動(dòng)態(tài)規(guī)劃的運(yùn)用(2)(2)* * 下一步任務(wù)是確定每年初的形狀，按照從前向下一步任

46、務(wù)是確定每年初的形狀，按照從前向后的順序依次計(jì)算出每年年初完好的機(jī)器數(shù)目。后的順序依次計(jì)算出每年年初完好的機(jī)器數(shù)目。知知s1=1000,根據(jù)形狀轉(zhuǎn)移方程，有根據(jù)形狀轉(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é)4 4動(dòng)態(tài)規(guī)劃的運(yùn)用動(dòng)態(tài)規(guī)劃的運(yùn)用(2)(2)* * 上面所討論的最優(yōu)戰(zhàn)略過程，初始端形狀上面所討論的最優(yōu)戰(zhàn)略過程，初始端形狀s1=100

47、0臺(tái)是固定的，終點(diǎn)形狀臺(tái)是固定的，終點(diǎn)形狀s6沒有要求。這種沒有要求。這種情況下得到最優(yōu)決策稱為初始端固定終點(diǎn)自在的情況下得到最優(yōu)決策稱為初始端固定終點(diǎn)自在的最優(yōu)戰(zhàn)略。最優(yōu)戰(zhàn)略。 假設(shè)終點(diǎn)附加一定的條件，那么問題就稱為假設(shè)終點(diǎn)附加一定的條件，那么問題就稱為“終端固定問題。例如，規(guī)定在第終端固定問題。例如，規(guī)定在第5年度終了時(shí)年度終了時(shí)仍要堅(jiān)持仍要堅(jiān)持500臺(tái)機(jī)器完好而不是臺(tái)機(jī)器完好而不是278臺(tái)，應(yīng)如臺(tái)，應(yīng)如何安排消費(fèi)才干使得總產(chǎn)量最大？何安排消費(fèi)才干使得總產(chǎn)量最大？ 下面來分析：下面來分析： 根據(jù)終點(diǎn)條件有根據(jù)終點(diǎn)條件有 可得可得500)(9 . 07 . 05556xsxs25005 .

48、455sx管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué)4 4動(dòng)態(tài)規(guī)劃的運(yùn)用動(dòng)態(tài)規(guī)劃的運(yùn)用(2)(2)* * 顯然，由于固定了終點(diǎn)的形狀，顯然，由于固定了終點(diǎn)的形狀，x5的取值遭的取值遭到了約束。因此有到了約束。因此有 類似的，類似的， 容易解得容易解得 ，f4(s4)=21.7s4-7500。75005 .18)25005 . 4(5)25005 . 4(8max)(555555sssssf75007 . 07 .21max75005 .18)(58max)()(58max)(4405444055444044444444xssxsxsfxsxsfsxsxsx0*4x管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué)4 4動(dòng)態(tài)規(guī)劃的

49、運(yùn)用動(dòng)態(tài)規(guī)劃的運(yùn)用(2)(2)* * 依次類推，得依次類推，得 f3(s3)=24.5s3-7500 f2(s2)=27.1s2-7500 f1(s1)=29.4s1-7500 再采用順序方法遞推計(jì)算各年的形狀，有再采用順序方法遞推計(jì)算各年的形狀，有 s1=1000， 0*1*2*3xxx9009 . 0)(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é)4 4動(dòng)態(tài)規(guī)劃的運(yùn)用動(dòng)態(tài)規(guī)

50、劃的運(yùn)用(2)(2)* * 可見，為了使終點(diǎn)完好的機(jī)器數(shù)量添加可見，為了使終點(diǎn)完好的機(jī)器數(shù)量添加到到500臺(tái)，需求安排前四年中全部完好機(jī)器臺(tái)，需求安排前四年中全部完好機(jī)器都要投入低負(fù)荷消費(fèi)，且在第都要投入低負(fù)荷消費(fèi)，且在第5年，也只能年，也只能全部投入高負(fù)荷。全部投入高負(fù)荷。 相應(yīng)的最優(yōu)目的為相應(yīng)的最優(yōu)目的為 f1(s1)=29.4s1-750021900。 可以看到，由于添加了附加條件，總產(chǎn)可以看到，由于添加了附加條件，總產(chǎn)量量f1(s1)要比終點(diǎn)自在情況下的產(chǎn)量要低。要比終點(diǎn)自在情況下的產(chǎn)量要低。管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué)二、離散隨機(jī)性動(dòng)態(tài)規(guī)劃二、離散隨機(jī)性動(dòng)態(tài)規(guī)劃 隨機(jī)型的動(dòng)態(tài)規(guī)劃是指

51、形狀的轉(zhuǎn)移律是不確定隨機(jī)型的動(dòng)態(tài)規(guī)劃是指形狀的轉(zhuǎn)移律是不確定的，即對(duì)給定的形狀和決策，下一階段的到達(dá)形的，即對(duì)給定的形狀和決策，下一階段的到達(dá)形狀是具有確定概率分布的隨機(jī)變量，這個(gè)概率分狀是具有確定概率分布的隨機(jī)變量，這個(gè)概率分布由本階段的形狀和決策完全確定。隨機(jī)型動(dòng)態(tài)布由本階段的形狀和決策完全確定。隨機(jī)型動(dòng)態(tài)規(guī)劃的根本構(gòu)造如以下圖：規(guī)劃的根本構(gòu)造如以下圖： 4 4動(dòng)態(tài)規(guī)劃的運(yùn)用動(dòng)態(tài)規(guī)劃的運(yùn)用(2)(2)* * sk形狀 xk決策概率k階段的收益p1p2pN.k + 1 階 段 的 形 狀sk+1c1c2cN 1 2N管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué)4 4動(dòng)態(tài)規(guī)劃的運(yùn)用動(dòng)態(tài)規(guī)劃的運(yùn)用(2)(2)*

52、 * 圖中圖中N表示第表示第k+1階段能夠的形狀數(shù)，階段能夠的形狀數(shù)，p1、p2、pN為給定形狀為給定形狀sk和決策和決策xk的前提下，能夠的前提下，能夠到達(dá)下一個(gè)形狀的概率。到達(dá)下一個(gè)形狀的概率。ci為從為從k階段形狀階段形狀sk轉(zhuǎn)移轉(zhuǎn)移到到k+1 階段形狀為階段形狀為i時(shí)的目的函數(shù)值。時(shí)的目的函數(shù)值。 在隨機(jī)性的動(dòng)態(tài)規(guī)劃問題中，由于下一階段到達(dá)在隨機(jī)性的動(dòng)態(tài)規(guī)劃問題中，由于下一階段到達(dá)的形狀和階段的效益值不確定，只能根據(jù)各階段的形狀和階段的效益值不確定，只能根據(jù)各階段的期望效益值進(jìn)展優(yōu)化。的期望效益值進(jìn)展優(yōu)化。管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué)離散隨機(jī)性動(dòng)態(tài)規(guī)劃離散隨機(jī)性動(dòng)態(tài)規(guī)劃 例2 某公司承

53、當(dāng)一種新產(chǎn)品研制義務(wù)，合同要求三個(gè)月內(nèi)交出一件合格的樣品，否那么將索賠2000元。根據(jù)有閱歷的技術(shù)人員估計(jì)，試制品合格的概率為0.4，每次試制一批的裝配費(fèi)為200元，每件產(chǎn)品的制造本錢為100元。每次試制的周期為1個(gè)月。問該如何安排試制，每次消費(fèi)多少件，才干使得期望費(fèi)用最小？ 管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué)離散隨機(jī)性動(dòng)態(tài)規(guī)劃離散隨機(jī)性動(dòng)態(tài)規(guī)劃 解：把三次試制當(dāng)作三個(gè)階段k=1,2,3,決策變量xk表示第k次消費(fèi)的產(chǎn)品的件數(shù)；形狀變量sk表示第k次試制前能否曾經(jīng)消費(fèi)出合格品，假設(shè)有合格品，那么sk=0；假設(shè)沒有合格品，記sk=1。最優(yōu)函數(shù)fk(sk)表示從形狀sk、決策xk出發(fā)的第k階段以后的最小

54、期望費(fèi)用。故有fk(0)0。 消費(fèi)出一件合格品的概率為0.4，所以消費(fèi)xk件產(chǎn)品都不合格的概率為 ，至少有一件合格品的概率為1- ，故有形狀轉(zhuǎn)移方程為 kx6 . 0kkxkxkspsp6 . 01)0(6 . 0) 1(11kx6 . 0管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué)離散隨機(jī)性動(dòng)態(tài)規(guī)劃離散隨機(jī)性動(dòng)態(tài)規(guī)劃 用用C(xk)C(xk)表示第表示第k k階段的費(fèi)用，第階段的費(fèi)用，第k k階段的費(fèi)用包階段的費(fèi)用包括制造本錢和裝配費(fèi)用，故有括制造本錢和裝配費(fèi)用，故有 根據(jù)形狀轉(zhuǎn)移方程以及根據(jù)形狀轉(zhuǎn)移方程以及C(xk)C(xk)，可得到，可得到 0002)(kkkkxxxxC)1 (6 . 0)0()6 .

55、 01 ()(min) 1 (11kxkxkxkffxcfkkk)1 (6 . 0)(min1kxkxfxckk管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué)離散隨機(jī)性動(dòng)態(tài)規(guī)劃離散隨機(jī)性動(dòng)態(tài)規(guī)劃 假設(shè)3個(gè)月后沒有試制出一件合格品，那么要承當(dāng)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é)離散隨機(jī)性動(dòng)態(tài)規(guī)劃離散隨機(jī)性動(dòng)態(tài)規(guī)劃當(dāng)k=2時(shí)，計(jì)算如下表： x2 s2 C(x2)+8.56f2

56、(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é)離散隨機(jī)性動(dòng)態(tài)規(guī)劃離散隨機(jī)性動(dòng)態(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.85 7.116.46 6.48 6.46 2 0.61x管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué)離散隨機(jī)性動(dòng)態(tài)規(guī)劃離散隨機(jī)性動(dòng)態(tài)規(guī)劃 上面三個(gè)表中并沒有列出xk取更大數(shù)值的情況，由于可以證明以后的C(xk)+ fk+1(1)的值是對(duì)xk單調(diào)添加的。 因此得到的最優(yōu)戰(zhàn)略是，在第1個(gè)階段試制2件產(chǎn)品；假設(shè)都不合格，在第2階段試制3件產(chǎn)品；假設(shè)仍都不合格，那么在第3個(gè)階段試制5件產(chǎn)品。該戰(zhàn)略得到的最小的期望費(fèi)用6.46。 0.6kx管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué)離散隨機(jī)性動(dòng)態(tài)規(guī)劃離散隨機(jī)性動(dòng)態(tài)規(guī)劃