動態(tài)規(guī)劃算法原理與的應用

1、動態(tài)規(guī)劃算法原理及其應用研究系 別： x x x姓 名： x x x指導教員： x x x2012年5月20日摘要：動態(tài)規(guī)劃是解決最優(yōu)化問題的基本方法，本文介紹了動態(tài)規(guī)劃的基本思想和基本步驟，并通過幾個實例的分析，研究了利用動態(tài)規(guī)劃設計算法的具體途徑。關鍵詞：動態(tài)規(guī)劃 多階段決策1.引言 規(guī)劃問題的最終目的就是確定各決策變量的取值，以使目標函數(shù)達到極大或極小。在線性規(guī)劃和非線性規(guī)劃中，決策變量都是以集合的形式被一次性處理的；然而，有時我們也會面對決策變量需分期、分批處理的多階段決策問題。所謂多階段決策問題是指這樣一類活動過程：它可以分解為若干個互相聯(lián)系的階段，在每一階段分別對應著一組可供選取的

2、決策集合；即構(gòu)成過程的每個階段都需要進行一次決策的決策問題。將各個階段的決策綜合起來構(gòu)成一個決策序列，稱為一個策略。顯然，由于各個階段選取的決策不同，對應整個過程可以有一系列不同的策略。當過程采取某個具體策略時，相應可以得到一個確定的效果，采取不同的策略，就會得到不同的效果。多階段的決策問題，就是要在所有可能采取的策略中選取一個最優(yōu)的策略，以便得到最佳的效果。動態(tài)規(guī)劃是一種求解多階段決策問題的系統(tǒng)技術，可以說它橫跨整個規(guī)劃領域（線性規(guī)劃和非線性規(guī)劃）。在多階段決策問題中，有些問題對階段的劃分具有明顯的時序性，動態(tài)規(guī)劃的“動態(tài)”二字也由此而得名。動態(tài)規(guī)劃的主要創(chuàng)始人是美國數(shù)學家貝爾曼（Bellm

3、an）。20世紀40年代末50年代初，當時在蘭德公司（Rand Corporation）從事研究工作的貝爾曼首先提出了動態(tài)規(guī)劃的概念。1957年貝爾曼發(fā)表了數(shù)篇研究論文，并出版了他的第一部著作動態(tài)規(guī)劃。該著作成為了當時唯一的進一步研究和應用動態(tài)規(guī)劃的理論源泉。在貝爾曼及其助手們致力于發(fā)展和推廣這一技術的同時，其他一些學者也對動態(tài)規(guī)劃的發(fā)展做出了重大的貢獻，其中最值得一提的是愛爾思（Aris）和梅特頓（Mitten）。愛爾思先后于1961年和1964年出版了兩部關于動態(tài)規(guī)劃的著作，并于1964年同尼母霍思爾（Nemhauser）、威爾德（Wild）一道創(chuàng)建了處理分枝、循環(huán)性多階段決策系統(tǒng)的一般性

4、理論。梅特頓提出了許多對動態(tài)規(guī)劃后來發(fā)展有著重要意義的基礎性觀點，并且對明晰動態(tài)規(guī)劃路徑的數(shù)學性質(zhì)做出了巨大的貢獻。動態(tài)規(guī)劃問世以來，在工程技術、經(jīng)濟管理等社會各個領域都有著廣泛的應用，并且獲得了顯著的效果。在經(jīng)濟管理方面，動態(tài)規(guī)劃可以用來解決最優(yōu)路徑問題、資源分配問題、生產(chǎn)調(diào)度問題、庫存管理問題、排序問題、設備更新問題以及生產(chǎn)過程最優(yōu)控制問題等，是經(jīng)濟管理中一種重要的決策技術。許多規(guī)劃問題用動態(tài)規(guī)劃的方法來處理，常比線性規(guī)劃或非線性規(guī)劃更有效。特別是對于離散的問題，由于解析數(shù)學無法發(fā)揮作用，動態(tài)規(guī)劃便成為了一種非常有用的工具。 動態(tài)規(guī)劃可以按照決策過程的演變是否確定分為確定性動態(tài)規(guī)劃和隨機性

