張燦最優(yōu)化理論

1、大作業(yè)封面模板理學(xué)院最優(yōu)化理論課程設(shè)計(jì)學(xué) 號(hào)：xxxxx專 業(yè)：應(yīng)用數(shù)學(xué)學(xué)生姓名：xxxx任課教師：xxxx教授 2015年10月摘 要針對(duì)本學(xué)期對(duì)于最優(yōu)化理論的學(xué)習(xí)，我們學(xué)到了很多東西，本文主要對(duì)于動(dòng)態(tài)規(guī)劃這一思想的核心內(nèi)容和其基本特點(diǎn)，探討了動(dòng)態(tài)規(guī)劃思想的適用范圍，通過(guò)數(shù)學(xué)建模的思維，構(gòu)建Matlab程序語(yǔ)言，解決實(shí)際問(wèn)題。本文總結(jié)指出，動(dòng)態(tài)規(guī)劃這一思想，關(guān)鍵還在于對(duì)不同的問(wèn)題建立有效的數(shù)學(xué)模型，在把握本質(zhì)的基礎(chǔ)上靈活運(yùn)用。本文對(duì)Matlab軟件作了簡(jiǎn)要的介紹, 并使用其優(yōu)化工具函數(shù)mixfy編寫(xiě)程序, 計(jì)算最優(yōu)決策序列和總利潤(rùn)的最大值,實(shí)現(xiàn)資源的優(yōu)化配置, 具有良好的通用性、有效性和簡(jiǎn)便

2、性, 并能夠簡(jiǎn)便快速分析與計(jì)算出資源優(yōu)化配置的結(jié)果, 為作出正確的決策提供了切實(shí)有效的方法。最優(yōu)化理論的靈活運(yùn)用，解決多階段決策過(guò)程最優(yōu)化問(wèn)題，將復(fù)雜問(wèn)題全局化，簡(jiǎn)潔的把結(jié)果呈現(xiàn)出來(lái)，方便及快捷。關(guān)鍵字 最優(yōu)化理論 動(dòng)態(tài)規(guī)劃 數(shù)學(xué)建模 Matlab軟件 一 課題背景及研究意義1 最優(yōu)化理論綜述最優(yōu)化理論是一個(gè)重要的數(shù)學(xué)分支，它所研究的問(wèn)題是討論在眾多的方案中什么樣的方案最優(yōu)，以及怎樣找到最優(yōu)方案。概括的說(shuō)，凡是追求最優(yōu)目標(biāo)的數(shù)學(xué)問(wèn)題都屬于最優(yōu)化問(wèn)題，作為最優(yōu)化問(wèn)題，一般都有三個(gè)要素：第一是目標(biāo)；第二是反感；第三是限制條件，而且目標(biāo)應(yīng)是方案的“函數(shù)”。如果方案與時(shí)間無(wú)關(guān)，則該問(wèn)題屬于靜態(tài)最優(yōu)化問(wèn)

3、題，否則稱為動(dòng)態(tài)最優(yōu)化問(wèn)題1。關(guān)于最優(yōu)化的問(wèn)題在生活中普遍存在，例如，工程設(shè)計(jì)中怎樣選擇設(shè)計(jì)參數(shù)，使得設(shè)計(jì)方案滿足設(shè)計(jì)要求，又能降低成本；資源分配中，怎樣分配有限資源，使得分配方案既能滿足各方面的基本要求，又能獲得好的經(jīng)濟(jì)效益；生產(chǎn)評(píng)價(jià)安排中，選擇怎樣的計(jì)劃方案才能提高產(chǎn)值和利潤(rùn)；原料配比問(wèn)題中，怎樣確定各種成分的比例，才能提高質(zhì)量，降低成本；城建規(guī)劃中，怎樣安排工廠、機(jī)關(guān)、學(xué)校、商店、醫(yī)院、住戶和其他單位的合理布局，才能方便群眾，有利于城市各行各業(yè)的發(fā)展；農(nóng)田規(guī)劃中，怎樣安排各種農(nóng)作物的合理布局，才能保持高產(chǎn)穩(wěn)產(chǎn)，發(fā)揮地區(qū)優(yōu)勢(shì)；軍事指揮中，怎樣確定最佳作戰(zhàn)方案，才能有效地消滅敵人，保存自己，

