多目標最優(yōu)化模型

1、第六章 最優(yōu)化數學模型§1 最優(yōu)化問題11 最優(yōu)化問題概念12 最優(yōu)化問題分類13 最優(yōu)化問題數學模型§2 經典最優(yōu)化方法 21 無約束條件極值22 等式約束條件極值23 不等式約束條件極值§3 線性規(guī)劃31 線性規(guī)劃32 整數規(guī)劃§4 最優(yōu)化問題數值算法41 直接搜索法42 梯度法43 罰函數法§5 多目標優(yōu)化問題51 多目標優(yōu)化問題52 單目標化解法53 多重優(yōu)化解法54 目標關聯函數解法55 投資收益風險問題第六章 最優(yōu)化問題數學模型§1 最優(yōu)化問題11 最優(yōu)化問題概念（1）最優(yōu)化問題 在工業(yè)、農業(yè)、交通運輸、商業(yè)、國防、建筑、

2、通信、政府機關等各部門各領域的實際工作中，我們經常會遇到求函數的極值或最大值最小值問題，這一類問題我們稱之為最優(yōu)化問題。而求解最優(yōu)化問題的數學方法被稱為最優(yōu)化方法。它主要解決最優(yōu)生產計劃、最優(yōu)分配、最佳設計、最優(yōu)決策、最優(yōu)管理等求函數最大值最小值問題。 最優(yōu)化問題的目的有兩個：求出滿足一定條件下，函數的極值或最大值最小值；求出取得極值時變量的取值。最優(yōu)化問題所涉及的內容種類繁多，有的十分復雜，但是它們都有共同的關鍵因素：變量，約束條件和目標函數。（2）變量 變量是指最優(yōu)化問題中所涉及的與約束條件和目標函數有關的待確定的量。一般來說，它們都有一些限制條件（約束條件），與目標函數緊密關聯。設問題中

3、涉及的變量為；我們常常也用表示。（3）約束條件 在最優(yōu)化問題中，求目標函數的極值時，變量必須滿足的限制稱為約束條件。 例如，許多實際問題變量要求必須非負，這是一種限制；在研究電路優(yōu)化設計問題時，變量必須服從電路基本定律，這也是一種限制等等。在研究問題時，這些限制我們必須用數學表達式準確地描述它們。 用數學語言描述約束條件一般來說有兩種：等式約束條件 不等式約束條件 或 注：在最優(yōu)化問題研究中，由于解的存在性十分復雜，一般來說，我們不考慮不等式約束條件或。這兩種約束條件最優(yōu)化問題最優(yōu)解的存在性較復雜。（4）目標函數 在最優(yōu)化問題中，與變量有關的待求其極值（或最大值最小值）的函數稱為目標函數。 目

4、標函數常用表示。當目標函數為某問題的效益函數時，問題即為求極大值；當目標函數為某問題的費用函數時，問題即為求極小值等等。求極大值和極小值問題實際上沒有原則上的區(qū)別，因為求的極小值，也就是要求的極大值，兩者的最優(yōu)值在同一點取到。12 最優(yōu)化問題分類 最優(yōu)化問題種類繁多，因而分類的方法也有許多。可以按變量的性質分類，按有無約束條件分類，按目標函數的個數分類等等。 一般來說，變量可以分為確定性變量，隨機變量和系統(tǒng)變量等等，相對應的最優(yōu)化問題分別稱為：普通最優(yōu)化問題，統(tǒng)計最優(yōu)化問題和系統(tǒng)最優(yōu)化問題。 按有無約束條件分類：無約束最優(yōu)化問題，有約束最優(yōu)化問題。按目標函數的個數分類：單目標最優(yōu)化問題，多目標

5、最優(yōu)化問題。按約束條件和目標函數是否是線性函數分類：線性最優(yōu)化問題（線性規(guī)劃），非線性最優(yōu)化問題（非線性規(guī)劃）。按約束條件和目標函數是否是時間的函數分類：靜態(tài)最優(yōu)化問題和動態(tài)最優(yōu)化問題（動態(tài)規(guī)劃）。按最優(yōu)化問題求解方法分類：解析法（間接法）數值算法（直接法）數值算法（梯度法）多目標優(yōu)化方法網絡優(yōu)化方法13 最優(yōu)化問題的求解步驟和數學模型 （1）最優(yōu)化問題的求解步驟最優(yōu)化問題的求解涉及到應用數學，計算機科學以及各專業(yè)領域等等，是一個十分復雜的問題，然而它卻是需要我們重點關心的問題之一。怎樣研究分析求解這類問題呢？其中最關鍵的是建立數學模型和求解數學模型。一般來說，應用最優(yōu)化方法解決實際問題可分為

6、四個步驟進行：步驟1：建立模型提出最優(yōu)化問題，變量是什么？約束條件有那些？目標函數是什么？建立最優(yōu)化問題數學模型：確定變量，建立目標函數，列出約束條件建立模型。步驟2：確定求解方法分析模型，根據數學模型的性質，選擇優(yōu)化求解方法確定求解方法。步驟3：計算機求解編程序（或使用數學計算軟件），應用計算機求最優(yōu)解計算機求解。步驟4：結果分析對算法的可行性、收斂性、通用性、時效性、穩(wěn)定性、靈敏性和誤差等等作出評價結果分析。（2）最優(yōu)化問題數學模型最優(yōu)化問題的求解與其數學模型的類型密切相關，因而我們有必要對最優(yōu)化問題的數學模型有所掌握。一般來說，最優(yōu)化問題的常見數學模型有以下幾種：無約束最優(yōu)化問題數學模型