5、動態(tài)規(guī)劃；也可以按照決策變量的取值是否連續(xù)分為連續(xù)性動態(tài)規(guī)劃和離散性動態(tài)規(guī)劃。雖然動態(tài)規(guī)劃主要用于求解以時間劃分階段的動態(tài)過程的優(yōu)化問題，但是一些與時間無關的靜態(tài)規(guī)劃(如線性規(guī)劃、非線性規(guī)劃)，只要人為地引進時間因素，把它視為多階段決策過程，也可以用動態(tài)規(guī)劃方法方便地求解。2.動態(tài)規(guī)劃的基本思想 一般來說，只要問題可以劃分成規(guī)模更小的子問題，并且原問題的最優(yōu)解中包含了子問題的最優(yōu)解，則可以考慮用動態(tài)規(guī)劃解決。動態(tài)規(guī)劃的實質(zhì)是分治思想和解決冗余，因此，動態(tài)規(guī)劃是一種將問題實例分解為更小的、相似的子問題，并存儲子問題的解而避免計算重復的子問題，以解決最優(yōu)化問題的算法策略。由此可知，動態(tài)規(guī)劃法與分治

6、法和貪心法類似，它們都是將問題實例歸納為更小的、相似的子問題，并通過求解子問題產(chǎn)生一個全局最優(yōu)解。其中貪心法的當前選擇可能要依賴已經(jīng)作出的所有選擇，但不依賴于有待于做出的選擇和子問題。因此貪心法自頂向下，一步一步地作出貪心選擇；而分治法中的各個子問題是獨立的 (即不包含公共的子子問題)，因此一旦遞歸地求出各子問題的解后，便可自下而上地將子問題的解合并成問題的解。但不足的是，如果當前選擇可能要依賴子問題的解時，則難以通過局部的貪心策略達到全局最優(yōu)解；如果各子問題是不獨立的，則分治法要做許多不必要的工作，重復地解公共的子問題。解決上述問題的辦法是利用動態(tài)規(guī)劃。該方法主要應用于最優(yōu)化問題，這類問題會

7、有多種可能的解，每個解都有一個值，而動態(tài)規(guī)劃找出其中最優(yōu)(最大或最小)值的解。若存在若干個取最優(yōu)值的解的話，它只取其中的一個。在求解過程中，該方法也是通過求解局部子問題的解達到全局最優(yōu)解，但與分治法和貪心法不同的是，動態(tài)規(guī)劃允許這些子問題不獨立，也允許其通過自身子問題的解作出選擇，該方法對每一個子問題只解一次，并將結(jié)果保存起來，避免每次碰到時都要重復計算。 因此，動態(tài)規(guī)劃法所針對的問題有一個顯著的特征，即它所對應的子問題樹中的子問題呈現(xiàn)大量的重復。動態(tài)規(guī)劃法的關鍵就在于，對于重復出現(xiàn)的子問題，只在第一次遇到時加以求解，并把答案保存起來，讓以后再遇到時直接引用，不必重新求解。3.動態(tài)規(guī)劃的基本概

8、念動態(tài)規(guī)劃的數(shù)學描述離不開它的一些基本概念與符號，因此有必要在介紹多階段決策過程的數(shù)學描述的基礎上，系統(tǒng)地介紹動態(tài)規(guī)劃的一些基本概念。3.1多階段決策問題如果一類活動過程可以分為若干個互相聯(lián)系的階段，在每一個階段都需作出決策，一個階段的決策確定以后，常常影響到下一個階段的決策，從而就完全確定了一個過程的活動路線，則稱它為多階段決策問題。各個階段的決策構(gòu)成一個決策序列，稱為一個策略。每一個階段都有若干個決策可供選擇，因而就有許多策略供我們選取，對應于一個策略可以確定活動的效果，這個效果可以用數(shù)量來確定。策略不同，效果也不同，多階段決策問題，就是要在可以選擇的那些策略中間，選取一個最優(yōu)策略，使在預

