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

1、動(dòng)態(tài)規(guī)劃是一種研究多階段決策問(wèn)題的理論和方法。這種方法把一個(gè)多階段決策問(wèn)題轉(zhuǎn)化成一系列相互聯(lián)系的單階段決策問(wèn)題來(lái)求解。 動(dòng)態(tài)規(guī)劃主要應(yīng)用于最短路問(wèn)題、裝載問(wèn)題、庫(kù)存問(wèn)題、資源分配、生產(chǎn)過(guò)程最優(yōu)化問(wèn)題。 動(dòng)態(tài)規(guī)劃模型可以分為離散確定性、離散隨機(jī)性、連續(xù)確定性、連續(xù)隨機(jī)性四種決策過(guò)程。其中最基本的是離散確定性過(guò)程,第6章 動(dòng)態(tài)規(guī)劃,第6章 動(dòng)態(tài)規(guī)劃,1 多階段的決策問(wèn)題 2 最優(yōu)化原理與動(dòng)態(tài)規(guī)劃的數(shù)學(xué) 模型 3 動(dòng)態(tài)規(guī)劃應(yīng)用舉例,1 多階段的決策問(wèn)題,多階段決策問(wèn)題：可以分為若干個(gè)互相聯(lián)系的階段，在每個(gè)階段分別對(duì)應(yīng)著一組可以選取的決策，當(dāng)每個(gè)階段的決策選定以后，過(guò)程也就隨之確定。 多階段決策問(wèn)題，

2、就是要在所有可能采取的策略中間選取一個(gè)最優(yōu)的策略，是在預(yù)定的標(biāo)準(zhǔn)下得到最好的效果,例1 最短路線問(wèn)題。設(shè)有一旅行者從下圖中的A點(diǎn)出發(fā)，途中要經(jīng)過(guò)B、C、D等處，最后到達(dá)終點(diǎn)E。從A到E有很多條路可以選擇，各點(diǎn)之間的距離如圖所示，問(wèn)該旅行者應(yīng)選擇哪一條路線，使從A到E的總路程最短,A,B3,B2,B1,C3,C2,C1,D2,D1,E,2,2,3,5,1,5,3,5,6,5,7,6,3,3,4,1,4,3,4,3,用窮舉法的計(jì)算量: 如果從A到E的站點(diǎn)有k個(gè)，除A、E之外每站有3個(gè)位置則 總共有3k-12條路徑； 計(jì)算各路徑長(zhǎng)度總共要進(jìn)行 (k+1) 3k-12次加法以及3k- 12-1次比較。

3、隨著 k 的值增加時(shí)，需要進(jìn)行的加法和比較的 次數(shù)將迅速增加； 例如當(dāng) k=20時(shí)，加法次數(shù)為 4.25508339662271015 次， 比較 1.37260754729771014 次。若用1億次/秒的計(jì)算機(jī)計(jì)算 需要約508天,例2 設(shè)有某種機(jī)器設(shè)備，用于完成兩類工作A和B.若k年初完好機(jī)器的數(shù)量為sk，若以數(shù)量xk用于A，余下的(sk-xk)用于工作B，則該年的預(yù)期收入為g(xk)+h(sk-xk).這里g(xk)和h(sk-xk)是已知函數(shù)，且g(0)=h(0)=0.又機(jī)器設(shè)備在使用中會(huì)有損壞，設(shè)機(jī)器用于工作A時(shí)，一年后能繼續(xù)使用的完好機(jī)器數(shù)占年初投入量的a%；若用于B項(xiàng)工作時(shí)，一

