交通運(yùn)輸工程系統(tǒng)分析課件

1、交通運(yùn)輸工程系統(tǒng)分析湖南大學(xué)道路與交通工程研究所李 碩 博士主講（第一分冊(cè)）交通運(yùn)輸工程系統(tǒng)分析使用教材：道路與交通工程系統(tǒng)分析，姚祖康主編， 人民交通出版社，1996年12月第一版；參考書目：1、交通運(yùn)輸工程學(xué)，沈志云、鄧學(xué)均，人民交通 出版社， 2005年5月第二版；2、運(yùn)籌學(xué)(修訂版)，運(yùn)籌學(xué)教材編寫組， 清華大學(xué)出版社，1990年1月第二版；3、交通運(yùn)輸工程，馮樹民，知識(shí)產(chǎn)權(quán)出版社， 2004年10月第一版；4、運(yùn)籌學(xué)習(xí)題集(修訂版)，胡運(yùn)權(quán)主編，清華大學(xué) 出版社，1995年5月第二版。第一章 概 論1.1 系統(tǒng)與系統(tǒng)分析（1）系統(tǒng)的定義 系統(tǒng)是由一些相互聯(lián)系、相互依賴、互感相關(guān)的獨(dú)立

2、單元或部分組合而成的復(fù)雜集合，每個(gè)單元或部分具有各自的特性和功能，這些相關(guān)單元或部分按一定目的和結(jié)構(gòu)方式協(xié)調(diào)統(tǒng)一在系統(tǒng)的整體中，以實(shí)現(xiàn)特定的系統(tǒng)功能。（2）系統(tǒng)的屬性普遍存在性（Ubiquity)天然與人造共存（工程系統(tǒng)是人造的）物理與概念同在局部與整體相互影響和協(xié)調(diào)性系統(tǒng)的目的性系統(tǒng)的層次性系統(tǒng)范圍和功能的界定人為性涉及學(xué)科的廣泛性和綜合性系統(tǒng)分析的方法論包括：1）利用數(shù)學(xué)的、物理的、仿真的方法對(duì)工程分析對(duì)象建立模型和進(jìn)行定量的分析與研究；2）利用專家的工程經(jīng)驗(yàn)和常識(shí)知識(shí)對(duì)工程分析對(duì)象進(jìn)行定性的分析與研究；3）定量與定性方法相結(jié)合的系統(tǒng)分析方法；4）微觀與宏觀分析方法相結(jié)合。 系統(tǒng)分析方法論

3、是一個(gè)多學(xué)科的綜合體，從整體和系統(tǒng)的觀念認(rèn)識(shí)和分析系統(tǒng)的各個(gè)組成單元特性和內(nèi)在關(guān)系，以及各單元協(xié)調(diào)形成的系統(tǒng)整體特性。 人造系統(tǒng)的目的是人為設(shè)定的，各個(gè)系統(tǒng)運(yùn)營時(shí)期的系統(tǒng)目的價(jià)值不一樣，其效能也不一樣，只有通過系統(tǒng)分析才能為系統(tǒng)設(shè)定新的效能更高的系統(tǒng)目的，故系統(tǒng)分析具有以下成效：1）提供多種不同的可選方案；2）充分有效的利用有限的資源；3）提供預(yù)定目的而資源消耗最小的方案；4）為工程項(xiàng)目決策層提供多方面決策依據(jù)；5）提供方案實(shí)施后的效果分析。（1）系統(tǒng)辨識(shí)與目標(biāo)設(shè)定 不同的系統(tǒng)有不同的結(jié)構(gòu)、組成單元、單元之間的相關(guān)關(guān)系、整體與個(gè)體的性狀，需要進(jìn)行辨識(shí)。如：城市交通系統(tǒng)與公路交通系統(tǒng)就不一樣。辨

4、識(shí)的方法則是進(jìn)行不同類型的調(diào)查，有現(xiàn)場(chǎng)調(diào)查、有問卷調(diào)查、有專家咨詢等。對(duì)調(diào)查所獲得的數(shù)據(jù)資料進(jìn)行科學(xué)的分析與研究，以期獲得系統(tǒng)的現(xiàn)狀特性和存在的問題，為設(shè)定新的系統(tǒng)目標(biāo)和設(shè)計(jì)新的系統(tǒng)方案提供科學(xué)的依據(jù)。（2）提出可選方案 為了解決現(xiàn)狀系統(tǒng)存在的問題，實(shí)現(xiàn)系統(tǒng)的新目標(biāo)，需要提出若干個(gè)在技術(shù)、經(jīng)濟(jì)、政治上可行的系統(tǒng)方案，以供進(jìn)一步的分析與研究。 可行性概念包括：1）技術(shù)可行性系統(tǒng)方案：達(dá)到系統(tǒng)技術(shù)性能指標(biāo)和 系統(tǒng)預(yù)定技術(shù)目標(biāo)的可能性；2）經(jīng)濟(jì)可行性系統(tǒng)方案：可用經(jīng)濟(jì)資源的可能性；3）政治可行性系統(tǒng)方案：在國家和地方政府政策允 許范圍以及行政主管部門決策層的許可性。3）分析與評(píng)價(jià)可選系統(tǒng)方案 對(duì)上述

5、若干可行系統(tǒng)方案進(jìn)行技術(shù)、經(jīng)濟(jì)、政治可行性對(duì)比分析（定量+定性方法），綜合評(píng)價(jià)各方案的優(yōu)劣程度，從中找出綜合評(píng)價(jià)最優(yōu)方案。 分析與評(píng)價(jià)按照定量與定性的指標(biāo)（技術(shù)的、經(jīng)濟(jì)的、政治的）進(jìn)行。（4）系統(tǒng)方案選擇與決策 系統(tǒng)分析人員向決策者提出推薦方案的過程，可能最優(yōu)方案不是決策者所要的（政治可行性存在問題），系統(tǒng)分析人員要向決策者指出各可行方案的優(yōu)劣（含實(shí)施風(fēng)險(xiǎn)）之處，并提出自己分析所得出的推薦方案。（5）系統(tǒng)方案實(shí)施與后續(xù)驗(yàn)證 對(duì)選定的系統(tǒng)方案實(shí)施，并在實(shí)施過程中進(jìn)行跟蹤分析與研究，驗(yàn)證系統(tǒng)實(shí)施的優(yōu)劣性。3、系統(tǒng)分析模型與方法（1）系統(tǒng)分析模型 定義：模型是對(duì)現(xiàn)實(shí)事物的簡化、模擬、和抽象。用數(shù)學(xué)語

6、言描述系統(tǒng)行為的模型稱之為數(shù)學(xué)模型。 數(shù)學(xué)模型的類型：1）宏觀模型；2）中觀模型；3）微觀模型；4）計(jì)算機(jī)模型；5）仿真模型；6）解析模型；7）確定型模型；8）隨機(jī)型模型等。數(shù) 學(xué) 模 型采用數(shù)學(xué)語言，對(duì)實(shí)際問題的一個(gè)近似描述，以便于人們采用數(shù)學(xué)的方法研究工程實(shí)際問題。 數(shù)學(xué)模型的特征1. 實(shí)踐性：有實(shí)際背景，有針對(duì)性。接受工程實(shí)踐的檢驗(yàn)；2. 應(yīng)用性：注意實(shí)際問題的要求。強(qiáng)調(diào)模型的工程實(shí)用價(jià) 值；3. 綜合性：數(shù)學(xué)與其他工程學(xué)科知識(shí)的綜合應(yīng)用。 建模舉例數(shù)學(xué)建模（Mathematical Modelling) 是一種數(shù)學(xué)的思考方法，利用數(shù)學(xué)的語言和方法，通過抽象、簡化建立能近似刻畫并“解決”