9、定的標準下達到最好的效果.3.2動態(tài)規(guī)劃問題中的術語階段：把所給求解問題的過程恰當?shù)胤殖扇舾蓚€相互聯(lián)系的階段，以便于求解，過程不同，階段數(shù)就可能不同描述階段的變量稱為階段變量。在多數(shù)情況下，階段變量是離散的，用k表示。此外，也有階段變量是連續(xù)的情形。如果過程可以在任何時刻作出決策，且在任意兩個不同的時刻之間允許有無窮多個決策時，階段變量就是連續(xù)的。狀態(tài)：狀態(tài)表示每個階段開始面臨的自然狀況或客觀條件，它不以人們的主觀意志為轉(zhuǎn)移，也稱為不可控因素。在上面的例子中狀態(tài)就是某階段的出發(fā)位置，它既是該階段某路的起點，同時又是前一階段某支路的終點。過程的狀態(tài)通?？梢杂靡粋€或一組數(shù)來描述，稱為狀態(tài)變量。一般

10、，狀態(tài)是離散的，但有時為了方便也將狀態(tài)取成連續(xù)的。當然，在現(xiàn)實生活中，由于變量形式的限制，所有的狀態(tài)都是離散的，但從分析的觀點，有時將狀態(tài)作為連續(xù)的處理將會有很大的好處。此外，狀態(tài)可以有多個分量(多維情形)，因而用向量來代表；而且在每個階段的狀態(tài)維數(shù)可以不同。無后效性：我們要求狀態(tài)具有下面的性質(zhì)：如果給定某一階段的狀態(tài)，則在這一階段以后過程的發(fā)展不受這階段以前各段狀態(tài)的影響，所有各階段都確定時，整個過程也就確定了。換句話說，過程的每一次實現(xiàn)可以用一個狀態(tài)序列表示，在前面的例子中每階段的狀態(tài)是該線路的始點，確定了這些點的序列，整個線路也就完全確定。從某一階段以后的線路開始，當這段的始點給定時，不

11、受以前線路（所通過的點）的影響。狀態(tài)的這個性質(zhì)意味著過程的歷史只能通過當前的狀態(tài)去影響它的未來的發(fā)展，這個性質(zhì)稱為無后效性。決策：一個階段的狀態(tài)給定以后，從該狀態(tài)演變到下一階段某個狀態(tài)的一種選擇（行動）稱為決策。在最優(yōu)控制中，也稱為控制。在許多間題中，決策可以自然而然地表示為一個數(shù)或一組數(shù)。不同的決策對應著不同的數(shù)值。描述決策的變量稱決策變量，因狀態(tài)滿足無后效性，故在每個階段選擇決策時只需考慮當前的狀態(tài)而無須考慮過程的歷史。決策變量的范圍稱為允許決策集合。策略：由每個階段的決策組成的序列稱為策略。對于每一個實際的多階段決策過程，可供選取的策略有一定的范圍限制，這個范圍稱為允許策略集合。允許策略

