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

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

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

3、得名。 動態(tài)規(guī)劃的主要創(chuàng)始人是美國數(shù)學(xué)家貝爾曼 （ Bellman）。 20世紀(jì)40年代末50年代初，當(dāng)時在蘭德公司（Rand Corporation）從事研究工 作的貝爾曼首先提出了動態(tài)規(guī)劃的概念。 1957 年貝爾曼發(fā)表了數(shù)篇研究論文， 并出版了他的第一部著作動態(tài)規(guī)劃 。該著作成為了當(dāng)時唯一的進(jìn)一步研究和 應(yīng)用動態(tài)規(guī)劃的理論源泉。 在貝爾曼及其助手們致力于發(fā)展和推廣這一技術(shù)的同 時，其他一些學(xué)者也對動態(tài)規(guī)劃的發(fā)展做出了重大的貢獻(xiàn)， 其中最值得一提的是 愛爾思（Aris）和梅特頓（Mitten ）。愛爾思先后于1961年和1964年出版了兩部 關(guān)于動態(tài)規(guī)劃的著作，并于1964年同尼母霍思爾（

4、Nemhause）、威爾德（Wild） 一道創(chuàng)建了處理分枝、 循環(huán)性多階段決策系統(tǒng)的一般性理論。 梅特頓提出了許多 對動態(tài)規(guī)劃后來發(fā)展有著重要意義的基礎(chǔ)性觀點， 并且對明晰動態(tài)規(guī)劃路徑的數(shù) 學(xué)性質(zhì)做出了巨大的貢獻(xiàn)。動態(tài)規(guī)劃問世以來， 在工程技術(shù)、 經(jīng)濟(jì)管理等社會各個領(lǐng)域都有著廣泛的應(yīng) 用，并且獲得了顯著的效果。 在經(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ī)劃更有效。 特別是對于離 散的問題，由于

5、解析數(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ī)劃主要用于求解以時間劃分階段的動態(tài)過程的優(yōu)化問題， 但是一 些與時間無關(guān)的靜態(tài)規(guī)劃 （如線性規(guī)劃、非線性規(guī)劃 ），只要人為地引進(jìn)時間因素， 把它視為多階段決策過程，也可以用動態(tài)規(guī)劃方法方便地求解。2. 動態(tài)規(guī)劃的基本思想一般來說，只要問題可以劃分成規(guī)模更小的子問題， 并且原問題的最優(yōu)解中 包含了子問題的最優(yōu)解， 則可以考慮用動態(tài)規(guī)劃解決。 動態(tài)規(guī)劃的實質(zhì)是分治思 想和解決冗余，

6、因此，動態(tài)規(guī)劃是一種將問題實例分解為更小的、 相似的子問題， 并存儲子問題的解而避免計算重復(fù)的子問題， 以解決最優(yōu)化問題的算法策略。 由 此可知，動態(tài)規(guī)劃法與分治法和貪心法類似， 它們都是將問題實例歸納為更小的、 相似的子問題， 并通過求解子問題產(chǎn)生一個全局最優(yōu)解。 其中貪心法的當(dāng)前選擇 可能要依賴已經(jīng)作出的所有選擇， 但不依賴于有待于做出的選擇和子問題。 因此 貪心法自頂向下， 一步一步地作出貪心選擇； 而分治法中的各個子問題是獨立的 （即不包含公共的子子問題 ），因此一旦遞歸地求出各子問題的解后，便可自下而 上地將子問題的解合并成問題的解。 但不足的是， 如果當(dāng)前選擇可能要依賴子問 題的解

7、時， 則難以通過局部的貪心策略達(dá)到全局最優(yōu)解； 如果各子問題是不獨立 的，則分治法要做許多不必要的工作， 重復(fù)地解公共的子問題。 解決上述問題的 辦法是利用動態(tài)規(guī)劃。 該方法主要應(yīng)用于最優(yōu)化問題， 這類問題會有多種可能的 解，每個解都有一個值，而動態(tài)規(guī)劃找出其中最優(yōu) （最大或最小 ）值的解。若存在 若干個取最優(yōu)值的解的話， 它只取其中的一個。 在求解過程中， 該方法也是通過 求解局部子問題的解達(dá)到全局最優(yōu)解， 但與分治法和貪心法不同的是， 動態(tài)規(guī)劃 允許這些子問題不獨立， 也允許其通過自身子問題的解作出選擇， 該方法對每一 個子問題只解一次，并將結(jié)果保存起來，避免每次碰到時都要重復(fù)計算。因此，