7、工程實(shí)際問題的強(qiáng)有力的數(shù)學(xué)工具。下面給出一個(gè)數(shù)學(xué)建模的例子，重點(diǎn)說明：(1)如何做出合理的、簡化的假設(shè)；(2)如何選擇參數(shù)、變量，用數(shù)學(xué)語言確切的表述工 程實(shí)際問題；(3)如何分析模型的結(jié)果，解決或解釋工程實(shí)際問 題，或根據(jù)工程實(shí)際情況改進(jìn)模型。 模 型1.停車位模型： Sn(0)=(n-1)(L+D)；2.啟動(dòng)時(shí)間模型：tn=(n-1)T；3.行駛模型：Sn(t)=Sn(0)+(1/2)a(t-tn)2,ttn；參數(shù)估計(jì)： L=5m，D=2m，T=1s，a=2m/s；解: Sn(30)=-7(n-1)+(30-(n-1)20，解得 n19， 且t19=18s30s=t 成立。答案：一個(gè)信號(hào)周

8、期內(nèi)最多19輛車通過路口。改進(jìn)：考慮到城市車輛的限速，在勻加速運(yùn)動(dòng)啟動(dòng)后，達(dá)到最高限速后，停止加速, 按最高限速通過上述道路交叉口。 最高限速：校園內(nèi)v*=15km/h=4m/s，長安街v*=40km/h =11m/s，環(huán)城路上v*=60公里/小時(shí)=17m/s。取最高限速 v*=11m/s，達(dá)到最高限速時(shí)間tn*=v*/a+tn=5.5+n-1。 限速行駛模型： Sn(t)=Sn(0)+1/2a(tn *tn )2+v*(t-tn*)，ttn* =Sn(0)+1/2a(t-tn)2， tn*ttn =Sn(0)， tnt解：Sn(30)=-7(n-1)+(5.5)2+11(30-5.5-(n-

9、1)0 得 n17 且t17* =5.5+16=21.5s0時(shí)，當(dāng)前解不是最優(yōu)解，選擇其中最大的Cj為進(jìn)入基的新變量(即xj) ，最小的bi/aij中的xi被換出基。確定換入基的變量確定換出基的變量故本例中第一次迭代將x1換入基變量，而將x5換出基變量。CbCj31000bibi/aijxb xjx1x2x3x4x5003x3x4x1001-13-1100010-1-215145-5/114/3-5/1最優(yōu)解判斷依據(jù)Cj0400-3當(dāng)前目標(biāo)函數(shù)值Z1=15經(jīng)過行變換得到下面新的單純形表確定換入基的變量確定換出基的變量故x2換入，x4換出CbCj31000bibi/aijxb xjx1x2x3x

10、4x5013x3x2x10010101001/31/31/3-5/3-2/31/329/314/329/3最優(yōu)解判斷依據(jù)Cj000-4/3-1/3當(dāng)前目標(biāo)函數(shù)值Z2=101/3x2=x1=最優(yōu)解最優(yōu)目標(biāo)函數(shù)值Z2=101/32.4.3 約束方程為和號(hào)情況的處理 約束方程為號(hào)時(shí)所添加松弛變量前面是“”號(hào)，而約束方程為號(hào)時(shí)無須添加松弛變量，這兩種情況均不能產(chǎn)生初始基本變量（前面的符號(hào)為+1），故需要做特別處理。處理方法則是增加人工變量，例如：將左邊方程組轉(zhuǎn)換為右邊標(biāo)準(zhǔn)形式式中 為系數(shù)符號(hào)分別為正負(fù)松弛變量，而 為人工變量。由于人工變量與原線性規(guī)劃問題無關(guān)，最終解不能含有人工變量，即最終解時(shí)的人工變

11、量必須為0。要求解這樣的問題必須采用兩階段單純形法。階段1、虛擬含有人工變量的目標(biāo)函數(shù)，即人工變量之和。采用單純形法求解當(dāng)虛擬目標(biāo)函數(shù)達(dá)到0時(shí)（此時(shí)所有人工變量均為0）的解，就可獲得原線性規(guī)劃問題的初始基本可行解；階段2、以第一階段的解作為第二階段的初始基本可行解，采用單純形法求解原問題的最優(yōu)解。詳見P18-19，例2.5。2.4.4 改進(jìn)型單純形法 單純形算法每一次迭代只計(jì)算 ， ， ， 故其他變量的計(jì)算都與單純形計(jì)算無關(guān)。根據(jù)這一特點(diǎn)，設(shè)計(jì)出通過矩陣運(yùn)算直接從初始基本可行解計(jì)算出任一輪基本可行解的計(jì)算表，即改進(jìn)型單純形法。 由矩陣?yán)碚摽芍?，任一輪單純形?jì)算表中的非基本變量的系數(shù)列陣 ，可以

12、通過對(duì)初始系數(shù)矩陣中相應(yīng)的列陣 乘以基本變量系數(shù)矩陣的逆陣 后得到：也可以計(jì)算本輪單純形計(jì)算表中的右端常數(shù)列陣B矢量即為基本變量值。而非基本變量的相對(duì)效益系數(shù)的計(jì)算 改進(jìn)型單純形法計(jì)算步驟：（1）計(jì)算初始基本可行解和 ，確定進(jìn)出基本變量集合的變量；（2）計(jì)算 、 、 ，確定新的進(jìn)出基本變量集合的變量； （3）計(jì)算 、 ，確定新的進(jìn)出基本變量集合的變量；（4）重復(fù)2、3步，直至獲得最優(yōu)解為止。 2.5 對(duì)偶理論及其對(duì)偶單純形法2.5.1 對(duì)偶關(guān)系 每一個(gè)線性規(guī)劃問題都有一個(gè)對(duì)應(yīng)的另外一個(gè)線性規(guī)劃問題，稱之為對(duì)偶問題。例如，一個(gè)求極大值的含有4個(gè)變量和2個(gè)約束條件的原線性規(guī)劃問題：就相應(yīng)的有一個(gè)求

13、極小值的含有2個(gè)變量和4個(gè)約束條件的對(duì)偶線性規(guī)劃問題。原、對(duì)偶問題的對(duì)應(yīng)關(guān)系：（1）原問題的變量數(shù)與對(duì)偶問題的約束條件互為對(duì)應(yīng)關(guān)系；（2）原問題目標(biāo)函數(shù)的系數(shù)是對(duì)偶問題約束條件的右端常 數(shù)，反之亦然；（3）原問題約束條件的系數(shù)矩陣與對(duì)偶問題約束條件的系數(shù) 矩陣互為轉(zhuǎn)置關(guān)系；（4）原、對(duì)偶問題的目標(biāo)函數(shù)極大與極小對(duì)應(yīng)；（5）原、對(duì)偶問題的約束條件不等號(hào)方向相反；（6）對(duì)偶問題的對(duì)偶問題即為原問題。原問題：對(duì)偶問題：原問題：對(duì)偶問題：2.5.2 對(duì)偶定理 對(duì)原線性規(guī)劃問題求解的同時(shí)，也獲得了對(duì)偶線性規(guī)劃問題的解。這就是對(duì)偶定理的核心內(nèi)容。定理1：弱對(duì)偶定律。原、對(duì)偶問題的任一基本可行解互為對(duì) 方目