12、集合中達到最優(yōu)效果的策略稱為最優(yōu)策略。給定k階段狀態(tài)變量x(k)的值后，如果這一階段的決策變量一經(jīng)確定，第k+1階段的狀態(tài)變量x(k+1)也就完全確定，即x(k+1)的值隨x(k)和第k階段的決策u(k)的值變化而變化，那么可以把這一關系看成(x(k)，u(k)與x(k+1)確定的對應關系，用x(k+1)=Tk(x(k),u(k)表示。這是從k階段到k+1階段的狀態(tài)轉(zhuǎn)移規(guī)律，稱為狀態(tài)轉(zhuǎn)移方程。最優(yōu)性原理: 作為整個過程的最優(yōu)策略，它滿足：相對前面決策所形成的狀態(tài)而言，余下的子策略必然構(gòu)成“最優(yōu)子策略”。4.動態(tài)規(guī)劃求解的基本步驟動態(tài)規(guī)劃所處理的問題是一個多階段決策問題，一般由初始狀態(tài)開始，通過

13、對中間階段決策的選擇，達到結(jié)束狀態(tài)。這些決策形成了一個決策序列，同時確定了完成整個過程的一條活動路線(通常是求最優(yōu)的活動路線)。如圖所示。動態(tài)規(guī)劃的設計都有著一定的模式，一般要經(jīng)歷以下幾個步驟。初始狀態(tài)決策決策決策結(jié)束狀態(tài) 動態(tài)規(guī)劃決策過程示意圖(1)劃分階段：，按照問題的時間或空間特征，把問題分為若干個階段。在劃分階段時，注意劃分后的階段一定要是有序的或者是可排序的，否則問題就無法求解。 (2)確定狀態(tài)和狀態(tài)變量：將問題發(fā)展到各個階段時所處于的各種客觀情況用不同的狀態(tài)表示出來。當然，狀態(tài)的選擇要滿足無后效性。 (3)確定決策并寫出狀態(tài)轉(zhuǎn)移方程：因為決策和狀態(tài)轉(zhuǎn)移有著天然的聯(lián)系，狀態(tài)轉(zhuǎn)移就是根

14、據(jù)上一階段的狀態(tài)和決策來導出本階段的狀態(tài)。所以如果確定了決策，狀態(tài)轉(zhuǎn)移方程也就可寫出。但事實上常常是反過來做，根據(jù)相鄰兩段各狀態(tài)之間的關系來確定決策。 (4)尋找邊界條件：給出的狀態(tài)轉(zhuǎn)移方程是一個遞推式，需要一個遞推的終止條件或邊界條件。 (5)程序設計實現(xiàn)：動態(tài)規(guī)劃的主要難點在于理論上的設計，一旦設計完成，實現(xiàn)部分就會非常簡單。根據(jù)上述動態(tài)規(guī)劃設計的步驟，可得到大體解題框架如圖所示。 動態(tài)規(guī)劃設計的一般模式圖 上述提供了動態(tài)規(guī)劃方法的一般模式，對于簡單的動態(tài)規(guī)劃問題，可以按部就班地進行動態(tài)規(guī)劃的設計。下面，給出一個利用動態(tài)規(guī)劃方法求解的典型例子。 上圖示出了一個數(shù)字三角形寶塔。數(shù)字三角形中的

15、數(shù)字為不超過100的整數(shù)?，F(xiàn)規(guī)定從最頂層走到最底層，每一步可沿左斜線向下或右斜線向下走。 任務一：假設三角形行數(shù)10，鍵盤輸入一個確定的整數(shù)值M，編程確定是否存在一條路徑，使得沿著該路徑所經(jīng)過的數(shù)字的總和恰為M，若存在則給出所有路徑，若不存在，則輸出“NOAnswer!”字樣。 任務二：假設三角形行數(shù)100，編程求解從最頂層走到最底層的一條路徑，使得沿著該路徑所經(jīng)過的數(shù)字的總和最大，輸出最大值。輸人數(shù)據(jù)：由文件輸入數(shù)據(jù)，任務一中文件第一行是三角形的行數(shù)N和整數(shù)值M。以后的N行分別是從最頂層到最底層的每一層中的數(shù)字。任務二中文件數(shù)據(jù)格式同任務一，只是第一行中沒有整數(shù)值M。在例子中任務二的文件數(shù)據(jù)

16、表示如下： 輸入：5 7 輸出： 輸出路徑和最大值 3 8 7 或“No Answer!”字樣。 8 1 0 38 2 7 7 4 810 4 5 2 6 5 2744圖3 數(shù)字三角形 45265【分析】對于這一問題，很容易想到用枚舉的方法去解決，即列舉出所有路徑并記錄每一條路徑所經(jīng)過的數(shù)字總和。然后判斷數(shù)字總和是否等于給定的整數(shù)值M或?qū)ふ页鲎畲蟮臄?shù)字總和，這一想法很直觀，而且對于任務一，由于數(shù)字三角形的行數(shù)不大(10)，因此其枚舉量不是很大，應該能夠?qū)崿F(xiàn)。但對于任務二，如果用枚舉的方法，當三角形的行數(shù)等于100時，其枚舉量之大是可想而知的，顯然，枚舉法對于任務二的求解并不適用。其實，只要對對

