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

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

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

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

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

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

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

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

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

9、定的標(biāo)準(zhǔn)下達(dá)到最好的效果.3.2動(dòng)態(tài)規(guī)劃問題中的術(shù)語階段：把所給求解問題的過程恰當(dāng)?shù)胤殖扇舾蓚€(gè)相互聯(lián)系的階段，以便于求解，過程不同，階段數(shù)就可能不同描述階段的變量稱為階段變量。在多數(shù)情況下，階段變量是離散的，用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)變量。一般

10、，狀態(tài)是離散的，但有時(shí)為了方便也將狀態(tài)取成連續(xù)的。當(dāng)然，在現(xiàn)實(shí)生活中，由于變量形式的限制，所有的狀態(tài)都是離散的，但從分析的觀點(diǎn)，有時(shí)將狀態(tài)作為連續(xù)的處理將會(huì)有很大的好處。此外，狀態(tài)可以有多個(gè)分量(多維情形)，因而用向量來代表；而且在每個(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í)，不

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

12、集合中達(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)的值變化而變化，那么可以把這一關(guān)系看成(x(k)，u(k)與x(k+1)確定的對(duì)應(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)策略，它滿足：相對(duì)前面決策所形成的狀態(tài)而言，余下的子策略必然構(gòu)成“最優(yōu)子策略”。4.動(dòng)態(tài)規(guī)劃求解的基本步驟動(dòng)態(tài)規(guī)劃所處理的問題是一個(gè)多階段決策問題，一般由初始狀態(tài)開始，通過

13、對(duì)中間階段決策的選擇，達(dá)到結(jié)束狀態(tài)。這些決策形成了一個(gè)決策序列，同時(shí)確定了完成整個(gè)過程的一條活動(dòng)路線(通常是求最優(yōu)的活動(dòng)路線)。如圖所示。動(dòng)態(tài)規(guī)劃的設(shè)計(jì)都有著一定的模式，一般要經(jīng)歷以下幾個(gè)步驟。初始狀態(tài)決策決策決策結(jié)束狀態(tài) 動(dòng)態(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)移就是根

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

15、數(shù)字為不超過100的整數(shù)?，F(xiàn)規(guī)定從最頂層走到最底層，每一步可沿左斜線向下或右斜線向下走。 任務(wù)一：假設(shè)三角形行數(shù)10，鍵盤輸入一個(gè)確定的整數(shù)值M，編程確定是否存在一條路徑，使得沿著該路徑所經(jīng)過的數(shù)字的總和恰為M，若存在則給出所有路徑，若不存在，則輸出“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ù)

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【分析】對(duì)于這一問題，很容易想到用枚舉的方法去解決，即列舉出所有路徑并記錄每一條路徑所經(jīng)過的數(shù)字總和。然后判斷數(shù)字總和是否等于給定的整數(shù)值M或?qū)ふ页鲎畲蟮臄?shù)字總和，這一想法很直觀，而且對(duì)于任務(wù)一，由于數(shù)字三角形的行數(shù)不大(10)，因此其枚舉量不是很大，應(yīng)該能夠?qū)崿F(xiàn)。但對(duì)于任務(wù)二，如果用枚舉的方法，當(dāng)三角形的行數(shù)等于100時(shí)，其枚舉量之大是可想而知的，顯然，枚舉法對(duì)于任務(wù)二的求解并不適用。其實(shí)，只要對(duì)對(duì)

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

18、對(duì)應(yīng)的路徑中的數(shù)字總和，判定其是否等于M而求得問題的解。 對(duì)于任務(wù)二，采用動(dòng)態(tài)規(guī)劃中的順推解法。按三角形的行劃分階段，若行數(shù)為n，則可把問題看做一個(gè)n-1個(gè)階段的決策問題。從始點(diǎn)出發(fā)，依順向求出第一階段、第二階段第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階段中Uk

19、1的數(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個(gè)數(shù)的N條路徑，在這N條路徑所經(jīng)過的N個(gè)數(shù)字和中，最大值即為正確答案。5.動(dòng)態(tài)規(guī)劃的應(yīng)用實(shí)例5.1最短路線問題例1 美國黑金石油公司（The Black Gold Petroleum Company）最近在阿拉斯加（Alaska）的北斯洛波（North Slope）發(fā)現(xiàn)了大的石油儲(chǔ)量。為了大規(guī)模開發(fā)這一油田，首先必須建立相應(yīng)的輸運(yùn)網(wǎng)絡(luò)，使北斯洛波生

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

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

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

23、線可以選擇，即選擇M22或M23；故： 選擇M22，當(dāng)時(shí)：由結(jié)點(diǎn)C到達(dá)下一階段有兩條路線可以選擇，即選擇M11或M12；故： 選擇M11,，而通過順序（計(jì)算的反順序）追蹤（黑體標(biāo)示）可以得到兩條最佳的輸運(yùn)線路：CM11M22M32P2；CM11M22M33P3。最短的輸送距離是280千米。5.2資源分配問題所謂資源分配問題，就是將一定數(shù)量的一種或若干種資源（如原材料、機(jī)器設(shè)備、資金、勞動(dòng)力等）恰當(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)第

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

25、資源的擁有量；決策變量xk表示第k個(gè)階段資源的分配量。于是有狀態(tài)轉(zhuǎn)移律：允許決策集合：最優(yōu)指標(biāo)函數(shù)（動(dòng)態(tài)規(guī)劃的逆序遞推關(guān)系式）： 利用這一遞推關(guān)系式，最后求得的即為所求問題的最大總收益，下面來看一個(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)決策。表7-2 （單位：百萬元）0 1234501234500.40.61.11.21.2當(dāng)時(shí)：。于是有表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