4、年后能繼續(xù)使用的完好機(jī)器數(shù)占年初投入量的b%，即下一年初能繼續(xù)用于完成這兩項(xiàng)工作的設(shè)備數(shù)為sk+1=axk+b(sk-xk).設(shè)第一年初完好的機(jī)器總數(shù)為s0，問(wèn)在連續(xù)三年內(nèi)每年應(yīng)如何分配用于A、B兩項(xiàng)工作的機(jī)器數(shù)，使三年的總收益最大,例3 將一個(gè)數(shù)c(c0)分成n個(gè)部分c1,c2,.,cn之和，且ci0(i=1,.,n)，問(wèn)應(yīng)如何分割使其乘積 為最大,2 最優(yōu)化原理與動(dòng)態(tài)規(guī)劃的數(shù)學(xué)模型,動(dòng)態(tài)規(guī)劃問(wèn)題的解題思路 動(dòng)態(tài)規(guī)劃的基本概念 最優(yōu)化原理與動(dòng)態(tài)規(guī)劃的數(shù)學(xué)模型 逆序解法與順序解法 動(dòng)態(tài)規(guī)劃模型的分類,2.1 動(dòng)態(tài)規(guī)劃問(wèn)題的解題思路,基本思路：是將一個(gè)n階段的決策問(wèn)題轉(zhuǎn)化為依次求解n個(gè)具有遞推關(guān)