4、有利于戰(zhàn)爭(zhēng)的全局，在人類活動(dòng)的各個(gè)領(lǐng)域中，諸如此類，不勝枚舉。最優(yōu)化這一數(shù)學(xué)分支，正是為這些問(wèn)題的解決，提供理論基礎(chǔ)和求解方法，它是一門(mén)應(yīng)用廣泛、實(shí)用性強(qiáng)的學(xué)科。通過(guò)本學(xué)期對(duì)于最優(yōu)化理論的學(xué)習(xí)，我們學(xué)到了很多東西，主要針對(duì)以下的五個(gè)方面：（1） 基本的線性規(guī)劃問(wèn)題，它是最優(yōu)化問(wèn)題的一種特殊情形，實(shí)質(zhì)是從多個(gè)變量中選取一組適當(dāng)?shù)淖兞孔鳛榻猓惯@組變量滿足一組確定的線性式，而且使一個(gè)線性目標(biāo)函數(shù)達(dá)到最優(yōu)（最大或最?。?，熟練的將原問(wèn)題化為標(biāo)準(zhǔn)形式，或引入人工變量進(jìn)行轉(zhuǎn)化，利用單純形法使可行域中的某個(gè)基可行解轉(zhuǎn)換為另一個(gè)基可行解，直到目標(biāo)函數(shù)達(dá)到最優(yōu)，基可行解即為最優(yōu)解；或研究對(duì)偶問(wèn)題的實(shí)際經(jīng)濟(jì)意義，

5、例如資源分配下的工廠利益最大的問(wèn)題的討論，將原線性規(guī)劃問(wèn)題轉(zhuǎn)換為對(duì)偶問(wèn)題，從一個(gè)角度分析使問(wèn)題更易求解。（2） 一維搜索法：通過(guò)構(gòu)造一個(gè)搜索方向和確定一個(gè)步長(zhǎng)，使下一個(gè)迭代點(diǎn)所處的目標(biāo)函數(shù)值下降的方法，分別采用了對(duì)分法，Newton切線法，黃金分割法，拋物線插值法等進(jìn)行求最優(yōu)解。（3） 常用無(wú)約束最優(yōu)化方法：可直接用來(lái)求解無(wú)約束優(yōu)化問(wèn)題，也可將很多約束優(yōu)化問(wèn)題轉(zhuǎn)化為無(wú)約束優(yōu)化問(wèn)題，用無(wú)約束的方法進(jìn)行求解，采用多種方法：最速下降法，以一個(gè)給定的初始點(diǎn)出發(fā)，通過(guò)迭代公式，按照特定的算法產(chǎn)生一串點(diǎn)列，則收斂的點(diǎn)列為其最優(yōu)解；Newton法，為了尋求迭代速度快，用一個(gè)二元函數(shù)來(lái)近似該點(diǎn)處的目標(biāo)函數(shù)，其

6、極小點(diǎn)的方向構(gòu)造搜索方向；修正Newton法，克服Newton法的缺點(diǎn)，保留Newton方向作為搜索方向，摒棄步長(zhǎng)恒取1，用一維搜索確定最優(yōu)步長(zhǎng)；共軛方向法，它是一種對(duì)初始點(diǎn)要求較為嚴(yán)格的收斂速度不宜過(guò)快的新算法，相比下最速下降法收斂速度降低，Newton法收斂速度快，但計(jì)算量大；共軛梯度法：通過(guò)由共軛方向的迭代點(diǎn)的負(fù)梯度與共軛向量的線性組合確定，構(gòu)成一種具體的共軛方向法等等的一系列方法。（4） 動(dòng)態(tài)規(guī)劃：同前面介紹過(guò)的各種優(yōu)化方法不同，它不是一種算法，而是考察問(wèn)題的一種途徑。動(dòng)態(tài)規(guī)劃是一種求解多階段決策問(wèn)題的系統(tǒng)技術(shù)，可以說(shuō)它橫跨整個(gè)規(guī)劃領(lǐng)域（線性規(guī)劃和非線性規(guī)劃）。當(dāng)然，由于動(dòng)態(tài)規(guī)劃不是一

7、種特定的算法，因而它不象線性規(guī)劃那樣有一個(gè)標(biāo)準(zhǔn)的數(shù)學(xué)表達(dá)式和明確定義的一組規(guī)則，動(dòng)態(tài)規(guī)劃必須對(duì)具體問(wèn)題進(jìn)行具體的分析處理。（5） 通過(guò)學(xué)習(xí)最優(yōu)化理論的課程，在最優(yōu)序列的應(yīng)用實(shí)例中，我熟練的運(yùn)用各種方法求最優(yōu)解，建立符合問(wèn)題的數(shù)學(xué)模型，學(xué)會(huì)使用Matlab軟件及其優(yōu)化工具函數(shù)mixfy編寫(xiě)程序解決實(shí)際問(wèn)題，計(jì)算最優(yōu)決策序列和總利潤(rùn)的最大值的方法和技巧，對(duì)運(yùn)用計(jì)算機(jī)軟件完成課程的波形繪制，微分方程的求解及數(shù)據(jù)處理，學(xué)習(xí)動(dòng)態(tài)規(guī)劃的基本方法，實(shí)現(xiàn)資源的優(yōu)化配置，其具有良好的通用性，有效性和簡(jiǎn)便性，并能夠簡(jiǎn)便快速分析與計(jì)算出資源優(yōu)化配置的結(jié)果，為實(shí)際解決提供切實(shí)有效的方法。關(guān)于最優(yōu)化理論的經(jīng)典算法和分類