8、動態(tài)規(guī)劃法所針對的問題有一個顯著的特征， 即它所對應(yīng)的子問題樹 中的子問題呈現(xiàn)大量的重復(fù)。 動態(tài)規(guī)劃法的關(guān)鍵就在于， 對于重復(fù)出現(xiàn)的子問題， 只在第一次遇到時加以求解， 并把答案保存起來， 讓以后再遇到時直接引用， 不 必重新求解。3. 動態(tài)規(guī)劃的基本概念動態(tài)規(guī)劃的數(shù)學(xué)描述離不開它的一些基本概念與符號， 因此有必要在介紹多階段決策過程的數(shù)學(xué)描述的基礎(chǔ)上，系統(tǒng)地介紹動態(tài)規(guī)劃的一些基本概念。3.1 多階段決策問題 如果一類活動過程可以分為若干個互相聯(lián)系的階段， 在每一個階段都需作出 決策，一個階段的決策確定以后， 常常影響到下一個階段的決策， 從而就完全確 定了一個過程的活動路線，則稱它為多階段決

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

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

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

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

13、階段的決 策u(k)的值變化而變化，那么可以把這一關(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)性原理 : 作為整個過程的最優(yōu)策略，它滿足：相對前面決策所形成的狀 態(tài)而言，余下的子策略必然構(gòu)成 !優(yōu)子策略It4. 動態(tài)規(guī)劃求解的基本步驟動態(tài)規(guī)劃所處理的問題是一個多階段決策問題， 一般由初始狀態(tài)開始， 通過 對中間階段決策的選擇， 達(dá)到結(jié)束狀態(tài)。 這些決策形成了一個決策序列， 同時確 定了完成整個過程的一條活動路線 (通常是求最優(yōu)的活動路線 )。如圖所示。動態(tài)

14、 規(guī)劃的設(shè)計都有著一定的模式，一般要經(jīng)歷以下幾個步驟。初始狀態(tài)丨決策1 |f|決策2 |I決策n |t結(jié)束狀態(tài)動態(tài)規(guī)劃決策過程示意圖劃分階段：，按照問題的時間或空間特征，把問題分為若干個階段。在劃 分階段時，注意劃分后的階段一定要是有序的或者是可排序的， 否則問題就無法 求解。（2）確定狀態(tài)和狀態(tài)變量：將問題發(fā)展到各個階段時所處于的各種客觀情況用 不同的狀態(tài)表示出來。當(dāng)然，狀態(tài)的選擇要滿足無后效性。（3）確定決策并寫出狀態(tài)轉(zhuǎn)移方程：因為決策和狀態(tài)轉(zhuǎn)移有著天然的聯(lián)系，狀態(tài)轉(zhuǎn)移就是根據(jù)上一階段的狀態(tài)和決策來導(dǎo)出本階段的狀態(tài)所以如果確定了決策，狀態(tài)轉(zhuǎn)移方程也就可寫出。但事實上常常是反過來做,根據(jù)相鄰

15、兩段各狀態(tài)之間的關(guān)系來確定決策（4）尋找邊界條件：給出的狀態(tài)轉(zhuǎn)移方程是一個遞推式,需要一個遞推的終止條件或邊界條件（5）程序設(shè)計實現(xiàn)：動態(tài)規(guī)劃的主要難點在于理論上的設(shè)計，一旦設(shè)計完成, 實現(xiàn)部分就會非常簡單。根據(jù)上述動態(tài)規(guī)劃設(shè)計的步驟，可得到大體解題框架如圖所示。對f石）初站化i邊界條件） forkdoi】（這里以順序求解為例）對每一個SkGSfc以恥）一個極值（8或一8）對毒一個協(xié)GJwDb）-«£（亂"心）奴g1'輸出fn(sj動態(tài)規(guī)劃設(shè)計的一般模式圖上述提供了動態(tài)規(guī)劃方法的一般模式， 對于簡單的動態(tài)規(guī)劃問題，可以按部就班地進(jìn)行動態(tài)規(guī)劃的設(shè)計。下面，給