14、標(biāo)函數(shù)的上、下界；定理2：最優(yōu)解定律。如果對(duì)稱對(duì)偶線性規(guī)劃問題存在可行 解，并且其對(duì)應(yīng)的目標(biāo)函數(shù)值相等，則這些可行解就 是該問題的最優(yōu)解； 定理3：主對(duì)偶定律。如果原、對(duì)偶問題都是可行的，則它們 一定有最優(yōu)解，其最優(yōu)目標(biāo)函數(shù)值相等； 定理4：互補(bǔ)松弛定理。詳見P24?？捎糜谝粋€(gè)問題的最優(yōu)解 尋求另一個(gè)問題的最優(yōu)解。2.5.3 對(duì)偶單純形法 利用對(duì)偶定理求解原線性規(guī)劃問題的一種方法。原問題的標(biāo)準(zhǔn)形式為：則基本可行解的條件是：基本變量 ，即右端常數(shù)為非負(fù)值。而符合最優(yōu)解的條件是：各個(gè)非基本變量的相對(duì)效益系數(shù) （最小化問題時(shí) ）其對(duì)偶問題為：假設(shè)系數(shù)矩陣A可用列向量P1、P2、Pn表示，則上述約束條

15、件可改寫成：上述最后一個(gè)式子就是判斷原問題基本可行解是否為最優(yōu)解的條件式。因此，原問題最優(yōu)解的判斷依據(jù)就是滿足對(duì)偶問題的約束條件。對(duì)偶單純形法是從對(duì)偶問題可行的系數(shù)陣（也即 ）開始，變換到另一個(gè)對(duì)偶問題可行的系數(shù)陣，直到系數(shù)陣變?yōu)樵瓎栴}可行的（即B0 ）為止。對(duì)偶單純形法也采用單純形表進(jìn)行行變換計(jì)算，表中相對(duì)收益系數(shù) 需保持為非正值（Max）或非負(fù)值（Min），而右端常數(shù)bi可以不是非負(fù)值，變換計(jì)算是使右端常數(shù)bi都變?yōu)榉秦?fù)值。當(dāng)實(shí)現(xiàn)時(shí)，其解對(duì)原、對(duì)偶問題都是可行的，故是最優(yōu)解。計(jì)算步驟：為使bi變?yōu)榉秦?fù)值，通過選擇非基本變量置換基本變量來實(shí)現(xiàn)，首先選擇b為負(fù)最大的基本變量xi退出基本變量集合

16、，而后在系數(shù)aij為為負(fù)值的非基本變量中選取比值cj/aij為最大的（aijZ2=39，需要進(jìn)一步考察LP3可行域內(nèi)是否還有更優(yōu)的整數(shù)解。如果Z3Z2，就不需要再去搜尋最優(yōu)解了，因?yàn)樵黾蛹s束條件不會(huì)獲得更優(yōu)的解；（5）重復(fù)第二步，對(duì)非整數(shù)變量x，按其兩側(cè)鄰近整數(shù)值繼續(xù)分解LP3的可行域，形成兩個(gè)新的線性規(guī)劃問題LP4和LP5。LP4問題： LP5問題：（6）重復(fù)第三步，選擇LP4繼續(xù)求解。在LP3問題的最后一個(gè)單純形表的基礎(chǔ)上加一行約束條件，通過行變換得：x1=0，x2=5，Z4=40。此為整數(shù)解，目標(biāo)函數(shù)值Z4大于LP2的下限值Z2 =39。（7）重復(fù)第四步，選擇LP5繼續(xù)求解。但由于新增約

17、束條件x1 2會(huì)違背第一個(gè)約束條件（因?yàn)榇藭r(shí)x24），故LP5不存在可行解。 最終本整數(shù)規(guī)劃問題的最優(yōu)解為LP4的最優(yōu)解，即x1=0，x2=5，Z*=Z4*=40。上述解題過程可用下圖來表示：LP1LP2LP3LP4LP5非整數(shù)解x1=2.25，x2=3.75，Z1=41.25；為分枝定界上限值。整數(shù)解x1=3，x2=3，Z2=39；為分枝定界下限值。整數(shù)解x1=0，x2=5，Z4=40；為最優(yōu)整數(shù)解非整數(shù)解x1=1.8, x2=4, Z3=41；無可行解 上述樹狀圖中每一個(gè)節(jié)點(diǎn)代表一個(gè)線性規(guī)劃問題，當(dāng)其解（1）為整數(shù)解時(shí)；（2）或?yàn)椴豢尚薪鈺r(shí)；（3）或其解的目標(biāo)函數(shù)值Z下限值（Max）或上限

18、值（Min）時(shí)，均為終節(jié)點(diǎn)，不再繼續(xù)向下分枝。否則，選擇一個(gè)非整數(shù)變量，分岔出兩個(gè)各增加一個(gè)約束條件的節(jié)點(diǎn)（新的線性規(guī)劃問題），繼續(xù)分別求解，直至所有節(jié)點(diǎn)均為終節(jié)點(diǎn)為止。以終節(jié)點(diǎn)中目標(biāo)函數(shù)值最大的可行整數(shù)解為本問題的最終解。 因此，其計(jì)算效率取決于如何盡快使各節(jié)點(diǎn)變成終節(jié)點(diǎn)，故與進(jìn)行分枝的非整數(shù)變量選擇次序有關(guān)，一些規(guī)則：（1）選擇分?jǐn)?shù)值最大的非整數(shù)變量進(jìn)行分枝；（2）按決策變量在目標(biāo)函數(shù)中的權(quán)重（系數(shù)）最大（Max）或 最?。∕in）進(jìn)行選擇；（3）選擇目標(biāo)函數(shù)值最大（Max）或最?。∕in）的非整數(shù)解先 進(jìn)行分枝；（4）對(duì)新近解出的非整數(shù)解先進(jìn)行分枝。第三章 非線性規(guī)劃Non Linear

19、 Programming3.1 概述3.1.1 NLP模型：現(xiàn)實(shí)中有很多的問題其目標(biāo)函數(shù)或約束條件是非線性的，這類問題稱之為非線性規(guī)劃問題，需要借助非線性規(guī)劃方法求解。例如：轉(zhuǎn)換為因?yàn)樯鲜鍪嵌兞繂栴}，可用圖解法求解，詳見P34圖3-1。20134652461-2可行域g1約束條件g2約束條件g4約束條件x1g3約束條件目標(biāo)函數(shù)等值線約束最優(yōu)點(diǎn)Z*=3.8，x1*=0.58，x2*=1.34非線性規(guī)劃問題的一般形式：對(duì)于無約束的非線性規(guī)劃問題，可采用求導(dǎo)數(shù)的方法獲得最優(yōu)解。對(duì)于有約束的非線性規(guī)劃問題，目前仍然沒有普遍適用的方法求解，但是有三類方法可以求解一部分有約束的非線性規(guī)劃問題：（1）反