7、由某實際問題設立變量，建立一個目標函數且無約束條件，這樣的求函數極值或最大值最小值問題，我們稱為無約束最優(yōu)化問題。其數學模型為： 目標函數例如：求一元函數和二元函數的極值。又例如：求函數的極值和取得極值的點。有約束最優(yōu)化問題數學模型由某實際問題設立變量，建立一個目標函數和若干個約束條件（等式或不等式），這樣的求函數極值或最大值最小值問題，我們稱為有約束最優(yōu)化問題。其數學模型為： 目標函數 約束條件有約束最優(yōu)化問題的例子：求函數在約束條件條件下的最大值和取得最大值的點。線性規(guī)劃問題數學模型由某實際問題設立變量，建立一個目標函數和若干個約束條件，目標函數和約束條件都是變量的線性函數，而且變量是非負

8、的，這樣的求函數最大值最小值問題，我們稱為線性最優(yōu)化問題，簡稱為線性規(guī)劃問題。其標準數學模型為： 目標函數 約束條件矩陣形式： 目標函數 約束條件其中 ， 在線性規(guī)劃問題中，關于約束條件我們必須注意以下幾個問題。注1：非負約束條件，一般來說這是實際問題要求的需要。如果約束條件為，我們作變量替換；如果約束條件為，我們作變量替換。注2：在線性規(guī)劃的標準數學模型中，約束條件為等式。如果約束條件不是等式，我們引入松馳變量，化不等式約束條件為等式約束條件。情況1：若約束條件為，引入松馳變量原約束條件變?yōu)?。情況2：若約束條件為，引入松馳變量原約束條件變?yōu)?在其它最優(yōu)化問題中，我們也常常采取上述方法化不等

9、式約束條件為等式約束條件。實際問題中，我們經常遇到兩類特殊的線性規(guī)劃問題。一類是：所求變量要求是非負整數，稱為整數規(guī)劃問題；另一類是所求變量要求只取或，稱為0-1規(guī)劃問題。例如：整數規(guī)劃問題 。又例如：0-1規(guī)劃問題 。非線性規(guī)劃問題數學模型由某實際問題設立變量，建立一個目標函數和若干個約束條件，如果目標函數或約束條件表達式中有變量的非線性函數，那么，這樣的求函數最大值最小值問題，我們稱為非線性規(guī)劃最優(yōu)化問題，簡稱為非線性規(guī)劃問題。其數學模型為： 目標函數 約束條件其中目標函數或約束條件中有變量的非線性函數。例如：非線性規(guī)劃問題 。 上述最優(yōu)化問題中，目標函數是非線性函數，故稱為非線性規(guī)劃問題

10、。 前面介紹的四種最優(yōu)化數學模型都只有一個目標函數，稱為單目標最優(yōu)化問題，簡稱為最優(yōu)化問題。 多目標最優(yōu)化問題數學模型由某實際問題設立變量，建立兩個或多個目標函數和若干個約束條件，且目標函數或約束條件是變量的函數，這樣的求函數最大值最小值問題，我們稱為多目標最優(yōu)化問題。其數學模型為： 目標函數 約束條件 上述模型中有個目標函數，個等式約束條件。例如：“生產商如何使得產值最大而且消耗資源最少問題”“投資商如何使得投資收益最大而且風險最小問題”等都是多目標最優(yōu)化問題。§2 經典最優(yōu)化方法 經典最優(yōu)化方法包括無約束條件極值問題和等式約束條件極值問題兩種，不等式約束條件極值問題可以化為等式約

11、束條件極值問題。 經典的極值理論：首先，根據可微函數取極值的必要條件確定可能極值點；其次，根據函數取極值的充分條件判斷是否取極值？是極大值？還是極小值？這種方法已經幾百年的歷史了。21 無約束條件極值 設元函數，求的極值和取得極值的點。這是一個無約束條件極值問題，經典的極值理論如下。定理1（極值必要條件）：設元函數具有偏導數，則在處取得極值的必要條件為： 。 定理在此不給出證明，讀者可自己參看有關資料。注1：對于一元函數上述定理當然成立，只是偏導數應為導數；注2：定理只是在偏導數存在的前提下的必要條件。如果函數在某一點偏導數不存在，那在這一點處仍然可能取得極值；注3：如果函數在某一點偏導數存在

12、，且偏導數都等于零，那么函數在這一點處也不一定取得極值。例如，函數在點處偏導數不存在，但在這一點處函數仍然取得極小值零。函數在點處偏導數存在，且偏導數都等于零，但在這一點處函數不取極值。定理1的作用在于，求出函數的可能極值點，然后，我們再研究這些點是否取得極值。對于許多實際問題來說，函數一定能夠取得極大值或極小值，而函數的可能極值點（滿足必要條件的點）又只有一點，則這一點當然是函數取得極大值或極小值的點。對于一般函數而言，我們怎樣判定函數在某點是否取極值？是極大值？還是極小值？我們有下面的極值的充分條件定理。定理2（極值充分條件）：設元函數具有二階偏導數，則在處取得極值的充分條件為： （1）；

13、 （2）黑塞矩陣在處正定或負定；（3）黑塞矩陣在處正定時，函數取極小值；負定時，函數取極大值。 本章內容簡要講解理論，注重實際應用，對于許多經典的定理都不進行證明，讀者可自己參看有關資料。例1：求函數的極值。解：（1）根據極值存在的必要條件，確定可能取得極值的點： ，令，解得 。（2) 根據極值存在的充分條件，確定是否是極值點：計算 ，； ，；函數的黑塞矩陣為 因為 ，；所以黑塞矩陣負定，故函數在處取得極大值。22 等式約束條件極值下面我們研究的是有若干個等式約束條件下，一個目標函數的極值問題，其數學模型為： 目標函數 約束條件拉格朗日（Lagrange)乘數法：（1）令 稱為上述問題的拉格朗

