動態(tài)規(guī)劃算法原理及應(yīng)用

1、動態(tài)規(guī)劃算法 劉興田（浙江工業(yè)大學(xué) 計(jì)算機(jī)學(xué)院 軟件工程1205班 201226630512）摘要：動態(tài)規(guī)劃是解決最優(yōu)化問題的基本方法，本文介紹了動態(tài)規(guī)劃的基本思想和基本步驟，并通過幾個(gè)實(shí)例的分析，研究了利用動態(tài)規(guī)劃設(shè)計(jì)算法的具體途徑。關(guān)鍵詞：動態(tài)規(guī)劃 算法Dynamic Programming Liu xingtian(Zhe Jiang University Of Technology, Computer Science and Technology Campus, Software Engineering 1205 26630512)Abstract: Dynamic Programmi

2、ng is the most effective way to solve the problem of optimization .This dissertation introduce the thinking of Dynamic Programming and the step to using Dynamic Programming ,it also gives some examples to help analysis Dynamic Programming and the specific method to use Dynamic Programming .Key words

3、 : Dynamic Programming , Alsgorithm1.引言 規(guī)劃問題的最終目的就是確定各決策變量的取值，以使目標(biāo)函數(shù)達(dá)到極大或極小。在線性規(guī)劃和非線性規(guī)劃中，決策變量都是以集合的形式被一次性處理的；然而，有時(shí)我們也會面對決策變量需分期、分批處理的多階段決策問題。所謂多階段決策問題是指這樣一類活動過程：它可以分解為若干個(gè)互相聯(lián)系的階段，在每一階段分別對應(yīng)著一組可供選取的決策集合；即構(gòu)成過程的每個(gè)階段都需要進(jìn)行一次決策的決策問題。將各個(gè)階段的決策綜合起來構(gòu)成一個(gè)決策序列，稱為一個(gè)策略。顯然，由于各個(gè)階段選取的決策不同，對應(yīng)整個(gè)過程可以有一系列不同的策略。當(dāng)過程采取某個(gè)具體策略時(shí)

4、，相應(yīng)可以得到一個(gè)確定的效果，采取不同的策略，就會得到不同的效果。多階段的決策問題，就是要在所有可能采取的策略中選取一個(gè)最優(yōu)的策略，以便得到最佳的效果。動態(tài)規(guī)劃是一種求解多階段決策問題的系統(tǒng)技術(shù)，可以說它橫跨整個(gè)規(guī)劃領(lǐng)域（線性規(guī)劃和非線性規(guī)劃）。在多階段決策問題中，有些問題對階段的劃分具有明顯的時(shí)序性，動態(tài)規(guī)劃的“動態(tài)”二字也由此而得名。動態(tài)規(guī)劃的主要創(chuàng)始人是美國數(shù)學(xué)家貝爾曼（Bellman）。20世紀(jì)40年代末50年代初，當(dāng)時(shí)在蘭德公司（Rand Corporation）從事研究工作的貝爾曼首先提出了動態(tài)規(guī)劃的概念。1957年貝爾曼發(fā)表了數(shù)篇研究論文，并出版了他的第一部著作動態(tài)規(guī)劃。該著作成

5、為了當(dāng)時(shí)唯一的進(jìn)一步研究和應(yīng)用動態(tài)規(guī)劃的理論源泉。在貝爾曼及其助手們致力于發(fā)展和推廣這一技術(shù)的同時(shí)，其他一些學(xué)者也對動態(tài)規(guī)劃的發(fā)展做出了重大的貢獻(xiàn)，其中最值得一提的是愛爾思（Aris）和梅特頓（Mitten）。愛爾思先后于1961年和1964年出版了兩部關(guān)于動態(tài)規(guī)劃的著作，并于1964年同尼母霍思爾（Nemhauser）、威爾德（Wild）一道創(chuàng)建了處理分枝、循環(huán)性多階段決策系統(tǒng)的一般性理論。梅特頓提出了許多對動態(tài)規(guī)劃后來發(fā)展有著重要意義的基礎(chǔ)性觀點(diǎn)，并且對明晰動態(tài)規(guī)劃路徑的數(shù)學(xué)性質(zhì)做出了巨大的貢獻(xiàn)。動態(tài)規(guī)劃問世以來，在工程技術(shù)、經(jīng)濟(jì)管理等社會各個(gè)領(lǐng)域都有著廣泛的應(yīng)用，并且獲得了顯著的效果。在