20、復(fù)線性逼近，將LP方法擴(kuò)展到NLP中；（2）采用懲罰函數(shù)將有約束的非線性規(guī)劃問題轉(zhuǎn)變成無約束 的非線性規(guī)劃問題；（3）將不等式約束問題等效轉(zhuǎn)換為等式約束問題；將n維無 約束問題轉(zhuǎn)化為一維無約束問題。3.1.2 一維函數(shù)的極值問題 回顧微積分學(xué)，一維連續(xù)函數(shù)的局部極值概念詳見P35圖3-2。全局極值概念：如果在某點(diǎn)x*上，f(x*)在整個(gè)定義域上是極值（極大或極?。?，則稱f(x*)是f(x)的全局極值。 微積分學(xué)中的極值定理：一維連續(xù)函數(shù)f(x)極值點(diǎn)的必要條件是它的一階導(dǎo)數(shù)f(x)=0。但這一條件并不是充分條件，也即一階導(dǎo)數(shù)為0的點(diǎn)不一定準(zhǔn)是極值點(diǎn)。 f(x)=0的點(diǎn)稱之為駐點(diǎn)。 判斷駐點(diǎn)是否

21、為極值點(diǎn)的充分條件：需要由二階或更高階導(dǎo)數(shù)來判斷。假設(shè)一維連續(xù)函數(shù)f(x)存在一階和二階導(dǎo)數(shù)，并且在x0上， f(x0)=0， f(x0)0，則 當(dāng)f(x0)0時(shí)， f(x)在x0處有極大值； 當(dāng)f(x0)0時(shí)，f(x)在x0處有極小值；如果在駐點(diǎn)x0上，f(x0)=0，而x0又不是拐點(diǎn)，判斷x0是否為極值點(diǎn)只有借助更高一階的導(dǎo)數(shù)來進(jìn)行。3.1.3 多維函數(shù)的極值問題 由于太復(fù)雜，討論多維函數(shù)極值問題時(shí)一般都采用展開式的二階逼近。假設(shè)目標(biāo)函數(shù)f(X)是定義于n維歐氏空間的區(qū)域R中的多元函數(shù)f(x1, x2, , xn)，且在R中的點(diǎn) 處有連續(xù)的n+1階偏導(dǎo)數(shù)存在，則對(duì)該函數(shù)在 附近的泰勒展開式

22、取到二階導(dǎo)數(shù)時(shí)，有：上式可寫成向量矩陣形式：或者簡寫成：上式中：一階偏導(dǎo)數(shù) 稱之為目標(biāo)函數(shù)f(X)在 處的梯度向量，簡稱梯度；二階偏導(dǎo)數(shù) 稱之為目標(biāo)函數(shù)f(X)在 處的海森矩陣（Hessian Matrix)，記作 。類似一維函數(shù)極值問題，多維函數(shù)極值定理為：（1）n維目標(biāo)函數(shù)f(X)在R內(nèi)存在極值點(diǎn)X*的必要條件是：即梯度向量是一個(gè)n維的零向量。滿足上式的X*只說明是多維函數(shù)f(X)的一個(gè)駐點(diǎn)，是否是極值點(diǎn)，還要做進(jìn)一步的判斷。（2）如果n維目標(biāo)函數(shù)f(X) 在駐點(diǎn)X*附近的泰勒級(jí)數(shù)展開到二階近似，即：亦即：若在X*附近的鄰域內(nèi)，對(duì)于一切X，有：則稱海森陣H(X*)在點(diǎn)X*處是正定（Posi

23、tive Definite）的，則點(diǎn)X*為極小值點(diǎn)；c. 若H(X*) =0，即H(X*)為不定時(shí)，f(X)在X*處無極值。b. 類似地，若則稱海森陣H(X*)在點(diǎn)X*處是負(fù)定（Negative Definite）的，則點(diǎn)X*為極大值點(diǎn)；舉例說明，P37例3.2，求解下列目標(biāo)函數(shù)的極值點(diǎn)和極值解：由必要條件得：聯(lián)立上述方程可得：X*=1，1 。由充分條件得：故海森陣H(X*)為正定，X*=1，1 為極小值點(diǎn)，函數(shù)極值為4。3.1.4 目標(biāo)函數(shù)的凸性討論 前面討論了多元目標(biāo)函數(shù)的極值問題，但都是局部極值。在非線性規(guī)劃中希望求解出全局極值（最優(yōu)解）。一般而言，在可行域內(nèi)最優(yōu)解點(diǎn)必為極值點(diǎn)，但反過來

24、卻未必成立。在什么條件下二者相同呢？找到這個(gè)條件就可以通過極值點(diǎn)求解最優(yōu)解。定理：當(dāng)多元目標(biāo)函數(shù)f(X)在可行域內(nèi)為一凸函數(shù)時(shí)，函數(shù)的極值就是最優(yōu)解值。定義：設(shè)函數(shù)f(X)為定義在n維歐氏空間（E）中某個(gè)凸集S上的函數(shù)，若對(duì)于任一0a0，則af(X)也是凸集 S內(nèi)的一個(gè)凸函數(shù)；（2）設(shè)f1(X) 、f2(X)均是凸集S內(nèi)的凸函數(shù)，且a、b0，則af1(X) +bf2(X)也是凸集S內(nèi)的一個(gè)凸函數(shù)，即凸函數(shù)的線性組合也 是凸函數(shù)；（3）若X1、X2為凸函數(shù)f(X)中的兩個(gè)極值點(diǎn)，則其連線上的任何 點(diǎn)都是f(X)的極值點(diǎn)。 凸函數(shù)的極值點(diǎn)=最優(yōu)值點(diǎn)，因此，凸函數(shù)的最優(yōu)解只要考察它的一階條件即可。3

25、.1.5 NLP的一般解題方法 如果目標(biāo)函數(shù)是凸函數(shù)，可行域是凸集，則只要求解目標(biāo)函數(shù)的一階導(dǎo)數(shù)就可以求出最優(yōu)解。但是對(duì)于一般的NLP問題，存在以下幾個(gè)難點(diǎn)：（1）目標(biāo)函數(shù)的一階偏導(dǎo)數(shù)很難求出或者根本就無法求出， 無法判斷目標(biāo)函數(shù)的凸性；（2）有些目標(biāo)函數(shù)根本不滿足凸性的要求；（3）為了求解極值點(diǎn)，需要求解梯度函數(shù)等于0的微分方程 組， 這些方程組有時(shí)是非線性的，非常難以求解。 因此，有時(shí)求解NLP問題時(shí)需采用數(shù)值解法，稱之為直接法。而直接法和解析法統(tǒng)稱為尋優(yōu)法（或搜索法）。對(duì)于前者稱之為直接搜索法；對(duì)于后者稱之為解析搜索法。 直接搜索法有：坐標(biāo)輪換法、步長加速法、順序單純形法、以及隨機(jī)方向搜

26、索法等；解析搜索法有：最速下降法、共軛梯度法、DEP法（變尺度法）、以及懲罰函數(shù)法等。后面章節(jié)中將分別介紹這兩類方法中的代表。但是，搜索法的基本步驟大體相同，都采用迭代的計(jì)算步驟，如下所示：（1）選擇初始近似點(diǎn)X0（越靠近局部最優(yōu)解越好）；（2）如果已經(jīng)求解出第k次近似解Xk，但Xk還不是所要求精度的局部最優(yōu)解的近似值，要求進(jìn)一步尋優(yōu)，可以選擇一個(gè)尋優(yōu)方向Pk，稱Pk為在Xk點(diǎn)處的搜索方向，使得沿Pk方向目標(biāo)函數(shù)值f(X)下降（Min）或上升（Max）的速度最快；（3）在Pk確定以后，由Xk點(diǎn)出發(fā)，以Pk為方向，作向量Xk+ Pk，其中，0，稱為步長因子，即在方向Pk上定出搜索的步長=k，使得