14、日乘數函數，稱為拉格朗日乘數。（2）設和均可微，則得到方程組（3）若是上述方程組的解，則點可能為該問題的最優(yōu)點。 拉格朗日（Lagrange)乘數法的本質是：將求有約束條件極值問題轉化為求無條件極值問題；所求得的點，即是取得極值的必要條件點。 拉格朗日乘數法沒有解決極值的存在性問題，但是，如果拉格朗日乘數函數具有二階連續(xù)偏導數，我們也可以應用黑塞矩陣來判定函數是否取得極值。在具體問題中，點是否為最優(yōu)點通?？捎蓡栴}的實際意義決定。例2：求表面積為定值，而體積為最大的長方體的體積。解：設長方體的三棱長為，體積為；建立數學模型如下： 構造拉格朗日乘數函數，則有解得 ， 為所求。23 不等式約束條件極

15、值 對于不等式約束條件極值問題： 目標函數 約束條件我們有與拉格朗日乘數法密切相關的方法庫恩圖克定理。定理3（庫恩圖克定理）：對于上述不等式約束條件極值問題，設和均可微，令 假設存在，則在最優(yōu)點處，必滿足下述條件：（1）；（2）；（3）；（4）。 根據庫恩圖克定理我們可以求解許多不等式約束條件極值問題，值得注意的是應用庫恩圖克定理求解不等式約束條件極值問題，定理并沒有解決最優(yōu)解的存在性問題，因此，我們必須另行判斷。例3：求解最優(yōu)化問題（最優(yōu)解存在） 解：構造函數 ，根據庫恩圖克定理則有 解得： ；所求最優(yōu)解為，最優(yōu)值為。§3 線性規(guī)劃31 線性規(guī)劃設線性規(guī)劃標準數學模型為： 目標函數

16、 約束條件矩陣形式： 目標函數 約束條件其中 ，線性規(guī)劃問題的求解有一整套理論體系，一般來說，應用單純形法求解。此方法盡管比較復雜，然而在計算機上實現并不困難。解線性規(guī)劃問題的單純形法已在許多數學計算軟件中實現，我們求解線性規(guī)劃問題可根據需要，應用數學計算軟件求解即可。在此，我們不系統(tǒng)研究其理論，只是簡單介紹線性規(guī)劃的窮舉法和單純形法的基本思想。3.2 線性規(guī)劃的窮舉法 （1）窮舉法基本原理和步驟步驟1：將線性規(guī)劃問題化成矩陣的標準形式，設系數矩陣的秩，則對應線性方程組的基礎解系自由變量的個數為個。步驟2：窮舉法求解：令，解得對應線性方程組一組解為 ；對應目標函數值為。 從個變量中選個作為自由

17、變量，令它們的值為0，可得到組解。步驟3：確定最優(yōu)解：如果最優(yōu)解存在，則上述求解得到的對應個目標函數值中，最小者（或最大者）即為所求最?。ɑ蜃畲螅┳顑?yōu)值，對應的解為最優(yōu)解。步驟4：證明解為最優(yōu)解：將最優(yōu)解對應的自由變量看成參數；解對應線性方程組得 。將對應線性方程組解代入目標函數得：。 如果，則所求為最小值最優(yōu)解；否則，線性規(guī)劃問題無最小值最優(yōu)解。 如果，則所求為最大值最優(yōu)解；否則，線性規(guī)劃問題無最大值最優(yōu)解。 例1：目標函數：解：約束條件的增廣矩陣為： ，；令，解得；令，無解；令，解得，不滿足非負條件，舍去；令，解得；令，解得；令，解得，不滿足非負條件，舍去；令，無解；令，解得；令，解得，不

18、滿足非負條件，舍去；令，解得；所以，最優(yōu)解為。證明：令解得 目標函數；因為非負，所以，故最優(yōu)解存在。（2）單純形法基本原理和步驟將線性規(guī)劃問題化成矩陣的標準形式，設系數矩陣的秩，則對應線性方程組的基礎解系的個數為個，即有個自由參數變量。選取個非基變量（自由參數變量）,不妨假設為；解得線性規(guī)劃問題的典式 定理1：如果線性規(guī)劃問題的上述典式中所有；則為最優(yōu)解。定理2：如果線性規(guī)劃問題的上述典式中存在某個，且對應；則線性規(guī)劃問題無最優(yōu)解。由定理1和定理2知，如果我們選擇適當的個非基變量，就可以根據所求得的典式判斷最優(yōu)解的存在與否，從而求解該線性規(guī)劃問題。單純形法的思想是：選擇適當的基變換（進基和退基

19、），不斷地變換典式，使得典式中目標函數值不斷下降，從而求得最優(yōu)解。其核心為如何選擇進基和退基。進基規(guī)則和退基規(guī)則進基規(guī)則正檢驗數最小下標規(guī)則，即選取，由此確定為進基。退基規(guī)則：選取這樣的下標（表示第個基變量的下標） 由此確定離基。單純形法的基本步驟：步驟1：化線性規(guī)劃問題為標準形式。步驟2：確定基變量，求得基本可行解和典式；是否滿足最優(yōu)解定理或最優(yōu)解不存在定理的條件？判斷最優(yōu)解的情況。步驟3：根據進基規(guī)則和退基規(guī)則，選擇進基和退基，進行基變換，求得對應典式。重復進行基變換，直到求出最優(yōu)解或判斷出無最優(yōu)解為止。例2：解線性規(guī)劃問題 解：（1）約束條件的增廣矩陣為： ，；所以非基變量個數為兩個。（