6、經(jīng)濟(jì)管理方面，動態(tài)規(guī)劃可以用來解決最優(yōu)路徑問題、資源分配問題、生產(chǎn)調(diào)度問題、庫存管理問題、排序問題、設(shè)備更新問題以及生產(chǎn)過程最優(yōu)控制問題等，是經(jīng)濟(jì)管理中一種重要的決策技術(shù)。許多規(guī)劃問題用動態(tài)規(guī)劃的方法來處理，常比線性規(guī)劃或非線性規(guī)劃更有效。特別是對于離散的問題，由于解析數(shù)學(xué)無法發(fā)揮作用，動態(tài)規(guī)劃便成為了一種非常有用的工具。 動態(tài)規(guī)劃可以按照決策過程的演變是否確定分為確定性動態(tài)規(guī)劃和隨機(jī)性動態(tài)規(guī)劃；也可以按照決策變量的取值是否連續(xù)分為連續(xù)性動態(tài)規(guī)劃和離散性動態(tài)規(guī)劃。雖然動態(tài)規(guī)劃主要用于求解以時(shí)間劃分階段的動態(tài)過程的優(yōu)化問題，但是一些與時(shí)間無關(guān)的靜態(tài)規(guī)劃(如線性規(guī)劃、非線性規(guī)劃)，只要人為地引進(jìn)時(shí)

7、間因素，把它視為多階段決策過程，也可以用動態(tài)規(guī)劃方法方便地求解。2.動態(tài)規(guī)劃的基本思想 一般來說，只要問題可以劃分成規(guī)模更小的子問題，并且原問題的最優(yōu)解中包含了子問題的最優(yōu)解，則可以考慮用動態(tài)規(guī)劃解決。動態(tài)規(guī)劃的實(shí)質(zhì)是分治思想和解決冗余，因此，動態(tài)規(guī)劃是一種將問題實(shí)例分解為更小的、相似的子問題，并存儲子問題的解而避免計(jì)算重復(fù)的子問題，以解決最優(yōu)化問題的算法策略。由此可知，動態(tài)規(guī)劃法與分治法和貪心法類似，它們都是將問題實(shí)例歸納為更小的、相似的子問題，并通過求解子問題產(chǎn)生一個(gè)全局最優(yōu)解。其中貪心法的當(dāng)前選擇可能要依賴已經(jīng)作出的所有選擇，但不依賴于有待于做出的選擇和子問題。因此貪心法自頂向下，一步一

8、步地作出貪心選擇；而分治法中的各個(gè)子問題是獨(dú)立的 (即不包含公共的子子問題)，因此一旦遞歸地求出各子問題的解后，便可自下而上地將子問題的解合并成問題的解。但不足的是，如果當(dāng)前選擇可能要依賴子問題的解時(shí)，則難以通過局部的貪心策略達(dá)到全局最優(yōu)解；如果各子問題是不獨(dú)立的，則分治法要做許多不必要的工作，重復(fù)地解公共的子問題。解決上述問題的辦法是利用動態(tài)規(guī)劃。該方法主要應(yīng)用于最優(yōu)化問題，這類問題會有多種可能的解，每個(gè)解都有一個(gè)值，而動態(tài)規(guī)劃找出其中最優(yōu)(最大或最小)值的解。若存在若干個(gè)取最優(yōu)值的解的話，它只取其中的一個(gè)。在求解過程中，該方法也是通過求解局部子問題的解達(dá)到全局最優(yōu)解，但與分治法和貪心法不同

9、的是，動態(tài)規(guī)劃允許這些子問題不獨(dú)立，也允許其通過自身子問題的解作出選擇，該方法對每一個(gè)子問題只解一次，并將結(jié)果保存起來，避免每次碰到時(shí)都要重復(fù)計(jì)算。 因此，動態(tài)規(guī)劃法所針對的問題有一個(gè)顯著的特征，即它所對應(yīng)的子問題樹中的子問題呈現(xiàn)大量的重復(fù)。動態(tài)規(guī)劃法的關(guān)鍵就在于，對于重復(fù)出現(xiàn)的子問題，只在第一次遇到時(shí)加以求解，并把答案保存起來，讓以后再遇到時(shí)直接引用，不必重新求解。3.動態(tài)規(guī)劃的基本概念動態(tài)規(guī)劃的數(shù)學(xué)描述離不開它的一些基本概念與符號，因此有必要在介紹多階段決策過程的數(shù)學(xué)描述的基礎(chǔ)上，系統(tǒng)地介紹動態(tài)規(guī)劃的一些基本概念。3.1多階段決策問題如果一類活動過程可以分為若干個(gè)互相聯(lián)系的階段，在每一個(gè)階