16、出一個利用動態(tài)規(guī)劃方法求解的典型例 子。數(shù)字三角形問題 上圖示出了一個數(shù)字三角形寶塔。數(shù)字三角形中的數(shù)字 為不超過 100 的整數(shù)?，F(xiàn)規(guī)定從最頂層走到最底層， 每一步可沿左斜線向下或右 斜線向下走。任務(wù)一：假設(shè)三角形行數(shù) 10鍵盤輸入一個確定的整數(shù)值 M，編程確定是 否存在一條路徑，使得沿著該路徑所經(jīng)過的數(shù)字的總和恰為 M ，若存在則給出 所有路徑，若不存在，則輸出 一NOAnswer!字樣。任務(wù)二：假設(shè)三角形行數(shù) 100編程求解從最頂層走到最底層的一條路徑， 使得沿著該路徑所經(jīng)過的數(shù)字的總和最大，輸出最大值。 輸人數(shù)據(jù)：由文件輸入數(shù)據(jù)，任務(wù)一中文件第一行是三角形的行數(shù)N 和整數(shù)值M。以后的N

17、行分別是從最頂層到最底層的每一層中的數(shù)字。任務(wù)二中文件數(shù)據(jù)格式同任務(wù)一，只是第一行中沒有整數(shù)值M 。在例子中任務(wù)二的文件數(shù)據(jù)表示如下：輸入： 57輸出：輸出路徑和最大值3 87或一No An swer字 樣。8 1 0382 7 7 48 1 04 5 2 6 52744圖345265【分析】對于這一問題，很容易想到用枚舉的方法去解決，即列舉出所有路 徑并記錄每一條路徑所經(jīng)過的數(shù)字總和。 然后判斷數(shù)字總和是否等于給定的整數(shù) 值 M 或?qū)ふ页鲎畲蟮臄?shù)字總和，這一想法很直觀，而且對于任務(wù)一，由于數(shù)字 三角形的行數(shù)不大（=10），因此其枚舉量不是很大，應(yīng)該能夠?qū)崿F(xiàn)。但對于任 務(wù)二，如果用枚舉的方法，

18、 當(dāng)三角形的行數(shù)等于 100時，其枚舉量之大是可想而 知的，顯然，枚舉法對于任務(wù)二的求解并不適用。其實，只要對對任務(wù)二稍加分 析，就可以得出一個結(jié)論：如果得到一條由頂至底的某處的一條最佳路徑，那么對于該路徑上的每一 個中間點來說， 由頂至該中間點的路徑所經(jīng)過的數(shù)字和也為最大。 因此該問題是 一個典型的多階段決策最優(yōu)化的問題。算法設(shè)計與分析如下：對于任務(wù)一，合理地確認(rèn)枚舉的方法，可以優(yōu)化問題的解法。由于從塔頂 到底層每次都只有兩種走法，即左或右。設(shè) 一0表示左，一1表示右，對于層數(shù)為 N 的數(shù)字塔， 從頂?shù)降椎囊环N走法可用一個 N-1 位的二進(jìn)制數(shù)表示。 如例中二進(jìn) 制數(shù)字串 1011，其對應(yīng)的

19、路徑應(yīng)該是： 8146。這樣就可以用一個 Nl 位 的二進(jìn)制數(shù)來模擬走法和確定解的范圍。窮舉出從 0 到 2n-1 個十進(jìn)制數(shù)所對應(yīng) 的 N-1 位二進(jìn)制串對應(yīng)的路徑中的數(shù)字總和，判定其是否等于 M 而求得問題的 解。對于任務(wù)二， 采用動態(tài)規(guī)劃中的順推解法。 按三角形的行劃分階段， 若行數(shù) 為n,則可把問題看做一個n-1個階段的決策問題。從始點出發(fā)，依順向求出第 一階段、第二階段 第n1階段中各決策點至始點的最佳路徑，最終求出始 點到終點的最佳路徑。設(shè)：fk(Uk)為從第k階段中的點Uk至三角形頂點有一條最佳路徑，該路徑 所經(jīng)過的數(shù)字的總和最大，fk(Uk)表示為這個數(shù)字和；由于每一次決策有兩