8、情況眾多，本文主要研究動(dòng)態(tài)規(guī)劃問(wèn)題的解決方法,主要對(duì)于動(dòng)態(tài)規(guī)劃這一思想的核心內(nèi)容和其基本特點(diǎn)，探討了動(dòng)態(tài)規(guī)劃思想的適用范圍，通過(guò)數(shù)學(xué)建模的思維，構(gòu)建Matlab程序語(yǔ)言，解決實(shí)際問(wèn)題。本文總結(jié)指出，動(dòng)態(tài)規(guī)劃這一思想，關(guān)鍵還在于對(duì)不同的問(wèn)題建立有效的數(shù)學(xué)模型，在把握本質(zhì)的基礎(chǔ)上靈活運(yùn)用。2 動(dòng)態(tài)規(guī)劃理論綜述2.1 課題背景動(dòng)態(tài)規(guī)劃是一種重要的程序設(shè)計(jì)思想，具有廣泛的應(yīng)用價(jià)值。使用動(dòng)態(tài)規(guī)劃思想來(lái)設(shè)計(jì)算法，對(duì)于不少問(wèn)題往往具有高時(shí)效，因而，對(duì)于能夠使用動(dòng)態(tài)規(guī)劃思想來(lái)解決的問(wèn)題，使用動(dòng)態(tài)規(guī)劃是比較明智的選擇，它橫跨整個(gè)規(guī)劃領(lǐng)域（線性規(guī)劃和非線性規(guī)劃）。當(dāng)然，由于動(dòng)態(tài)規(guī)劃不是一種特定的算法，因而它不象線

9、性規(guī)劃那樣有一個(gè)標(biāo)準(zhǔn)的數(shù)學(xué)表達(dá)式和明確定義的一組規(guī)則，動(dòng)態(tài)規(guī)劃必須對(duì)具體問(wèn)題進(jìn)行具體的分析處理。在多階段決策問(wèn)題中，有些問(wèn)題對(duì)階段的劃分具有明顯的時(shí)序性，動(dòng)態(tài)規(guī)劃的“動(dòng)態(tài)”二字也由此而得名。動(dòng)態(tài)規(guī)劃的主要?jiǎng)?chuàng)始人是美國(guó)數(shù)學(xué)家貝爾曼（Bellman）。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ī)劃的理論源泉。1961年貝爾曼出版了他的第二部著作，并于1962年同杜瑞佛思（Dreyfus）合作出版了第三部著作

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

11、問(wèn)題、生產(chǎn)調(diào)度問(wèn)題、庫(kù)存管理問(wèn)題、排序問(wèn)題、設(shè)備更新問(wèn)題以及生產(chǎn)過(guò)程最優(yōu)控制問(wèn)題等，是經(jīng)濟(jì)管理中一種重要的決策技術(shù)。許多規(guī)劃問(wèn)題用動(dòng)態(tài)規(guī)劃的方法來(lái)處理，常比線性規(guī)劃或非線性規(guī)劃更有效。特別是對(duì)于離散的問(wèn)題，由于解析數(shù)學(xué)無(wú)法發(fā)揮作用，動(dòng)態(tài)規(guī)劃便成為了一種非常有用的工具。我們知道，能夠用動(dòng)態(tài)規(guī)劃解決的問(wèn)題，往往是最優(yōu)化問(wèn)題，且問(wèn)題的最優(yōu)解(或特定解)的局部往往是局部問(wèn)題在相應(yīng)條件下的最優(yōu)解，而且問(wèn)題的最優(yōu)解與其子問(wèn)題的最優(yōu)解要有一定的關(guān)聯(lián)，要能建立遞推關(guān)系。如果這種關(guān)系難以建立，即問(wèn)題的特定解不僅依賴于子問(wèn)題的特定解，而且與子問(wèn)題的一般解相關(guān)，那么，一方面難以記錄下那么多的“一般解”，另一方面，遞

12、推的效率也將是很低的；此外，為了體現(xiàn)動(dòng)態(tài)規(guī)劃的高時(shí)效，子問(wèn)題應(yīng)當(dāng)是互相重疊的，即很多不同的問(wèn)題共享相同的子問(wèn)題3。2.2 研究意義動(dòng)態(tài)規(guī)劃為我們解決與重疊子問(wèn)題相關(guān)的最優(yōu)化問(wèn)題提供了一個(gè)思考方向，通過(guò)迭代的方法考慮子問(wèn)題，將問(wèn)題規(guī)模減小而最終解決問(wèn)題。通過(guò)學(xué)習(xí)動(dòng)態(tài)規(guī)劃的基本方法，對(duì)多階段決策過(guò)程進(jìn)行數(shù)學(xué)描述，建立相應(yīng)的數(shù)學(xué)模型，利用Matlab軟件及其優(yōu)化工具函數(shù)mixfy編程計(jì)算最優(yōu)決策序列和總利潤(rùn)的最大值,學(xué)會(huì)求解各種優(yōu)化問(wèn)題和使用優(yōu)化工具箱，以數(shù)學(xué)模型解決最短路線，資源分配等實(shí)際問(wèn)題。故本文主要采用動(dòng)態(tài)規(guī)劃的方法進(jìn)行探究實(shí)際問(wèn)題。3 Matlab軟件 MATLAB 是目前在國(guó)際上被廣泛接