10、段都需作出決策，一個(gè)階段的決策確定以后，常常影響到下一個(gè)階段的決策，從而就完全確定了一個(gè)過程的活動路線，則稱它為多階段決策問題。各個(gè)階段的決策構(gòu)成一個(gè)決策序列，稱為一個(gè)策略。每一個(gè)階段都有若干個(gè)決策可供選擇，因而就有許多策略供我們選取，對應(yīng)于一個(gè)策略可以確定活動的效果，這個(gè)效果可以用數(shù)量來確定。策略不同，效果也不同，多階段決策問題，就是要在可以選擇的那些策略中間，選取一個(gè)最優(yōu)策略，使在預(yù)定的標(biāo)準(zhǔn)下達(dá)到最好的效果.3.2動態(tài)規(guī)劃問題中的術(shù)語階段：把所給求解問題的過程恰當(dāng)?shù)胤殖扇舾蓚€(gè)相互聯(lián)系的階段，以便于求解，過程不同，階段數(shù)就可能不同描述階段的變量稱為階段變量。在多數(shù)情況下，階段變量是離散的，用

11、k表示。此外，也有階段變量是連續(xù)的情形。如果過程可以在任何時(shí)刻作出決策，且在任意兩個(gè)不同的時(shí)刻之間允許有無窮多個(gè)決策時(shí)，階段變量就是連續(xù)的。狀態(tài)：狀態(tài)表示每個(gè)階段開始面臨的自然狀況或客觀條件，它不以人們的主觀意志為轉(zhuǎn)移，也稱為不可控因素。在上面的例子中狀態(tài)就是某階段的出發(fā)位置，它既是該階段某路的起點(diǎn)，同時(shí)又是前一階段某支路的終點(diǎn)。過程的狀態(tài)通?？梢杂靡粋€(gè)或一組數(shù)來描述，稱為狀態(tài)變量。一般，狀態(tài)是離散的，但有時(shí)為了方便也將狀態(tài)取成連續(xù)的。當(dāng)然，在現(xiàn)實(shí)生活中，由于變量形式的限制，所有的狀態(tài)都是離散的，但從分析的觀點(diǎn)，有時(shí)將狀態(tài)作為連續(xù)的處理將會有很大的好處。此外，狀態(tài)可以有多個(gè)分量(多維情形)，因

12、而用向量來代表；而且在每個(gè)階段的狀態(tài)維數(shù)可以不同。無后效性：我們要求狀態(tài)具有下面的性質(zhì)：如果給定某一階段的狀態(tài)，則在這一階段以后過程的發(fā)展不受這階段以前各段狀態(tài)的影響，所有各階段都確定時(shí)，整個(gè)過程也就確定了。換句話說，過程的每一次實(shí)現(xiàn)可以用一個(gè)狀態(tài)序列表示，在前面的例子中每階段的狀態(tài)是該線路的始點(diǎn)，確定了這些點(diǎn)的序列，整個(gè)線路也就完全確定。從某一階段以后的線路開始，當(dāng)這段的始點(diǎn)給定時(shí)，不受以前線路（所通過的點(diǎn)）的影響。狀態(tài)的這個(gè)性質(zhì)意味著過程的歷史只能通過當(dāng)前的狀態(tài)去影響它的未來的發(fā)展，這個(gè)性質(zhì)稱為無后效性。決策：一個(gè)階段的狀態(tài)給定以后，從該狀態(tài)演變到下一階段某個(gè)狀態(tài)的一種選擇（行動）稱為決策

13、。在最優(yōu)控制中，也稱為控制。在許多間題中，決策可以自然而然地表示為一個(gè)數(shù)或一組數(shù)。不同的決策對應(yīng)著不同的數(shù)值。描述決策的變量稱決策變量，因狀態(tài)滿足無后效性，故在每個(gè)階段選擇決策時(shí)只需考慮當(dāng)前的狀態(tài)而無須考慮過程的歷史。決策變量的范圍稱為允許決策集合。策略：由每個(gè)階段的決策組成的序列稱為策略。對于每一個(gè)實(shí)際的多階段決策過程，可供選取的策略有一定的范圍限制，這個(gè)范圍稱為允許策略集合。允許策略集合中達(dá)到最優(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)的值變

