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

1、. . - 優(yōu)選第六章最優(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ù)解法. . - 優(yōu)選55 投資收益風(fēng)險(xiǎn)問題第六章最優(yōu)化問題數(shù)學(xué)模型. . - 優(yōu)選 1 最優(yōu)化問題11 最優(yōu)化問題概念（1）最優(yōu)化問題在工業(yè)、農(nóng)業(yè)、交通運(yùn)輸、商業(yè)、國(guó)防、建筑、通信、政府機(jī)關(guān)等各部

2、門各領(lǐng)域的實(shí)際工作中， 我們經(jīng)常會(huì)遇到求函數(shù)的極值或最大值最小值問題，這一類問題我們稱之為 最優(yōu)化問題 。而求解最優(yōu)化問題的數(shù)學(xué)方法被稱為最優(yōu)化方法。它主要解決最優(yōu)生產(chǎn)計(jì)劃、最優(yōu)分配、最佳設(shè)計(jì)、最優(yōu)決策、最優(yōu)管理等求函數(shù)最大值最小值問題。最優(yōu)化問題的目的有兩個(gè)： 求出滿足一定條件下， 函數(shù)的極值或最大值最小值； 求出取得極值時(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、nxxx,21；我們常常也用),(21nxxxx表示。（3）約束條件在最優(yōu)化問題中，求目標(biāo)函數(shù)的極值時(shí)，變量必須滿足的限制稱為約束條件 。例如，許多實(shí)際問題變量要求必須非負(fù)，這是一種限制；在研究電路優(yōu)化設(shè)計(jì)問題時(shí)，變量必須服從電路基本定律，這也是一種限制等等。在研究問題時(shí)，這些限制我們必須用數(shù)學(xué)表達(dá)式準(zhǔn)確地描述它們。用數(shù)學(xué)語言描述約束條件一般來說有兩種：. . - 優(yōu)選等式約束條件mixgi,2, 1,0)(不等式約束條件rixhi,2, 1,0)(或rixhi,2, 1,0)(注：在最優(yōu)化問題研究中，由于解的存在性十分復(fù)雜，一般來說，我們不考慮不等式約束條件0)(xh或0)(xh。這兩種約束

4、條件最優(yōu)化問題最優(yōu)解的存在性較復(fù)雜。（4）目標(biāo)函數(shù)在最優(yōu)化問題中，與變量有關(guān)的待求其極值（或最大值最小值） 的函數(shù)稱為 目標(biāo)函數(shù)。目標(biāo)函數(shù)常用),()(21nxxxfxf表示。當(dāng)目標(biāo)函數(shù)為某問題的效益函數(shù)時(shí)，問題即為求極大值； 當(dāng)目標(biāo)函數(shù)為某問題的費(fèi)用函數(shù)時(shí)，問題即為求極小值等等。求極大值和極小值問題實(shí)際上沒有原則上的區(qū)別，因?yàn)榍?(xf的極小值，也就是要求)(xf的極大值，兩者的最優(yōu)值在同一點(diǎn)取到。12 最優(yōu)化問題分類最優(yōu)化問題種類繁多，因而分類的方法也有許多。可以按變量的性質(zhì)分類，按有無約束條件分類，按目標(biāo)函數(shù)的個(gè)數(shù)分類等等。一般來說， 變量可以分為確定性變量，隨機(jī)變量和系統(tǒng)變量等等，相對(duì)

5、應(yīng)的最優(yōu)化問題分別稱為：普通最優(yōu)化問題，統(tǒng)計(jì)最優(yōu)化問題和系統(tǒng)最優(yōu)化問題。按有無約束條件分類：無約束最優(yōu)化問題，有約束最優(yōu)化問題。按目標(biāo)函數(shù)的個(gè)數(shù)分類：?jiǎn)文繕?biāo)最優(yōu)化問題，多目標(biāo)最優(yōu)化問題。按約束條件和目標(biāo)函數(shù)是否是線性函數(shù)分類：線性最優(yōu)化問題 （線性規(guī)劃），. . - 優(yōu)選非線性最優(yōu)化問題（非線性規(guī)劃） 。按約束條件和目標(biāo)函數(shù)是否是時(shí)間的函數(shù)分類：靜態(tài)最優(yōu)化問題和動(dòng)態(tài)最優(yōu)化問題（動(dòng)態(tài)規(guī)劃）。按最優(yōu)化問題求解方法分類：解析法（間接法）圖克定理庫恩極大值原理有約束古典變分法古典微分法無約束數(shù)值算法（直接法）隨機(jī)搜索法單純形法方向加速法步長(zhǎng)加速法坐標(biāo)輪換法多維搜索法插值法黃金分割法斐波那西法一維搜索法

6、數(shù)值算法（梯度法）復(fù)形法法法化有約束為無約束梯度投影法可行方向法有約束梯度法變尺度法共軛梯度法擬牛頓法最速下降法無約束梯度法swiftsumt多目標(biāo)優(yōu)化方法目標(biāo)關(guān)聯(lián)函數(shù)法多重目標(biāo)化方法單目標(biāo)化方法網(wǎng)絡(luò)優(yōu)化方法13 最優(yōu)化問題的求解步驟和數(shù)學(xué)模型. . - 優(yōu)選（1）最優(yōu)化問題的求解步驟最優(yōu)化問題的求解涉及到應(yīng)用數(shù)學(xué)，計(jì)算機(jī)科學(xué)以及各專業(yè)領(lǐng)域等等，是一個(gè)十分復(fù)雜的問題， 然而它卻是需要我們重點(diǎn)關(guān)心的問題之一。怎樣研究分析求解這類問題呢？其中最關(guān)鍵的是建立數(shù)學(xué)模型和求解數(shù)學(xué)模型。一般來說，應(yīng)用最優(yōu)化方法解決實(shí)際問題可分為四個(gè)步驟進(jìn)行：步驟 1：建立模型提出最優(yōu)化問題，變量是什么？約束條件有那些？目

7、標(biāo)函數(shù)是什么？建立最優(yōu)化問題數(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)化問題數(shù)學(xué)模型最優(yōu)化問題的求解與其數(shù)學(xué)模型的類型密切相關(guān)，因而我們有必要對(duì)最優(yōu)化問題的數(shù)學(xué)模型有所掌握。一般來說，最優(yōu)化問題的常見數(shù)學(xué)模型有以下幾種：無約束最優(yōu)化問題數(shù)學(xué)模型由某實(shí)際問題設(shè)立變量， 建立一個(gè)目標(biāo)函數(shù)且無約束條件，這樣