13、受和使用的科學(xué)與工程計(jì)算軟件，是美國(guó)MathWorks公司開(kāi)發(fā)的計(jì)算機(jī)軟件,一種在工程計(jì)算領(lǐng)域廣為流行的程序包。雖 然 Cleve Moler 教授開(kāi)發(fā)它的初衷是為了更簡(jiǎn)單、更快捷地解決矩陣運(yùn)算，但 MATLAB 現(xiàn) 在的發(fā)展已經(jīng)使其成為一種集數(shù)值運(yùn)算、符號(hào)運(yùn)算、數(shù)據(jù)可視化、圖形界面設(shè)計(jì)、程序設(shè) 計(jì)、仿真等多種功能于一體的集成軟件。Matlab的典型應(yīng)用：（1）Matlab軟件操作實(shí)驗(yàn)，主要介紹Matlab的基本語(yǔ)法和用法，以及它在線性代數(shù)，解析幾何，微積分，數(shù)理統(tǒng)計(jì)中的應(yīng)用和圖形處理功能；（2）數(shù)理實(shí)驗(yàn)，主要引導(dǎo)學(xué)生去探究一些基本的數(shù)學(xué)概念和數(shù)值計(jì)算方法，并對(duì)一些常見(jiàn)物理過(guò)程進(jìn)行計(jì)算，模擬；

14、（3）數(shù)學(xué)建模實(shí)驗(yàn)，應(yīng)用于實(shí)際，解決現(xiàn)實(shí)的問(wèn)題。二 動(dòng)態(tài)規(guī)劃基本理論知識(shí)1. 多階段決策過(guò)程的數(shù)學(xué)描述有這樣一類活動(dòng)過(guò)程，其整個(gè)過(guò)程可分為若干相互聯(lián)系的階段，每一階段都要作出相應(yīng)的決策，以使整個(gè)過(guò)程達(dá)到最佳的活動(dòng)效果。任何一個(gè)階段（stage，即決策點(diǎn)）都是由輸入（input）、決策（decision）、狀態(tài)轉(zhuǎn)移律（transformation function）和輸出（output）構(gòu)成的，如圖2-1（a）所示。其中輸入和輸出也稱為狀態(tài)（state），輸入稱為輸入狀態(tài)，輸出稱為輸出狀態(tài)。Sn+1SndnStage ngn = r(Sn,dn)（b）輸 出輸 入決 策階 段狀態(tài)轉(zhuǎn)移（a） 圖2

15、-1 輸出狀態(tài)與輸入狀態(tài)由于每一階段都有一個(gè)決策，所以每一階段都應(yīng)存在一個(gè)衡量決策效益大小的指標(biāo)函數(shù)，這一指標(biāo)函數(shù)稱為階段指標(biāo)函數(shù)，用表示。顯然是狀態(tài)變量和決策變量的函數(shù)，即，如圖2-1所示，顯然，輸出是輸入和決策的函數(shù)，即： （2-1） 式（1-1）即為狀態(tài)轉(zhuǎn)移律。在由N個(gè)階段構(gòu)成的過(guò)程里，前一個(gè)階段的輸出即為后一個(gè)階段的輸入。2. 動(dòng)態(tài)規(guī)劃的基本概念動(dòng)態(tài)規(guī)劃的數(shù)學(xué)描述離不開(kāi)它的一些基本概念與符號(hào)，因此有必要在介紹多階段決策過(guò)程的數(shù)學(xué)描述的基礎(chǔ)上，系統(tǒng)地介紹動(dòng)態(tài)規(guī)劃的一些基本概念。（1）階段（stage）階段是過(guò)程中需要做出決策的決策點(diǎn)。描述階段的變量稱為階段變量，常用k來(lái)表示。階段的劃分一

16、般是根據(jù)時(shí)間和空間的自然特征來(lái)進(jìn)行的，但要便于將問(wèn)題的過(guò)程轉(zhuǎn)化為多階段決策的過(guò)程。對(duì)于具有N個(gè)階段的決策過(guò)程，其階段變量k1，2，N。（2）狀態(tài)（state）狀態(tài)表示每個(gè)階段開(kāi)始所處的自然狀況或客觀條件，它描述了研究問(wèn)題過(guò)程的狀況。狀態(tài)既反映前面各階段系列決策的結(jié)局，又是本階段決策的一個(gè)出發(fā)點(diǎn)和依據(jù)；它是各階段信息的傳遞點(diǎn)和結(jié)合點(diǎn)。各階段的狀態(tài)通常用狀態(tài)變量來(lái)加以描述。作為狀態(tài)應(yīng)具有這樣的性質(zhì)：如果某階段狀態(tài)給定后，則該階段以后過(guò)程的發(fā)展不受此階段以前各階段狀態(tài)的影響。換句話說(shuō)，過(guò)程的歷史只能通過(guò)當(dāng)前的狀態(tài)來(lái)影響未來(lái)，當(dāng)前的狀態(tài)是以往歷史的一個(gè)總結(jié)。這個(gè)性質(zhì)稱為無(wú)后效性或健忘性。（3）決策（d