20、2）選取作為非基變量，作為基變量，解得典式為 不滿足最優(yōu)解定理和最優(yōu)解不存在定理的條件，故必須進行基變換。（3）進行基變換選取進基： ，根據得為進基。選取退基：，根據，得為離基。進行基變換，求新基的典式： 判斷：不滿足最優(yōu)解定理和最優(yōu)解不存在定理的條件，故繼續(xù)進行基變換。（4）繼續(xù)進行基變換選取進基： ，根據得為進基。選取退基：，根據，得為離基。進行基變換，求新基的典式： 滿足最優(yōu)解定理的條件，根據定理最優(yōu)解為 。32 整數規(guī)劃設純整數線性規(guī)劃數學模型為： 目標函數 約束條件 這一類問題與一般線性規(guī)劃比較起來，似乎是變簡單了，但實際上恰恰相反，由于解集是一些離散的整數點集，使得單純形法失去了應

21、用的基礎，求解變得困難而復雜。整數線性規(guī)劃目前還缺乏統(tǒng)一的解法，這里只介紹分枝定界法，它是目前求解純整數線性規(guī)劃和混合整數線性規(guī)劃最常用的方法，計算機求解整數線性規(guī)劃的大多數程序也是以它為基礎的。分枝定界法：考慮上述純整數線性規(guī)劃問題，（1）解對應線性規(guī)劃問題 目標函數 約束條件若無最優(yōu)解，則原純整數線性規(guī)劃問題無最優(yōu)解；若有最優(yōu)解，最優(yōu)點，目標函數最優(yōu)值。若最優(yōu)點全為整數，則為原純整數線性規(guī)劃問題的最優(yōu)解；若最優(yōu)點不全為整數，則進行下一步。（2）定界和分枝定界：其中取原純整數線性規(guī)劃問題中，滿足約束條件的某一整數可行解所對應的目標函數值。原純整數線性規(guī)劃問題的最優(yōu)解必須滿足定界條件。分枝：選

22、取中一個不為整數所對應的分枝， 和稱為對應線性規(guī)劃問題的兩枝，也是兩個新線性規(guī)劃問題的約束條件。顯然，原純整數線性規(guī)劃問題的最優(yōu)解滿足或。（3）對和進行剪枝和分枝解對應的線性規(guī)劃問題，對其進行剪枝和分枝：若無最優(yōu)解，則原純整數線性規(guī)劃問題在內無最優(yōu)解。不需要對該區(qū)域繼續(xù)討論剪枝。若有最優(yōu)解，最優(yōu)點，目標函數的最優(yōu)值。若，則原純整數線性規(guī)劃問題在內無最優(yōu)解。不需要對該區(qū)域繼續(xù)討論剪枝。若最優(yōu)點全為整數，則可能為原純整數線性規(guī)劃問題的最優(yōu)解，定界：記，則，本分枝求解結束。若最優(yōu)點不全為整數，對繼續(xù)進行分枝。完全類似，解對應線性規(guī)劃問題，對其進行剪枝和分枝。依此類推，對所有分枝進行求解，剪枝，分枝，

23、定界；直至求得最優(yōu)解。（4）最優(yōu)解的確定若某，則為最優(yōu)解，求解結束。若所有分枝求解結束，則最后的上界即為最優(yōu)解。例3：應用分枝定界法，求解整數線性規(guī)劃問題 解：設原整數線性規(guī)劃問題目標函數的最優(yōu)值為，（1）求解線性規(guī)劃問題： 得最優(yōu)解為 ；。記約束區(qū)域為。（2）對進行分枝：選取最優(yōu)解中不是整數的變量，例如，將分成兩個子區(qū)域。， （3）定界：確定最優(yōu)值的上下界。由（1）中求得的最優(yōu)值知；而的上界可由內的任意一個可行解確定，例如，即為一個可行解。故。從而，。（4）在內求最優(yōu)解，得 ；。（5）在內求最優(yōu)解，得 ；。（6）因為內最優(yōu)解不全是整數，因而必須繼續(xù)對分枝： （7）顯然內無解，剪枝。在內求最優(yōu)

24、解，得 ；為整數可行解。但因，而，故剪枝。（8）因為內最優(yōu)解不全是整數，因而必須繼續(xù)對分枝： （9）顯然內無解，剪枝。在內求最優(yōu)解，得 ；。（10）因為內最優(yōu)解不全是整數，因而必須繼續(xù)對分枝： （11）在內求最優(yōu)解，得 ；。因大于的上界，故剪枝。（12）在內求最優(yōu)解，得 ；。所求原整數規(guī)劃問題的最優(yōu)解為：；。§4 最優(yōu)化問題數值算法 最優(yōu)化問題的數值算法很多，常用的算法多為搜索法，本節(jié)只介紹搜索法的基本思想、無約束最優(yōu)化問題的最速下降法（梯度法）和有約束最優(yōu)化問題的罰函數法。41 搜索算法考慮無約束最優(yōu)化問題： 我們已經討論了這類問題的最優(yōu)解條件，這必須用到函數的解析性質。我們的方法

25、是，先利用必要條件求出平穩(wěn)點，再應用充分條件判斷是否是極值點。但是，我們必須求解一個個變量個方程的方程組，并且常常是非線性的。這只有在特殊的情況下，才能求出它的精確解。在一般情況下，都不能用解析法求得精確解。更何況許多實際問題中，函數的解析表達式很難得到。因此，我們必須尋求一些切合實際問題的行之有效的數值解法。搜索算法就是我們常用的方法。（1）搜索算法的基本思想：假定目標函數極小值問題。首先，確定目標函數的初始點；然后，按照一定規(guī)則產生一個點列，這種規(guī)則稱為算法；規(guī)則必須滿足（1）點列收斂；（2）點列收斂到目標函數的極小值點。（2）搜索算法的基本步驟：選定初始點（越接近最優(yōu)點越好），允許誤差，