8、的求函數(shù)極值或最大值最小值問題，我們稱為無約束最優(yōu)化問題 。其數(shù)學(xué)模型為：),(min21nxxxf目標(biāo)函數(shù). . - 優(yōu)選例如：求一元函數(shù))(xfy和二元函數(shù)),(yxfz的極值。又例如：求函數(shù)323121232221321242643),(xxxxxxxxxxxxf的極值和取得極值的點(diǎn)。有約束最優(yōu)化問題數(shù)學(xué)模型由某實(shí)際問題設(shè)立變量， 建立一個(gè)目標(biāo)函數(shù)和若干個(gè)約束條件（等式或不等式） ，這樣的求函數(shù)極值或最大值最小值問題，我們稱為有約束最優(yōu)化問題 。其數(shù)學(xué)模型為：),(min21nxxxf目標(biāo)函數(shù)mixxxgni, 2, 10),(21約束條件有約束最優(yōu)化問題的例子：求函數(shù)nxxxxxxf3

9、1321),(在約束條件條件nixxxxin,2, 1,0,200831下的最大值和取得最大值的點(diǎn)。線性規(guī)劃問題數(shù)學(xué)模型由某實(shí)際問題設(shè)立變量，建立一個(gè)目標(biāo)函數(shù)和若干個(gè)約束條件，目標(biāo)函數(shù)和約束條件都是變量的線性函數(shù)，而且變量是非負(fù)的， 這樣的求函數(shù)最大值最小值問題，我們稱為線性最優(yōu)化問題，簡(jiǎn)稱為線性規(guī)劃問題 。其標(biāo)準(zhǔn)數(shù)學(xué)模型為：nnnxcxcxcxxxf221121),(min目標(biāo)函數(shù)0, 2 , 12211iinimiixmibxaxaxa約束條件矩陣形式：xcxft)(min目標(biāo)函數(shù)0xbax約束條件其中tnxxxx),(21，tncccc),(21，tmbbbb),(21. . - 優(yōu)選m

10、nmmnnaaaaaaaaaa212222111211在線性規(guī)劃問題中，關(guān)于約束條件我們必須注意以下幾個(gè)問題。注 1：非負(fù)約束條件),2,1(0nixi，一般來說這是實(shí)際問題要求的需要。如果約束條件為iidx，我們作變量替換0iiidxz；如果約束條件為iidx，我們作變量替換0iiixdz。注 2：在線性規(guī)劃的標(biāo)準(zhǔn)數(shù)學(xué)模型中，約束條件為等式。如果約束條件不是等式， 我們引入松馳變量， 化不等式約束條件為等式約束條件。情況 1：若約束條件為inimiibxaxaxa2211，引入松馳變量02211inimiiibxaxaxaz原約束條件變?yōu)閕inimiibzxaxaxa2211。情況 2：若約

11、束條件為inimiibxaxaxa2211，引入松馳變量0)(2211nimiiiixaxaxabz原約束條件變?yōu)閕inimiibzxaxaxa2211在其它最優(yōu)化問題中， 我們也常常采取上述方法化不等式約束條件為等式約束條件。實(shí)際問題中， 我們經(jīng)常遇到兩類特殊的線性規(guī)劃問題。一類是：所求變量要求是非負(fù)整數(shù)， 稱為整數(shù)規(guī)劃問題 ；另一類是所求變量要求只取0或1，稱為 0-1規(guī)劃問題 。例如：整數(shù)規(guī)劃問題. . - 優(yōu)選213minxxz且為整數(shù)0,0285342213.3.21212xxxxxts。又例如： 0-1 規(guī)劃問題321523maxxxxz10,6434422. .321322132

12、1321或xxxxxxxxxxxxxts。非線性規(guī)劃問題數(shù)學(xué)模型由某實(shí)際問題設(shè)立變量， 建立一個(gè)目標(biāo)函數(shù)和若干個(gè)約束條件，如果目標(biāo)函數(shù)或約束條件表達(dá)式中有變量的非線性函數(shù)，那么，這樣的求函數(shù)最大值最小值問題，我們稱為非線性規(guī)劃最優(yōu)化問題， 簡(jiǎn)稱為 非線性規(guī)劃問題 。 其數(shù)學(xué)模型為：),(min21nxxxf目標(biāo)函數(shù)mixxxgni, 2, 10),(21約束條件其中目標(biāo)函數(shù)或約束條件中有變量的非線性函數(shù)。例如：非線性規(guī)劃問題yxyxf2)1(),(min0),(02),(21yyxgyxyxg。上述最優(yōu)化問題中，目標(biāo)函數(shù)是非線性函數(shù)，故稱為非線性規(guī)劃問題。前面介紹的四種最優(yōu)化數(shù)學(xué)模型都只有一個(gè)

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

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

15、是偏導(dǎo)數(shù)應(yīng)為導(dǎo)數(shù)；. . - 優(yōu)選注 2：定理只是在偏導(dǎo)數(shù)存在的前提下的必要條件。如果函數(shù)在某一點(diǎn)偏導(dǎo)數(shù)不存在，那在這一點(diǎn)處仍然可能取得極值；注 3：如果函數(shù)在某一點(diǎn)偏導(dǎo)數(shù)存在，且偏導(dǎo)數(shù)都等于零，那么函數(shù)在這一點(diǎn)處也不一定取得極值。例如，函數(shù)232),(yxyxf在點(diǎn))0 ,0(處偏導(dǎo)數(shù)不存在，但在這一點(diǎn)處函數(shù)仍然取得極小值零。函數(shù)53),(yxyxf在點(diǎn))0, 0(處偏導(dǎo)數(shù)存在，且偏導(dǎo)數(shù)都等于零，但在這一點(diǎn)處函數(shù)不取極值。定理 1 的作用在于， 求出函數(shù)的可能極值點(diǎn)，然后，我們?cè)傺芯窟@些點(diǎn)是否取得極值。對(duì)于許多實(shí)際問題來說， 函數(shù)一定能夠取得極大值或極小值，而函數(shù)的可能極值點(diǎn)（滿足必要條件的

16、點(diǎn)） 又只有一點(diǎn)， 則這一點(diǎn)當(dāng)然是函數(shù)取得極大值或極小值的點(diǎn)。對(duì)于一般函數(shù)而言， 我們?cè)鯓优卸ê瘮?shù)在某點(diǎn)是否取極值？是極大值？還是極小值？我們有下面的極值的充分條件定理。定理 2（極值充分條件）：設(shè)n元函數(shù)),()(21nxxxfxf具有二階偏導(dǎo)數(shù)，則)(xf在*xx處取得極值的充分條件為：（1）nixfxxi,3,20|*；（2）黑塞矩陣2222122222212212212212nxnnnxfxxfxxfxxfxfxxfxxfxxfxf在*xx處正定或負(fù)定；. . - 優(yōu)選（3）黑塞矩陣在*xx處正定時(shí)，函數(shù)取極小值； 負(fù)定時(shí)，函數(shù)取極大值。本章內(nèi)容簡(jiǎn)要講解理論， 注重實(shí)際應(yīng)用，對(duì)于許多經(jīng)

17、典的定理都不進(jìn)行證明，讀者可自己參看有關(guān)資料。例 1：求函數(shù)322123222132122462),(xxxxxxxxxxf的極值。解： （1）根據(jù)極值存在的必要條件，確定可能取得極值的點(diǎn)：21124xxxf，31222212xxxxf，23328xxxf令0321xfxfxf，解得)0 ,0 ,0(),(321xxx。（2) 根據(jù)極值存在的充分條件，確定)0,0 ,0(),(321xxx是否是極值點(diǎn)：計(jì)算4212xf，12222xf，8232xf；2212xxf，0312xxf，2322xxf；函數(shù)的黑塞矩陣為8202122024)0,0 ,0(2f因?yàn)?4，04412224，0320820