17、ecision）決策是指決策者在所面臨的若干個(gè)方案中做出的選擇。決策變量dk表示第k階段的決策。決策變量的取值會(huì)受到狀態(tài)的某種限制，用表示第k階段狀態(tài)為時(shí)決策變量允許的取值范圍，稱為允許決策集合，因而有。（4）狀態(tài)轉(zhuǎn)移律（transformation function）狀態(tài)轉(zhuǎn)移律是確定由一個(gè)狀態(tài)到另一狀態(tài)演變過(guò)程的方程，這種演變的對(duì)應(yīng)關(guān)系記為。（5）策略（policy）與子策略（sub-policy）由所有階段決策所組成的一個(gè)決策序列稱為一個(gè)策略，具有N個(gè)階段的動(dòng)態(tài)規(guī)劃問(wèn)題的策略可表示為：從某一階段開(kāi)始到過(guò)程終點(diǎn)為止的一個(gè)決策子序列，稱為過(guò)程子策略或子策略。從第k個(gè)階段起的一個(gè)子策略可表示為：

18、（6）指標(biāo)函數(shù)指標(biāo)函數(shù)有階段指標(biāo)函數(shù)和過(guò)程指標(biāo)函數(shù)之分。階段指標(biāo)函數(shù)是對(duì)應(yīng)某一階段決策的效率度量，用來(lái)表示；過(guò)程指標(biāo)函數(shù)是用來(lái)衡量所實(shí)現(xiàn)過(guò)程優(yōu)劣的數(shù)量指標(biāo)，是定義在全過(guò)程（策略）或后續(xù)子過(guò)程（子策略）上的一個(gè)數(shù)量函數(shù)，從第k個(gè)階段起的一個(gè)子策略所對(duì)應(yīng)的過(guò)程指標(biāo)函數(shù)常用來(lái)表示，即： 構(gòu)成動(dòng)態(tài)規(guī)劃的過(guò)程指標(biāo)函數(shù)，應(yīng)具有可分性并滿足遞推關(guān)系；即： 這里的表示某種運(yùn)算，最常見(jiàn)的運(yùn)算關(guān)系有如下兩種：a. 過(guò)程指標(biāo)函數(shù)是其所包含的各階段指標(biāo)函數(shù)的“和”，即： 于是 b. 過(guò)程指標(biāo)函數(shù)是其所包含的各階段指標(biāo)函數(shù)的“積”，即： 于是 (7)最優(yōu)指標(biāo)函數(shù)從第個(gè)階段起的最優(yōu)子策略所對(duì)應(yīng)的過(guò)程指標(biāo)函數(shù)稱為最優(yōu)指標(biāo)函

19、數(shù)，可以用式（1-2）加以表示： (2-2)其中“opt”是最優(yōu)化“optimization”的縮寫(xiě)，可根據(jù)題意取最大“max”或最小“min”。在不同的問(wèn)題中，指標(biāo)函數(shù)的含義可能是不同的，它可能是距離、利潤(rùn)、成本、產(chǎn)量或資源量等。3. 動(dòng)態(tài)規(guī)劃的數(shù)學(xué)模型動(dòng)態(tài)規(guī)劃的數(shù)學(xué)模型除包括式（2-2）外，還包括階段的劃分、各階段的狀態(tài)變量和決策變量的選取、允許決策集合和狀態(tài)轉(zhuǎn)移律的確定等。如何獲得最優(yōu)指標(biāo)函數(shù)呢？一個(gè)N階段的決策過(guò)程，具有如下一些特性：（1）剛好有N個(gè)決策點(diǎn)；（2）對(duì)階段k而言，除了其所處的狀態(tài)和所選擇的決策外，再?zèng)]有任何其它因素影響決策的最優(yōu)性了；(3)階段k僅影響階段的決策，這一影響

20、是通過(guò)來(lái)實(shí)現(xiàn)的；(4)貝爾曼（Bellman）最優(yōu)化原理：在最優(yōu)策略的任意一階段上，無(wú)論過(guò)去的狀態(tài)和決策如何，對(duì)過(guò)去決策所形成的當(dāng)前狀態(tài)而言，余下的諸決策必須構(gòu)成最優(yōu)子策略4。根據(jù)貝爾曼（Bellman）最優(yōu)化原理，可以將式（2-2）表示為遞推最優(yōu)指標(biāo)函數(shù)關(guān)系式（2-3）或式（2-4）： （2-3） （2-4）利用式（2-3）和式（2-4）可表示出最后一個(gè)階段（第N個(gè)階段，即k=N）的最優(yōu)指標(biāo)函數(shù)： （2-5） （2-6）其中稱為邊界條件。一般情況下，第階段的輸出狀態(tài)已經(jīng)不再影響本過(guò)程的策略，即式（2-5）中的邊界條件，式（2-6）中的邊界條件；但當(dāng)問(wèn)題第階段的輸出狀態(tài)對(duì)本過(guò)程的策略產(chǎn)生某種影