14、化而變化，那么可以把這一關(guān)系看成(x(k)，u(k)與x(k+1)確定的對應(yīng)關(guān)系，用x(k+1)=Tk(x(k),u(k)表示。這是從k階段到k+1階段的狀態(tài)轉(zhuǎn)移規(guī)律，稱為狀態(tài)轉(zhuǎn)移方程。最優(yōu)性原理: 作為整個(gè)過程的最優(yōu)策略，它滿足：相對前面決策所形成的狀態(tài)而言，余下的子策略必然構(gòu)成“最優(yōu)子策略”。4.動態(tài)規(guī)劃求解的基本步驟動態(tài)規(guī)劃所處理的問題是一個(gè)多階段決策問題，一般由初始狀態(tài)開始，通過對中間階段決策的選擇，達(dá)到結(jié)束狀態(tài)。這些決策形成了一個(gè)決策序列，同時(shí)確定了完成整個(gè)過程的一條活動路線(通常是求最優(yōu)的活動路線)。如圖所示。動態(tài)規(guī)劃的設(shè)計(jì)都有著一定的模式，一般要經(jīng)歷以下幾個(gè)步驟。初始狀態(tài)決策決策

15、決策結(jié)束狀態(tài) 動態(tài)規(guī)劃決策過程示意圖(1)劃分階段：，按照問題的時(shí)間或空間特征，把問題分為若干個(gè)階段。在劃分階段時(shí)，注意劃分后的階段一定要是有序的或者是可排序的，否則問題就無法求解。 (2)確定狀態(tài)和狀態(tài)變量：將問題發(fā)展到各個(gè)階段時(shí)所處于的各種客觀情況用不同的狀態(tài)表示出來。當(dāng)然，狀態(tài)的選擇要滿足無后效性。 (3)確定決策并寫出狀態(tài)轉(zhuǎn)移方程：因?yàn)闆Q策和狀態(tài)轉(zhuǎn)移有著天然的聯(lián)系，狀態(tài)轉(zhuǎn)移就是根據(jù)上一階段的狀態(tài)和決策來導(dǎo)出本階段的狀態(tài)。所以如果確定了決策，狀態(tài)轉(zhuǎn)移方程也就可寫出。但事實(shí)上常常是反過來做，根據(jù)相鄰兩段各狀態(tài)之間的關(guān)系來確定決策。 (4)尋找邊界條件：給出的狀態(tài)轉(zhuǎn)移方程是一個(gè)遞推式，需要一

16、個(gè)遞推的終止條件或邊界條件。 (5)程序設(shè)計(jì)實(shí)現(xiàn)：動態(tài)規(guī)劃的主要難點(diǎn)在于理論上的設(shè)計(jì)，一旦設(shè)計(jì)完成，實(shí)現(xiàn)部分就會非常簡單。根據(jù)上述動態(tài)規(guī)劃設(shè)計(jì)的步驟，可得到大體解題框架如圖所示。 動態(tài)規(guī)劃設(shè)計(jì)的一般模式圖 上述提供了動態(tài)規(guī)劃方法的一般模式，對于簡單的動態(tài)規(guī)劃問題，可以按部就班地進(jìn)行動態(tài)規(guī)劃的設(shè)計(jì)。下面，給出一個(gè)利用動態(tài)規(guī)劃方法求解的典型例子。 上圖示出了一個(gè)數(shù)字三角形寶塔。數(shù)字三角形中的數(shù)字為不超過100的整數(shù)。現(xiàn)規(guī)定從最頂層走到最底層，每一步可沿左斜線向下或右斜線向下走。 任務(wù)一：假設(shè)三角形行數(shù)10，鍵盤輸入一個(gè)確定的整數(shù)值M，編程確定是否存在一條路徑，使得沿著該路徑所經(jīng)過的數(shù)字的總和恰為M

17、，若存在則給出所有路徑，若不存在，則輸出“NOAnswer!”字樣。 任務(wù)二：假設(shè)三角形行數(shù)100，編程求解從最頂層走到最底層的一條路徑，使得沿著該路徑所經(jīng)過的數(shù)字的總和最大，輸出最大值。輸人數(shù)據(jù)：由文件輸入數(shù)據(jù)，任務(wù)一中文件第一行是三角形的行數(shù)N和整數(shù)值M。以后的N行分別是從最頂層到最底層的每一層中的數(shù)字。任務(wù)二中文件數(shù)據(jù)格式同任務(wù)一，只是第一行中沒有整數(shù)值M。在例子中任務(wù)二的文件數(shù)據(jù)表示如下： 輸入：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【分析】對于這

18、一問題，很容易想到用枚舉的方法去解決，即列舉出所有路徑并記錄每一條路徑所經(jīng)過的數(shù)字總和。然后判斷數(shù)字總和是否等于給定的整數(shù)值M或?qū)ふ页鲎畲蟮臄?shù)字總和，這一想法很直觀，而且對于任務(wù)一，由于數(shù)字三角形的行數(shù)不大(10)，因此其枚舉量不是很大，應(yīng)該能夠?qū)崿F(xiàn)。但對于任務(wù)二，如果用枚舉的方法，當(dāng)三角形的行數(shù)等于100時(shí)，其枚舉量之大是可想而知的，顯然，枚舉法對于任務(wù)二的求解并不適用。其實(shí)，只要對對任務(wù)二稍加分析，就可以得出一個(gè)結(jié)論： 如果得到一條由頂至底的某處的一條最佳路徑，那么對于該路徑上的每一個(gè)中間點(diǎn)來說，由頂至該中間點(diǎn)的路徑所經(jīng)過的數(shù)字和也為最大。因此該問題是一個(gè)典型的多階段決策最優(yōu)化的問題。算法