5、系的單階段的決策問(wèn)題，從而簡(jiǎn)化計(jì)算過(guò)程。 在例1中，這種轉(zhuǎn)化的實(shí)現(xiàn)是從終點(diǎn)E出發(fā)一步步進(jìn)行反推，這種算法稱為逆序算法,例1 最短路線問(wèn)題。設(shè)有一旅行者從下圖中的A點(diǎn)出發(fā)，途中要經(jīng)過(guò)B、C、D等處，最后到達(dá)終點(diǎn)E。從A到E有很多條路可以選擇，各點(diǎn)之間的距離如圖所示，問(wèn)該旅行者應(yīng)選擇哪一條路線，使從A到E的總路程最短,A,B3,B2,B1,C3,C2,C1,D2,D1,E,2,2,3,5,1,5,3,5,6,5,7,6,3,3,4,1,4,3,4,3,按逆序推算，例1的計(jì)算步驟為,從D出發(fā)，f(D1)=3;f(D2)=4。 從C出發(fā)，f(C1)=4;f(C2)=7;f(C3)=6。 從B出發(fā)，f(

6、B1)=11;f(B2)=7;f(B3)=8。 從A出發(fā)，f(A)=11,2.2 動(dòng)態(tài)規(guī)劃的基本概念,1、階段(stage).是指一個(gè)問(wèn)題需要做出決策的步數(shù)。如例1中旅行者需要在A、B、C、D四個(gè)階段做出下一步的決策。通常用k來(lái)表示問(wèn)題包含的階段數(shù)，稱為階段變量。 2、狀態(tài)(state).這是動(dòng)態(tài)規(guī)劃中最關(guān)鍵的參數(shù)，它既反映前面各階段決策的結(jié)局，又是本階段做出決策的出發(fā)點(diǎn)和依據(jù)。狀態(tài)是動(dòng)態(tài)規(guī)劃問(wèn)題各階段信息的傳遞點(diǎn)和結(jié)合點(diǎn)，第k階段的狀態(tài)通常用狀態(tài)變量sk來(lái)描述。在例1中第2階段的狀態(tài)s2=(B1,B2,B3,3、決策(decision).是指某階段初從給定的狀態(tài)出發(fā)，決策者在面臨的若干種不同

7、方案中做出的選擇。用Dk(sk)表示k階段狀態(tài)為sk時(shí)決策允許的取值范圍，xk(sk)表示第k階段狀態(tài)為sk時(shí)對(duì)方案的選擇。如例1中D2(B1)=C1,C2,C3。 4、策略(policy)和子策略(sub policy).動(dòng)態(tài)規(guī)劃問(wèn)題各階段決策組成的序列總體稱作一個(gè)策略。如：x1(s1),x2(s2),.,xn(sn)。 把從某一階段開(kāi)始到過(guò)程最終的決策序列稱為問(wèn)題的子過(guò)程策略或子策略。如：xk(sk),xk+1(sk+1),.,xn(sn,5、狀態(tài)轉(zhuǎn)移律，也稱狀態(tài)轉(zhuǎn)移方程.從sk的某一狀態(tài)值出發(fā)，當(dāng)決策變量xk(sk)的取值決定后，下一階段狀態(tài)變量sk+1的取值也就隨之確定。這種從上一階段

8、的某一狀態(tài)值到下一階段某一狀態(tài)值的轉(zhuǎn)移的規(guī)律成為狀態(tài)轉(zhuǎn)移律。如sk+1=T(sk,xk(sk)。 6、指標(biāo)函數(shù).階段的指標(biāo)函數(shù)是對(duì)應(yīng)某一階段狀態(tài)和從該狀態(tài)出發(fā)的一個(gè)階段的決策的某種效益度量，用rk(sk,xk)表示。過(guò)程的指標(biāo)函數(shù)是指從狀態(tài)sk(k=1,2,.,n)出發(fā)至過(guò)程最終，當(dāng)采取某種子策略時(shí)，按預(yù)定標(biāo)準(zhǔn)得到的效益值。所謂最優(yōu)指標(biāo)函數(shù)，是指對(duì)某一確定狀態(tài)選取最優(yōu)策略后得到的指標(biāo)函數(shù)值。記作fk(sk,2.3 最優(yōu)化原理與動(dòng)態(tài)規(guī)劃的數(shù)學(xué)模型,求解動(dòng)態(tài)規(guī)劃的最優(yōu)化原理(R.Bellman)：作為整個(gè)過(guò)程的最優(yōu)策略具有這樣的性質(zhì)，無(wú)論過(guò)去的狀態(tài)和決策如何，對(duì)先前決策所形成的狀態(tài)而言，余下的諸決

9、策必構(gòu)成最優(yōu)策略。 基本方程：對(duì)于n階段的動(dòng)態(tài)規(guī)劃問(wèn)題，在求子過(guò)程上的最優(yōu)指標(biāo)函數(shù)時(shí)，k子過(guò)程與k+1過(guò)程有如下遞推關(guān)系： fk(sk)=minrk(sk,xk)+fk+1(xk+1),k=n,.,2,1 邊界條件（終點(diǎn)條件）：fn+1(xn+1)=0 邊界條件是指從最后一個(gè)階段向前逆推時(shí)需要確定的條件,關(guān)于階段的劃分、狀態(tài)變量、決策變量、允許決策集合和狀態(tài)轉(zhuǎn)移方程，應(yīng)注意如下幾點(diǎn),狀態(tài)變量的確定是構(gòu)造動(dòng)態(tài)規(guī)劃模型中最關(guān)鍵的一步，狀態(tài)變量首先應(yīng)描述反映研究過(guò)程的演變特征，其次它應(yīng)包含到達(dá)這個(gè)狀態(tài)前的足夠信息，并具有無(wú)后效性，還應(yīng)具有可知性。 決策變量是對(duì)過(guò)程進(jìn)行控制的手段，復(fù)雜的問(wèn)題決策變量也

10、可以是多維的向量，允許決策集合相當(dāng)于線性規(guī)劃問(wèn)題中的約束條件。 狀態(tài)轉(zhuǎn)移律。當(dāng)給出sk、xk的取值后，如果sk+1的取值唯一確定，相應(yīng)的決策過(guò)程稱為確定性的多階段決策過(guò)程，否則稱為隨機(jī)性的多階段決策過(guò)程。 指標(biāo)函數(shù)是衡量決策過(guò)程效益高低的指標(biāo)，它是一個(gè)定義在全過(guò)程或從k到n階段的子過(guò)程上的函數(shù)，指標(biāo)函數(shù)必須具有遞推性,2.4 逆序解法與順序解法,動(dòng)態(tài)規(guī)劃有兩種基本方法：逆序解法與順序解法。 所謂逆序解法，是從問(wèn)題的最后一個(gè)階段開(kāi)始，逆多階段決策的實(shí)際過(guò)程反向?qū)?yōu)。 順序解法則從問(wèn)題的最初階段開(kāi)始，同多階段決策的實(shí)際過(guò)程順序?qū)?yōu)。 具體采取哪一種解法，應(yīng)根據(jù)問(wèn)題的初始條件和終端條件來(lái)決定,2.5

