運籌學(xué)-動態(tài)規(guī)劃ppt課件

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

2、就是要在所有可能采取的策略中間選取一個最優(yōu)的策略，是在預(yù)定的標準下得到最好的效果,例1 最短路線問題。設(shè)有一旅行者從下圖中的A點出發(fā)，途中要經(jīng)過B、C、D等處，最后到達終點E。從A到E有很多條路可以選擇，各點之間的距離如圖所示，問該旅行者應(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,用窮舉法的計算量: 如果從A到E的站點有k個，除A、E之外每站有3個位置則 總共有3k-12條路徑； 計算各路徑長度總共要進行 (k+1) 3k-12次加法以及3k- 12-1次比較。

3、隨著 k 的值增加時，需要進行的加法和比較的 次數(shù)將迅速增加； 例如當 k=20時，加法次數(shù)為 4.25508339662271015 次， 比較 1.37260754729771014 次。若用1億次/秒的計算機計算 需要約508天,例2 設(shè)有某種機器設(shè)備，用于完成兩類工作A和B.若k年初完好機器的數(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.又機器設(shè)備在使用中會有損壞，設(shè)機器用于工作A時，一年后能繼續(xù)使用的完好機器數(shù)占年初投入量的a%；若用于B項工作時，一

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

5、系的單階段的決策問題，從而簡化計算過程。 在例1中，這種轉(zhuǎn)化的實現(xiàn)是從終點E出發(fā)一步步進行反推，這種算法稱為逆序算法,例1 最短路線問題。設(shè)有一旅行者從下圖中的A點出發(fā)，途中要經(jīng)過B、C、D等處，最后到達終點E。從A到E有很多條路可以選擇，各點之間的距離如圖所示，問該旅行者應(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的計算步驟為,從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 動態(tài)規(guī)劃的基本概念,1、階段(stage).是指一個問題需要做出決策的步數(shù)。如例1中旅行者需要在A、B、C、D四個階段做出下一步的決策。通常用k來表示問題包含的階段數(shù)，稱為階段變量。 2、狀態(tài)(state).這是動態(tài)規(guī)劃中最關(guān)鍵的參數(shù)，它既反映前面各階段決策的結(jié)局，又是本階段做出決策的出發(fā)點和依據(jù)。狀態(tài)是動態(tài)規(guī)劃問題各階段信息的傳遞點和結(jié)合點，第k階段的狀態(tài)通常用狀態(tài)變量sk來描述。在例1中第2階段的狀態(tài)s2=(B1,B2,B3,3、決策(decision).是指某階段初從給定的狀態(tài)出發(fā)，決策者在面臨的若干種不同

7、方案中做出的選擇。用Dk(sk)表示k階段狀態(tài)為sk時決策允許的取值范圍，xk(sk)表示第k階段狀態(tài)為sk時對方案的選擇。如例1中D2(B1)=C1,C2,C3。 4、策略(policy)和子策略(sub policy).動態(tài)規(guī)劃問題各階段決策組成的序列總體稱作一個策略。如：x1(s1),x2(s2),.,xn(sn)。 把從某一階段開始到過程最終的決策序列稱為問題的子過程策略或子策略。如：xk(sk),xk+1(sk+1),.,xn(sn,5、狀態(tài)轉(zhuǎn)移律，也稱狀態(tài)轉(zhuǎn)移方程.從sk的某一狀態(tài)值出發(fā)，當決策變量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、指標函數(shù).階段的指標函數(shù)是對應(yīng)某一階段狀態(tài)和從該狀態(tài)出發(fā)的一個階段的決策的某種效益度量，用rk(sk,xk)表示。過程的指標函數(shù)是指從狀態(tài)sk(k=1,2,.,n)出發(fā)至過程最終，當采取某種子策略時，按預(yù)定標準得到的效益值。所謂最優(yōu)指標函數(shù)，是指對某一確定狀態(tài)選取最優(yōu)策略后得到的指標函數(shù)值。記作fk(sk,2.3 最優(yōu)化原理與動態(tài)規(guī)劃的數(shù)學(xué)模型,求解動態(tài)規(guī)劃的最優(yōu)化原理(R.Bellman)：作為整個過程的最優(yōu)策略具有這樣的性質(zhì)，無論過去的狀態(tài)和決策如何，對先前決策所形成的狀態(tài)而言，余下的諸決

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

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

11、 動態(tài)規(guī)劃模型的分類,3 動態(tài)規(guī)劃應(yīng)用舉例,資源分配問題 背包問題 生產(chǎn)與存貯問題 其它,某公司擬將某種設(shè)備5臺，分配給所屬的甲、乙、丙三個工廠，各工廠獲得此設(shè)備后，預(yù)測可創(chuàng)造的利潤如下表所示，問應(yīng)如何分配這5臺設(shè)備給3個工廠，可使所創(chuàng)造利潤最大,資源分配問題,解：將問題按工廠分為三個階段，甲、乙、丙三廠分別編號為1、2、3廠。設(shè)： sk=在第k階段可供分配的機器臺數(shù)(k=1,2,3)；或者說，分配給第k個廠至第三個廠的設(shè)備臺數(shù)(k=1,2,3) 。 xk=分配給第k個工廠的設(shè)備臺數(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)臺機器設(shè)備都分配給第3個工廠時，也就是s3=x3時，第三階段的指標值（即第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ù)值計算見下表,其中x3*表示第3子過程上最優(yōu)指標值f3(s3)時的x3的決策即為最優(yōu)決策。例如s3=4時,有r3(4,4)=12,有f3(4)=12,此時x3*=4,即為最優(yōu)決策,第二階段,當把s2(s2=0,1,2,3,

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

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

15、包問題,背包問題是指在攜帶物品總重量一定的情況下，怎樣將N種不同重量和不同價值的物品裝入背包，使得背包所裝物品的總價值最大,按照咨詢類型將決策分為四個階段，第一階段處理第一種咨詢類型的客戶；第二、三、四階段處理第二、三、四種咨詢類型的客戶。設(shè)： sk=分配給第k種咨詢項目到第四種咨詢項目的所有客戶的總工作日（狀態(tài)變量）； xk=在第k種咨詢項目中處理客戶的數(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,中括號 為取整符號，因為

16、s410，所以x4可取0或1。f4(s4)=max r4(s4,x4)=r4(s4,s4/7).計算結(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)存貯問題,某公司為主要電力公司生產(chǎn)大型變壓器，由于電力公司采取預(yù)定方式購買，所以該公司可以預(yù)測未來幾個月的需求量。為確保需求，該公司為新的一年前四個月制定一項生產(chǎn)計

17、劃，這四個月的需求如表所示。 生產(chǎn)成本隨著生產(chǎn)數(shù)量而變化。調(diào)試費為4，除了調(diào)試費用外，每月生產(chǎn)的頭兩臺各花費為2，后兩臺各花費為1。最大生產(chǎn)能力為每月4臺，生產(chǎn)成本如表所示。 每臺變壓器在倉庫中由這個月存到下個月的儲存費用為1，倉庫的最大儲存能力為3臺，另外，知道在1月1日時倉庫里存有1臺變壓器，要求在4月30日倉庫的庫存量為0。該如何制定生產(chǎn)計劃，使得四個月的生產(chǎn)成本和儲存總費用最少,表1、需求表,表2、成本表,按月份劃分為四個階段，設(shè)： sk為第k階段期初庫存量；k=1,2,3,4 xk為第k階段的生產(chǎn)量；k=1,2,3,4 dk為第k階段需求量；k=1,2,3,4,各個階段的狀態(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)成本、存儲費三部分構(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)費用,存儲費用,第三階段： 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)成本,存儲費,第4階段最優(yōu)指標函數(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(