18、2122024；所以黑塞矩陣負(fù)定，故函數(shù)在)0,0 ,0(),(321xxx處取得極大值0)0,0,0(f。22 等式約束條件極值下面我們研究的是有若干個(gè)等式約束條件下，一個(gè)目標(biāo)函數(shù)的極值問題， 其數(shù)學(xué)模型為：),(min21nxxxf目標(biāo)函數(shù). . - 優(yōu)選mixxxgtsni,2, 10),(.21約束條件拉格朗日（ lagrange) 乘數(shù)法 ：（1）令),(),(21121nimiinxxxgxxxfl稱為上述問題的拉格朗日乘數(shù)函數(shù)，稱i為拉格朗日乘數(shù)。（2）設(shè)),(21nxxxf和),(21nixxxg均可微，則得到方程組nixxxglnjxgxfxlniimijiijj,2, 10

19、),(, 2, 10211（3）若),(2121mnxxx是上述方程組的解， 則點(diǎn)),(21nxxx可能為該問題的最優(yōu)點(diǎn)。拉格朗日（lagrange) 乘數(shù)法的本質(zhì)是： 將求有約束條件極值問題轉(zhuǎn)化為求無條件極值問題；所求得的點(diǎn)，即是取得極值的必要條件點(diǎn)。拉格朗日乘數(shù)法沒有解決極值的存在性問題，但是，如果拉格朗日乘數(shù)函數(shù)具有二階連續(xù)偏導(dǎo)數(shù)，我們也可以應(yīng)用黑塞矩陣來判定函數(shù)是否取得極值。在具體問題中， 點(diǎn)),(21nxxx是否為最優(yōu)點(diǎn)通常可由問題的實(shí)際意義決定。例 2：求表面積為定值2a，而體積為最大的長(zhǎng)方體的體積。解：設(shè)長(zhǎng)方體的三棱長(zhǎng)為zyx,，體積為 v ；建立數(shù)學(xué)模型如下：xyzvmax0,

20、 0,0222.2zyxayzxzxyts構(gòu)造拉格朗日乘數(shù)函數(shù))222(),(2axzyzxyxyzzyxl，則有. . - 優(yōu)選0)(20)(20)(2yxxyzlzxxzylzyyzxl解得azyx66，3366maxav為所求。23 不等式約束條件極值對(duì)于不等式約束條件極值問題：),(min21nxxxf目標(biāo)函數(shù)mixxxgtsni, 2, 10),(.21約束條件我們有與拉格朗日乘數(shù)法密切相關(guān)的方法庫恩圖克定理。定理 3 （庫恩圖克定理） ： 對(duì)于上述不等式約束條件極值問題， 設(shè)),(21nxxxf和),(21nixxxg均可微，令),(),(21121nimiinxxxgxxxfl假

21、設(shè)i存在，則在最優(yōu)點(diǎn)*xx),(21nxxx處，必滿足下述條件：（1）mijiijjnjxgxfxl1, 2, 10；（2）mixxxgni, 2, 10),(21；（3）mixxxgnii,2, 10),(21；（4）0i。根據(jù)庫恩圖克定理我們可以求解許多不等式約束條件極值問題，值得注意的是應(yīng)用庫恩圖克定理求解不等式約束條件極值問題，定理并沒有解決最優(yōu)解的存在性問題，因此，我們必須另行判斷。例 3：求解最優(yōu)化問題（最優(yōu)解存在）. . - 優(yōu)選yxyxf2)1(),(min0),(02),(21yyxgyxyxg解：構(gòu)造函數(shù))()2() 1(),(212yyxyxzyxl，根據(jù)庫恩圖克定理則有

22、0,000)2(010) 1(22121211yyxylxxl解得：1,0,0, 121yx；所求最優(yōu)解為)0, 1(),(yx，最優(yōu)值為 0。 3 線性規(guī)劃31 線性規(guī)劃設(shè)線性規(guī)劃標(biāo)準(zhǔn)數(shù)學(xué)模型為：nnnxcxcxcxxxf221121),(min目標(biāo)函數(shù)nixmibxaxaxatsiinimii,2 , 10, 2, 1.2211約束條件矩陣形式：xcxft)(min目標(biāo)函數(shù)0xbax約束條件其中tnxxxx),(21，tncccc),(21，tmbbbb),(21線性規(guī)劃問題的求解有一整套理論體系，一般來說，應(yīng)用單純形法求解。此方法盡管比較復(fù)雜， 然而在計(jì)算機(jī)上實(shí)現(xiàn)并不困難。解線性規(guī)劃問題

23、的單純形法已在許多數(shù)學(xué)計(jì)算軟件中實(shí)現(xiàn)，我們求解線性規(guī)劃問題可根據(jù)需要，應(yīng)用數(shù)學(xué)計(jì)算軟件求解即可。在此， 我們不系統(tǒng)研究其理論， 只是簡(jiǎn)單介紹線性規(guī)劃的窮舉. . - 優(yōu)選法和單純形法的基本思想。3.2 線性規(guī)劃的窮舉法（1）窮舉法基本原理和步驟步驟 1：將線性規(guī)劃問題化成矩陣的標(biāo)準(zhǔn)形式，設(shè)系數(shù)矩陣的秩mar)(，則對(duì)應(yīng)線性方程組的基礎(chǔ)解系自由變量的個(gè)數(shù)為mn個(gè)。步驟 2：窮舉法求解：令0)(21mniiixxx，解得對(duì)應(yīng)線性方程組一組解為),(21nxxx；對(duì)應(yīng)目標(biāo)函數(shù)值為infxxxf),(21。從n個(gè)變量x中選mn個(gè)作為自由變量， 令它們的值為 0，可得到mnnmncc組解。步驟 3：確定

24、最優(yōu)解：如果最優(yōu)解存在，則上述求解得到的對(duì)應(yīng)mnnmncc個(gè)目標(biāo)函數(shù)值中，最小者（或最大者）即為所求最小（或最大）最優(yōu)值，對(duì)應(yīng)的解為最優(yōu)解。步驟 4：證明解為最優(yōu)解：將最優(yōu)解對(duì)應(yīng)的自由變量看成參數(shù))(21,mnttt；解對(duì)應(yīng)線性方程組得nitbtbtbbxmnmniiiii,2, 1,)()(22110。將對(duì)應(yīng)線性方程組解nitbtbtbbxmnmniiiii,2, 1,)()(22110代入目標(biāo)函數(shù)得：)()(22110mnmntdtdtdff。如果nidi,2 ,1,0，則所求為最小值最優(yōu)解；否則，線性規(guī)劃問題無最小值最優(yōu)解。如果nidi,2 ,1,0，則所求為最大值最優(yōu)解；否則，線性規(guī)劃

25、問題無最大值最優(yōu)解。例 1：目標(biāo)函數(shù)：32132)(maxxxxxf. . - 優(yōu)選5, 4, 3 , 2, 1, 041025. .5242131ixxxxxxxxtsi解：約束條件的增廣矩陣為：100100102100101a，3)(ar；令021xx，解得5)(),4,10,5 ,0 ,0(xfx；令031xx，無解；令041xx，解得)1,0,5 ,5, 0(x，不滿足非負(fù)條件，舍去；令051xx，解得17)(),0 ,2,5 ,4,0(xfx；令032xx，解得10)(),4 ,5 ,0 ,0,5(xfx；令042xx，解得)4,0, 5,0,10(x，不滿足非負(fù)條件，舍去；令052

26、xx，無解；令043xx，解得235)(),23, 0, 0,25, 5(xfx；令053xx，解得)0 ,3,0 ,4, 5(x，不滿足非負(fù)條件，舍去；令054xx，解得19)(),0, 0, 3,4, 2(xfx；所以19)(maxxf，最優(yōu)解為)0,0, 3, 4,2(x。證明：令sxtx54,解得5 , 1,023422321ixstxsxstxi目標(biāo)函數(shù)stxf19)(；因?yàn)閟xtx54,非負(fù)，所以19)(maxxf，故最優(yōu)解存在。（2）單純形法基本原理和步驟. . - 優(yōu)選將線性規(guī)劃問題化成矩陣的標(biāo)準(zhǔn)形式，設(shè)系數(shù)矩陣的秩mar)(，則對(duì)應(yīng)線性方程組的基礎(chǔ)解系的個(gè)數(shù)為mn個(gè)，即有mn

27、個(gè)自由參數(shù)變量。選取mn個(gè)非基變量 （自由參數(shù)變量） ,不妨假設(shè)為nmjxj, 1,；解得線性規(guī)劃問題的 典式njxmixffmixxjnmjjjnmjjijii,2, 10), 2, 1(min), 2, 1(101定理 1：如果線性規(guī)劃問題的上述典式中所有nmjj, 1,0；則)0,0 ,(21mx為最優(yōu)解。定理 2：如果線性規(guī)劃問題的上述典式中存在某個(gè)0km，且對(duì)應(yīng)mikmi,2, 1,0)(；則線性規(guī)劃問題無最優(yōu)解。由定理 1 和定理 2 知，如果我們選擇適當(dāng)?shù)膍n個(gè)非基變量，就可以根據(jù)所求得的典式判斷最優(yōu)解的存在與否，從而求解該線性規(guī)劃問題。單純形法的思想是：選擇適當(dāng)?shù)幕儞Q（進(jìn)基和