20、個選 擇，或沿左斜線向下，或沿右斜線向下，因此設(shè)：Uk1 為 k-1 階段中某點 Uk 沿左斜線向下的點；Uk2為k-1階段中某點Uk沿右斜線向下的點；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) = 0經(jīng)過一次順推，便可分別求出由頂至底 N個數(shù)的N條路徑，在這N條路徑所經(jīng) 過的 N 個數(shù)字和中，最大值即為正確答案。5. 動態(tài)規(guī)劃的應(yīng)用實例5.1 最短路線問題例 1 美國黑金石油公司( The

21、 Black Gold Petroleum Company )最近在阿拉斯 加(Alaska)的北斯洛波(North Slope)發(fā)現(xiàn)了大的石油儲量。為了大規(guī)模開發(fā) 這一油田， 首先必須建立相應(yīng)的輸運(yùn)網(wǎng)絡(luò)， 使北斯洛波生產(chǎn)的原油能運(yùn)至美國的 3個裝運(yùn)港之一。在油田的集輸站(結(jié)點 C)與裝運(yùn)港(結(jié)點P1、P2、P3)之間 需要若干個中間站，中間站之間的聯(lián)通情況如圖 7-2所示，圖中線段上的數(shù)字代 表兩站之間的距離（單位：10千米）。試確定一最佳的輸運(yùn)線路，使原油的輸送 距離最短。解：最短路線有一個重要性質(zhì)，即如果由起點 A經(jīng)過B點和C點到達(dá)終點D是 一條最短路線，則由B點經(jīng)C點到達(dá)終點D 一定是

22、B到D的最短路（貝爾曼最 優(yōu)化原理）。此性質(zhì)用反證法很容易證明，因為如果不是這樣，則從 B點到D點 有另一條距離更短的路線存在，不妨假設(shè)為 B P D;從而可知路線 A B P D比原路線A BCD距離短，這與原路線 A BC D是最短路線相矛 盾，性質(zhì)得證。根據(jù)最短路線的這一性質(zhì)，尋找最短路線的方法就是從最后階段開始， 由后向前 逐步遞推求出各點到終點的最短路線， 最后求得由始點到終點的最短路；即動態(tài) 規(guī)劃的方法是從終點逐段向始點方向?qū)ふ易疃搪肪€的一種方法。 按照動態(tài)規(guī)劃的方法，將此過程劃分為4個階段，即階段變量k",2,3,4 ;取過程在各階段所處的位置為狀態(tài)變量Sk，按逆序算法

