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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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