17、任務二稍加分析，就可以得出一個結(jié)論： 如果得到一條由頂至底的某處的一條最佳路徑，那么對于該路徑上的每一個中間點來說，由頂至該中間點的路徑所經(jīng)過的數(shù)字和也為最大。因此該問題是一個典型的多階段決策最優(yōu)化的問題。算法設計與分析如下： 對于任務一，合理地確認枚舉的方法，可以優(yōu)化問題的解法。由于從塔頂?shù)降讓用看味贾挥袃煞N走法，即左或右。設“0”表示左，“1”表示右，對于層數(shù)為N的數(shù)字塔，從頂?shù)降椎囊环N走法可用一個N-1位的二進制數(shù)表示。如例中二進制數(shù)字串1011，其對應的路徑應該是：8146。這樣就可以用一個Nl位的二進制數(shù)來模擬走法和確定解的范圍。窮舉出從0到2n-1個十進制數(shù)所對應的N-1位二進制串

18、對應的路徑中的數(shù)字總和，判定其是否等于M而求得問題的解。 對于任務二，采用動態(tài)規(guī)劃中的順推解法。按三角形的行劃分階段，若行數(shù)為n，則可把問題看做一個n-1個階段的決策問題。從始點出發(fā)，依順向求出第一階段、第二階段第n1階段中各決策點至始點的最佳路徑，最終求出始點到終點的最佳路徑。 設：fk(Uk)為從第k階段中的點Uk至三角形頂點有一條最佳路徑，該路徑所經(jīng)過的數(shù)字的總和最大，fk(Uk)表示為這個數(shù)字和；由于每一次決策有兩個選擇，或沿左斜線向下，或沿右斜線向下，因此設： Uk1為k-1階段中某點Uk沿左斜線向下的點； Uk2為k-1階段中某點Uk沿右斜線向下的點； dk(Uk1)為k階段中Uk

19、1的數(shù)字；dk(Uk2)為k階段中Uk2的數(shù)字。因而可寫出順推關系式(狀態(tài)轉(zhuǎn)移方程)為： fk(Uk)=maxfk-1(Uk)+dk(Uk1)，fk-1(Uk)+dk(Uk2)(k=1，2，3，n) f0(U0)0經(jīng)過一次順推，便可分別求出由頂至底N個數(shù)的N條路徑，在這N條路徑所經(jīng)過的N個數(shù)字和中，最大值即為正確答案。5.動態(tài)規(guī)劃的應用實例5.1最短路線問題例1 美國黑金石油公司（The Black Gold Petroleum Company）最近在阿拉斯加（Alaska）的北斯洛波（North Slope）發(fā)現(xiàn)了大的石油儲量。為了大規(guī)模開發(fā)這一油田，首先必須建立相應的輸運網(wǎng)絡，使北斯洛波生

20、產(chǎn)的原油能運至美國的3個裝運港之一。在油田的集輸站（結(jié)點C）與裝運港（結(jié)點P1、P2、P3）之間需要若干個中間站，中間站之間的聯(lián)通情況如圖7-2所示，圖中線段上的數(shù)字代表兩站之間的距離（單位：10千米）。試確定一最佳的輸運線路，使原油的輸送距離最短。解：最短路線有一個重要性質(zhì)，即如果由起點A經(jīng)過B點和C點到達終點D是一條最短路線，則由B點經(jīng)C點到達終點D一定是B到D的最短路（貝爾曼最優(yōu)化原理）。此性質(zhì)用反證法很容易證明，因為如果不是這樣，則從B點到D點有另一條距離更短的路線存在，不妨假設為BPD；從而可知路線ABPD比原路線ABCD距離短，這與原路線ABCD是最短路線相矛盾，性質(zhì)得證。根據(jù)最短

21、路線的這一性質(zhì)，尋找最短路線的方法就是從最后階段開始，由后向前逐步遞推求出各點到終點的最短路線，最后求得由始點到終點的最短路；即動態(tài)規(guī)劃的方法是從終點逐段向始點方向?qū)ふ易疃搪肪€的一種方法。按照動態(tài)規(guī)劃的方法，將此過程劃分為4個階段，即階段變量；取過程在各階段所處的位置為狀態(tài)變量，按逆序算法求解。CP3P2P1M11M12M21M22M23M31M32M33M34101286911107697511468643776534k=1k=2k=3k=4圖7-2當時：由結(jié)點M31到達目的地有兩條路線可以選擇，即選擇P1或P2；故：選擇P2,由結(jié)點M32到達目的地有三條路線可以選擇，即選擇P1、P2或P3