21、響時(shí)，邊界條件就要根據(jù)問(wèn)題的具體情況取適當(dāng)?shù)闹?，這一情況將在后續(xù)例題中加以反映。已知邊界條件，利用式（2-3）或式（2-4）即可求得最后一個(gè)階段的最優(yōu)指標(biāo)函數(shù)；有了，繼續(xù)利用式（2-3）或式（2-4）即可求得最后兩個(gè)階段的最優(yōu)指標(biāo)函數(shù)；有了，進(jìn)一步又可以求得最后三個(gè)階段的最優(yōu)指標(biāo)函數(shù)；反復(fù)遞推下去，最終即可求得全過(guò)程個(gè)階段的最優(yōu)指標(biāo)函數(shù)，從而使問(wèn)題得到解決。由于上述最優(yōu)指標(biāo)函數(shù)的構(gòu)建是按階段的逆序從后向前進(jìn)行的，所以也稱為動(dòng)態(tài)規(guī)劃的逆序算法。通過(guò)上述分析可以看出，任何一個(gè)多階段決策過(guò)程的最優(yōu)化問(wèn)題，都可以用非線性規(guī)劃（特殊的可以用線性規(guī)劃）模型來(lái)描述；因此，從原則上講，一般也可以用非線性規(guī)劃（

22、或線性規(guī)劃）的方法來(lái)求解。那么利用動(dòng)態(tài)規(guī)劃求解多階段決策過(guò)程有什么優(yōu)越性、又有什么局限性呢？4. 動(dòng)態(tài)規(guī)劃的優(yōu)缺點(diǎn)動(dòng)態(tài)規(guī)劃的優(yōu)點(diǎn)：第一，求解更容易、效率更高。動(dòng)態(tài)規(guī)劃方法是一種逐步改善法，它把原問(wèn)題化成一系列結(jié)構(gòu)相似的最優(yōu)化子問(wèn)題，而每個(gè)子問(wèn)題的變量個(gè)數(shù)比原問(wèn)題少得多，約束集合也簡(jiǎn)單得多，故較易于確定最優(yōu)解。第二，解的信息更豐富。非線性規(guī)劃（或線性規(guī)劃）的方法是對(duì)問(wèn)題的整體進(jìn)行一次性求解的，因此只能得到全過(guò)程的解；而動(dòng)態(tài)規(guī)劃方法是將過(guò)程分解成多個(gè)階段進(jìn)行求解的，因此不僅可以得到全過(guò)程的解，同時(shí)還可以得到所有子過(guò)程的解。動(dòng)態(tài)規(guī)劃的缺點(diǎn)：第一，沒(méi)有一個(gè)統(tǒng)一的標(biāo)準(zhǔn)模型。由于實(shí)際問(wèn)題不同，其動(dòng)態(tài)規(guī)劃模

23、型也就各有差異，模型構(gòu)建存在一定困難。第二，應(yīng)用條件苛刻。由于構(gòu)造動(dòng)態(tài)規(guī)劃模型狀態(tài)變量必須滿足“無(wú)后效性”條件，這一條件不僅依賴于狀態(tài)轉(zhuǎn)移律，還依賴于允許決策集合和指標(biāo)函數(shù)的結(jié)構(gòu)，不少實(shí)際問(wèn)題在取其自然特征作為狀態(tài)變量時(shí)并不滿足這一條件，這就降低了動(dòng)態(tài)規(guī)劃的通用性。第三，狀態(tài)變量存在“維數(shù)障礙”。最優(yōu)指標(biāo)函數(shù)是狀態(tài)變量的函數(shù)，當(dāng)狀態(tài)變量的維數(shù)增加時(shí)，最優(yōu)指標(biāo)函數(shù)的計(jì)算量將成指數(shù)倍增長(zhǎng)；因此，無(wú)論是手工計(jì)算還是電算“維數(shù)障礙”都是無(wú)法完全克服的。三 動(dòng)態(tài)規(guī)劃理論在實(shí)際問(wèn)題中的應(yīng)用通過(guò)學(xué)習(xí)動(dòng)態(tài)規(guī)劃的基本方法，對(duì)多階段決策過(guò)程進(jìn)行數(shù)學(xué)描述，建立相應(yīng)的數(shù)學(xué)模型，利用Matlab軟件及其優(yōu)化工具函數(shù)mi