28、退基），不斷地變換典式，使得典式中目標(biāo)函數(shù)值不斷下降，從而求得最優(yōu)解。 其核心為如何選擇進(jìn)基和退基。進(jìn)基規(guī)則和退基規(guī)則進(jìn)基規(guī)則 正檢驗(yàn)數(shù)最小下標(biāo)規(guī)則，即選取0|minjjs，由此確定sx為進(jìn)基。退基規(guī)則 ：選取這樣的下標(biāo)rj（ij表示第 i 個(gè)基變量的下標(biāo)）0|minisisi 0,|minisisiirjj. . - 優(yōu)選由此確定rjx離基。單純形法的基本步驟：步驟 1：化線性規(guī)劃問題為標(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)行基變換，

29、直到求出最優(yōu)解或判斷出無最優(yōu)解為止。例 2：解線性規(guī)劃問題212minxxf5 , 4, 3, 2, 1, 0212605.521421321ixxxxxxxxxxtsi解： （1）約束條件的增廣矩陣為：100260101100111a，3)(ar；所以非基變量個(gè)數(shù)為兩個(gè)。（2）選取21,xx作為非基變量，543,xxx作為基變量，解得典式為5, 1, 02min2621521215214213ixxxfxxxxxxxxxi不滿足最優(yōu)解定理和最優(yōu)解不存在定理的條件，故必須進(jìn)行基變換。（3）進(jìn)行基變換. . - 優(yōu)選選取進(jìn)基：01,0221，根據(jù)0|minjjs得1x為進(jìn)基。選取退基：62162

30、1,15min，根據(jù)0|minisisi， 0,|minisisiirjj得5x為離基。進(jìn)行基變換，求新基的典式：5, 1,031317min61312761342761322352521524523ixxxfxxxxxxxxxi判斷：不滿足最優(yōu)解定理和最優(yōu)解不存在定理的條件，故繼續(xù)進(jìn)行基變換。（4）繼續(xù)進(jìn)行基變換選取進(jìn)基：0312，根據(jù)0|minjjs得2x為進(jìn)基。選取退基：49221,821,49min，根據(jù)0|minisisi， 0,|minisisiirjj得3x為離基。進(jìn)行基變換，求新基的典式：5, 1,04121431min41214112122141234953531534532

31、ixxxfxxxxxxxxxi滿足最優(yōu)解定理的條件，根據(jù)定理最優(yōu)解為. . - 優(yōu)選431min),0,21, 0,49,411(fx。32 整數(shù)規(guī)劃設(shè)純整數(shù)線性規(guī)劃數(shù)學(xué)模型為：nnnxcxcxcxxxf221121),(min目標(biāo)函數(shù)nixxmibxaxaxatsiiinimii, 2, 1,0, 2, 1.2211為整數(shù)約束條件這一類問題與一般線性規(guī)劃比較起來，似乎是變簡(jiǎn)單了， 但實(shí)際上恰恰相反，由于解集是一些離散的整數(shù)點(diǎn)集，使得單純形法失去了應(yīng)用的基礎(chǔ)，求解變得困難而復(fù)雜。整數(shù)線性規(guī)劃目前還缺乏統(tǒng)一的解法，這里只介紹分枝定界法，它是目前求解純整數(shù)線性規(guī)劃和混合整數(shù)線性規(guī)劃最常用的方法，計(jì)

32、算機(jī)求解整數(shù)線性規(guī)劃的大多數(shù)程序也是以它為基礎(chǔ)的。分枝定界法：考慮上述純整數(shù)線性規(guī)劃問題，（1）解對(duì)應(yīng)線性規(guī)劃問題nnnxcxcxcxxxf221121),(min目標(biāo)函數(shù)nixmibxaxaxatsiinimii, 2, 10, 2, 1. .2211約束條件若無最優(yōu)解，則原純整數(shù)線性規(guī)劃問題無最優(yōu)解；若有最優(yōu)解，最優(yōu)點(diǎn)),(21nxxx，目標(biāo)函數(shù)最優(yōu)值),(210nxxxfz。若最優(yōu)點(diǎn)),(21nxxx全為整數(shù)，則為原純整數(shù)線性規(guī)劃問題的最優(yōu)解；若最優(yōu)點(diǎn)),(21nxxx不全為整數(shù)，則進(jìn)行下一步。（2）定界和分枝定界：00210),(minmzxxxfmn. . - 優(yōu)選其中0m取原純整數(shù)

33、線性規(guī)劃問題中，滿足約束條件的某一整數(shù)可行解所對(duì)應(yīng)的目標(biāo)函數(shù)值。原純整數(shù)線性規(guī)劃問題的最優(yōu)解必須滿足定界條件。分枝： 選取),(21nxxx中一個(gè)不為整數(shù)所對(duì)應(yīng)的kx 分枝，1rnixmibxaxaxaxxiinimiikk, 2 , 10, 2, 122112rnixmibxaxaxaxxiinimiikk,2, 10,2, 122111r和2r稱為對(duì)應(yīng)線性規(guī)劃問題的兩枝，也是兩個(gè)新線性規(guī)劃問題的約束條件。顯然，原純整數(shù)線性規(guī)劃問題的最優(yōu)解滿足1r或2r。（3）對(duì)1r和2r進(jìn)行剪枝和分枝解1r對(duì)應(yīng)的線性規(guī)劃問題，對(duì)其進(jìn)行剪枝和分枝：若無最優(yōu)解，則原純整數(shù)線性規(guī)劃問題在1r內(nèi)無最優(yōu)解。不需要對(duì)

34、該區(qū)域繼續(xù)討論 剪枝 。若有最優(yōu)解，最優(yōu)點(diǎn)),(21nxxx，目標(biāo)函數(shù)的最優(yōu)值),(211nxxxfz。若0211),(mxxxfzn，則原純整數(shù)線性規(guī)劃問題在1r內(nèi)無最優(yōu)解。 不需要對(duì)該區(qū)域繼續(xù)討論剪枝 。若最優(yōu)點(diǎn)),(21nxxx全為整數(shù)，則可能為原純整數(shù)線性規(guī)劃問題的最優(yōu)解，定界：記0211),(mxxxfmn，則0211),(minmxxxfmn，本分枝求解結(jié)束。若最優(yōu)點(diǎn)),(21nxxx不全為整數(shù)，對(duì)1r繼續(xù)進(jìn)行分枝。完全類似，解2r對(duì)應(yīng)線性規(guī)劃問題，對(duì)其進(jìn)行剪枝和分枝。依此類推，對(duì)所有分枝進(jìn)行求解，剪枝，分枝，定界；直至求得最優(yōu)解。. . - 優(yōu)選（4）最優(yōu)解的確定若某0mmk，則

35、為最優(yōu)解，求解結(jié)束。若所有分枝求解結(jié)束，則最后的上界km即為最優(yōu)解。例 3：應(yīng)用分枝定界法，求解整數(shù)線性規(guī)劃問題213minxxz且為整數(shù)0,0285342213.3.21212xxxxxts解：設(shè)原整數(shù)線性規(guī)劃問題目標(biāo)函數(shù)的最優(yōu)值為*z ，（1）求解線性規(guī)劃問題：213minxxz0,0285342213. 3.21212xxxxxts得最優(yōu)解為13.3,12.821xx；51.17min z。記約束區(qū)域0,0285342213.321212xxxxx為 r。（2）對(duì) r進(jìn)行分枝：選取最優(yōu)解中不是整數(shù)的變量，例如1x，將 r分成兩個(gè)子區(qū)域21,rr。0,0285342213.39:21212

36、11xxxxxxr，0, 0285342213. 38:2121212xxxxxxr（3）定界：確定最優(yōu)值*z 的上下界。由（1）中求得的最優(yōu)值知51.17*z；而*z的上界可由 r內(nèi)的任意一個(gè)可行解確定，例如，4,721xx即為一個(gè)可行解。故19* z。從而，19*51.17z。（4）在1r內(nèi)求最優(yōu)解，得13.3,921xx；39.18min z。. . - 優(yōu)選（5）在2r內(nèi)求最優(yōu)解，得21.3,821xx；62.17min z。（6）因?yàn)?r內(nèi)最優(yōu)解不全是整數(shù)，因而必須繼續(xù)對(duì)1r分枝：0, 0285342213. 394:212121211xxxxxxxr0, 0285342213. 3