22、；故： 選擇P2,由結(jié)點M33到達目的地也有三條路線可以選擇，即選擇P1、P2或P3；故： 選擇P3,由結(jié)點M34到達目的地有兩條路線可以選擇，即選擇P2或P3；故： 選擇P2當時：由結(jié)點M21到達下一階段有三條路線可以選擇，即選擇M31、M32或M33；故： 選擇M32由結(jié)點M22到達下一階段也有三條路線可以選擇，即選擇M31、M32或M33；故： 選擇M32或M33，由結(jié)點M23到達下一階段也有三條路線可以選擇，即選擇M32、M33或M34；故： 選擇M33或M34當時：由結(jié)點M11到達下一階段有兩條路線可以選擇，即選擇M21或M22；故： 選擇M22,由結(jié)點M12，到達下一階段也有兩條路

23、線可以選擇，即選擇M22或M23；故： 選擇M22，當時：由結(jié)點C到達下一階段有兩條路線可以選擇，即選擇M11或M12；故： 選擇M11,，而通過順序（計算的反順序）追蹤（黑體標示）可以得到兩條最佳的輸運線路：CM11M22M32P2；CM11M22M33P3。最短的輸送距離是280千米。5.2資源分配問題所謂資源分配問題，就是將一定數(shù)量的一種或若干種資源（如原材料、機器設備、資金、勞動力等）恰當?shù)胤峙浣o若干個使用者，以使資源得到最有效地利用。設有m種資源，總量分別為bi（i = 1,2,m），用于生產(chǎn)n種產(chǎn)品，若用xij代表用于生產(chǎn)第j種產(chǎn)品的第i種資源的數(shù)量（j = 1,2,n），則生產(chǎn)第

24、j種產(chǎn)品的收益是其所獲得的各種資源數(shù)量的函數(shù)，即gj = f（x1j,x2j, xmj）。由于總收益是n種產(chǎn)品收益的和，此問題可用如下靜態(tài)模型加以描述： 若是連續(xù)變量，當 = f（, ）是線性函數(shù)時，該模型是線性規(guī)劃模型；當 = f（, ）是非線性函數(shù)時，該模型是非線性規(guī)劃模型。若是離散變量或（和） = f（, ）是離散函數(shù)時，此模型用線性規(guī)劃或非線性規(guī)劃來求解都將是非常麻煩的。然而在此情況下，由于這類問題的特殊結(jié)構(gòu)，可以將它看成為一個多階段決策問題，并利用動態(tài)規(guī)劃的遞推關系來求解。本例只考慮一維資源的分配問題，設狀態(tài)變量表示分配于從第k個階段至過程最終（第N個階段）的資源數(shù)量，即第k個階段初

25、資源的擁有量；決策變量xk表示第k個階段資源的分配量。于是有狀態(tài)轉(zhuǎn)移律：允許決策集合：最優(yōu)指標函數(shù)（動態(tài)規(guī)劃的逆序遞推關系式）： 利用這一遞推關系式，最后求得的即為所求問題的最大總收益，下面來看一個具體的例子。例2 某公司擬將500萬元的資本投入所屬的甲、乙、丙三個工廠進行技術改造，各工廠獲得投資后年利潤將有相應的增長，增長額如表7-1所示。試確定500萬元資本的分配方案，以使公司總的年利潤增長額最大。表7-1投資額100萬元200萬元300萬元400萬元500萬元甲307090120130乙50100110110110丙4060110120120解：將問題按工廠分為三個階段k=1，2，3，設狀態(tài)變量（）代表從第個工廠到第3個工廠的投資額，決策變量代表第k個工廠的投資額。于是有狀態(tài)轉(zhuǎn)移率、允許決策集合和遞推關系式： 當時：于是有表7-2，表中表示第三個階段的最優(yōu)決策。表7-2 （單位：百萬元）0 1234501234500.40.61.11.21.2當時：。于是有表7-3。表7-3 （單位：百萬元）x2S2g2（x2）+f3（s2 - x2）01234500+00010+0.40.5+00.5120+0.60.5+0.41.0+01.0230+1.10.5+0