11、 動(dòng)態(tài)規(guī)劃模型的分類,3 動(dòng)態(tài)規(guī)劃應(yīng)用舉例,資源分配問(wèn)題 背包問(wèn)題 生產(chǎn)與存貯問(wèn)題 其它,某公司擬將某種設(shè)備5臺(tái)，分配給所屬的甲、乙、丙三個(gè)工廠，各工廠獲得此設(shè)備后，預(yù)測(cè)可創(chuàng)造的利潤(rùn)如下表所示，問(wèn)應(yīng)如何分配這5臺(tái)設(shè)備給3個(gè)工廠，可使所創(chuàng)造利潤(rùn)最大,資源分配問(wèn)題,解：將問(wèn)題按工廠分為三個(gè)階段，甲、乙、丙三廠分別編號(hào)為1、2、3廠。設(shè)： sk=在第k階段可供分配的機(jī)器臺(tái)數(shù)(k=1,2,3)；或者說(shuō)，分配給第k個(gè)廠至第三個(gè)廠的設(shè)備臺(tái)數(shù)(k=1,2,3) 。 xk=分配給第k個(gè)工廠的設(shè)備臺(tái)數(shù)。已知 s1=5，并有s2=T1(s1,x1)=s1-x1，s3=T2(s2,x2)=s2-x2,從sk與xk的

12、定義，可知s3=x3. 采用逆序算法,第三階段,顯然將s3(s3=0,1,2,3,4,5)臺(tái)機(jī)器設(shè)備都分配給第3個(gè)工廠時(shí)，也就是s3=x3時(shí)，第三階段的指標(biāo)值（即第3廠的盈利）最大，即 max r3(s3,x3)=r3(s3,s3) 由于第3 階段是最后的階段，故有 f3(s3) =max r3(s3,x3)=r3(s3,s3) 其中x3可能取值為0，1，2，3，4，5.其數(shù)值計(jì)算見(jiàn)下表,其中x3*表示第3子過(guò)程上最優(yōu)指標(biāo)值f3(s3)時(shí)的x3的決策即為最優(yōu)決策。例如s3=4時(shí),有r3(4,4)=12,有f3(4)=12,此時(shí)x3*=4,即為最優(yōu)決策,第二階段,當(dāng)把s2(s2=0,1,2,3,

13、4,5)臺(tái)設(shè)備分配給第2 個(gè)工廠和第3個(gè)工廠時(shí)，則對(duì)每個(gè)s2值，有一種最優(yōu)分配方案，使最大盈利即最優(yōu)。2子過(guò)程最優(yōu)指標(biāo)函數(shù)值為： f2(s2)=max r2(s2,x2)+f3(s3) 因?yàn)閟3=s2-x2，上式也可以寫(xiě)成 f2(s2)=max r2(s2,x2)+f3(s2-x2) 其中，x2可取值0，1，2，3，4，5，其數(shù)值計(jì)算結(jié)果如下表,其中，在s2=4的這一行里，當(dāng)x2=1時(shí) r2(s2,x2)+f3(s2-x2)=r2(4,1)+f3(4-1) =r2(4,1)+f(3)=5+11=16同樣可知，當(dāng)x2=2時(shí)，f2(s2) 也等于16。故這一行的最優(yōu)決策有兩種,第一階段,把s1(s

14、1=5)臺(tái)設(shè)備分配給第1，第2，第3廠時(shí)，最大盈利為 f1(5)=max r1(5,x1)+f2(5-x1) 其中x1可取值0，1，2，3，4，5。數(shù)值計(jì)算結(jié)果見(jiàn)下表,最終的最優(yōu)分配結(jié)果有兩個(gè),甲廠0臺(tái)，乙廠2臺(tái)，丙廠3臺(tái)。 甲廠2臺(tái)，乙廠2臺(tái)，丙廠1臺(tái)。 這兩種分配方案都能得到最高的總盈利21萬(wàn)元,某咨詢公司有10 個(gè)工作日可以去處理四種類型的咨詢項(xiàng)目，每種類型的咨詢項(xiàng)目中待處理的客戶數(shù)量、處理每個(gè)客戶所需的工作日數(shù)以及所獲得的利潤(rùn)如下表所示。顯然該公司在10天內(nèi)不能處理完所有的客戶，它可以自己挑選一些客戶，其余的請(qǐng)其他咨詢公司去做，該咨詢公司應(yīng)如何選擇客戶使得在這10個(gè)工作日中獲利最大,背