24、xfy編程計(jì)算最優(yōu)決策序列和總利潤(rùn)的最大值,學(xué)會(huì)求解各種優(yōu)化問(wèn)題和使用優(yōu)化工具箱，以數(shù)學(xué)模型解決最短路線，資源分配等實(shí)際問(wèn)題。1. 最短路線問(wèn)題 用自編函數(shù)mixfy求解圖3-1所示網(wǎng)絡(luò)中從出發(fā)點(diǎn)到收點(diǎn)的最短路（圖中各弧邊為各段距離）。 圖3-1 路線的網(wǎng)絡(luò)圖 解：圖3-1有5個(gè)結(jié)點(diǎn)，12個(gè)流段。設(shè)分段流量為，并標(biāo)在圖3-1上，下面利用自編函數(shù)mixfy求圖3-1中，從出發(fā)點(diǎn)到收點(diǎn)的最短路。先求出結(jié)點(diǎn)流段出入矩陣q。i=1,2,2,2,3,4,4,4,5,5;j=1,2,4,5,3,6,7,10,8,9;i1=1,1,2,2,3,3,4,5,5;j1=4,6,7,8,5,9,11,10,12;

25、使用自編函數(shù)stp:q=stg(i,j,i1,j1,5,12)求出結(jié)點(diǎn)流段出入矩陣q。從圖3-1發(fā)點(diǎn)處可知流量函數(shù)為：f=1,1,1,zeros(1,9);因規(guī)定分段容量為單位容量，故ub=ones(12,);分段距離作為費(fèi)用，故費(fèi)用函數(shù)為：f1=2,5,4,2,1,7,5,3,4,1,5,7;至此，取v=1,用編函數(shù)mixfy:ex,z,fp=mixfy(1,f,f1,q,ub);求得，ex=1,fp=13,以及 z=1.0,0.0,0.0,1.0,0.0,0.0,0.0,1.0,0.0,1.0,1.0,0.0取 p=round(z) 得p=1,0,0,1,0,0,0,1,0,1,1,0使用

26、自編函數(shù)check2:qp,pf,pf1,rb,p=check2(f,f1,q,ub,p)求得： qp=0,0,0,0,pf=1,pf1=13,rb0由此可知，p是流值為1的最小費(fèi)用整流，其費(fèi)用值為13。取 zr=find(p)得 zr=1,4,8,10,11zr是0-1流p的流值為1的流段標(biāo)號(hào)。參照?qǐng)D3-1.沿著zr所指流段，得到一條從發(fā)點(diǎn)至收點(diǎn)的最短路： 其路長(zhǎng)為13，這就是從發(fā)點(diǎn)至收點(diǎn)的最短路。2. 資源分配問(wèn)題所謂資源分配問(wèn)題，就是將一定數(shù)量的一種或若干種資源（如原材料、機(jī)器設(shè)備、資金、勞動(dòng)力等）恰當(dāng)?shù)胤峙浣o若干個(gè)使用者，以使資源得到最有效地利用。審計(jì)人員任務(wù)分配。某會(huì)計(jì)公司有3名審計(jì)

27、員：一名是已在公司服務(wù)4 年以上的高級(jí)審計(jì)員，兩名是在公司工作不到2年的初級(jí)審計(jì)員。公司要用這3名審計(jì)員從事3項(xiàng)即將簽訂的合同任務(wù)：兩名審計(jì)和一項(xiàng)專業(yè)發(fā)展計(jì)劃。計(jì)劃員的任務(wù)是以最佳方式把審計(jì)人員分配到3項(xiàng)不同的合同任務(wù)中。該公司不僅要求最大利潤(rùn)，而且要盡可能的為公眾服務(wù)，目標(biāo)函數(shù)還必須反應(yīng)各項(xiàng)工作因每個(gè)審計(jì)員的承擔(dān)而體現(xiàn)出來(lái)的無(wú)形的貨幣價(jià)值。在本例中，只需考慮以下兩種無(wú)形價(jià)值：用于此項(xiàng)工作的過(guò)去經(jīng)驗(yàn)的價(jià)值和由新經(jīng)驗(yàn)所獲得的知識(shí)。故目標(biāo)函數(shù)中各變量的系數(shù)等于賬面價(jià)值，過(guò)去經(jīng)驗(yàn)價(jià)值和知識(shí)價(jià)值之和，均列于表3-1中。關(guān)于表3-1的幾點(diǎn)說(shuō)明： （1）專業(yè)發(fā)展規(guī)劃未列出賬面價(jià)值，但對(duì)各審計(jì)員卻可以產(chǎn)生很

