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

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

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

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

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

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

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

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

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

9、性規(guī)劃那樣有一個標(biāo)準(zhǔn)的數(shù)學(xué)表達式和明確定義的一組規(guī)則，動態(tài)規(guī)劃必須對具體問題進行具體的分析處理。在多階段決策問題中，有些問題對階段的劃分具有明顯的時序性，動態(tài)規(guī)劃的“動態(tài)”二字也由此而得名。動態(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)時唯一的進一步研究和應(yīng)用動態(tài)規(guī)劃的理論源泉。1961年貝爾曼出版了他的第二部著作，并于1962年同杜瑞佛思（Dreyfus）合作出版了第三部著作

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

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

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

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

14、（3）數(shù)學(xué)建模實驗，應(yīng)用于實際，解決現(xiàn)實的問題。二 動態(tài)規(guī)劃基本理論知識1. 多階段決策過程的數(shù)學(xué)描述有這樣一類活動過程，其整個過程可分為若干相互聯(lián)系的階段，每一階段都要作出相應(yīng)的決策，以使整個過程達到最佳的活動效果。任何一個階段（stage，即決策點）都是由輸入（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)由于每一階段都有一個決策，所以每一階段都應(yīng)存在一個衡量決策效益大小的指標(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òu)成的過程里，前一個階段的輸出即為后一個階段的輸入。2. 動態(tài)規(guī)劃的基本概念動態(tài)規(guī)劃的數(shù)學(xué)描述離不開它的一些基本概念與符號，因此有必要在介紹多階段決策過程的數(shù)學(xué)描述的基礎(chǔ)上，系統(tǒng)地介紹動態(tài)規(guī)劃的一些基本概念。（1）階段（stage）階段是過程中需要做出決策的決策點。描述階段的變量稱為階段變量，常用k來表示。階段的劃分一

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

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

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

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

20、是通過來實現(xiàn)的；(4)貝爾曼（Bellman）最優(yōu)化原理：在最優(yōu)策略的任意一階段上，無論過去的狀態(tài)和決策如何，對過去決策所形成的當(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）可表示出最后一個階段（第N個階段，即k=N）的最優(yōu)指標(biāo)函數(shù)： （2-5） （2-6）其中稱為邊界條件。一般情況下，第階段的輸出狀態(tài)已經(jīng)不再影響本過程的策略，即式（2-5）中的邊界條件，式（2-6）中的邊界條件；但當(dāng)問題第階段的輸出狀態(tài)對本過程的策略產(chǎn)生某種影

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

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

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

24、xfy編程計算最優(yōu)決策序列和總利潤的最大值,學(xué)會求解各種優(yōu)化問題和使用優(yōu)化工具箱，以數(shù)學(xué)模型解決最短路線，資源分配等實際問題。1. 最短路線問題 用自編函數(shù)mixfy求解圖3-1所示網(wǎng)絡(luò)中從出發(fā)點到收點的最短路（圖中各弧邊為各段距離）。 圖3-1 路線的網(wǎng)絡(luò)圖 解：圖3-1有5個結(jié)點，12個流段。設(shè)分段流量為，并標(biāo)在圖3-1上，下面利用自編函數(shù)mixfy求圖3-1中，從出發(fā)點到收點的最短路。先求出結(jié)點流段出入矩陣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é)點流段出入矩陣q。從圖3-1發(fā)點處可知流量函數(shù)為：f=1,1,1,zeros(1,9);因規(guī)定分段容量為單位容量，故ub=ones(12,);分段距離作為費用，故費用函數(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的最小費用整流，其費用值為13。取 zr=find(p)得 zr=1,4,8,10,11zr是0-1流p的流值為1的流段標(biāo)號。參照圖3-1.沿著zr所指流段，得到一條從發(fā)點至收點的最短路： 其路長為13，這就是從發(fā)點至收點的最短路。2. 資源分配問題所謂資源分配問題，就是將一定數(shù)量的一種或若干種資源（如原材料、機器設(shè)備、資金、勞動力等）恰當(dāng)?shù)胤峙浣o若干個使用者，以使資源得到最有效地利用。審計人員任務(wù)分配。某會計公司有3名審計

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

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

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

30、下面來看約束條件。最多工時不超過100工時： 1號審計員 2號審計員 高級審計員每項合同完成時數(shù)約束： 第一項審計 第一項審計 第二項審計 發(fā)展規(guī)劃 發(fā)展規(guī)劃這樣，所述問題的數(shù)學(xué)模型為： 下面給出上述問題的計算程序：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。這樣，使會計公司獲得最大的分配方案為：初級審計員1號用77.5工時作專業(yè)發(fā)展規(guī)劃，初級審計員2號用100工時作第二項審計，高級審計員用50工時作第一項審計，用37.5工時作第二項審計，用12，5工時作發(fā)展規(guī)劃。其最大利潤為8400元。如用xx=reshape(x,3,3);xx=xx;則得 這就是最優(yōu)解審計人員的分配方案表示排列。又用 得 y表示初級審計員1號，初級審計員2號，高級審計員所用總工時。又用 得 z表示初級審計員1號，初級審計員2號，高級審計員分別給公司貢獻得收入為1937.5元、3000元、3