19、設(shè)計(jì)與分析如下： 對于任務(wù)一，合理地確認(rèn)枚舉的方法，可以優(yōu)化問題的解法。由于從塔頂?shù)降讓用看味贾挥袃煞N走法，即左或右。設(shè)“0”表示左，“1”表示右，對于層數(shù)為N的數(shù)字塔，從頂?shù)降椎囊环N走法可用一個(gè)N-1位的二進(jìn)制數(shù)表示。如例中二進(jìn)制數(shù)字串1011，其對應(yīng)的路徑應(yīng)該是：8146。這樣就可以用一個(gè)Nl位的二進(jìn)制數(shù)來模擬走法和確定解的范圍。窮舉出從0到2n-1個(gè)十進(jìn)制數(shù)所對應(yīng)的N-1位二進(jìn)制串對應(yīng)的路徑中的數(shù)字總和，判定其是否等于M而求得問題的解。 對于任務(wù)二，采用動態(tài)規(guī)劃中的順推解法。按三角形的行劃分階段，若行數(shù)為n，則可把問題看做一個(gè)n-1個(gè)階段的決策問題。從始點(diǎn)出發(fā)，依順向求出第一階段、第二階

20、段第n1階段中各決策點(diǎn)至始點(diǎn)的最佳路徑，最終求出始點(diǎn)到終點(diǎn)的最佳路徑。 設(shè)：fk(Uk)為從第k階段中的點(diǎn)Uk至三角形頂點(diǎn)有一條最佳路徑，該路徑所經(jīng)過的數(shù)字的總和最大，fk(Uk)表示為這個(gè)數(shù)字和；由于每一次決策有兩個(gè)選擇，或沿左斜線向下，或沿右斜線向下，因此設(shè)： Uk1為k-1階段中某點(diǎn)Uk沿左斜線向下的點(diǎn)； Uk2為k-1階段中某點(diǎn)Uk沿右斜線向下的點(diǎn)； dk(Uk1)為k階段中Uk1的數(shù)字；dk(Uk2)為k階段中Uk2的數(shù)字。因而可寫出順推關(guān)系式(狀態(tài)轉(zhuǎn)移方程)為： fk(Uk)=maxfk-1(Uk)+dk(Uk1)，fk-1(Uk)+dk(Uk2)(k=1，2，3，n) f0(U0

21、)0經(jīng)過一次順推，便可分別求出由頂至底N個(gè)數(shù)的N條路徑，在這N條路徑所經(jīng)過的N個(gè)數(shù)字和中，最大值即為正確答案。5.動態(tài)規(guī)劃的應(yīng)用實(shí)例5.1最短路線問題例1 現(xiàn)有一張地圖，各結(jié)點(diǎn)代表城市，兩結(jié)點(diǎn)間連線代表道路，線上數(shù)字表示城市間的距離。如圖1所示，試找出從結(jié)點(diǎn)A到結(jié)點(diǎn)E的最短距離。 我們可以用深度優(yōu)先搜索法來解決此問題，該問題的遞歸式為其中是與v相鄰的節(jié)點(diǎn)的集合，w(v,u)表示從v到u的邊的長度。這個(gè)程序的效率如何呢？我們可以看到，每次除了已經(jīng)訪問過的城市外，其他城市都要訪問，所以時(shí)間復(fù)雜度為O(n!)，這是一個(gè)“指數(shù)級”的算法。 首先，我們來觀察一下這個(gè)算法。在求從B1到E的最短距離的時(shí)候，

