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

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

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

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

4、標(biāo)函數(shù)常用表示。當(dāng)目標(biāo)函數(shù)為某問(wèn)題的效益函數(shù)時(shí)，問(wèn)題即為求極大值；當(dāng)目標(biāo)函數(shù)為某問(wèn)題的費(fèi)用函數(shù)時(shí)，問(wèn)題即為求極小值等等。求極大值和極小值問(wèn)題實(shí)際上沒有原則上的區(qū)別，因?yàn)榍蟮臉O小值，也就是要求的極大值，兩者的最優(yōu)值在同一點(diǎn)取到。12 最優(yōu)化問(wèn)題分類 最優(yōu)化問(wèn)題種類繁多，因而分類的方法也有許多?？梢园醋兞康男再|(zhì)分類，按有無(wú)約束條件分類，按目標(biāo)函數(shù)的個(gè)數(shù)分類等等。 一般來(lái)說(shuō)，變量可以分為確定性變量，隨機(jī)變量和系統(tǒng)變量等等，相對(duì)應(yīng)的最優(yōu)化問(wèn)題分別稱為：普通最優(yōu)化問(wèn)題，統(tǒng)計(jì)最優(yōu)化問(wèn)題和系統(tǒng)最優(yōu)化問(wèn)題。 按有無(wú)約束條件分類：無(wú)約束最優(yōu)化問(wèn)題，有約束最優(yōu)化問(wèn)題。按目標(biāo)函數(shù)的個(gè)數(shù)分類：?jiǎn)文繕?biāo)最優(yōu)化問(wèn)題，多目標(biāo)

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

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

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

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

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

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

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

12、且偏導(dǎo)數(shù)都等于零，那么函數(shù)在這一點(diǎn)處也不一定取得極值。例如，函數(shù)在點(diǎn)處偏導(dǎo)數(shù)不存在，但在這一點(diǎn)處函數(shù)仍然取得極小值零。函數(shù)在點(diǎn)處偏導(dǎo)數(shù)存在，且偏導(dǎo)數(shù)都等于零，但在這一點(diǎn)處函數(shù)不取極值。定理1的作用在于，求出函數(shù)的可能極值點(diǎn)，然后，我們?cè)傺芯窟@些點(diǎn)是否取得極值。對(duì)于許多實(shí)際問(wèn)題來(lái)說(shuō)，函數(shù)一定能夠取得極大值或極小值，而函數(shù)的可能極值點(diǎn)（滿足必要條件的點(diǎn)）又只有一點(diǎn)，則這一點(diǎn)當(dāng)然是函數(shù)取得極大值或極小值的點(diǎn)。對(duì)于一般函數(shù)而言，我們?cè)鯓优卸ê瘮?shù)在某點(diǎn)是否取極值？是極大值？還是極小值？我們有下面的極值的充分條件定理。定理2（極值充分條件）：設(shè)元函數(shù)具有二階偏導(dǎo)數(shù)，則在處取得極值的充分條件為： （1）；

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

35、。例3：應(yīng)用罰函數(shù)法求解非線性規(guī)劃問(wèn)題解：構(gòu)造罰函數(shù) 求的極小值點(diǎn)當(dāng)時(shí)，顯然上兩式不能同時(shí)等于零，所以，此時(shí)不存在極小值點(diǎn)。 當(dāng)時(shí)，有令上面兩式等于零：，；解得的極小值點(diǎn)為當(dāng)取不同值時(shí)，可得到相應(yīng)的值，計(jì)算如下表1101001000-0.25-0.04545-0.004950-0.00049950-0.4375-0.1415-0.004975-0.00049980根據(jù)定理得，原問(wèn)題的極小值點(diǎn)為，極小值為。§5 多目標(biāo)優(yōu)化問(wèn)題在許多實(shí)際的最優(yōu)化問(wèn)題中，常常遇到目標(biāo)函數(shù)是幾個(gè)的情況，這一類問(wèn)題我們稱之為多目標(biāo)優(yōu)化問(wèn)題。例如，投資方向選擇問(wèn)題，我們不僅要求投資的收益最大，而且要求投資的風(fēng)險(xiǎn)