37、93:212121212xxxxxxxr（7）顯然12r內(nèi)無解，剪枝。在11r內(nèi)求最優(yōu)解，得4,921xx；21min z；為整數(shù)可行解。但因19*51.17z，而1921，故剪枝。（8）因?yàn)?r內(nèi)最優(yōu)解不全是整數(shù)，因而必須繼續(xù)對(duì)2r分枝：0, 0285342213.384:212121221xxxxxxxr0,0285342213.383:212121222xxxxxxxr（9）顯然22r內(nèi)無解，剪枝。在21r內(nèi)求最優(yōu)解，得4,77.621xx；77.18min z。（10）因?yàn)?1r內(nèi)最優(yōu)解不全是整數(shù)，因而必須繼續(xù)對(duì)21r分枝：0,0285342213.3847:21212121211xx

38、xxxxxxr0,0285342213.3846:21212121212xxxxxxxxr（11）在212r內(nèi)求最優(yōu)解，得5.4,621xx；5.19min z。因5 .19min z大于*z 的上界，故剪枝。（12）在211r內(nèi)求最優(yōu)解，得4,721xx；19min z。. . - 優(yōu)選所求原整數(shù)規(guī)劃問題的最優(yōu)解為：4,721xx；19min z。 4 最優(yōu)化問題數(shù)值算法最優(yōu)化問題的數(shù)值算法很多，常用的算法多為搜索法，本節(jié)只介紹搜索法的基本思想、無約束最優(yōu)化問題的最速下降法（梯度法） 和有約束最優(yōu)化問題的罰函數(shù)法。41 搜索算法考慮無約束最優(yōu)化問題：),(min21nxxxf我們已經(jīng)討論了這

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

40、列kx收斂到目標(biāo)函數(shù))(xf的極小值點(diǎn)。（2）搜索算法的基本步驟：. . - 優(yōu)選選定初始點(diǎn)0x（越接近最優(yōu)點(diǎn)越好），允許誤差0 ，令0k。假定已得非最優(yōu)點(diǎn)kx，則選取一個(gè)搜索方向ks，滿足：目標(biāo)函數(shù))(xf下降，或0)(?kksxgradf。選定搜索步長(zhǎng)0k，kkkksxx1，滿足：)()()(1kkkkkxfsxfxf。判斷1kx是否是最優(yōu)點(diǎn)或是滿足要求的近似解。假定給定精度要求為0，常用確定求近似解搜索結(jié)束的方法有：|)(|1kxgradf梯度模確定法；|)()(|1kkxfxf目標(biāo)函數(shù)差值絕對(duì)誤差法；|1kkxx相鄰搜索點(diǎn)絕對(duì)誤差法。如果1kx滿足給定精度要求，則搜索完成，近似最優(yōu)點(diǎn)為

41、1*kxx；如果1kx不滿足給定精度要求，令1kk返回（ 2）繼續(xù)搜索。注意 1：我們的搜索算法一般得到的都是局部最優(yōu)解。注意 2：確定求近似解搜索結(jié)束的方法還有| )(|)()(|1kkkxfxfxf目標(biāo)函數(shù)差值相對(duì)誤差法；|1kkkxxx相鄰搜索點(diǎn)相對(duì)誤差法。（3）搜索算法的關(guān)鍵因素：從搜索算法的基本步驟中，我們知道，搜索算法的關(guān)鍵因素為：一是搜索方向，二是搜索步長(zhǎng)。搜索方向的選擇， 一般考慮既要使它盡可能的指向極小值點(diǎn)，又要不至于花費(fèi)太多的計(jì)算量。搜索步長(zhǎng)的選擇， 既要確保目標(biāo)函數(shù)的下降性質(zhì)，又要考慮近似解的精度要. . - 優(yōu)選求，還要考慮算法的計(jì)算量，問題十分復(fù)雜。常用方法有，固定步

42、長(zhǎng)法，最優(yōu)步長(zhǎng)法和變步長(zhǎng)法。固定步長(zhǎng)法（簡(jiǎn)單算法）是選取0k為固定值。方法簡(jiǎn)單，但是有時(shí)不能保證目標(biāo)函數(shù)的下降性質(zhì)。最優(yōu)步長(zhǎng)法（一維搜索算法）是選取k使得，)(min)(kkkkksxfsxf這是一個(gè)關(guān)于單變量的函數(shù)求極小值問題，這樣確定的步長(zhǎng)稱為最優(yōu)步長(zhǎng)。變步長(zhǎng)法（可接受點(diǎn)算法）是任意選取k，只要使得)()(1kkxfxf即可。這種選取步長(zhǎng)的方法， 確保了目標(biāo)函數(shù)的下降性質(zhì)， 盡管每次選取的步長(zhǎng)不是最優(yōu)的，但實(shí)踐證明，方法能達(dá)到更好的數(shù)值效果?？傊?dāng)搜索方向確定以后，步長(zhǎng)就是決定最優(yōu)化算法好壞的重要因素，因此，我們必須特別注重步長(zhǎng)的選取問題。（4） 搜索算法的收斂性： 搜索算法的收斂性是指