27、Xk+1 =Xk+kPk，滿足f(Xk+1) f(Xk) （Min）或 f(Xk+1) f(Xk)（Max）；（4）檢驗(yàn)所得的新點(diǎn)Xk+1是否滿足精度要求： f(Xk+1)= f(Xk+1)f(Xk)如果滿足，則Xk+1為局部近似最優(yōu)解；否則，再以Xk+1點(diǎn)為初始近似點(diǎn)，轉(zhuǎn)入第二輪搜索。注意：搜索方向Pk和搜索步長k構(gòu)成了每次迭代計(jì)算的修正量，它們往往是決定算法好壞的重要因素。 從理論上講，Pk盡可能的指向問題的最優(yōu)解或使得f(X) 值的尋優(yōu)最快的方向。在確定搜索方向Pk后，從Xk出發(fā)，取k，使得f(X)沿Pk方向取最優(yōu)值，即 這種計(jì)算的好處：1）將一個(gè)多維的無約束極值問題轉(zhuǎn)化為沿Pk（k0）

28、方向的一維搜索問題；2）保證了大量搜索問題的收斂性。由此看來，一維搜索問題是解決NLP問題的最基本和最重要的問題。3.2 一維搜索問題求解方法 欲求解一元函數(shù)f(x)的極小值（Minf(x)，從已經(jīng)得到的迭代點(diǎn)xk出發(fā)，沿搜索方向Pk前進(jìn)所得到的新點(diǎn)xk+1=xk +kPk，總是位于通過xk點(diǎn)的Pk方向上，見下圖。由于此時(shí)x和P已確定（為已知數(shù)），故函數(shù)f(x)變成以步長因子為變量的一元函數(shù)，此問題就變成了取何值時(shí)，使得f(xk+1)=f(xk +kPk)為極小值的求單變量函數(shù)極值問題。目標(biāo)函數(shù)等值線目標(biāo)函數(shù)極值，極值點(diǎn)X*X1X2PkP*Xk+Pk 點(diǎn)稱將求解最佳步長k，使得：的過程為一維搜

29、索，常用的一維搜索法有黃金分割法、二次插值法、Fibonacci法等。3.2.1 一維搜索區(qū)間的確定 從X1點(diǎn)出發(fā)，跨出步長h，得X2=X1+h，分別算出這兩點(diǎn)的目標(biāo)函數(shù)值f1=f(X1)，f2=f(X2)，然后比較其大小，再確定搜索方向。（1）若f1f2，則將步長加倍，向右搜索，分別得X3=X2+2h，X4 =X3+4h，Xk=Xk-1+2 h，并計(jì)算出與其相應(yīng)的目標(biāo)函數(shù)值f(Xk)，直至目標(biāo)函數(shù)值增加為止，如下圖所示：X1X2X3X4X5Xf(X)h2h4h8h（2）若f1f2，所以向右搜索，得：X3=X2+2h=3， f(X3)=15； X4=X3+4h=7， f(X4)=15； X5=

30、X4+8h=15， f(X5)=111f(X4)；故X3=3X*15=X5，作X6=(X4+X5)/2=11，f(X6)=47，取d=2 h=4h=4， Minf(X3)、f(X4)、 f(X5)、 f(X6) = f(X3)、或f(X4) ；若Xc=X3 =3，則Xa=3-4=-1，Xb=3+4=7，故極小點(diǎn)所在區(qū)間為-1，7；若Xc=X4 =7，則Xa=7-4=3，Xb=7+4=11，故極小點(diǎn)所在區(qū)間為3，11。比較兩種結(jié)果，可得極小點(diǎn)所在區(qū)域?yàn)?，7。同理，令X1=8，h=1，也可得到相同結(jié)果，詳見P41。3.2.2 Fibonacci搜索法 假設(shè)單變量目標(biāo)函數(shù)y=f(X)是定義在區(qū)間a

31、，b上的向下單凸的函數(shù)，即存在唯一的最優(yōu)點(diǎn)X*，若在此區(qū)間任意選取a1、b1（a10的情況下，作如下幾次等價(jià)變換和計(jì)算：（1）令y=xa，當(dāng)x=a，b時(shí)，y=0，ba。此時(shí)，原問題變成FP1：（2）再令則原問題轉(zhuǎn)化為標(biāo)準(zhǔn)的0，1搜索區(qū)間的問題FP2：（3）搜索次數(shù)（迭代次數(shù)）的計(jì)算。由于0，而從此式中可以計(jì)算出搜索次數(shù)n。（4）初始點(diǎn)的確定：（5）后續(xù)計(jì)算點(diǎn)：計(jì)算比較 ：a）若令 ，第二次試驗(yàn)點(diǎn)為：b）若 縮小后的區(qū)間為（6）結(jié)束計(jì)算判斷：若 成立，則結(jié)束迭代計(jì)算，令 為最優(yōu)解的近似值；否則繼續(xù)迭代計(jì)算，直至達(dá)到計(jì)算精度為止。舉例說明，P44-45例3.4。3.2.3 黃金分割法（Golden

32、 Section Partition） 是Fibonacci法的一種簡化方法，對(duì)于Fibonacci法，若迭代次數(shù)為n，則每次迭代后搜索區(qū)間長度縮小的比例為：即：可以證明，當(dāng)n時(shí)， ，證明詳見P45-46。如果以不變的搜索區(qū)間縮小率0.618代替Fibonacci法每次不同的搜索區(qū)間縮小率，就得到所謂的0.618法，或黃金分割法。假設(shè)第k次迭代后，保留區(qū)間為顯然：x+y=akbk，而且此時(shí)，然后計(jì)算這兩點(diǎn)上的函數(shù)值 按照前面的方法作判斷，選擇進(jìn)一步搜索區(qū)間，即： 是原區(qū)間長度的0.618倍，反復(fù)迭代直至達(dá)到精度為止。舉例P46-47例3.5。3.2.4 二次插值法（自學(xué)）3.3 多變量無約束極

33、值問題3.3.1 最速下降法（梯度法） 思路：尋求使目標(biāo)函數(shù)f(X)下降（Min）或上升（Max）最快的搜索方向Pk和最佳步長k。 假設(shè)無約束NLP問題目標(biāo)函數(shù)f(X)具有一階和二階偏導(dǎo)數(shù)，X*為其局部最優(yōu)解，且令X0為X*的初始近似解，Xk為X*的第k次迭代近似解。如果從Xk點(diǎn)出發(fā)，尋找第k+1次的近似逼近，則在Xk點(diǎn)選擇使目標(biāo)函數(shù)f(X)下降的方向Pk作為第k+1次搜索的方向Xk+1 =Xk+kPk， k0，計(jì)算f(Xk+kPk)，希望值f(X)下降最快。根據(jù)微積分學(xué)可知，函數(shù)f(X)在Xk點(diǎn)處數(shù)值下降最快的方向是該點(diǎn)處的負(fù)梯度方向，即Pk=f(Xk)；而上升最快的為： Pk=f(Xk)。

34、搜索方向確定之后，還需要確定搜索步長，最佳搜索步長為：也可用解析式直接計(jì)算：最速下降法基本步驟：（1）給定初始近似點(diǎn)X0En及其梯度模允許誤差： 令k=0；（2）計(jì)算Pk=f(Xk)；（3）判別式Pk= f(Xk)如果成立，則認(rèn)為Xk便是近 似極小值點(diǎn)，否則轉(zhuǎn)入下一步；（4）若f(Xk)，則利用一維搜索法求出最優(yōu)步長k， 即：（5）令Xk+1=Xk kf(Xk)，以其作為新的近似點(diǎn)，返回第二步。計(jì)算實(shí)例說明詳見P50-51例3.7。3.3.2 步長加速法簡介（Pattern Search） 基本步驟：（1）任選一初始近似點(diǎn)B1，以它為基點(diǎn)進(jìn)行搜索；（2）為每一個(gè)獨(dú)立變量xi（i=1，2，n）選