26、令。假定已得非最優(yōu)點，則選取一個搜索方向，滿足： 目標函數下降，或。選定搜索步長，滿足：。判斷是否是最優(yōu)點或是滿足要求的近似解。假定給定精度要求為，常用確定求近似解搜索結束的方法有： 梯度模確定法； 目標函數差值絕對誤差法； 相鄰搜索點絕對誤差法。如果滿足給定精度要求，則搜索完成，近似最優(yōu)點為；如果不滿足給定精度要求，令返回（2）繼續(xù)搜索。注意1：我們的搜索算法一般得到的都是局部最優(yōu)解。注意2：確定求近似解搜索結束的方法還有 目標函數差值相對誤差法； 相鄰搜索點相對誤差法。（3）搜索算法的關鍵因素：從搜索算法的基本步驟中，我們知道，搜索算法的關鍵因素為：一是搜索方向，二是搜索步長。搜索方向的選

27、擇，一般考慮既要使它盡可能的指向極小值點，又要不至于花費太多的計算量。搜索步長的選擇，既要確保目標函數的下降性質，又要考慮近似解的精度要求，還要考慮算法的計算量，問題十分復雜。常用方法有，固定步長法，最優(yōu)步長法和變步長法。固定步長法（簡單算法）是選取為固定值。方法簡單，但是有時不能保證目標函數的下降性質。最優(yōu)步長法（一維搜索算法）是選取使得， 這是一個關于單變量的函數求極小值問題，這樣確定的步長稱為最優(yōu)步長。變步長法（可接受點算法）是任意選取，只要使得即可。這種選取步長的方法，確保了目標函數的下降性質，盡管每次選取的步長不是最優(yōu)的，但實踐證明，方法能達到更好的數值效果?？傊斔阉鞣较虼_定以后

28、，步長就是決定最優(yōu)化算法好壞的重要因素，因此，我們必須特別注重步長的選取問題。（4）搜索算法的收斂性：搜索算法的收斂性是指，由某算法得到的點列能夠在有限步驟內收斂到目標函數的最優(yōu)點或能夠在有限步驟內達到滿足精度要求的目標函數的最優(yōu)點的近似值。顯然，只有具有收斂性質的算法才有意義。搜索算法的收斂速度：作為一個好的算法，還必須要求它以較快的速度收斂于最優(yōu)解。階收斂定義：對于收斂于最優(yōu)解的序列，若存在與無關的數和，當從某個開始時，有 成立，則稱序列收斂的階為，或稱階收斂。當時，稱迭代序列為線性收斂；當時，稱迭代序列為超線性收斂；當時，稱迭代序列為二階收斂。一般來說，線性收斂是比較慢的，而二階收斂則是

29、很快的，超線性收斂介于二者之間。如果一個算法具有超線性以上的收斂速度，我們就認為是一個好的算法了。42 無約束最優(yōu)化問題的梯度法無約束最優(yōu)化問題 的計算方法很多。無約束最優(yōu)化問題的計算方法分為兩大類：一類是解析法，包括經典最優(yōu)化方法，最速下降法（梯度法），共軛梯度法，牛頓法和變尺度法等。另一類是直接法，包括坐標輪換法，步長加速法，方向加速法和單純形法等。 所謂解析法就是在方法的計算過程中，應用到了函數的解析性質（可導性質等）；所謂直接法就是在方法的計算過程中，僅僅涉及目標函數值的計算，而不涉及函數導數等解析性質。我們在這里只介紹最速下降法（梯度法）。 最速下降法理論根據：早在1847年，法國著

30、名數學家Cauchy就曾提出，從任意給定點出發(fā)，函數沿哪個方向下降最快的問題。這個問題已從理論上解決了，即沿著函數在該點的負梯度方向前進時，函數下降最快。這就是最速下降法的理論根據。 最速下降法的搜索步驟：步驟1：選定初始點（越接近最優(yōu)點越好），允許誤差，令。步驟2：假定已得非最優(yōu)點，計算梯度，選取搜索方向 步驟3：選定搜索步長，滿足：。步驟4：判斷是否是最優(yōu)點或是滿足要求的近似解。根據精度要求，檢驗是否滿足收斂性判斷準則：或或 如果滿足給定精度要求，則搜索完成，近似最優(yōu)點為；如果不滿足給定精度要求，令返回（2）繼續(xù)搜索。例1：應用最速下降法求解。解：（1）選定初始點，允許誤差，置收斂判斷準則

31、 。（2）計算梯度，選取搜索方向 ， 第一點搜索計算：，（3）選定搜索步長，滿足： 第一點搜索計算：求最優(yōu)步長解得。（4）判斷是否是最優(yōu)點或是滿足要求的近似解。第一點搜索計算：驗證收斂判斷準則 ，不滿足，繼續(xù)搜索。依次類推，直到搜索到最優(yōu)解或滿足精度要求為止。搜索計算列表如下：搜索步長搜索方向 搜索點函數值為最優(yōu)解43 罰函數法對于約束最優(yōu)化問題也有許多種方法，本段只介紹把約束最優(yōu)化問題轉化為無約束最優(yōu)化問題的一種求解方法罰函數法。分為等式約束最優(yōu)化問題和不等式約束最優(yōu)化問題兩種情況討論。（1） 等式約束最優(yōu)化問題的罰函數法首先，考慮等式約束最優(yōu)化問題 假定上述等式約束最優(yōu)化問題的最優(yōu)解存在。