23、求解。810PiM218764639P2CM22796511115P3M2336M 34M12M 31M 33M11M 32k=2k=3k=4圖7-2當(dāng)k =4時：由結(jié)點M31到達(dá)目的地有兩條路線可以選擇， 即選擇P1或P2;故: (8彳4 (S4 = M 31) = min 丿? = 6選擇P2，由結(jié)點M32到達(dá)目的地有三條路線可以選擇，即選擇P1、P2或P3； 故:i Nf4 (S4 = M 32) = min < 3 卜=3選擇P2，由結(jié)點M33到達(dá)目的地也有三條路線可以選擇，即選擇 P1、P2或P3； 故：f4 (S4 = M 33) = min <6=5選擇P3，由結(jié)點M

24、34到達(dá)目的地有兩條路線可以選擇，即選擇 P2或P3；故：f4 (S4 = M 34) = min， > = 3*選擇P2當(dāng)k = 3時：由結(jié)點M21到達(dá)下一階段有三條路線可以選擇，即選擇M31、M32 或 M33;故：10+6、f3(S3 =M21) =min < 7 +3 , = 106+5,選擇M32由結(jié)點M22到達(dá)下一階段也有三條路線可以選擇，即選擇 M31、M32或M33;故：9+6f3(S3 = M22) = mi n<7 +3= 10選擇M32或M33，由結(jié)點M23至V達(dá)下一階段也有三條路線可以選擇，即選擇M32、M33 或 M34;故：113f3(S3 = M

25、23)=min4+5、= 9(6+3,選擇M33或M34當(dāng)k = 2時：由結(jié)點M11到達(dá)下一階段有兩條路線可以選擇，即選擇M21或M22;故：”8+10、f2 (S2 = M“)= mi n，> = 1621£+10：選擇M22,由結(jié)點M12，至U達(dá)下一階段也有兩條路線可以選擇，即選擇M22或M23;故：.9+10、f? （S2 = M2）=min>=19J1 +9：選擇M22，當(dāng)k=1時：由結(jié)點C到達(dá)下一階段有兩條路線可以選擇，即選擇 M11 或 M12;故:.12+16fi （S| = C） = min,=280+19：選擇M11,而通過順序（計算的反順序）追蹤（黑體

26、標(biāo)示）可以得到兩條最佳 的輸運(yùn)線路：CM11 M22 M32 P2； CM11 M22 M33 P3。最短的輸 送距離是280千米。5.2資源分配問題所謂資源分配問題，就是將一定數(shù)量的一種或若干種資源（如原材料、機(jī)器設(shè)備、資金、勞動力等）恰當(dāng)?shù)胤峙浣o若干個使用者，以使資源得到最有效地利 用。設(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)模型加以描

27、述：n.maxz 八 gjj 二nJ Z Xij =b (i =1,2,m)xj Z0(i = 1,2, m 匕 T 2n若Xij是連續(xù)變量，當(dāng)gj = f （ X1j,X2j,., Xmj ）是線性函數(shù)時，該模型是線性規(guī)劃模型；當(dāng)gj = f（ X1j,X2j,，Xmj ）是非線性函數(shù)時，該模型是非線性規(guī) 劃模型。若xij是離散變量或（和）gj = f （ XtjXzj,，xmj）是離散函數(shù)時，此模型用線性規(guī)劃或非線性規(guī)劃來求解都將是非常麻煩的。 然而在此情況下，由于 這類問題的特殊結(jié)構(gòu)，可以將它看成為一個多階段決策問題， 并利用動態(tài)規(guī)劃的 遞推關(guān)系來求解。本例只考慮一維資源的分配問題，設(shè)狀

28、態(tài)變量&表示分配于從第k個階段至 過程最終（第N個階段）的資源數(shù)量，即第k個階段初資源的擁有量；決策變 量xk表示第k個階段資源的分配量。于是有狀態(tài)轉(zhuǎn)移律：允許決策集合：Dk(Sk) =兀 |0_xk _Sk最優(yōu)指標(biāo)函數(shù)(動態(tài)規(guī)劃的逆序遞推關(guān)系式)：-fk(Sk) = mia)Sgk(Xk) - fki(Ski)(k 二 N, N-1,N- 2, , 1Y J f N 卑(Sn 屮)=0利用這一遞推關(guān)系式，最后求得的f/S)即為所求問題的最大總收益，下面來看 一個具體的例子。例2某公司擬將500萬元的資本投入所屬的甲、乙、丙三個工廠進(jìn)行技術(shù)改造， 各工廠獲得投資后年利潤將有相應(yīng)的增長，

29、增長額如表7-1所示。試確定500萬元資本的分配方案，以使公司總的年利潤增長額最大。表7-1投100200300萬400500資額萬元萬元元萬元萬元甲307090120130乙：50100110110:110丙4060110120120解：將問題按工廠分為三個階段 k=1，2，3，設(shè)狀態(tài)變量Sk( k =1,2,3)代表從 第k個工廠到第3個工廠的投資額，決策變量Xk代表第k個工廠的投資額。于是 有狀態(tài)轉(zhuǎn)移率£ Sk - Xk、允許決策集合Dk(SJ =兀| 0乞Xk乞Sk和遞推關(guān)系式：-fk(SkH0mja)Sgk(Xk) - fk 16 -Xk) (k 二 3,2,1-f4(S4

30、)=0當(dāng)k =3時：f3(S3)=関093(滄)9 =0鑒曲3區(qū))于是有表7-2，表中x3表示第二個階段的最優(yōu)決策表7-2（單位：百萬元）S3oi2345x3oi2345f3 (S3)00.40.6i.ii.2i.2當(dāng) k=2 時：f2(S2) max g2(x2) f3(S2-x2)。于是有表 7-3。表7-3 （單位：百萬元）x2<2g2( x2)+f3( s2 - x2)f2(S2)x2012345() 0+000*0+0.40.5+00.512> 0+0.60.5+0.41.0+01.0230+1.10.5+0.61.0+0.41.1+01.42I0+1.20.5+1.11.0+0.61.1+0.41.1+01.61，25j0+1.20.5+1.21.0+1.11.1+0.61.1+0.41.1+02.12當(dāng)k =1時:fi(Si) maxgi(xi) f2(Si - 為)于是:11gi (xi) +f2 (si -xi)fi(S)xixS01234550+2.10.3+1.60.7+1.40.9+1.01.2+0.51.3+02.10, 2然后按計算表格的順序反推算，可知最優(yōu)分配方案有兩個：（1）甲工廠投資 200萬元，乙工廠投資200萬元，丙工廠投資100萬元；（2）甲工廠沒有投資， 乙工廠投資200萬元，丙工廠投資300萬元。按最優(yōu)分配方案分配投資（