35、定步長：（2）（3）計(jì)算初始基點(diǎn)B1的目標(biāo)函數(shù)值f(B1)，對(duì)于點(diǎn)B1+1，若f(B1+1)f(B1)，即B1+1點(diǎn)沒有B1點(diǎn)好，則試驗(yàn)B11點(diǎn)，如果它比B1點(diǎn)好，則以它為臨時(shí)矢點(diǎn)T11，否則就以B1為臨時(shí)矢點(diǎn)，即：（3）對(duì)于下一個(gè)獨(dú)立變量x2進(jìn)行同樣的攝動(dòng)，此時(shí)用臨時(shí)矢點(diǎn)T12代替原來的基點(diǎn)B1，一般有： 當(dāng)n個(gè)變量都被攝動(dòng)之后，得臨時(shí)矢點(diǎn)T1n，并用原來的基點(diǎn)B1和新基點(diǎn)B2建立了第一個(gè)模矢；（4）將第一個(gè)模矢延長一倍，得第二個(gè)模矢的初始臨時(shí)矢點(diǎn)T20=B1+2(B2B1)=2B2B1；（5）在T20附近進(jìn)行與上述類似的搜索，建立臨時(shí)矢點(diǎn)T21，T22，T2n，以T2n為第三個(gè)基點(diǎn)B3，即

36、T2n=B3，確立了第三個(gè)模矢： T30=B2+2(B3B2)=2B3B2；.，（i）繼續(xù)上述過程，對(duì)于第i個(gè)模矢，如果f(Ti0)f(Bi)，則以Ti0為Bi+1，而且不將此模矢延長，繼續(xù)搜索；若f(Ti0)f(Bi) ，則應(yīng)退回到Bi，并在Bi附件繼續(xù)搜索。如果能得出新的下降點(diǎn)，建立新的模矢，否則將步長縮小，以進(jìn)行更加精確的搜索，直至搜索步長縮小到要求精度時(shí)，可以停止搜索。3.4 多變量有約束求解極值問題 有約束多變量極值問題一般形式： 有約束NLP問題解法的基本思路為：（1）將不等式約束轉(zhuǎn)化為等式約束；（2）將有約束的求解極值問題等效的轉(zhuǎn)化為無約束求解極值問 題。 以下介紹工程上常用的求

37、解有約束多元NLP的方法，即拉格朗日乘子法和懲罰函數(shù)法。3.4.1 等式約束條件下的拉格朗日乘子法 對(duì)于具有等式約束條件的多元NLP極值問題：構(gòu)造拉格朗日函數(shù)（Lagrange Function）：式中i為待定的拉格朗日系數(shù)或乘數(shù)?？梢宰C明上述約束極值問題等價(jià)于minL(X, )。此時(shí)問題變成具有n+m個(gè)變量，即x1，x2，xn，和1，2，m的無約束極值問題。對(duì)這n+m個(gè)變量求一階導(dǎo)數(shù)，可得極值點(diǎn)必要條件：上述后m個(gè)方程恰是原問題中的約束條件，如果求解上述n+m個(gè)方程得minL(X, )的解為：則有故有結(jié)論：若X*和*是minL(X, )的解，則X*必為原問題minf(X)的解。詳見P53例3

38、.8。3.4.2 不等式約束條件下的拉格朗日乘子法 對(duì)于不等式約束條件下的多元NLP問題，需要在約束條件中加入松弛變量，使之變成等式約束條件即可采用上述的拉格朗日乘子法求解。對(duì)于約束條件：引入松弛變量S使得：詳見P54例3.9。3.4.3 懲罰函數(shù)法（SUMT法） 類似于拉格朗日乘子法，SUMT法也是將有約束的多元NLP問題轉(zhuǎn)化為無約束的多元NLP問題。對(duì)于：其新的目標(biāo)函數(shù)為：式中(X, )為懲罰函數(shù)，為懲罰因子。只有當(dāng)滿足約束條件時(shí)，上式第二項(xiàng)（懲罰項(xiàng)）才不起作用，此時(shí)懲罰函數(shù)的極值點(diǎn)就是原函數(shù)的極值點(diǎn)。1、外點(diǎn)法 將懲罰函數(shù)(X, )定義于可行域之外的方法稱之為外點(diǎn)懲罰函數(shù)法。對(duì)于問題：其

39、懲罰函數(shù)的一般形式為：式中這就保證了在可行域內(nèi)(X, )的解與f(X)的解等價(jià)性，而在可行域之外將受到懲罰。將上述懲罰函數(shù)(X, )的近似解序列看成以懲罰因子k為參數(shù)的一條軌跡，當(dāng)取012k，且 時(shí)，點(diǎn)列X, k將從可行域外沿著這條軌跡向可行域的約束邊界運(yùn)動(dòng)，最后達(dá)到約束邊界上的最優(yōu)點(diǎn)X*。說明詳見P55-56例3.10。其優(yōu)點(diǎn)（1）對(duì)等式約束問題較簡單；（2）初始點(diǎn)容易選取。其缺點(diǎn)：只適用于最優(yōu)解在約束條件（可行域）邊界的問題。2、內(nèi)點(diǎn)法 對(duì)于問題：定義懲罰函數(shù)上式右邊第二項(xiàng)稱之為障礙項(xiàng)，顯然當(dāng)X向可行域邊界移動(dòng)時(shí)，即gj(X) 0時(shí)， (X, k) ， k稱為障礙因子。當(dāng)k逐步減少時(shí)，障礙

40、項(xiàng)所起的作用也就越來越小，所求解出的min(X, k) 的解(X, k)也就逼近原問題的極小值解X*。 說明詳見P56-57例3.11。 第四章 動(dòng)態(tài)規(guī)劃（Dynamic Programming）4.1 動(dòng)態(tài)規(guī)劃原理4.1.1 概述 不同于線性和非線性規(guī)劃問題不與時(shí)間發(fā)生關(guān)系（稱之為靜態(tài)規(guī)劃問題），而動(dòng)態(tài)規(guī)劃問題牽涉到時(shí)間或階段性因素，任何一個(gè)階段作決策不是孤立的，而是與整個(gè)問題所有階段都有關(guān)聯(lián)，不能只考慮本階段的決策，要考慮動(dòng)態(tài)規(guī)劃問題整條鏈上的所有問題，形成一條決策鏈。 各個(gè)階段的決策構(gòu)成一個(gè)決策序列，稱之為策略，對(duì)應(yīng)于某一策略，系統(tǒng)會(huì)達(dá)到某種特定的效果。這種系統(tǒng)效果一般采用定量的指標(biāo)體系

41、來衡量，解決動(dòng)態(tài)規(guī)劃問題的目的則是選擇一種策略，使得采用指標(biāo)衡量的系統(tǒng)效果最優(yōu)，稱這一策略為最優(yōu)策略。 R. Bellman1951年提出解決多階段決策問題的最優(yōu)化原理（The Principle of Optimality），稱之為動(dòng)態(tài)規(guī)劃法。 舉例說明，P58例4.1，最短路徑問題ABDGCEHKFILNJMPQ15271352224034422148352G2Q1求解沿箭頭方向從A到Q的最短路徑。這個(gè)問題的特點(diǎn)則是完成既定目標(biāo)需要一個(gè)過程，這個(gè)過程或與時(shí)間有關(guān)，或可以分成若干個(gè)階段。解例4.1：（1）直接枚舉法 將所有的可能路徑羅列出來，再比較大小，得出最短路徑。得出結(jié)果：最短路徑為A-