22、先求出從C2到E的最短距離；而在求從B2到E的最短距離的時(shí)候，又求了一遍從C2到E的最短距離。也就是說，從C2到E的最短距離我們求了兩遍。同樣可以發(fā)現(xiàn)，在求從C1、C2到E的最短距離的過程中，從D1到E的最短距離也被求了兩遍。而在整個(gè)程序中，從D1到E的最短距離被求了四遍。如果在求解的過程中，同時(shí)將求得的最短距離記錄在案，隨時(shí)調(diào)用，就可以避免這種情況。于是，可以改進(jìn)該算法，將每次求出的從v到E的最短距離記錄下來，在算法中遞歸地求MinDistance(v)時(shí)先檢查以前是否已經(jīng)求過了MinDistance(v)，如果求過了則不用重新求一遍，只要查找以前的記錄就可以了。這樣，由于所有的點(diǎn)有n個(gè)，因

23、此不同的狀態(tài)數(shù)目有n個(gè)，該算法的數(shù)量級為O(n)。更進(jìn)一步，可以將這種遞歸改為遞推，這樣可以減少遞歸調(diào)用的開銷。5.2資源分配問題所謂資源分配問題，就是將一定數(shù)量的一種或若干種資源（如原材料、機(jī)器設(shè)備、資金、勞動力等）恰當(dāng)?shù)胤峙浣o若干個(gè)使用者，以使資源得到最有效地利用。設(shè)有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)第j種產(chǎn)品的收益是其所獲得的各種資源數(shù)量的函數(shù)，即gj = f（x1j,x2j, xmj）。由于總收益是n種產(chǎn)品收益的和，此問題可用如下靜態(tài)模型加以描述： 若是連續(xù)變量，當(dāng) = f

24、（, ）是線性函數(shù)時(shí)，該模型是線性規(guī)劃模型；當(dāng) = f（, ）是非線性函數(shù)時(shí)，該模型是非線性規(guī)劃模型。若是離散變量或（和） = f（, ）是離散函數(shù)時(shí)，此模型用線性規(guī)劃或非線性規(guī)劃來求解都將是非常麻煩的。然而在此情況下，由于這類問題的特殊結(jié)構(gòu)，可以將它看成為一個(gè)多階段決策問題，并利用動態(tài)規(guī)劃的遞推關(guān)系來求解。本例只考慮一維資源的分配問題，設(shè)狀態(tài)變量表示分配于從第k個(gè)階段至過程最終（第N個(gè)階段）的資源數(shù)量，即第k個(gè)階段初資源的擁有量；決策變量xk表示第k個(gè)階段資源的分配量。于是有狀態(tài)轉(zhuǎn)移律：允許決策集合：最優(yōu)指標(biāo)函數(shù)（動態(tài)規(guī)劃的逆序遞推關(guān)系式）： 利用這一遞推關(guān)系式，最后求得的即為所求問題的最大

25、總收益，下面來看一個(gè)具體的例子。例2 某公司擬將500萬元的資本投入所屬的甲、乙、丙三個(gè)工廠進(jìn)行技術(shù)改造，各工廠獲得投資后年利潤將有相應(yīng)的增長，增長額如表7-1所示。試確定500萬元資本的分配方案，以使公司總的年利潤增長額最大。表7-1投資額100萬元200萬元300萬元400萬元500萬元甲307090120130乙50100110110110丙4060110120120解：將問題按工廠分為三個(gè)階段k=1，2，3，設(shè)狀態(tài)變量（）代表從第個(gè)工廠到第3個(gè)工廠的投資額，決策變量代表第k個(gè)工廠的投資額。于是有狀態(tài)轉(zhuǎn)移率、允許決策集合和遞推關(guān)系式： 當(dāng)時(shí)：于是有表7-2，表中表示第三個(gè)階段的最優(yōu)決策。