32、若記 ，構造輔助函數 罰函數其中（罰因子）是一個充分大的正數。定理1：若對于某確定數，無約束最優(yōu)化問題 的最優(yōu)解，則必為原等式約束最優(yōu)化問題的最優(yōu)解。證明：設無約束最優(yōu)化問題 的最優(yōu)解，則有： 而當時，所以即為原等式約束最優(yōu)化問題的最優(yōu)解。定理2：設和均為連續(xù)函數，若對于任意正數，無約束最優(yōu)化問題 的最優(yōu)解，且，則為原等式約束最優(yōu)化問題的最優(yōu)解。定理2的證明請參看有關參考資料。 根據定理1和定理2，我們就可以將通過構造罰函數的方法化為無約束最優(yōu)化問題求解，這種方法稱為罰函數法。罰函數法的步驟：（等式約束最優(yōu)化問題罰函數法）步驟1：構造罰函數 ， 選定，允許誤差，令；步驟2：求無約束問題 的最優(yōu)

33、解；步驟3：判斷是否是最優(yōu)點或是滿足要求的近似解。根據精度要求，檢驗是否滿足收斂性判斷準則： 或 如果滿足收斂性判斷準則，則，結束搜索；否則，令，取，返回（2），繼續(xù)搜索。下面我們通過一個簡單的例子來說明等式約束最優(yōu)化問題的罰函數法。例2：應用罰函數法求解非線性規(guī)劃問題 解：構造罰函數：求罰函數的最優(yōu)解：應用解析法， 令上述兩式等于零，解得 令得 為所求最優(yōu)解。（2） 不等式約束最優(yōu)化問題的罰函數法 對于，不等式約束最優(yōu)化問題 假定上述不等式約束最優(yōu)化問題的最優(yōu)解存在。 由于不等式約束條件等價于等式約束條件因而，上述不等式約束最優(yōu)化問題可以轉化為問題 類似問題（1）構造罰函數 則將上述等式約束

34、最優(yōu)化問題的求解轉化為下面無約束最優(yōu)化問題的求解： 定理3：若對于某確定數，無約束最優(yōu)化問題 的最優(yōu)解，則必為原不等式約束最優(yōu)化問題的最優(yōu)解，其中。定理4：設（1）和均為連續(xù)函數； （2）原不等式約束最優(yōu)化問題的最優(yōu)解存在； （3）數列滿足且； （4）對任意，問題的最優(yōu)解都存在，且有界； （5）點列存在極限點；則：點列的極限點是原不等式約束最優(yōu)化問題的最優(yōu)解。罰函數法的步驟：（不等式約束最優(yōu)化問題罰函數法）步驟1：構造罰函數 ， 選定，允許誤差，令；步驟2：求無約束問題 的最優(yōu)解；步驟3：判斷是否是最優(yōu)點或是滿足要求的近似解。根據精度要求，檢驗是否滿足收斂性判斷準則： 或 如果滿足收斂性判斷準

35、則，則，結束搜索；否則，令，取，返回（2），繼續(xù)搜索。例3：應用罰函數法求解非線性規(guī)劃問題 解：構造罰函數 求的極小值點 當時，顯然上兩式不能同時等于零，所以，此時不存在極小值點。 當時，有 令上面兩式等于零：，；解得的極小值點為 當取不同值時，可得到相應的值，計算如下表1101001000-0.25-0.04545-0.004950-0.00049950-0.4375-0.1415-0.004975-0.00049980根據定理得，原問題的極小值點為，極小值為。§5 多目標優(yōu)化問題在許多實際的最優(yōu)化問題中，常常遇到目標函數是幾個的情況，這一類問題我們稱之為多目標優(yōu)化問題。例如，投資

36、方向選擇問題，我們不僅要求投資的收益最大，而且要求投資的風險最小。再例如，購買商品問題，我們既要考慮商品的價格，又要考慮商品的質量，甚至還要考慮商品的性能等等。 所謂多目標優(yōu)化問題是指：目標函數是兩個或兩個以上的最優(yōu)化問題。其數學模型為： 目標函數 約束條件例1：求解多目標優(yōu)化問題 和 解：易求時，。例2：求解多目標優(yōu)化問題 和 解：顯然，無最優(yōu)解。51 多目標優(yōu)化問題的解多目標優(yōu)化問題解的存在性極其復雜，這是由多目標優(yōu)化問題的目標函數多個性和目標函數相互之間的復雜性質決定的。由于目標函數在很多情況下不可能同時達到最大值或最小值，因而，多目標最優(yōu)化問題很少有最優(yōu)解，而實際問題又要求我們做出決擇

37、，求得一個比較好的解。什么樣的解才是我們需要的解呢？對于同一個問題不同的要求導致不同的求解標準，從而就會得到不同的求解結果。為此，我們給出多目標最優(yōu)化問題的條件最優(yōu)解概念。最優(yōu)解：滿足約束條件且使所有目標函數達到要求的最大值或最小值的點稱為多目標優(yōu)化問題的最優(yōu)解?？尚薪猓簼M足多目標優(yōu)化問題的約束條件的點稱為可行解。條件最優(yōu)解：滿足多目標優(yōu)化問題的約束條件且滿足根據需要設定條件的可行解稱為條件最優(yōu)解。對于一個多目標優(yōu)化問題，即使最優(yōu)解存在，要求解它也是十分困難的，特殊情況下，我們也只好用搜索法求解。更何況它常常還不存在最優(yōu)解，因而我們必須尋求其求解條件最優(yōu)解的方法。為了求得滿足我們要求的解，常常