42、S-E-I-L-N-Q，最短路徑長度為13，詳見P59。由于每條路徑有6個(gè)路段，要做5次加法計(jì)算，總共有20條路徑，要做100次加法計(jì)算，還要做19次比較，才能最后計(jì)算出上述結(jié)果，很麻煩。（2）更快的算法動(dòng)態(tài)規(guī)劃法 令fi 表示從點(diǎn)i（i=A, B，P）到終點(diǎn)Q的最短距離，rij為路段（i，j）的長度，如路段A-B的長度為rAB。因此，fA 應(yīng)等于（rAB+fB）和（rAC+fC）中的較小者，即由于目前還不知道fB和fC的值，故fA的值暫時(shí)還無法得知，需要繼續(xù)計(jì)算fB和fC的值。采用同樣的方法對(duì)fB和fC進(jìn)行分析可見fB取決于fD和fE， fC取決于fE和fF。以此類推，直至終點(diǎn)前面的兩個(gè)節(jié)點(diǎn)

43、N和P，故這個(gè)問題可以從后面向前推算，即從節(jié)點(diǎn)出來只有一個(gè)路段的節(jié)點(diǎn)有G、K、N、J、M、P這六個(gè)，只需計(jì)算一次加法，對(duì)于其余九個(gè)節(jié)點(diǎn)需要計(jì)算2次加法和1次比較，故共24次加法計(jì)算和9次比較，遠(yuǎn)比枚舉法要快。 最短路徑追蹤法：從起點(diǎn)A開始，沿著取最小值的點(diǎn)逐個(gè)向后追蹤，直至終點(diǎn)為止。由fA的算式可知B點(diǎn)，由fB可知E點(diǎn)，, 直至終點(diǎn)，即可得到最短路徑的軌跡點(diǎn)序列。4.1.2 動(dòng)態(tài)規(guī)劃的基本概念（1）階段（Stage） 一個(gè)階段就是需要做出一個(gè)決策的子問題。階段是按照決策進(jìn)行的時(shí)間或空間上的先后順序劃分的。用以描述階段的變量叫做階段變量，用k來表示。階段數(shù)等于多階段決策過程從開始到結(jié)束需做出的決

44、策數(shù)目。例如例4.1，階段1有2條支路（AB、AC）；階段2有4條支路（BD、BE、CE、CF）；階段3有6條支路（DG、GH、EH、EI、FI、FJ）；，直至最末一個(gè)階段為止，總共有6個(gè)階段。（2）狀態(tài)（State） 狀態(tài)表示某階段的出發(fā)位置，它既是該階段某支路的起點(diǎn)，又是前一階段某一支路的終點(diǎn)。通常，一個(gè)階段包含若干個(gè)狀態(tài)，如例4.1，階段1有一個(gè)狀態(tài)A，階段2有二個(gè)狀態(tài)B和C，階段3有三個(gè)狀態(tài)D、E、F，。 描述狀態(tài)的變量稱之為狀態(tài)變量，可為標(biāo)量或向量。常用Xk表示第k階段的狀態(tài)集合，則第k階段狀態(tài)變量集合為：如例4.1中第三個(gè)階段有D、E、F三個(gè)狀態(tài)，用1、2、3編碼，可得：X3=1，

45、2，3，或X3=D，E，F(xiàn) 。（3）決策（Decision） 對(duì)于狀態(tài)的選擇就是決策。常用uk(xk)表示第k階段當(dāng)狀態(tài)為xk時(shí)的決策變量。決策變量的取值限制在一定范圍時(shí)，這一范圍稱之為決策變量集合，用Uk(xk)來表示。顯然uk(xk) Uk(xk)。（4）策略（Policy） 所有階段決策序列組成策略，記為p1, n，n為階段數(shù)，即 p1, n=u1(x1)， u2(x2)，un(xn)第k階段至最末階段的決策集合稱之為k子策略，即 p1, n=uk(xk)， uk+1(xk+1)，un(xn)可供選擇的策略范圍稱之為允許策略集合，從中系統(tǒng)效果最優(yōu)的策略稱之為最優(yōu)策略。（5）指標(biāo)函數(shù) 衡量

46、實(shí)行決策優(yōu)劣的數(shù)量指標(biāo)就是指標(biāo)函數(shù)（也稱效用函數(shù)），它定義于所有階段和所有過程，即 v1, n=v1, n(x1，u1，x2，u2 ，xn，un)k子策略指標(biāo)函數(shù)為 vk, n=vk,n(xk，uk，xk+1， uk+1 ，xn，un)指標(biāo)函數(shù)的物理意義可包括：距離、時(shí)間、費(fèi)用、成本、利潤、產(chǎn)量、資源消耗等。指標(biāo)函數(shù)的最優(yōu)值稱之為最優(yōu)指標(biāo)函數(shù)。例如，例4.1中的第k點(diǎn)最優(yōu)指標(biāo)函數(shù)為fk(xk)，k=A，B，表示從第k階段xk點(diǎn)到終點(diǎn)的最短距離。（6）狀態(tài)轉(zhuǎn)移方程 如果第k階段的狀態(tài)變量xk和決策變量uk確定后，第k+1階段的狀態(tài)變量xk+1和決策變量uk+1也隨之確定，這種連鎖確定是通過狀態(tài)轉(zhuǎn)

47、移方程完成的，記為xk+1=gk(xk, uk)，稱之為xk+1xk的狀態(tài)轉(zhuǎn)移方程。4.1.3 最優(yōu)化原理、動(dòng)態(tài)規(guī)劃基本方程 動(dòng)態(tài)規(guī)劃整個(gè)過程是多階段的，每一階段都要求做出決策，并且（1）下一階段是在上一階段決策的基礎(chǔ)上做出決策，即本階段的決策對(duì)下一階段的決策有影響；（2）本階段的決策一定要對(duì)整個(gè)動(dòng)態(tài)規(guī)劃全過程產(chǎn)生最優(yōu)效果，但不一定是本階段的最優(yōu)決策。 從例4.1可以看出：如果從AQ的最短路徑軌跡為（xA， xB，xk，xQ），那么該軌跡線中的從任意第k點(diǎn)截?cái)嗟暮竺娌糠忠彩菑膋點(diǎn)到終點(diǎn)Q的最短路徑，即（xk，xk+1，xQ） 這就是最優(yōu)化原理的具體描述。P63對(duì)最優(yōu)化原理有定義，但太深?yuàn)W，語言

48、太拗口。根據(jù)最優(yōu)化原理，可通過逐段逆推先求解后面階段最優(yōu)決策的方法來求解全過程的最優(yōu)決策。以最后階段作為邊界條件，從倒數(shù)第一階段開始，逐步利用第k+1階段以后的最優(yōu)子策略fk+1(xk+1)，求出第k階段以后的最優(yōu)策略fk(xk)，最終求得f1(x1)。（2）動(dòng)態(tài)規(guī)劃（DP）模型 DP建模程序：1）階段序數(shù)k=1，2，n；階段數(shù)=年；2）第k階段的狀態(tài)變量為xk，狀態(tài)變量集合為Xk；3）第k階段的決策變量為uk，允許決策變量集合為Uk；4）狀態(tài)轉(zhuǎn)移方程為：xk+1 =gk(xk, uk)；5）確定各階段的收益dk(xk, uk)；6）建立DP的指標(biāo)函數(shù)方程，求解最優(yōu)指標(biāo)函數(shù)這里逆推算過程是從最