36、最小。再例如，購(gòu)買商品問(wèn)題，我們既要考慮商品的價(jià)格，又要考慮商品的質(zhì)量，甚至還要考慮商品的性能等等。 所謂多目標(biāo)優(yōu)化問(wèn)題是指：目標(biāo)函數(shù)是兩個(gè)或兩個(gè)以上的最優(yōu)化問(wèn)題。其數(shù)學(xué)模型為： 目標(biāo)函數(shù) 約束條件例1：求解多目標(biāo)優(yōu)化問(wèn)題 和解：易求時(shí)，。例2：求解多目標(biāo)優(yōu)化問(wèn)題 和解：顯然，無(wú)最優(yōu)解。51 多目標(biāo)優(yōu)化問(wèn)題的解多目標(biāo)優(yōu)化問(wèn)題解的存在性極其復(fù)雜，這是由多目標(biāo)優(yōu)化問(wèn)題的目標(biāo)函數(shù)多個(gè)性和目標(biāo)函數(shù)相互之間的復(fù)雜性質(zhì)決定的。由于目標(biāo)函數(shù)在很多情況下不可能同時(shí)達(dá)到最大值或最小值，因而，多目標(biāo)最優(yōu)化問(wèn)題很少有最優(yōu)解，而實(shí)際問(wèn)題又要求我們做出決擇，求得一個(gè)比較好的解。什么樣的解才是我們需要的解呢？對(duì)于同一個(gè)問(wèn)

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

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

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

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

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

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

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

44、函數(shù)的最優(yōu)解的方法。 為了討論方便，我們以雙目標(biāo)優(yōu)化問(wèn)題為例來(lái)說(shuō)明目標(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ù)為第一個(gè)目標(biāo)關(guān)于第二個(gè)目標(biāo)的目標(biāo)關(guān)聯(lián)函數(shù)。也稱為主目標(biāo)關(guān)于次目標(biāo)的目標(biāo)關(guān)聯(lián)函數(shù)。類似地，我們可以定義第二個(gè)目標(biāo)關(guān)于第一個(gè)目標(biāo)的目標(biāo)關(guān)聯(lián)函數(shù)。（2）目標(biāo)關(guān)聯(lián)函數(shù)的求解對(duì)不同的值，解數(shù)學(xué)模型：得到目標(biāo)關(guān)聯(lián)函數(shù)，為第一目標(biāo)關(guān)于第二目標(biāo)的關(guān)聯(lián)函數(shù)。注：關(guān)于的取值范圍，在可行解集上（3）目標(biāo)關(guān)聯(lián)函數(shù)的性質(zhì)性質(zhì)1：設(shè)第一目標(biāo)關(guān)于第二目標(biāo)的關(guān)聯(lián)函數(shù)為，如

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

46、應(yīng)目標(biāo)關(guān)聯(lián)函數(shù)一取值點(diǎn)對(duì)應(yīng)的可行解；要么總存在某目標(biāo)關(guān)聯(lián)函數(shù)一取值點(diǎn)的可行解優(yōu)于該可行解。證明：以雙目標(biāo)最優(yōu)化問(wèn)題為例證明。 設(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ù)在點(diǎn)處對(duì)應(yīng)的可行解為，則，所以，要么是比劣的解，要么對(duì)應(yīng)目標(biāo)關(guān)聯(lián)函數(shù)一取值點(diǎn)對(duì)應(yīng)的可行解。 根據(jù)性質(zhì)4，我們求雙目標(biāo)優(yōu)化問(wèn)題的最優(yōu)解或條件最優(yōu)解，只需要求出它的兩個(gè)目標(biāo)關(guān)聯(lián)函數(shù)，再根據(jù)目標(biāo)關(guān)聯(lián)函數(shù)求解即可。（5） 條件最優(yōu)解的確定 一般來(lái)說(shuō)，如果多目標(biāo)優(yōu)化問(wèn)題存在最優(yōu)解，我們就沒有必要應(yīng)用目標(biāo)關(guān)聯(lián)函數(shù)法求解，只需要應(yīng)用單目標(biāo)優(yōu)化法或多重目標(biāo)優(yōu)化法。如果多目標(biāo)優(yōu)化問(wèn)題不

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