38、不得不設定一些新的條件，從而求得條件最優(yōu)解。設定新條件的方法是我們求解多目標優(yōu)化問題的基本方法。下面的“單目標化方法、多重目標函數方法和目標關聯函數方法”都是針對目標函數設定新條件的方法。52 單目標化解法 將原多目標優(yōu)化問題多個目標函數轉化成為只有一個目標函數的單目標優(yōu)化問題求解的方法稱為單目標化方法。（1）單目標化解法的基本思想步驟1：構造一個新的目標函數 滿足性質：在約束條件的區(qū)域內是的單調增函數。特別注意：構造新目標函數也可以根據實際問題，將定義為的不減函數。步驟2：建立單目標優(yōu)化數學模型 目標函數 約束條件步驟3：求解上述單目標優(yōu)化數學模型得到：單目標優(yōu)化問題的最優(yōu)解，從而可得到原多

39、目標優(yōu)化問題的最優(yōu)解或條件最優(yōu)解。（2） 單目標優(yōu)化問題最優(yōu)解的性質 單目標優(yōu)化問題的最優(yōu)解與原多目標最優(yōu)化問題的最優(yōu)解有著密切的內在關系。下面的定理揭示了兩者之間最重要的一種關系。定理1：設是的單調增函數，原多目標最優(yōu)化問題的最優(yōu)解存在，則單目標優(yōu)化問題 的最優(yōu)解存在，且為原多目標最優(yōu)化問題的最優(yōu)解。證明：顯然，單目標優(yōu)化問題的最優(yōu)解存在。設原多目標最優(yōu)化問題的最優(yōu)解為，則在該點處，目標函數都取得最小值。設單目標最優(yōu)化問題的最優(yōu)解為，則在該點處，目標函數取得最小值。顯然，1） 2） 又因為，是的單調增函數，根據1）有：所以， ，故必有 即為原多目標最優(yōu)化問題的最優(yōu)解。定理告訴我們：如果多目標

40、最優(yōu)化問題的最優(yōu)解存在，則只需求解一個單目標最優(yōu)化問題就可以得到。但是，如果多目標最優(yōu)化問題的最優(yōu)解不存在呢？則單目標最優(yōu)化問題的最優(yōu)解可能存在，也可能不存在。當原多目標最優(yōu)化問題的最優(yōu)解不存在，而單目標最優(yōu)化問題的最優(yōu)解存在時，我們稱解為單目標條件最優(yōu)解。這種解在一定程度上反應了原多目標最優(yōu)化問題的性質，因此，在實踐中常常被選用。（3） 單目標化的常用目標函數當多目標最優(yōu)化問題的最優(yōu)解不存在時，應用單目標化求解方法尋求條件最優(yōu)解，構造目標函數是關鍵。新的目標函數反應了原多目標之間的復雜關系，因而，必須根據實際問題構造目標函數，以比較準確地反應實際問題的性質。下面是幾種常用的目標函數。均衡優(yōu)化

41、函數 權重優(yōu)化函數 其中為大于零的權重系數平方和優(yōu)化函數 平方和均衡優(yōu)化函數 其中為大于零的權重系數例2：求解多目標優(yōu)化問題 和 解：問題涉及兩個目標函數，可應用單目標化方法求解。（1）構造單目標函數 （2）求解模型 得最優(yōu)解為，此時。（3）易知原問題最優(yōu)解存在（可通過作圖驗證），所以最優(yōu)解為，此時 ，。53 多重優(yōu)化解法 根據實際問題的性質，將原多目標優(yōu)化問題轉化成為多重單目標優(yōu)化問題的方法稱為多重優(yōu)化法。（1）多重優(yōu)化方法的基本思想 根據多目標優(yōu)化問題目標函數的性質，確定目標函數優(yōu)化對象和優(yōu)化次序。 建立多重優(yōu)化數學模型第一重優(yōu)化： 其中為中的某一函數 求解得解集為第二重優(yōu)化： 其中為中的

42、某一函數 求解得解集為依次類推，進行重優(yōu)化第重優(yōu)化： 其中為中的某一函數 求解得解集為，即為多重優(yōu)化問題的最優(yōu)解集。 原多目標優(yōu)化問題的最優(yōu)解集或條件最優(yōu)解集為。值得特別注意的是，我們不一定對所有目標函數進行多重優(yōu)化，也可以根據需要只選取某幾個目標函數進行多重優(yōu)化，甚至只選取某一個目標函數進行優(yōu)化。（2）多重優(yōu)化問題最優(yōu)解的性質 多重優(yōu)化問題的最優(yōu)解與原多目標最優(yōu)化問題的最優(yōu)解也有著密切的內在關系。下面的定理揭示了兩者之間的相互關系。定理2：設原多目標最優(yōu)化問題的最優(yōu)解存在，則多重優(yōu)化問題第一重優(yōu)化： 其中為中的某一函數 解集為第二重優(yōu)化： 其中為中的某一函數 解集為依次類推第重優(yōu)化： 其中為

43、中的某一函數 解集為的最優(yōu)解必存在，且為原多目標最優(yōu)化問題的最優(yōu)解。定理的證明留給讀者自己練習。例3：求解多目標優(yōu)化問題 和 解：問題涉及兩個目標函數，可應用多重優(yōu)化方法求解。（1）求解第一重優(yōu)化： 的解集為，此時（2）求解第二重優(yōu)化： 得解為，此時。（3）易知原問題最優(yōu)解存在（可以通過作圖驗證），所以最優(yōu)解為，此時，。54 目標關聯函數方法 在多目標最優(yōu)化問題數學模型中，如果我們只是選定某一個目標函數（稱為主目標）做為目標，而固定其余目標函數（稱為次目標）在允許取值范圍內為常數，則得到下列單目標優(yōu)化數學模型： 其中為中的某一函數，其中為的某排列 如果上述問題有解，則與其余目標函數的取值有關。