49、末階段k=n開始，逐階段逆推，直至推算出u1和f1(x1)為止，從而獲得全過程的最優(yōu)策略和指標(biāo)函數(shù)最優(yōu)值。4.2 動(dòng)態(tài)規(guī)劃應(yīng)用之一資源分配問題 所謂資源分配問題就是將一種或若干種供應(yīng)量有限的資源（如原材料、設(shè)備、資金、人力、能源等）分配給若干個(gè)使用者，分配方案使得目標(biāo)函數(shù)達(dá)到最優(yōu)。若只分配一種資源，其總量為a，用于投入n個(gè)項(xiàng)目，則稱之為一維資源分配問題； 若資源多于一種，則稱之為多維資源分配問題。本課程只介紹一維資源分配問題。令xj為分配于項(xiàng)目j的資源量，其收益函數(shù)為gj(xj)，應(yīng)該如何分配這種資源，使得這n個(gè)項(xiàng)目的收益總和最大？這個(gè)問題可寫成靜態(tài)數(shù)學(xué)規(guī)劃模型：上述模型可能是線性或非線性數(shù)學(xué)

50、規(guī)劃問題，但由于它的特殊性，也可以采用DP的方法來求解。應(yīng)用動(dòng)態(tài)規(guī)劃方法求解一維資源分配問題的步驟：（1）將上述問題的項(xiàng)目數(shù)（即變量個(gè)數(shù)n）作為DP問題的階 段數(shù)；（2）將上述問題中的變量（即每個(gè)項(xiàng)目分配到的資源量xk） 作為DP問題的決策變量uk ，等價(jià)于上述問題中的xk；（3）將每個(gè)階段k可用的資源量作為狀態(tài)變量xk 。經(jīng)上述三個(gè)步驟的轉(zhuǎn)換后，上述數(shù)學(xué)規(guī)劃問題就變成了DP問題，可采用DP方法求解。詳見下圖。 1 2 k n資源量 ax1x2xkxnu1u2ukun顯然，根據(jù)上述轉(zhuǎn)換，有關(guān)系式x1=a, x2=x1u1, x3=x2u2, , xk=xk-1uk-1, , xn=xn-1un

51、-1=x1(=a)(u1+u2+un-1)=un。其狀態(tài)轉(zhuǎn)移方程為： xk+1=xkuk，1kn1；建立允許決策變量集合：Uk(xk)=uk0ukxk；建立最優(yōu)指標(biāo)函數(shù)逆向推算方程：令fk(xk)為以xk數(shù)量的可用資源分配給第k個(gè)項(xiàng)目至第n個(gè)項(xiàng)目所得到的最大總收益。根據(jù)最優(yōu)化原理，有：式中：gk(uk)為向第k個(gè)項(xiàng)目投入u數(shù)量的資源所產(chǎn)生的收益，等價(jià)于數(shù)學(xué)規(guī)劃問題中的 gj(xj)。邊界條件：fn+1(xn+1)=0， fn(xn)= fn(un)= gn(un)。需要指出的是：當(dāng)xk在0，a上連續(xù)變化時(shí)，計(jì)算機(jī)也無法對(duì)所有的xk求解出fk(xk)。因此，首先需要將可供分配的資源數(shù)離散化，按照

52、分割后的最小單位進(jìn)行分配，即將0，a分割成m個(gè)等分，令xk=0, , 2, , m(=a)。的大小可根據(jù)計(jì)算精度和計(jì)算機(jī)容量來確定。說明詳見P65-68例4.4（此題也可用整數(shù)規(guī)劃求解）。4.3 動(dòng)態(tài)規(guī)劃應(yīng)用之二生產(chǎn)庫存問題采用P69的例4.5來說明：某工廠生產(chǎn)某種產(chǎn)品有三個(gè)周期，開始時(shí)的庫存量為0個(gè)單位（每個(gè)周期庫存量不受限制），在每個(gè)周期初生產(chǎn)j個(gè)單位產(chǎn)品的成本為：每個(gè)周期內(nèi)最后的庫存量為j個(gè)單位，存貯費(fèi)EIC(J)為3j個(gè)單位，對(duì)應(yīng)于各周期的產(chǎn)品需求量見下表。在滿足每個(gè)周期產(chǎn)品需求量的前提下，如何確定每周期初的生產(chǎn)量，才能使得總費(fèi)用（包括生產(chǎn)成本和存儲(chǔ)費(fèi)）最?。恐?期 k1 2 3需求量

53、Dk2 2 4解：采用DP方法求解生產(chǎn)庫存問題，其步驟為：（1）每一生產(chǎn)周期為一個(gè)決策階段，K=1，2，3；每個(gè)周期初的生產(chǎn)量可根據(jù)本周期的需求量與上周期末的庫存量來決定；（2）當(dāng)K=3，D3=4時(shí)，令上一周期末的庫存量為m，又因?yàn)橐笞詈笠粋€(gè)周期（K=3）的庫存量為0，所以，最后一個(gè)周期（K=3）的最佳生產(chǎn)量為：上述計(jì)算結(jié)果詳見下表。第2周期末庫存量 m201234本周期初的最優(yōu)生產(chǎn)量x3(m2)43210本周期末的最優(yōu)生產(chǎn)費(fèi)f3(x3)403530250第三周期生產(chǎn)量與生產(chǎn)費(fèi)用計(jì)算表（3）當(dāng)K=2，D=2時(shí)，要決定第二周期初的生產(chǎn)量x2(m)，使得第三周期初和第二周期初的生產(chǎn)費(fèi)用之和以及與

54、庫存費(fèi)之和最小。若上周期末的庫存量為m，則第二周期初最多生產(chǎn)量是：D2+D3-m。如果第二周期初的生產(chǎn)量為z，則最優(yōu)生產(chǎn)與庫存決策的總費(fèi)用為：由于EIC2(m+z-D2)=3(m+z-D2)，且D2=2，故：當(dāng)m=0時(shí)，2-0=2z2+4-0=6，則有：得x2(0)=6，f2(x2(0)=62。當(dāng)m=1時(shí)，2-1=1z2+4-1=5，則有：得x2(1)=5，f2(x2(1)=57。當(dāng)m=2時(shí)，2-2=0z2+4-2=4，則有：得x2(2)=0，f2(x2(2)=40。當(dāng)m=3時(shí)，0z2+4-3=3，則有：得x2(3)=0，f2(x2(3)=38。當(dāng)m=4時(shí)，0z2+4-4=2，則有：得x2(4)=0，f2(x2(4)=36。當(dāng)m=5時(shí)，0z2+4-5=1，則有：得x2(5)=0，f2(x2(5)=34。當(dāng)m=6時(shí)，0z2+4-6=0，z=0，則有： f2(x2(6)=PC2(0)(=0)+EIC2(3)(=12)+f3(0)(=0)=12得x2(6)=0，f2(x2(6)=12。第1周期末庫存量 m10123456本周期初的最優(yōu)生產(chǎn)量x2(m1)6500000本周期末的最優(yōu)生產(chǎn)費(fèi)f2(x