28、大的知識(shí)價(jià)值。 （2）高級(jí)審計(jì)員經(jīng)驗(yàn)價(jià)值通常高于初級(jí)審計(jì)員的經(jīng)驗(yàn)價(jià)值。 （3）如果一個(gè)高級(jí)審計(jì)員年年都從事一項(xiàng)審計(jì)工作，則他就會(huì)遲鈍化，對(duì)公司的價(jià)值將會(huì)變小。這樣，高級(jí)審計(jì)員的知識(shí)價(jià)值以負(fù)值來(lái)表現(xiàn)。表3-1 審計(jì)員承擔(dān)的各個(gè)無(wú)形價(jià)值審計(jì)員任務(wù)賬面價(jià)值既往經(jīng)驗(yàn)價(jià)值學(xué)識(shí)價(jià)值總價(jià)值初級(jí)審計(jì)第一項(xiàng)審計(jì)119828第二項(xiàng)審計(jì)1186251號(hào)發(fā)展規(guī)劃002525初級(jí)審計(jì)第一項(xiàng)審計(jì)1271029第二項(xiàng)審計(jì)12711302號(hào)發(fā)展規(guī)劃002727高級(jí)審計(jì)第一項(xiàng)審計(jì)1820-434第二項(xiàng)審計(jì)1725-537發(fā)展規(guī)劃003030下面給出約束條件：（1） 每個(gè)審計(jì)員分配3項(xiàng)合同的總工時(shí)數(shù)不超過(guò)100小時(shí)。（2） 每項(xiàng)

29、合同完成工時(shí)的上、下極限： 25第一項(xiàng)審計(jì)完成工時(shí)50 第二項(xiàng)審計(jì)完成工時(shí)=130 70發(fā)展規(guī)劃完成工時(shí)90問(wèn)應(yīng)如何分配審計(jì)員，使會(huì)計(jì)公司獲利最大？解：這是一個(gè)審計(jì)人員任務(wù)分配問(wèn)題。設(shè)為初級(jí)審計(jì)員1號(hào)從事第一項(xiàng)審計(jì)工作的工時(shí)數(shù)，為初級(jí)審計(jì)員1號(hào)從事第二項(xiàng)審計(jì)工作的工時(shí)數(shù)，為初級(jí)審計(jì)員1號(hào)從事發(fā)展規(guī)劃工作的工時(shí)數(shù)，為初級(jí)審計(jì)員2號(hào)從事第一項(xiàng)審計(jì)工作的工時(shí)數(shù)，為初級(jí)審計(jì)員2號(hào)從事第二項(xiàng)審計(jì)工作的工時(shí)數(shù)，為初級(jí)審計(jì)員2號(hào)從事發(fā)展規(guī)劃工作的工時(shí)數(shù)，為高級(jí)審計(jì)員從事第一項(xiàng)審計(jì)工作的工時(shí)數(shù)，為高級(jí)審計(jì)員從事第二項(xiàng)審計(jì)工作的工時(shí)數(shù)，為高級(jí)審計(jì)員從事發(fā)展規(guī)劃工作的工時(shí)數(shù)。從表3-1可知會(huì)計(jì)公司的利潤(rùn)函數(shù)為：

30、下面來(lái)看約束條件。最多工時(shí)不超過(guò)100工時(shí)： 1號(hào)審計(jì)員 2號(hào)審計(jì)員 高級(jí)審計(jì)員每項(xiàng)合同完成時(shí)數(shù)約束： 第一項(xiàng)審計(jì) 第一項(xiàng)審計(jì) 第二項(xiàng)審計(jì) 發(fā)展規(guī)劃 發(fā)展規(guī)劃這樣，所述問(wèn)題的數(shù)學(xué)模型為： 下面給出上述問(wèn)題的計(jì)算程序：f=28,25,25,29,30,27,34,37,30;0=ones(1,3);z2=zeros(1,2);Z3=zeros(1,3);z6=zeros(1,6);a=0,z6;z3,0,z3;z6,0;a1=1,z,2,1,z2,1,z2;a2=z2,1,z2,1,z2,1;a=a;a1;-a1;a2;-a2;b=100,100,100,50,-25,90,-70;q=0,0.

31、95,z2,0.9,z2,1.2,0;bq=135;1b=zeros(9,1);x,fv,ex=linprog(f,a,b,q,bq,ib,);上述程序執(zhí)行后，求得：ex=1,fv=-8400,及x=0,0,77.5,100,0,50,37.5,12.5。這樣，使會(huì)計(jì)公司獲得最大的分配方案為：初級(jí)審計(jì)員1號(hào)用77.5工時(shí)作專業(yè)發(fā)展規(guī)劃，初級(jí)審計(jì)員2號(hào)用100工時(shí)作第二項(xiàng)審計(jì)，高級(jí)審計(jì)員用50工時(shí)作第一項(xiàng)審計(jì)，用37.5工時(shí)作第二項(xiàng)審計(jì)，用12，5工時(shí)作發(fā)展規(guī)劃。其最大利潤(rùn)為8400元。如用xx=reshape(x,3,3);xx=xx;則得 這就是最優(yōu)解審計(jì)人員的分配方案表示排列。又用 得 y表示初級(jí)審計(jì)員1號(hào)，初級(jí)審計(jì)員2號(hào)，高級(jí)審計(jì)員所用總工時(shí)。又用 得 z表示初級(jí)審計(jì)員1號(hào)，初級(jí)審計(jì)員2號(hào)，高級(jí)審計(jì)員分別給公司貢獻(xiàn)得收入為1937.5元、3000元、3