43、， 由某算法得到的點(diǎn)列kx能夠在有限步驟內(nèi)收斂到目標(biāo)函數(shù))(xf的最優(yōu)點(diǎn)或能夠在有限步驟內(nèi)達(dá)到滿足精度要求的目標(biāo)函數(shù))(xf的最優(yōu)點(diǎn)的近似值。顯然，只有具有收斂性質(zhì)的算法才有意義。搜索算法的收斂速度： 作為一個(gè)好的算法， 還必須要求它以較快的速度收斂于最優(yōu)解。階收斂定義 ：對(duì)于收斂于最優(yōu)解*x的序列kx，若存在與 k 無關(guān)的數(shù)0和1，當(dāng) k 從某個(gè)0k開始時(shí)，有|*|*|1xxxxkk成立，. . - 優(yōu)選則稱序列kx收斂的階為，或稱階收斂。當(dāng)1時(shí)，稱迭代序列kx為線性收斂；當(dāng)21時(shí)，稱迭代序列kx為超線性收斂；當(dāng)2 時(shí)，稱迭代序列kx為二階收斂。一般來說， 線性收斂是比較慢的，而二階收斂則是

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

45、根據(jù)：早在1847 年，法國(guó)著名數(shù)學(xué)家cauchy就曾提出，從任意給定點(diǎn)出發(fā)，函數(shù)沿哪個(gè)方向下降最快的問題。 這個(gè)問題已從理論上解決了，即沿著函數(shù)在該點(diǎn)的負(fù)梯度方向前進(jìn)時(shí)，函數(shù)下降最快。 這就是最速下降法的理論根據(jù)。最速下降法的 搜索步驟：步驟 1：選定初始點(diǎn)0x（越接近最優(yōu)點(diǎn)越好） ，允許誤差0，令0k。步驟 2：假定已得非最優(yōu)點(diǎn)kx，計(jì)算梯度)(kxgradf，. . - 優(yōu)選選取搜索方向)(kkxgradfs步驟 3：選定搜索步長(zhǎng)0k，kkkksxx1，滿足：)(min)(0kkkkksxfsxf。步驟 4：判斷1kx是否是最優(yōu)點(diǎn)或是滿足要求的近似解。根據(jù)精度要求，檢驗(yàn)是否滿足收斂性判斷

46、準(zhǔn)則：|)(|1kxgradf或|)()(|1kkxfxf或|1kkxx如果1kx滿足給定精度要求，則搜索完成，近似最優(yōu)點(diǎn)為1*kxx；如果1kx不滿足給定精度要求，令1kk返回（ 2）繼續(xù)搜索。例 1：應(yīng)用最速下降法求解222125)(minxxxf。解： （1）選定初始點(diǎn))2,2(0x，允許誤差2.0，置0:k收斂判斷準(zhǔn)則|)()(|1kkxfxf。（2）計(jì)算梯度)(kxgradf，選取搜索方向)(kkxgradfskxxkxxxgradf|50,2)(21，kxxkxxs|50,221第一點(diǎn)搜索計(jì)算：100,4)(0xgradf，100, 40s（3）選定搜索步長(zhǎng)0k，kkkksxx1，

47、滿足：)(min)(0kkkkksxfsxf第一點(diǎn)搜索計(jì)算：求最優(yōu)步長(zhǎng)22000)1002(25)42()(minsxf解得02.00。（4）判斷1kx是否是最優(yōu)點(diǎn)或是滿足要求的近似解。第一點(diǎn)搜索計(jì)算：)0 ,92.1(1x. . - 優(yōu)選驗(yàn)證收斂判斷準(zhǔn)則02.031.100|)()(|01xfxf，不滿足，繼續(xù)搜索。依次類推，直到搜索到最優(yōu)解或滿足精度要求為止。搜索計(jì)算列表如下：搜索步長(zhǎng)k搜索方向ks搜索點(diǎn)kx函數(shù)值)(kxf)2,2(0x10402.00100,40s)0,92.1 (1x69. 35.010 ,84.31s)0,0(2x00,02s)0,0(2x為最優(yōu)解43 罰函數(shù)法對(duì)于

48、約束最優(yōu)化問題也有許多種方法，本段只介紹把約束最優(yōu)化問題轉(zhuǎn)化為無約束最優(yōu)化問題的一種求解方法罰函數(shù)法。分為等式約束最優(yōu)化問題和不等式約束最優(yōu)化問題兩種情況討論。（1）等式約束最優(yōu)化問題的罰函數(shù)法首先，考慮等式約束最優(yōu)化問題)(minxfmixgtsi,2, 10)(.假定上述等式約束最優(yōu)化問題的最優(yōu)解存在。. . - 優(yōu)選若記,2, 1,0)(|nirxmixgxd，構(gòu)造輔助函數(shù)miixgmxfmxt12)()(),(罰函數(shù)其中0m（罰因子 ）是一個(gè)充分大的正數(shù)。定理 1：若對(duì)于某確定數(shù)0m，無約束最優(yōu)化問題miixgmxfmxt12)()(),(min的最優(yōu)解dx*，則*x必為原等式約束最優(yōu)

49、化問題的最優(yōu)解。證明：設(shè)無約束最優(yōu)化問題miixgmxfmxt12)()(),(min的最優(yōu)解dx*，則有：mixgi, 2, 10)(而當(dāng)dx時(shí)，)(),(xfmxt所以*)()*,(),(min)(minxfmxtmxtxf即*x為原等式約束最優(yōu)化問題的最優(yōu)解。定理 2：設(shè))(xf和mixgi,2, 1,0)(均為連續(xù)函數(shù)，若對(duì)于任意正數(shù)0m，無約束最優(yōu)化問題miixgmxfmxt12)()(),(min的最優(yōu)解dmx)(*，且*)(*limxmxm，則*)(*limxmxm為原等式約束最優(yōu)化問題的最優(yōu)解。定理 2 的證明請(qǐng)參看有關(guān)參考資料。根據(jù)定理 1 和定理 2，我們就可以將通過構(gòu)造罰

50、函數(shù)的方法化為無約束最優(yōu)化問題求解，這種方法稱為罰函數(shù)法 。. . - 優(yōu)選罰函數(shù)法的步驟：（等式約束最優(yōu)化問題罰函數(shù)法）步驟 1：構(gòu)造罰函數(shù)miixgmxfmxt12)()(),(，選定01m，允許誤差0，令1:k；步驟 2：求無約束問題),(minkmxt的最優(yōu)解*kx；步驟 3：判斷*kx是否是最優(yōu)點(diǎn)或是滿足要求的近似解。根據(jù)精度要求，檢驗(yàn)是否滿足收斂性判斷準(zhǔn)則：mixgki,2, 1,|)(|*或mikixg12*)(如果滿足收斂性判斷準(zhǔn)則，則*kxx，結(jié)束搜索；否則，令1:kk，取01kkmm，返回（ 2） ，繼續(xù)搜索。下面我們通過一個(gè)簡(jiǎn)單的例子來說明等式約束最優(yōu)化問題的罰函數(shù)法。例

51、 2：應(yīng)用罰函數(shù)法求解非線性規(guī)劃問題2221)(minxxxf01.2xts解：構(gòu)造罰函數(shù)：222221)1(),(xmxxmxtkk求罰函數(shù)的最優(yōu)解：應(yīng)用解析法112xxt，)1(22222xmxxtk令上述兩式等于零，解得kkmmxx1,021令km得1,021xx為所求最優(yōu)解。（2）不等式約束最優(yōu)化問題的罰函數(shù)法. . - 優(yōu)選對(duì)于，不等式約束最優(yōu)化問題)(minxfmixgtsi,2 ,10)(.假定上述不等式約束最優(yōu)化問題的最優(yōu)解存在。由于不等式約束條件mixgi,2, 1,0)(等價(jià)于等式約束條件mixgi,2, 1,0)(,0min(因而，上述不等式約束最優(yōu)化問題可以轉(zhuǎn)化為問題)

52、(minxfmixgtsi,2 ,10)(,0min(.類似問題（ 1）構(gòu)造罰函數(shù)miixgmxfmxt12)(,0min()(),(則將上述等式約束最優(yōu)化問題的求解轉(zhuǎn)化為下面無約束最優(yōu)化問題的求解：miixgmxfmxt12)(,0min()(),(min定理 3：若對(duì)于某確定數(shù)0m，無約束最優(yōu)化問題miixgmxfmxt12)(,0min()(),(min的最優(yōu)解dx*，則*x必為原不等式約束最優(yōu)化問題的最優(yōu)解，其中, 2, 1,0)(|nirxmixgxd。定理 4：設(shè)（1）)(xf和mixgi,2, 1,0)(均為連續(xù)函數(shù)；（2）原不等式約束最優(yōu)化問題的最優(yōu)解*x存在；（3）數(shù)列km滿

53、足kmmm210且kkmlim；. . - 優(yōu)選（4） 對(duì)任意0km， 問題),(minmxt的最優(yōu)解)(kkmxx都存在，且有界；（5）點(diǎn)列kx存在極限點(diǎn)；則：點(diǎn)列kx的極限點(diǎn)是原不等式約束最優(yōu)化問題的最優(yōu)解。罰函數(shù)法的步驟：（不等式約束最優(yōu)化問題罰函數(shù)法）步驟 1：構(gòu)造罰函數(shù)miixgmxfmxt12)(,0min()(),(，選定01m，允許誤差0，令1:k；步驟 2：求無約束問題),(minkmxt的最優(yōu)解*kx；步驟 3：判斷*kx是否是最優(yōu)點(diǎn)或是滿足要求的近似解。根據(jù)精度要求，檢驗(yàn)是否滿足收斂性判斷準(zhǔn)則：mixgki,2, 1,|)(|*或mikixg12*)(如果滿足收斂性判斷準(zhǔn)

54、則，則*kxx，結(jié)束搜索；否則，令1:kk，取01kkmm，返回（ 2） ，繼續(xù)搜索。例 3：應(yīng)用罰函數(shù)法求解非線性規(guī)劃問題21)(minxxxf0)(0)(. .122211xxgxxxgts解：構(gòu)造罰函數(shù)miixgmxfmxt12)(,0min()(),(),0min(),0min(),(21222121xxxmxxmxtkk求),(kmxt的極小值點(diǎn). . - 優(yōu)選), 0min()22,0min(21121311xxxxmxtk),0min(212212xxmxtk當(dāng)0,01221xxx或時(shí)，顯然上兩式不能同時(shí)等于零，所以，此時(shí)),(kmxt不存在極小值點(diǎn)。當(dāng)0,01221xxx時(shí)，有

55、1213112)22(21xmxxxmxtkk)(212212xxmxtk令上面兩式等于零：01xt，02xt；解得),(kmxt的極小值點(diǎn)為)21)22(1,221(2kkkkmmmx當(dāng)km取不同值時(shí)，可得到相應(yīng)的kx值，計(jì)算如下表km1 10 100 1000 km1x-0.25 -0.04545 -0.004950 -0.0004995 0 2x-0.4375 -0.1415 -0.004975 -0.0004998 0 根據(jù)定理得，原問題的極小值點(diǎn)為)0 ,0(*x，極小值為0*)(xf。. . - 優(yōu)選 5 多目標(biāo)優(yōu)化問題在許多實(shí)際的最優(yōu)化問題中， 常常遇到目標(biāo)函數(shù)是幾個(gè)的情況，這一

56、類問題我們稱之為多目標(biāo)優(yōu)化問題。例如，投資方向選擇問題，我們不僅要求投資的收益最大，而且要求投資的風(fēng)險(xiǎn)最小。再例如，購(gòu)買商品問題，我們既要考慮商品的價(jià)格，又要考慮商品的質(zhì)量，甚至還要考慮商品的性能等等。所謂多目標(biāo)優(yōu)化問題是指：目標(biāo)函數(shù)是兩個(gè)或兩個(gè)以上的最優(yōu)化問題。其數(shù)學(xué)模型為：sixxxfni,2 ,1),(min21目標(biāo)函數(shù). . - 優(yōu)選mixxxgni,2, 10),(21約束條件例 1：求解多目標(biāo)優(yōu)化問題2min x和ymin11.yxts解：易求1,0 yx時(shí)，0min2x，1min y。例 2：求解多目標(biāo)優(yōu)化問題2max x和ymin11.yxts解：顯然，無最優(yōu)解。51 多目標(biāo)優(yōu)

57、化問題的解多目標(biāo)優(yōu)化問題解的存在性極其復(fù)雜，這是由多目標(biāo)優(yōu)化問題的目標(biāo)函數(shù)多個(gè)性和目標(biāo)函數(shù)相互之間的復(fù)雜性質(zhì)決定的。由于目標(biāo)函數(shù)在很多情況下不可能同時(shí)達(dá)到最大值或最小值， 因而，多目標(biāo)最優(yōu)化問題很少有最優(yōu)解，而實(shí)際問題又要求我們做出決擇， 求得一個(gè)比較好的解。 什么樣的解才是我們需要的解呢？對(duì)于同一個(gè)問題不同的要求導(dǎo)致不同的求解標(biāo)準(zhǔn)，從而就會(huì)得到不同的求解結(jié)果。為此，我們給出多目標(biāo)最優(yōu)化問題的條件最優(yōu)解概念。最優(yōu)解：滿足約束條件且使所有目標(biāo)函數(shù)達(dá)到要求的最大值或最小值的點(diǎn)稱為多目標(biāo)優(yōu)化問題的最優(yōu)解。可行解：滿足多目標(biāo)優(yōu)化問題的約束條件的點(diǎn)稱為可行解。條件最優(yōu)解：滿足多目標(biāo)優(yōu)化問題的約束條件且滿

58、足根據(jù)需要設(shè)定條件的可行解稱為條件最優(yōu)解。. . - 優(yōu)選對(duì)于一個(gè)多目標(biāo)優(yōu)化問題， 即使最優(yōu)解存在，要求解它也是十分困難的，特殊情況下，我們也只好用搜索法求解。更何況它常常還不存在最優(yōu)解，因而我們必須尋求其求解條件最優(yōu)解的方法。為了求得滿足我們要求的解， 常常不得不設(shè)定一些新的條件，從而求得條件最優(yōu)解。設(shè)定新條件的方法是我們求解多目標(biāo)優(yōu)化問題的基本方法。下面的“單目標(biāo)化方法、 多重目標(biāo)函數(shù)方法和目標(biāo)關(guān)聯(lián)函數(shù)方法”都是針對(duì)目標(biāo)函數(shù)設(shè)定新條件的方法。52 單目標(biāo)化解法將原多目標(biāo)優(yōu)化問題多個(gè)目標(biāo)函數(shù)轉(zhuǎn)化成為只有一個(gè)目標(biāo)函數(shù)的單目標(biāo)優(yōu)化問題求解的方法稱為單目標(biāo)化方法。（1）單目標(biāo)化解法的基本思想步驟

59、1：構(gòu)造一個(gè)新的目標(biāo)函數(shù)),(21sfffff滿足性質(zhì)：在約束條件的區(qū)域內(nèi)),(21sffff是sfff,21的單調(diào)增函數(shù)。特別注意：構(gòu)造新目標(biāo)函數(shù)也可以根據(jù)實(shí)際問題，將),(21sffff定義為sfff,21的不減函數(shù)。步驟 2：建立單目標(biāo)優(yōu)化數(shù)學(xué)模型),(min21sfffff目標(biāo)函數(shù)mixxxgni,2,10),(21約束條件步驟 3：求解上述單目標(biāo)優(yōu)化數(shù)學(xué)模型得到：?jiǎn)文繕?biāo)優(yōu)化問題的最優(yōu)解，從而可得到原多目標(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)在. . - 優(yōu)選關(guān)系。下面的定理揭示了兩者之間最重要的

60、一種關(guān)系。定理 1：設(shè)),(21sffff是sfff,21的單調(diào)增函數(shù)，原多目標(biāo)最優(yōu)化問題的最優(yōu)解存在，則單目標(biāo)優(yōu)化問題),(min21sfffffmixxxgni,2,10),(21的最優(yōu)解存在，且為原多目標(biāo)最優(yōu)化問題的最優(yōu)解。證明：顯然，單目標(biāo)優(yōu)化問題的最優(yōu)解存在。設(shè)原多目標(biāo)最優(yōu)化問題的最優(yōu)解為*x，則在該點(diǎn)處，目標(biāo)函數(shù)sfff,21都取得最小值。設(shè)單目標(biāo)最優(yōu)化問題的最優(yōu)解為*y ，則在該點(diǎn)處，目標(biāo)函數(shù)),(21sffff取得最小值*)(yf。顯然， 1）siyfxfii,2 ,1*)(*)(2）*)(*)(yfxf又因?yàn)椋?,(21sffff是sfff,21的單調(diào)增函數(shù)，根據(jù) 1）有：*