15、包問(wèn)題,背包問(wèn)題是指在攜帶物品總重量一定的情況下，怎樣將N種不同重量和不同價(jià)值的物品裝入背包，使得背包所裝物品的總價(jià)值最大,按照咨詢類型將決策分為四個(gè)階段，第一階段處理第一種咨詢類型的客戶；第二、三、四階段處理第二、三、四種咨詢類型的客戶。設(shè)： sk=分配給第k種咨詢項(xiàng)目到第四種咨詢項(xiàng)目的所有客戶的總工作日（狀態(tài)變量）； xk=在第k種咨詢項(xiàng)目中處理客戶的數(shù)量（決策變量,顯然，s1=10, s2=T1(s1,x1)=s1-x1, s3=T2(s2,x2)=s2-3x2, s4=T3(s3,x3)=s3-4x3=7x4,第四階段： s4=0,1,.,10,x4=s4/7,中括號(hào) 為取整符號(hào)，因?yàn)?/p>

16、s410，所以x4可取0或1。f4(s4)=max r4(s4,x4)=r4(s4,s4/7).計(jì)算結(jié)果如下,第三階段：s310，x3只可能為0,1,2。f3(s3)=maxr3(s3,x3)+f4 (s3-4x3,第二階段：s210，x2只能取0，1，2，3。f2(s2)=maxr2(s2,x2)+f3(s2-3x2,第一階段：s1=10，x1可取0，1，2，.，10。f1(10)=maxr1(10,x1)+f2(10-x1,生產(chǎn)存貯問(wèn)題,某公司為主要電力公司生產(chǎn)大型變壓器，由于電力公司采取預(yù)定方式購(gòu)買，所以該公司可以預(yù)測(cè)未來(lái)幾個(gè)月的需求量。為確保需求，該公司為新的一年前四個(gè)月制定一項(xiàng)生產(chǎn)計(jì)

17、劃，這四個(gè)月的需求如表所示。 生產(chǎn)成本隨著生產(chǎn)數(shù)量而變化。調(diào)試費(fèi)為4，除了調(diào)試費(fèi)用外，每月生產(chǎn)的頭兩臺(tái)各花費(fèi)為2，后兩臺(tái)各花費(fèi)為1。最大生產(chǎn)能力為每月4臺(tái)，生產(chǎn)成本如表所示。 每臺(tái)變壓器在倉(cāng)庫(kù)中由這個(gè)月存到下個(gè)月的儲(chǔ)存費(fèi)用為1，倉(cāng)庫(kù)的最大儲(chǔ)存能力為3臺(tái)，另外，知道在1月1日時(shí)倉(cāng)庫(kù)里存有1臺(tái)變壓器，要求在4月30日倉(cāng)庫(kù)的庫(kù)存量為0。該如何制定生產(chǎn)計(jì)劃，使得四個(gè)月的生產(chǎn)成本和儲(chǔ)存總費(fèi)用最少,表1、需求表,表2、成本表,按月份劃分為四個(gè)階段，設(shè)： sk為第k階段期初庫(kù)存量；k=1,2,3,4 xk為第k階段的生產(chǎn)量；k=1,2,3,4 dk為第k階段需求量；k=1,2,3,4,各個(gè)階段的狀態(tài)轉(zhuǎn)移方程

18、： s1=1 s2=1+x1-d1, s3=s2+x2-d2, s4=s3+x3-d3, 邊界條件： 0=s4+x4-d4. 必須滿足需求和生產(chǎn)能力約束。 每一階段的效益函數(shù)由本階段生產(chǎn)成本、上階段生 產(chǎn)成本、存儲(chǔ)費(fèi)三部分構(gòu)成,第四階段： s4=0,1,2,3. x4=0,1,2,3. d4=3. x4=d4-s4=3-s4. f4(s4)=min r4(s4,x4)=c4(3-s4)+h4(s4,3-s4)=c4(3-s4,生產(chǎn)費(fèi)用,存儲(chǔ)費(fèi)用,第三階段： s3=0,1,2,3. x3=0,1,2,3,4. d3=1 s4=s3+x3-d3=s3+x3-1 f3(s3)=min c3(x3)+1*(s3+x3-1)+f4(s3+x3-1,生產(chǎn)成本,存儲(chǔ)費(fèi),第4階段最優(yōu)指標(biāo)函數(shù),第二階段： s2=0,1,2,3. x2=0,1,2,3,4. d2=4 s3=s2+x2-d2=s2+x2-4 f2(s2)=min c2(