44、目標關聯函數方法的基本思想就是：固定某些目標函數的取值，求關于另一部分目標函數的最優(yōu)解的方法。 為了討論方便，我們以雙目標優(yōu)化問題為例來說明目標關聯函數方法的基本思想。雙目標優(yōu)化數學模型： （1）目標關聯函數定義目標關聯函數定義：選取目標函數作為主目標，作為次目標，固定，則得到單目標優(yōu)化數學模型： 記最優(yōu)值為，則為的函數，即，稱此函數為第一個目標關于第二個目標的目標關聯函數。也稱為主目標關于次目標的目標關聯函數。類似地，我們可以定義第二個目標關于第一個目標的目標關聯函數。（2）目標關聯函數的求解對不同的值，解數學模型： 得到目標關聯函數，為第一目標關于第二目標的關聯函數。注：關于的取值范圍，在

45、可行解集上（3）目標關聯函數的性質性質1：設第一目標關于第二目標的關聯函數為，如果原雙目標優(yōu)化問題最優(yōu)解存在，則必在所對應的點取得。性質2：如果目標關聯函數在處不取得最小值，則原雙目標優(yōu)化問題不存在最優(yōu)解。性質3：對于固定的值，目標關聯函數所對應取值點為原雙目標優(yōu)化問題在固定第二目標的條件下的條件最優(yōu)解。 上述三條性質比較簡單，證明都不難，讀者自己練習完成。（4）優(yōu)劣解的概念目標關聯函數還具有許多很好的性質，譬如單調函數的性質等等。當原雙目標優(yōu)化問題不存在最優(yōu)解時，應用目標關聯函數選取條件最優(yōu)解最有效。為了對條件最優(yōu)解有更深入的了解，下面我們引入優(yōu)劣解的概念。優(yōu)劣解的概念：設和為可行解，如果滿

46、足下列條件之一1），；2），；3），；則稱是比優(yōu)的解。性質4：任意可行解，要么對應目標關聯函數一取值點對應的可行解；要么總存在某目標關聯函數一取值點的可行解優(yōu)于該可行解。證明：以雙目標最優(yōu)化問題為例證明。 設為任意一可行解，記，目標函數關于目標函數的目標關聯函數為； 根據目標關聯函數的定義 。 設目標關聯函數在點處對應的可行解為，則，所以，要么是比劣的解，要么對應目標關聯函數一取值點對應的可行解。 根據性質4，我們求雙目標優(yōu)化問題的最優(yōu)解或條件最優(yōu)解，只需要求出它的兩個目標關聯函數，再根據目標關聯函數求解即可。（5） 條件最優(yōu)解的確定 一般來說，如果多目標優(yōu)化問題存在最優(yōu)解，我們就沒有必要應用

47、目標關聯函數法求解，只需要應用單目標優(yōu)化法或多重目標優(yōu)化法。如果多目標優(yōu)化問題不存在最優(yōu)解，那末我們就可以應用目標關聯函數法求其條件最優(yōu)解。為什么要求條件最優(yōu)解呢？這是因為多目標優(yōu)化問題現實生活中大量存在，需要解決，而它們往往又都不存在最優(yōu)解，因而尋求在一定條件下的最優(yōu)解。例如，“企業(yè)如何確定生產方案，使得資源消耗最少，而效益最大”問題、“投資公司如何確定投資方案，使得風險最少，而效益最大”問題、“公交公司如何確定公交車運營方案，使得乘客滿意度最大，而效益最好”問題等等，都是多目標優(yōu)化問題。顯然，這些問題都沒有最優(yōu)解。因此，我們只能夠尋求它們的條件最優(yōu)解。由目標關聯函數確定條件最優(yōu)解的方法分為

48、直接法和分析法。直接法：給定次目標函數的取值，直接求解關于主目標的對應單目標最優(yōu)化問題，得到條件最優(yōu)解。分析法：首先求出目標關聯函數；然后通過分析目標關聯函數的性質或圖形，選取條件最優(yōu)解。55 投資風險問題某投資公司有一定數量的資金進行投資，現有投資方向可供選擇。投資選擇和資金分配的原則為：總體收益盡可能大，總體風險盡可能小。已知：投資收益率，其中為投資的收益，為投資資金；投資風險率，其中為投資的風險；定義投資總體風險。投資方向收 益 率0.20.30.30.40.60.6風 險 率0.30.30.40.50.50.6試建立投資風險問題的數學模型，并根據上列數據計算選擇投資方向。 投資效益與風險問題建模一、問題分析（）問題的性質本問題是一個投資“關于效益與風險的雙目標”最優(yōu)化決策問題。必須在“總體收益盡可能大，總體風險盡可能小”的原則下確定投資方向，即確定每個投資方向的投資資金。（二）問題的主要因素 （1）每個投資方向的投資資金；（2）每個投資方向投資的收益率與收益； （3）每個投資方向投資的風險率與風險； （4）投資總收益； （5）投資總體風險。關鍵因素為投資總收益與投資總體風險。（三）解決問題的難點 從本實際問題出發(fā)，投資的收益與風險是一對矛盾。一般來說，投資的收益越大，風險就會越大。因此，根本不存在投資的收益最大，同時風險又最小的投資方案。怎