48、化問(wèn)題，得到條件最優(yōu)解。分析法：首先求出目標(biāo)關(guān)聯(lián)函數(shù)；然后通過(guò)分析目標(biāo)關(guān)聯(lián)函數(shù)的性質(zhì)或圖形，選取條件最優(yōu)解。55 投資風(fēng)險(xiǎn)問(wèn)題某投資公司有一定數(shù)量的資金進(jìn)行投資，現(xiàn)有投資方向可供選擇。投資選擇和資金分配的原則為：總體收益盡可能大，總體風(fēng)險(xiǎn)盡可能小。已知：投資收益率，其中為投資的收益，為投資資金；投資風(fēng)險(xiǎn)率，其中為投資的風(fēng)險(xiǎn)；定義投資總體風(fēng)險(xiǎn)。投資方向收 益 率0.20.30.30.40.60.6風(fēng) 險(xiǎn) 率0.30.30.40.50.50.6試建立投資風(fēng)險(xiǎn)問(wèn)題的數(shù)學(xué)模型，并根據(jù)上列數(shù)據(jù)計(jì)算選擇投資方向。 投資效益與風(fēng)險(xiǎn)問(wèn)題建模一、問(wèn)題分析（）問(wèn)題的性質(zhì)本問(wèn)題是一個(gè)投資“關(guān)于效益與風(fēng)險(xiǎn)的雙目標(biāo)”最

49、優(yōu)化決策問(wèn)題。必須在“總體收益盡可能大，總體風(fēng)險(xiǎn)盡可能小”的原則下確定投資方向，即確定每個(gè)投資方向的投資資金。（二）問(wèn)題的主要因素 （1）每個(gè)投資方向的投資資金；（2）每個(gè)投資方向投資的收益率與收益； （3）每個(gè)投資方向投資的風(fēng)險(xiǎn)率與風(fēng)險(xiǎn)； （4）投資總收益； （5）投資總體風(fēng)險(xiǎn)。關(guān)鍵因素為投資總收益與投資總體風(fēng)險(xiǎn)。（三）解決問(wèn)題的難點(diǎn) 從本實(shí)際問(wèn)題出發(fā)，投資的收益與風(fēng)險(xiǎn)是一對(duì)矛盾。一般來(lái)說(shuō)，投資的收益越大，風(fēng)險(xiǎn)就會(huì)越大。因此，根本不存在投資的收益最大，同時(shí)風(fēng)險(xiǎn)又最小的投資方案。怎樣協(xié)調(diào)收益與風(fēng)險(xiǎn)之間的矛盾？這是解決該問(wèn)題的難點(diǎn)。（四）目標(biāo)函數(shù)的確定 根據(jù)“總體收益盡可能大，總體風(fēng)險(xiǎn)盡可能小”

50、的原則，建立數(shù)學(xué)模型時(shí)，我們的目標(biāo)函數(shù)必須以總體收益和總體風(fēng)險(xiǎn)為基礎(chǔ)。 （1）總體收益函數(shù) （2）總體風(fēng)險(xiǎn)函數(shù)（五）數(shù)學(xué)建模的思路 （1）思路1建立雙目標(biāo)優(yōu)化模型以“總體收益函數(shù)最大，總體風(fēng)險(xiǎn)函數(shù)最小”為目標(biāo)函數(shù)，建立雙目標(biāo)最優(yōu)化模型。由于題目所給數(shù)據(jù)反應(yīng)的“收益最大和風(fēng)險(xiǎn)最小”是矛盾的，因此，此模型無(wú)最優(yōu)解。但模型反應(yīng)了投資的追求，是建立其他模型的基礎(chǔ)。 （2）思路2建立單目標(biāo)優(yōu)化模型 引入新的函數(shù)，從一定程度上反應(yīng)“收益最大和風(fēng)險(xiǎn)最小”的目標(biāo)，將此函數(shù)做為目標(biāo)函數(shù)，建立單目標(biāo)優(yōu)化模型。 新的目標(biāo)函數(shù)應(yīng)該滿足：收益越大，函數(shù)值越大；風(fēng)險(xiǎn)越小，函數(shù)值越大。 （3）思路3建立多重優(yōu)化模型 對(duì)于投資者來(lái)說(shuō)，有的重視的是收益，而將風(fēng)險(xiǎn)做為第二考慮；有的則重視的是風(fēng)險(xiǎn)，而將收益做為第二考慮。根據(jù)這種投資者的兩種特點(diǎn)，我們可以分別建立兩種模型。一是建立“先優(yōu)化收益，再優(yōu)化風(fēng)險(xiǎn)”的重視收益二重優(yōu)化模型；二是建立“先優(yōu)化風(fēng)險(xiǎn)，再優(yōu)化收益”的重視風(fēng)險(xiǎn)二重優(yōu)化模型。 （4）思路4建立目標(biāo)關(guān)聯(lián)函數(shù)模型 對(duì)于有些投資者來(lái)說(shuō)，選擇投資方案的原則是：在固定總體風(fēng)險(xiǎn)的前提下，選擇收益最大的投資