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

1、第六章最優(yōu)化數(shù)學(xué)模型 1最優(yōu)化問題1.1最優(yōu)化問題概念2.2最優(yōu)化問題分類3.3最優(yōu)化問題數(shù)學(xué)模型 2經(jīng)典最優(yōu)化方法2.1無約束條件極值3.2等式約束條件極值4.3不等式約束條件極值3線性規(guī)劃3.1線性規(guī)劃5.2整數(shù)規(guī)劃4最優(yōu)化問題數(shù)值算法4.1直接搜索法4.2梯度法6.3罰函數(shù)法5多目標(biāo)優(yōu)化問題5.1多目標(biāo)優(yōu)化問題5.2單目標(biāo)化解法5.3多重優(yōu)化解法5.4目標(biāo)關(guān)聯(lián)函數(shù)解法7.5投資收益風(fēng)險(xiǎn)問題第六章最優(yōu)化問題數(shù)學(xué)模型 1最優(yōu)化問題1.1最優(yōu)化問題概念(1)最優(yōu)化問題在工業(yè)、農(nóng)業(yè)、交通運(yùn)輸、商業(yè)、國(guó)防、建筑、通信、政府機(jī)關(guān)等各部門各領(lǐng)域的實(shí)際工作中，我們經(jīng)常會(huì)遇到求函數(shù)的極值或最大值最小值問題

2、，這一類問題我們稱之為最優(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è)問題中涉及的變量為 x1,x2,xn;我們常常也用 X(x1,x2,xn)表示。(3)約束條件在

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

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

5、類：無約束最優(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)化問題(非線性規(guī)劃)。按約束條件和目標(biāo)函數(shù)是否是時(shí)間的函數(shù)分類： 靜態(tài)最優(yōu)化問題和動(dòng)態(tài)最優(yōu)化問題(動(dòng)態(tài)規(guī)劃)。按最優(yōu)化問題求解方法分類：無約束解析法(間接法)古典微分法古典變分法有約束極大值原理庫恩圖克定理變尺度法SUMT 法化有約束為無約束 SWIFT 法復(fù)形法單目標(biāo)化方法多目標(biāo)優(yōu)化方法多重目標(biāo)化方法目標(biāo)關(guān)聯(lián)函數(shù)法網(wǎng)絡(luò)優(yōu)化方法1.3 最優(yōu)化問題的求解步驟和數(shù)學(xué)模型（1）最優(yōu)化問題的求解步驟最優(yōu)化問題的求解涉及到應(yīng)用數(shù)學(xué)

6、，計(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)化問題， 變量是什么？約束條件有那些？目標(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í)效

7、性、穩(wěn)定性、靈敏性和誤差等等作出評(píng)價(jià)結(jié)果分析。（2）最優(yōu)化問題數(shù)學(xué)模型數(shù)值算法（直接法）斐波那西法一維搜索法黃金分割法插值法坐標(biāo)輪換法步長(zhǎng)加速法多維搜索法方向加速法單純形法隨機(jī)搜索法最速下降法無約束梯度法擬牛頓法共軻梯度法數(shù)值算法（梯度法）有約束梯度法可行方向法梯度投影法XiX3Xn2008,Xi0,i1,2,n 下的最大值和取得最大值的點(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é)模型為:minf(X1,X2,Xn)C1

8、X1C2X2CnXn目標(biāo)函數(shù)科的2xi0aimXnbii1,2,m矩陣形式：minf(X)CTXAXBX0-約束條件目標(biāo)函數(shù)約束條件其中 X(X1,X2,Xn)T,C(C1,C2,牛)二 B(匕心，瓦)丁在線性規(guī)劃問題中，關(guān)于約束條件我們必須注意以下幾個(gè)問題注1:非負(fù)約束條件Xi0(i1,2,n),一般來說這是實(shí)際問題要求的需要。如果約束條件為 xidi,我們作變量替換 ZiXidi0;如果約束條件為最優(yōu)化問題的求解與其數(shù)學(xué)模型的類型密切相關(guān)，因而我們有必要對(duì)最優(yōu)化問題的數(shù)學(xué)模型有所掌握。一般來說，最優(yōu)化問題的常見數(shù)學(xué)模型有以下幾種：無約束最優(yōu)化問題數(shù)學(xué)模型由某實(shí)際問題設(shè)立變量，建立一個(gè)目標(biāo)函

9、數(shù)且無約束條件，這樣的求函數(shù)極值或最大值最小值問題，我們稱為無約束最優(yōu)化問題。其數(shù)學(xué)模型為：minf(xi,X2,Xn)目標(biāo)函數(shù)例如：求一元函數(shù) yf(x)和二元函數(shù) zf(x,y)的極值。又例如：求函數(shù) f(Xi,X2,X3)3x24x26x322x1X24x1X32x2X3的極值和取得極值的點(diǎn)。有約束最優(yōu)化問題數(shù)學(xué)模型由某實(shí)際問題設(shè)立變量，建立一個(gè)目標(biāo)函數(shù)和若干個(gè)約束條件(等式或不等式)，這樣的求函數(shù)極值或最大值最小值問題，我們稱為有約束最優(yōu)化問題。其數(shù)學(xué)模型為：minf(xi,X2,Xn)gi(Xi,X2,Xn)0i1,2,m有約束最優(yōu)化問題的例子：求函數(shù) f(x1,x2,x3)X1X3

10、xn在約束條件條件目標(biāo)函數(shù)約束條件Xidi,我們作變量替換 ZidiXi0。注 2:在線性規(guī)劃的標(biāo)準(zhǔn)數(shù)學(xué)模型中，約束條件為等式。如果約束條件不是等式，我們引入松馳變量，化不等式約束條件為等式約束條件。情況 1:若約束條件為 ai1x1ai2x2aimxnbi,引入松馳變量原約束條件變?yōu)?ai1x1ai2x2aimxnZib在其它最優(yōu)化問題中，我們也常常采取上述方法化不等式約束條件為等式約束條件。實(shí)際問題中，我們經(jīng)常遇到兩類特殊的線性規(guī)劃問題。一類是：所求變量要求是非負(fù)整數(shù)，稱為整數(shù)規(guī)劃問題；另一類是所求變量要求只取0或1,稱為0-1規(guī)劃問題。例如：整數(shù)規(guī)劃問題x23.13s.t.22x134x

11、2285。x10,x20 且為整數(shù)又例如：0-1規(guī)劃問題 maxz3x12x2為4x2*3s.t.為x234x2x36非線性規(guī)劃問題數(shù)學(xué)模型由某實(shí)際問題設(shè)立變量，建立一個(gè)目標(biāo)函數(shù)和若干個(gè)約束條件，如果目標(biāo)函數(shù)或約束條件表達(dá)式中有變量的非線性函數(shù)，那么，這樣的求函數(shù)最大值最小值問題，我們稱為非線性規(guī)劃最優(yōu)化問題，簡(jiǎn)稱為非線性規(guī)劃問題。其數(shù)學(xué)模型為:minf(x1,x2,xn)目標(biāo)函數(shù)gi(x1，x2,xn)0i1,2,m其中目標(biāo)函數(shù)或約束條件中有變量的非線性函數(shù)。例如：非線性規(guī)劃問題 minf(x,y)(x1)2yg1(x,y)xy20g2(x,y)y0原約束條件變?yōu)?ai1x1ai2x2amX

12、nZibi。情況 2:若約束條件為 ai1x1ai2x2aimxnbi,引入松馳變量5x324x1,x2,x30或1。約束條件上述最優(yōu)化問題中，目標(biāo)函數(shù)是非線性函數(shù)，故稱為非線性規(guī)劃問題。前面介紹的四種最優(yōu)化數(shù)學(xué)模型都只有一個(gè)目標(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ù)最大值最小值問題，我們稱為多目標(biāo)最優(yōu)化問題。其數(shù)學(xué)模型為：minfi(x1,x2,xn)i1,2,s 目標(biāo)函數(shù)gi(Xi,X2,Xn)0i1,2,m 約束條件上述模型中有 s 個(gè)目標(biāo)函數(shù)，m

13、個(gè)等式約束條件。例如：“生產(chǎn)商如何使得產(chǎn)值最大而且消耗資源最少問題”“投資商如何使得投資收益最大而且風(fēng)險(xiǎn)最小問題”等都是多目標(biāo)最優(yōu)化問題。2經(jīng)典最優(yōu)化方法經(jīng)典最優(yōu)化方法包括無約束條件極值問題和等式約束條件極值問題兩種，不等式約束條件極值問題可以化為等式約束條件極值問題。經(jīng)典的極值理論：首先，根據(jù)可微函數(shù)取極值的必要條件確定可能極值點(diǎn)；其次，根據(jù)函數(shù)取極值的充分條件判斷是否取極值？是極大值？還是極小值？這種方法已經(jīng)幾百年的歷史了。2. 1無約束條件極值設(shè) n 元函數(shù) f(X)f(Xi,X2,Xn),求 f(X)的極值和取得極值的點(diǎn)。這是一個(gè)無約束條件極值問題，經(jīng)典的極值理論如下。定理1(極值必要

14、條件)：設(shè) n 元函數(shù) f(X)f(Xi,X2,4)具有偏導(dǎo)數(shù)，則 f(X)在XX*處取得極值的必要條件為:定理在此不給出證明，讀者可自己參看有關(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ù)存在，且偏導(dǎo)數(shù)都等于零，那么函數(shù)在這一點(diǎn)處也不一定取得極值。例如，函數(shù)f(X,y)VX2y2在點(diǎn)(0,0)處偏導(dǎo)數(shù)不存在，但在這一點(diǎn)處函數(shù)仍然取得極小值零。函數(shù) f(x,y)x3y5在點(diǎn)(0,0)處偏導(dǎo)數(shù)存在，且偏導(dǎo)數(shù)都等于零，但在這一點(diǎn)處函數(shù)不取極值

15、。定理1的作用在于，求出函數(shù)的可能極值點(diǎn)，然后，我們?cè)傺芯窟@些點(diǎn)是否取得極值。fXi1XX,i1,2,no對(duì)于許多實(shí)際問題來說，函數(shù)一定能夠取得極大值或極小值，而函數(shù)的可能極值點(diǎn)(滿足必要條件的點(diǎn))又只有一點(diǎn)，則這一點(diǎn)當(dāng)然是函數(shù)取得極大值或極小值的點(diǎn)。對(duì)于一般函數(shù)而言，我們?cè)鯓优卸ê瘮?shù)在某點(diǎn)是否取極值？是極大值？還是極小值？我們有下面的極值的充分條件定理。定理 2(極值充分條件)：設(shè) n 元函數(shù) f(x)f(x1,x2,xj 具有二階偏導(dǎo)數(shù)，則f(X)在XX*處取得極值的充分條件為:(1)flxx*0i2,3,n;XiXiXn2fX2Xn在XX處正止或負(fù)止;*一、一.、一(3)黑塞矩陣在XX處

16、正定時(shí)，函數(shù)取極小值；負(fù)定時(shí)，函數(shù)取極大值。本章內(nèi)容簡(jiǎn)要講解理論，注重實(shí)際應(yīng)用，對(duì)于許多經(jīng)典的定理都不進(jìn)行證明，讀者可自己參看有關(guān)資料。例 i:求函數(shù) f(x),x2,x3)2x26x；4x22xix22x2x3的極值。解：(i)根據(jù)極值存在的必要條件，確定可能取得極值的點(diǎn):令,ff0,解得(ox2%)(0,0,0)XiX2X3(2)黑塞矩陣2f2f2-XiXiX22f2f2-X2XiX22f2f2fXnXiXXX22f-2XnfXi4X12X2,fX212X22 為2X3,fX38X32X2(2)根據(jù)極值存在的充分條件，確定(Xi,X2,X3)(0,0,0)是否是極值點(diǎn):2f計(jì)算-fXi4,

17、2fX2i2,2f2X38；2f2,2f。，二2；xix2XX3X2X3420函數(shù)的黑塞矩陣為2f(0,0,0)2122028442因?yàn)?0,440,22120所以黑塞矩陣負(fù)定,2.2等式約束條件極值下面我們研究的是有若干個(gè)等式約束條件下，一個(gè)目標(biāo)函數(shù)的極值問題，其數(shù)學(xué)模型為：minf(x1,x2,xn)目標(biāo)函數(shù)s.t.gi(xi,x2,xn)0i1,2,m 約束條件拉格朗日(Lagrange)乘數(shù)法：m(1)令 Lf(XI,x2,xn)igi(XI,*2,xn)i1稱為上述問題的拉格朗日乘數(shù)函數(shù)，稱i為拉格朗日乘數(shù)。(2)設(shè) f(X1，X2,多川口 gi(X1,X2,Xn)均可微,則得到方程

18、組(3)若(XI,X2,Xn,1,2,m)是上述方程組的解,則點(diǎn)(XI,X2,Xn)可能為該問題的最優(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)(W,Xj是否為最優(yōu)點(diǎn)通?？捎蓡栴}的實(shí)際意義決定。例2：求表面積為定值 a2,而體積為最大的長(zhǎng)方體的體積。解：設(shè)長(zhǎng)方體的三棱長(zhǎng)為x,y,z,體積為V;建立數(shù)學(xué)模型如下：maxVxyz構(gòu)造拉格朗日乘數(shù)函數(shù) L(x,y,

19、z)xyz(2xy2yz2xza2),則有20122283200；故函數(shù)在(x1,x2,X3)(0,0,0)處取得極大值f(0,0,0)0。解得 xyzamaxVa 為所求。6362.3不等式約束條件極值對(duì)于不等式約束條件極值問題：minf(xi,X2,Xn)目標(biāo)函數(shù)s.t.gi(x1,x2,xn)0i1,2,m 約束條件我們有與拉格朗日乘數(shù)法密切相關(guān)的方法庫恩圖克定理。定理 3(庫恩圖克定理)：對(duì)于上述不等式約束條件極值問題，設(shè) f(x1,x2,xn)m和 gi(x1,x2,1 門丹勻可微，令 Lf(x1,x2,xn)igi(x1,x2,xn)i1*k,_.X(x1,x2,xn)處，必潴足下

20、述條件:Ifm。；(1)i-g10j1,2,n；xjxji1xj(4)i0o根據(jù)庫恩圖克定理我們可以求解許多不等式約束條件極值問題，值得注意的是應(yīng)用庫恩一圖克定理求解不等式約束條件極值問題，定理并沒有解決最優(yōu)解的存在性問題，因此，我們必須另行判斷。例3:求解最優(yōu)化問題(最優(yōu)解存在)解：構(gòu)造函數(shù) L(x,y,z)(x1)2y1(xy2)2(y),2(x1)10 x,1120根據(jù)庫恩圖克定理則有y1(xy2)02y010,20解得：x1,y0,10,21；所求最優(yōu)解為(x,y)(1,0),最優(yōu)值為0。3線性規(guī)劃3. 1線性規(guī)劃假設(shè)i存在，則在最優(yōu)點(diǎn)X(2)gi(x1,x2,xn)0i1,2,m；(

21、3)igi(x1,x2,xn)0i1,2,m；設(shè)線性規(guī)劃標(biāo)準(zhǔn)數(shù)學(xué)模型為:線性規(guī)劃問題的求解有一整套理論體系，一般來說，應(yīng)用單純形法求解。此方法盡管比較復(fù)雜，然而在計(jì)算機(jī)上實(shí)現(xiàn)并不困難。解線性規(guī)劃問題的單純形法已在許多數(shù)學(xué)計(jì)算軟件中實(shí)現(xiàn)，我們求解線性規(guī)劃問題可根據(jù)需要，應(yīng)用數(shù)學(xué)計(jì)算軟件求解即可。在此，我們不系統(tǒng)研究其理論，只是簡(jiǎn)單介紹線性規(guī)劃的窮舉法和單純形法的基本思想。3.2線性規(guī)劃的窮舉法(1)窮舉法基本原理和步驟步驟 1:將線性規(guī)劃問題化成矩陣的標(biāo)準(zhǔn)形式，設(shè)系數(shù)矩陣的秩 R(A)m,則對(duì)應(yīng)線性方程組的基礎(chǔ)解系自由變量的個(gè)數(shù)為 nm 個(gè)(X1,X2,Xn)；對(duì)應(yīng)目標(biāo)函數(shù)值為f(X1,X2,X

22、n)fj。從 n 個(gè)變量X中選 nm 個(gè)作為自由變量，令它們的值為 0,可得到 CmC；m組解。步驟 3:確定最優(yōu)解：如果最優(yōu)解存在，則上述求解得到的對(duì)應(yīng) CmCm個(gè)目標(biāo)函數(shù)值中，最小者(或最大者)即為所求最小(或最大)最優(yōu)值，對(duì)應(yīng)的解為最優(yōu)解。步驟 4:證明解為最優(yōu)解：將最優(yōu)解對(duì)應(yīng)的自由變量看成參數(shù)匕&，m)；解對(duì)應(yīng)線性方程組得1.狐3i1t102%A(nm)%m),i1,2,n。將對(duì)應(yīng)線性方程組解 Xibi0*1bi2t2bi(nm)t(nm),i1,2,n代入目標(biāo)函數(shù)得：ff0d1t1d2t2d(nm)t(nm)o如果 d0,i1,2,n，則所求為最小值最優(yōu)解；否則，線性規(guī)劃問題

23、無最minf(xi,X2,Xn)C1X1C2X2cnxn目標(biāo)函數(shù)s.t.a*Xai2X20amXnbi1,2,mi1,2,n約束條件矩陣形式：minf(X)CTX目標(biāo)函數(shù)AXBX0約束條件其中(X1,X2,Xn)T,C(C1,C2,牛)丁,B(“，132,瓦),步驟2:窮舉法求解：令XMXi2Xi(nm)0,解得對(duì)應(yīng)線性方程組一組解為小值最優(yōu)解如果 di0,i1,2,n,則所求為最大值最優(yōu)解；否則，線性規(guī)劃問題無最大值最優(yōu)解。例 1:目標(biāo)函數(shù)：maxf(X)2x13x2x3解：約束條件的增廣矩陣為:1010010,R(A)3;01(0,0,5,10,4),f(X)5;令 x1x40,解得 X(

24、0,5,5,0,1),不滿足非負(fù)條件，舍去;(0,4,5,2,0),f(X)17;令 x2*50,無解；5335令 x3x4。，解得X(5,5,0,0,2),f(X)萬；令乂3x50,解得 X(5,4,0,3,0),不滿足非負(fù)條件，舍去;(2,4,3,0,0),f(X)19;所以 maxf(X)19,最優(yōu)解為 X(2,4,3,0,0)0證明：令 x4t,x5s 解得x12t2sx24s目標(biāo)函數(shù) f(X)19ts；x33t2sxi0,i1,5因?yàn)?x4t,x5s 非負(fù)，所以 maxf(X)19,故最優(yōu)解存在。(2)單純形法基本原理和步驟將線性規(guī)劃問題化成矩陣的標(biāo)準(zhǔn)形式，設(shè)系數(shù)矩陣的秩 R(A)m

25、,則對(duì)應(yīng)線令 x2x30,解得 X(5,0,0,5,4),f(X)10;令 x2x4(10,0,5,0,4),不滿足非負(fù)條件，舍去;性方程組的基礎(chǔ)解系的個(gè)數(shù)為 nm 個(gè)，即有 nm 個(gè)自由參數(shù)變量。選取 nm 個(gè)非基變量（自由參數(shù)變量）,不妨假設(shè)為 Xj,jm1,n；解得線性規(guī)劃問題的典式定理 1:如果線性規(guī)劃問題的上述典式中所有j0,jm1,n；則 X（1,2,m,0,0）為最優(yōu)解。定理2：如果線性規(guī)劃問題的上述典式中存在某個(gè)mk0,且對(duì)應(yīng)i（mk）0,i1,2,m；則線性規(guī)劃問題無最優(yōu)解。由定理1和定理2知，如果我們選擇適當(dāng)?shù)?nm 個(gè)非基變量，就可以根據(jù)所求得的典式判斷最優(yōu)解的存在與否，

26、從而求解該線性規(guī)劃問題。單純形法的思想是：選擇適當(dāng)?shù)幕儞Q（進(jìn)基和退基），不斷地變換典式，使得典式中目標(biāo)函數(shù)值不斷下降，從而求得最優(yōu)解。其核心為如何選擇進(jìn)基和退基。進(jìn)基規(guī)則和退基規(guī)則進(jìn)基規(guī)則一一正檢驗(yàn)數(shù)最小下標(biāo)規(guī)則，即選取 sminj|j0,由此確定 Xs為進(jìn)基。退基規(guī)則：選取這樣的下標(biāo) J,（J 表示第i個(gè)基變量的下標(biāo)）由此確定 Xjr離基。單純形法的基本步驟：步驟 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)行基變換，

27、直到求出最優(yōu)解或判斷出無最優(yōu)解為止。例 2:解線性規(guī)劃問題解：（1）約束條件的增廣矩陣為：11100A11010,R（A）3;62001所以非基變量個(gè)數(shù)為兩個(gè)。（2）選取 X1,X2作為非基變量，X3,X4,X5作為基變量，解得典式為不滿足最優(yōu)解定理和最優(yōu)解不存在定理的條件，故必須進(jìn)行基變換。（3）進(jìn)行基變換選取進(jìn)基:20,根據(jù) sminj|j0得 X1為進(jìn)基根據(jù) min|is0,JrminJJ，1s0得 x5為離基。isis進(jìn)行基變換，求新基的典式：判斷：不滿足最優(yōu)解定理和最優(yōu)解不存在定理的條件，故繼續(xù)進(jìn)行基變換(4)繼續(xù)進(jìn)行基變換選取進(jìn)基：210，根據(jù) sminj|j0得*2為進(jìn)基進(jìn)行基變

28、換，求新基的典式：滿足最優(yōu)解定理的條件，根據(jù)定理最優(yōu)解為V,119c131X(一,一,0,0),minfo44243.2整數(shù)規(guī)劃設(shè)純整數(shù)線性規(guī)劃數(shù)學(xué)模型為：這一類問題與一般線性規(guī)劃比較起來，似乎是變簡(jiǎn)單了，但實(shí)際上恰恰相反，由于解集是一些離散的整數(shù)點(diǎn)集，使得單純形法失去了應(yīng)用的基礎(chǔ)，求解變得困難而復(fù)雜。整數(shù)線性規(guī)劃目前還缺乏統(tǒng)一的解法，這里只介紹分枝定界法，它是目前求解純整數(shù)線性規(guī)劃和混合整數(shù)線性規(guī)劃最常用的方法,性規(guī)劃的大多數(shù)程序也是以它為基礎(chǔ)的。分枝定界法：考慮上述純整數(shù)線性規(guī)劃問題，(1)解對(duì)應(yīng)線性規(guī)劃問題若無最優(yōu)解，則原純整數(shù)線性規(guī)劃問題無最優(yōu)解；若有最優(yōu)解，最優(yōu)點(diǎn)(x1,x2,xn)

29、,目標(biāo)函數(shù)最優(yōu)值選取退基:.,5min彳,2166，選取退基:min皚48根據(jù)min|is0,JrminJi|isisis0得 x3為離基。minf(x1,x2,xn)c1x1c2x2cnxn目標(biāo)函數(shù)anx1ai2x2stX0,xi為整數(shù)aimxnbii1,2,mi1,2,n約束條件計(jì)算機(jī)求解整數(shù)線minf(x1,x2,xn)c1x1c2x2cnxn目標(biāo)函數(shù)s.t.ai*ai2x2x0aimxnhi1,2,mi1,2,n約束條件Z0f(XI,x2,xn)。若最優(yōu)點(diǎn)(XI,X2,xn)全為整數(shù)，則為原純整數(shù)線性規(guī)劃問題的最優(yōu)解;若最優(yōu)點(diǎn)(Xi,X2,Xn)不全為整數(shù)，則進(jìn)行下一步。(2)定界和分

30、枝定界：M0minf(x1,x2,xn)z0m0其中 Mo取原純整數(shù)線性規(guī)劃問題中， 滿足約束條件的某一整數(shù)可行解所對(duì)應(yīng)的目標(biāo)函數(shù)值。原純整數(shù)線性規(guī)劃問題的最優(yōu)解必須滿足定界條件。分枝：選取(x1,x2,xn)中一個(gè)不為整數(shù)所對(duì)應(yīng)的xk分枝，Ri和 R2稱為對(duì)應(yīng)線性規(guī)劃問題的兩枝，也是兩個(gè)新線性規(guī)劃問題的約束條件。顯然，原純整數(shù)線性規(guī)劃問題的最優(yōu)解滿足或七。(3)對(duì) Ri和 R2進(jìn)行剪枝和分枝解 Ri對(duì)應(yīng)的線性規(guī)劃問題，對(duì)其進(jìn)行剪枝和分枝：若無最優(yōu)解，則原純整數(shù)線性規(guī)劃問題在 Ri內(nèi)無最優(yōu)解。不需要對(duì)該區(qū)域繼續(xù)討論一一剪枝。若有最優(yōu)解，最優(yōu)點(diǎn)(x1,x2,xn),目標(biāo)函數(shù)的最優(yōu)值z(mì)if(xi,

31、x2,xn)。若Zif(xi,x；,x；)Mo,則原純整數(shù)線性規(guī)劃問題在 Ri內(nèi)無最優(yōu)解。不需要對(duì)該區(qū)域繼續(xù)討論一一剪枝。若最優(yōu)點(diǎn)(X;,XL,X)全為整數(shù),則可能為原純整數(shù)線性規(guī)劃問題的最優(yōu)解，定界：記乂1f(xi,x2,xn)Mo,則 Miminf(xi,x2,xn)m0,本分枝求解結(jié)束。若最優(yōu)點(diǎn)(k,二，x7)不全為整數(shù)，對(duì) Ri繼續(xù)進(jìn)行分枝。完全類似，解 R2對(duì)應(yīng)線性規(guī)劃問題，對(duì)其進(jìn)行剪枝和分枝。依此類推，對(duì)所有分枝進(jìn)行求解，剪枝，分枝，定界；直至求得最優(yōu)解。(4)最優(yōu)解的確定若某 Mkm0,則為最優(yōu)解，求解結(jié)束。若所有分枝求解結(jié)束，則最后的上界 Mk即為最優(yōu)解。例 3:應(yīng)用分枝定界法

32、，求解整數(shù)線性規(guī)劃問題解：設(shè)原整數(shù)線性規(guī)劃問題目標(biāo)函數(shù)的最優(yōu)值為z*,(1)求解線性規(guī)劃問題：minzxi3x2得最優(yōu)解為 x18.12,x23.13；minz17.51x23.13記約束區(qū)域 22x134x2285 為R。x10,x20(2)對(duì)R進(jìn)行分枝：選取最優(yōu)解中不是整數(shù)的變量，例如x1，將R分成兩個(gè)子x18的上界可由R內(nèi)的任意一個(gè)可行解確定，例如，x17,x24 即為一個(gè)可行解故z*19。從而，17.51z*19。(4)在 R內(nèi)求最優(yōu)解，得 x19,x23.13;minz18.39。(5)在 R2內(nèi)求最優(yōu)解，得 x18,x23.21;minz17.62。(6)因?yàn)镽內(nèi)最優(yōu)解不全是整數(shù)，

33、因而必須繼續(xù)對(duì)R分枝:(7)顯然R2內(nèi)無解，剪枝在年內(nèi)求最優(yōu)解，得為 9,x24;minz21;為整數(shù)可行解。但因17.51z*19,而2119,故剪枝。(8)因?yàn)?R2內(nèi)最優(yōu)解不全是整數(shù)，因而必須繼續(xù)對(duì) R2分枝：(9)顯然R22內(nèi)無解，剪枝。在 R21內(nèi)求最優(yōu)解，得 x16.77,x24;minz18.77。(10)因?yàn)镽21內(nèi)最優(yōu)解不全是整數(shù)，因而必須繼續(xù)對(duì)R21分枝:(11)在 R212內(nèi)求最優(yōu)解，得 x16,x24.5;minz19.5。因minz19.5大于z*的上界，故剪枝。(12)在 R211內(nèi)求最優(yōu)解，得為 7,x24;minz19。x19區(qū)域R,R2Ox23.1322x13

34、4x2285x23.1322x134x2285x10,x20(3)定界：確定最優(yōu)值z(mì)*的上下界x10,x20由(1)中求得的最優(yōu)值知z*17.51;而z*最優(yōu)化問題的數(shù)值算法很多，常用的算法多為搜索法，本節(jié)只介紹搜索法的基本思想、無約束最優(yōu)化問題的最速下降法(梯度法)和有約束最優(yōu)化問題的罰函數(shù)法。4.1搜索算法考慮無約束最優(yōu)化問題：minf(x1,x2,xn)我們已經(jīng)討論了這類問題的最優(yōu)解條件，這必須用到函數(shù)的解析性質(zhì)。我們的方法是，先利用必要條件求出平穩(wěn)點(diǎn)，再應(yīng)用充分條件判斷是否是極值點(diǎn)。但是，我們必須求解一個(gè) n 個(gè)變量 n 個(gè)方程的方程組，并且常常是非線性的。這只有在特殊的情況下，才能求

35、出它的精確解。在一般情況下，都不能用解析法求得精確解。更何況許多實(shí)際問題中，函數(shù)的解析表達(dá)式很難得到。因此，我們必須尋求一些切合實(shí)際問題的行之有效的數(shù)值解法。搜索算法就是我們常用的方法。(1)搜索算法的基本思想：假定目標(biāo)函數(shù) f(X)極小值問題。首先，確定目標(biāo)函數(shù) f(X)的初始點(diǎn) Xo；然后，按照一定規(guī)則產(chǎn)生一個(gè)點(diǎn)列Xk,這種規(guī)則稱為算法；規(guī)則必須滿足(1)點(diǎn)列Xk收斂；(2)點(diǎn)列Xk收斂到目標(biāo)函數(shù) f(X)的極小值點(diǎn)。(2)搜索算法的基本步驟：選定初始點(diǎn) Xo(越接近最優(yōu)點(diǎn)越好)，允許誤差0,令k0。假定已得非最優(yōu)點(diǎn) Xk,則選取一個(gè)搜索方向 Sk,滿足：目標(biāo)函數(shù) f(X)下降，或 gra

36、df(Xk)?Sk0。選定搜索步長(zhǎng)k0,Xk1XkkSk,滿足：f(Xk1)f(XkkSk)f(Xk)o判斷 Xk1是否是最優(yōu)點(diǎn)或是滿足要求的近似解。假定給定精度要求為0,常用確定求近似解搜索結(jié)束的方法有：| gradf(Xk1)|梯度模確定法；| f(Xk1)f(Xk)|目標(biāo)函數(shù)差值絕對(duì)誤差法；| Xk1Xk|相鄰搜索點(diǎn)絕對(duì)誤差法。如果 Xk1滿足給定精度要求，則搜索完成，近似最優(yōu)點(diǎn)為 X*Xk1；所求原整數(shù)規(guī)劃問題的最優(yōu)解為:4最優(yōu)化問題數(shù)值算法x17,x24；minz19。如果 Xk1不滿足給定精度要求，令kk1返回(2)繼續(xù)搜索。注意 1:我們的搜索算法一般得到的都是局部最優(yōu)解注意 2

37、:確定求近似解搜索結(jié)束的方法還有(3)搜索算法的關(guān)鍵因素：從搜索算法的基本步驟中，我們知道，搜索算法的關(guān)鍵因素為：一是搜索方向，二是搜索步長(zhǎng)。搜索方向的選擇，一般考慮既要使它盡可能的指向極小值點(diǎn)，又要不至于花費(fèi)太多的計(jì)算量。搜索步長(zhǎng)的選擇，既要確保目標(biāo)函數(shù)的下降性質(zhì)，又要考慮近似解的精度要求，還要考慮算法的計(jì)算量，問題十分復(fù)雜。常用方法有，固定步長(zhǎng)法，最優(yōu)步長(zhǎng)法和變步長(zhǎng)法。固定步長(zhǎng)法(簡(jiǎn)單算法)是選取k0 為固定值。方法簡(jiǎn)單，但是有時(shí)不能保證目標(biāo)函數(shù)的下降性質(zhì)。最優(yōu)步長(zhǎng)法(一維搜索算法)是選取k使得，這是一個(gè)關(guān)于單變量的函數(shù)求極小值問題，這樣確定的步長(zhǎng)稱為最優(yōu)步長(zhǎng)。變步長(zhǎng)法(可接受點(diǎn)算法)是任

38、意選取k,只要使得 f(Xki)f(Xk)即可。這種選取步長(zhǎng)的方法，確保了目標(biāo)函數(shù)的下降性質(zhì)，盡管每次選取的步長(zhǎng)不是最優(yōu)的，但實(shí)踐證明，方法能達(dá)到更好的數(shù)值效果。總之，當(dāng)搜索方向確定以后，步長(zhǎng)就是決定最優(yōu)化算法好壞的重要因素，因此，我們必須特別注重步長(zhǎng)的選取問題。(4)搜索算法的收斂性：搜索算法的收斂性是指，由某算法得到的點(diǎn)列XJ能夠在有限步驟內(nèi)收斂到目標(biāo)函數(shù) f(X)的最優(yōu)點(diǎn)或能夠在有限步驟內(nèi)達(dá)到滿足精度要求的目標(biāo)函數(shù) f(X)的最優(yōu)點(diǎn)的近似值。顯然，只有具有收斂性質(zhì)的算法才有意義。搜索算法的收斂速度：作為一個(gè)好的算法，還必須要求它以較快的速度收斂于最優(yōu)解。階收斂定義：對(duì)于收斂于最優(yōu)解X*的

39、序列Xk,若存在與k無關(guān)的數(shù)0 和 1,當(dāng)k從某個(gè) k。開始時(shí)，有|XkiX*|XkX*|成立，1時(shí)，稱迭代序列Xk為線性收斂；當(dāng)12時(shí)，稱迭代序列Xk|f(Xk1)f(Xk)|If(Xk)|目標(biāo)函數(shù)差值相對(duì)誤差法;|XkiXk|Xk|相鄰搜索點(diǎn)相對(duì)誤差法則稱序列Xk收斂的階為,或稱階收斂為超線性收斂；當(dāng)2時(shí)，稱迭代序列XJ 為二階收斂。一般來說，線性收斂是比較慢的，而二階收斂則是很快的，超線性收斂介于二者之間。如果一個(gè)算法具有超線性以上的收斂速度，我們就認(rèn)為是一個(gè)好的算法了。4.2無約束最優(yōu)化問題的梯度法無約束最優(yōu)化問題的計(jì)算方法很多。無約束最優(yōu)化問題的計(jì)算方法分為兩大類：一類是解析法，包括

40、經(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è)谶@里只介紹最速下降法(梯度法)。最速下降法理論根據(jù)：早在1847年，法國(guó)著名數(shù)學(xué)家Cauchy就曾提出，從任意給定點(diǎn)出發(fā)，函數(shù)沿哪個(gè)方向下降最快的問題。這個(gè)問題已從理論上解決了，即沿著函數(shù)在該點(diǎn)的負(fù)梯度方向前進(jìn)時(shí)，函數(shù)下降最快。這就是最速下降法的理論根據(jù)。最速下降法的搜索步驟：步驟1:選定初始點(diǎn)

41、Xo(越接近最優(yōu)點(diǎn)越好)，允許誤差0,令k00步驟 2:假定已得非最優(yōu)點(diǎn) Xk,計(jì)算梯度 gradf(Xk),選取搜索方向 Skgradf(Xk)步驟 3:選定搜索步長(zhǎng)k0,Xk1XkkSk,滿足：f(XkkSk)mipf(XkSk)。步驟4:判斷 Xk1是否是最優(yōu)點(diǎn)或是滿足要求的近似解。根據(jù)精度要求，檢驗(yàn)是否滿足收斂性判斷準(zhǔn)則：|gradf(Xk1)|或|f(Xk1)f(Xk)|或|Xk1Xk|如果 Xk1滿足給定精度要求，則搜索完成，近似最優(yōu)點(diǎn)為 X*Xk1；如果 Xk1不滿足給定精度要求，令kk1返回(2)繼續(xù)搜索。例 1:應(yīng)用最速下降法求解 minf(X)x1225x；。解：(1)選定

42、初始點(diǎn) X0(2,2),允許誤差0.2,置k:0收斂判斷準(zhǔn)則|f(Xk1)f(Xk)|。(2)計(jì)算梯度 gradf(X。，選取搜索方向 Skgradf(Xk)gradf(Xk)2x1,50 x2)|XXk，Sk2x1,50 x2)|XXk第一點(diǎn)搜索計(jì)算：gradf(Xo)4,100,S4,100)(3)選定搜索步長(zhǎng)k0,XkiXkkSk,滿足：第一點(diǎn)搜索計(jì)算：求最優(yōu)步長(zhǎng)解得00.02。(4)判斷Xki是否是最優(yōu)點(diǎn)或是滿足要求的近似解。第一點(diǎn)搜索計(jì)算：Xi(1.92,0)驗(yàn)證收斂判斷準(zhǔn)則|f(Xi)f(X0)|100.310.02,不滿足，繼續(xù)搜索依次類推，直到搜索到最優(yōu)解或滿足精度要求為止搜索

43、計(jì)算列表如下：搜索步長(zhǎng)k搜索方向Sk搜索點(diǎn) Xk函數(shù)值 f(Xk)X2(0,0)為最優(yōu)解4.3罰函數(shù)法對(duì)于約束最優(yōu)化問題也有許多種方法， 本段只介紹把約束最優(yōu)化問題轉(zhuǎn)化為無約束最優(yōu)化問題的一種求解方法一一罰函數(shù)法。分為等式約束最優(yōu)化問題和不等式約束最優(yōu)化問題兩種情況討論。(1)等式約束最優(yōu)化問題的罰函數(shù)法首先，考慮等式約束最優(yōu)化問題假定上述等式約束最優(yōu)化問題的最優(yōu)解存在。若記 DX|gi(X)0,i1,2,m,XRn),m構(gòu)造輔助函數(shù) T(X,M)f(X)Mgi(X)2罰函數(shù)i1其中M0(罰因子)是一個(gè)充分大的正數(shù)。定理1:若對(duì)于某確定數(shù)M0,無約束最優(yōu)化問題的最優(yōu)解X*D,則X*必為原等式約

44、束最優(yōu)化問題的最優(yōu)解。m證明：設(shè)無約束最優(yōu)化問題 minT(X,M)f(X)Mgi(X)2i1而當(dāng)XD時(shí)，T(X,M)f(X)所以 minf(X)minT(X,M)T(X*,M)f(X*)即X*為原等式約束最優(yōu)化問題的最優(yōu)解。定理 2:設(shè) f(X)和 gMX)0,i1,2,2 均為連續(xù)函數(shù)，若對(duì)于任意正數(shù)M0,無約束最優(yōu)化問題的最優(yōu)解 X*(M)D,且limX*(M)X*,M則limX*(M)X*為原等式約束最優(yōu)化問題的最優(yōu)解。M定理2的證明請(qǐng)參看有關(guān)參考資料。根據(jù)定理1和定理2,我們就可以將通過構(gòu)造罰函數(shù)的方法化為無約束最優(yōu)化問題求解，這種方法稱為罰函數(shù)法。罰函數(shù)法的步驟：(等式約束最優(yōu)化問

45、題罰函數(shù)法)m步驟 1:構(gòu)造罰函數(shù) T(X,M)f(X)Mgi(X)2,i1選定M10,允許誤差0,令k：1;步驟 2:求無約束問題 minT(X,Mk)的最優(yōu)解 Xk；步驟3:判斷Xk是否是最優(yōu)點(diǎn)或是滿足要求的近似解。根據(jù)精度要求，檢驗(yàn)是否滿足收斂性判斷準(zhǔn)則：m或gi(Xk)2i1如果滿足收斂性判斷準(zhǔn)則，則 X*X：,結(jié)束搜索；否則，令k:k1,取 Mk1Mk0,返回(2),繼續(xù)搜索。下面我們通過一個(gè)簡(jiǎn)單的例子來說明等式約束最優(yōu)化問題的罰函數(shù)法。例2:應(yīng)用罰函數(shù)法求解非線性規(guī)劃問題解：構(gòu)造罰函數(shù)：T(X,Mk)X2x2Mk(x21)2求罰函數(shù)的最優(yōu)解：應(yīng)用解析法2x1,T-2x22Mk(x2

46、1)X2cMkx10,x21Mk的最優(yōu)解X*D,則有:gi（x）0i1,2,mX1令上述兩式等于零，解得令 Mk得 Xi0,X21 為所求最優(yōu)解。22)不等式約束最優(yōu)化問題的罰函數(shù)法對(duì)于，不等式約束最優(yōu)化問題假定上述不等式約束最優(yōu)化問題的最優(yōu)解存在。由于不等式約束條件 gi(X)0,i1,2,m 等價(jià)于等式約束條件因而，上述不等式約束最優(yōu)化問題可以轉(zhuǎn)化為問題類似問題(1)構(gòu)造罰函數(shù)則將上述等式約束最優(yōu)化問題的求解轉(zhuǎn)化為下面無約束最優(yōu)化問題的求解：定理3:若對(duì)于某確定數(shù)M0,無約束最優(yōu)化問題的最優(yōu)解X*D,則X*必為原不等式約束最優(yōu)化問題的最優(yōu)解，其中 DX|gi(X)0,i1,2,m,XRn)

47、。定理4:設(shè)(1)f(X)和 gMX)0,i1,2,2 均為連續(xù)函數(shù)；(2)原不等式約束最優(yōu)化問題的最優(yōu)解X*存在；(3)數(shù)列Mk滿足 0M1M2Mk且limMk；k(4)對(duì)任意 Mk0,問題 minT(X,M)的最優(yōu)解 XkX(Mk)都存在,且有界；(5)點(diǎn)列Xk存在極限點(diǎn)；則：點(diǎn)列XJ 的極限點(diǎn)是原不等式約束最優(yōu)化問題的最優(yōu)解。罰函數(shù)法的步驟：(不等式約束最優(yōu)化問題罰函數(shù)法)m步驟 1:構(gòu)造罰函數(shù) T(X,M)f(X)Mmin(0,gi(X)2,i1選定M10,允許誤差0,令k：1;步驟2:求無約束問題 minT(X,Mk)的最優(yōu)解 Xk;步驟3:判斷Xk是否是最優(yōu)點(diǎn)或是滿足要求的近似解。

48、根據(jù)精度要求，檢驗(yàn)是否滿足收斂性判斷準(zhǔn)則：m或gi(Xk)2i1.*如果滿足收斂性判斷準(zhǔn)則，則 X*Xk,結(jié)束搜索；否則，令k:k1,取 MkiMk0,返回(2),繼續(xù)搜索例3:應(yīng)用罰函數(shù)法求解非線性規(guī)劃問題m解：構(gòu)造罰函數(shù) T(X,M)f(X)Mmin(0(X)2i1求 T(X,Mk)的極小值點(diǎn)當(dāng) xi2X20,或 xi0 時(shí)，顯然上兩式不能同時(shí)等于零，所以，此時(shí) T(X,Mk)不存在極小值點(diǎn)。當(dāng) Xi2X20,xi0 時(shí)，有令上面兩式等于零：0,0;XiX2解得 T(X,Mk)的極小值點(diǎn)為當(dāng) Mk取不同值時(shí)，可得到相應(yīng)的 Xk值，計(jì)算如下表ii0i00i000-0.25-0.04545-0

49、.004950-0.00049950-0.4375-0.i4i5-0.004975-0.00049980根據(jù)定理得，原問題的極小值點(diǎn)為 X*(0,0),極小值為 f(X*)05多目標(biāo)優(yōu)化問題在許多實(shí)際的最優(yōu)化問題中， 常常遇到目標(biāo)函數(shù)是幾個(gè)的情況， 這一類問題我們稱之為多目標(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é)模型為：minfi(Xi,X2,Xn)ii,2,s 目標(biāo)函數(shù)gi(Xi,

50、X2,Xn)0ii,2,m 約束條件例i：求解多目標(biāo)優(yōu)化問題minX2和 miny解：易求X0,yi 時(shí)，minX20,minyi。例2:求解多目標(biāo)優(yōu)化問題maxx2和 miny解：顯然，無最優(yōu)解。5.1多目標(biāo)優(yōu)化問題的解多目標(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)化問題

51、的條件最優(yōu)解概念。最優(yōu)解：滿足約束條件且使所有目標(biāo)函數(shù)達(dá)到要求的最大值或最小值的點(diǎn)稱為多目標(biāo)優(yōu)化問題的最優(yōu)解?？尚薪猓簼M足多目標(biāo)優(yōu)化問題的約束條件的點(diǎn)稱為可行解。條件最優(yōu)解：滿足多目標(biāo)優(yōu)化問題的約束條件且滿足根據(jù)需要設(shè)定條件的可行解稱為條件最優(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ù)方法”

52、都是針對(duì)目標(biāo)函數(shù)設(shè)定新條件的方法。5.2單目標(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)化解法的基本思想步驟 1:構(gòu)造一個(gè)新的目標(biāo)函數(shù) ff(f1,f2,fs)滿足性質(zhì)：在約束條件的區(qū)域內(nèi) f(fi,f2，,fs)是 fi,f2,fs的單調(diào)增函數(shù)特別注意：構(gòu)造新目標(biāo)函數(shù)也可以根據(jù)實(shí)際問題，將 f(fi,f2，,fs)定義為fl,f2,fs的不減函數(shù)。步驟2：建立單目標(biāo)優(yōu)化數(shù)學(xué)模型minff(fi,f2,fs)目標(biāo)函數(shù)gi(xi,x2,Xn)0i1,2,m 約束條件步驟3:求解上述單目標(biāo)優(yōu)化數(shù)學(xué)模型得到：?jiǎn)文繕?biāo)優(yōu)化問題的最

53、優(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)在關(guān)系。下面的定理揭示了兩者之間最重要的一種關(guān)系。定理 1：設(shè) f(fi,f2，,fs)是 fi,f2,fs的單調(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)解為X*,則在該點(diǎn)處，目標(biāo)函數(shù) fi,f2,fs都取得最小值。設(shè)單目標(biāo)最優(yōu)化問題的最優(yōu)解為Y*,則在該點(diǎn)處，目標(biāo)函數(shù) f(f1,f2,fs)取得最小值 f(Y*)。顯然，

54、1)fi(X*)fi(Y*)i1,2,s2)f(X*)f(Y*)又因?yàn)椋琭(f1,f2,fs)是 f1,f2,fs的單調(diào)增函數(shù)，根據(jù) 1)有：f(X*)f(Y*)所以，f(X*)f(Y*),故必有 fi(X*)*(丫*)i1,2,s即Y*為原多目標(biāo)最優(yōu)化問題的最優(yōu)解。定理告訴我們：如果多目標(biāo)最優(yōu)化問題的最優(yōu)解存在，則只需求解一個(gè)單目標(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)解存在時(shí)，我們稱解為單目標(biāo)條件最優(yōu)解。這種解在一定程度上反應(yīng)了原多目標(biāo)最優(yōu)化問題的性質(zhì)，

55、因此，在實(shí)踐中常常被選用。(3)單目標(biāo)化的常用目標(biāo)函數(shù)當(dāng)多目標(biāo)最優(yōu)化問題的最優(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í)際問題構(gòu)造目標(biāo)函數(shù)，以比較準(zhǔn)確地反應(yīng)實(shí)際問題的性質(zhì)。下面是幾種常用的目標(biāo)函數(shù)。均衡優(yōu)化函數(shù) f(f1，f2,fs)f1f2fs權(quán)重優(yōu)化函數(shù) f(f1,f2,fs)1f12f2sfs其中1,2,s為大于零的權(quán)重系數(shù)平方和優(yōu)化函數(shù) f(f1,f2,fs)fi2i1s平方和均衡優(yōu)化函數(shù) f(f1,f2,fs)ifi2si1其中1,2,s為大于零的權(quán)重系數(shù)例 2:求解多目標(biāo)優(yōu)化問題max(x2y)和

56、max(yx)解： 問題涉及兩個(gè)目標(biāo)函數(shù)， 可應(yīng)用單目標(biāo)化方法求解。 (1)構(gòu)造單目標(biāo)函數(shù)f(x,y)(x2y)(yx)3y(2)求解模型 maxf(x,y)3y得最優(yōu)解為 x0,y1,此時(shí) maxf3。(3)易知原問題最優(yōu)解存在(可通過作圖驗(yàn)證)，所以最優(yōu)解為 x0,y1,此時(shí) max(x2y)2,max(yx)1。5.3 多重優(yōu)化解法根據(jù)實(shí)際問題的性質(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)化對(duì)象和優(yōu)化次序。建立多重優(yōu)化數(shù)學(xué)模型第一重優(yōu)化：min 九(為？2,xn)其中九為 f1，f2

57、,fs中的某一函數(shù)求解得解集為 D1第二重優(yōu)化：min 人(為？2,xn)其中九為 f1，f2,fs中的某一函數(shù)求解得解集為 D2依次類推，進(jìn)行 s 重優(yōu)化第 s 重優(yōu)化：minfi(x1，x2,xn)其中九為 i/,fs中的某一函數(shù)求解得解集為 Ds,即為多重優(yōu)化問題的最優(yōu)解集。原多目標(biāo)優(yōu)化問題的最優(yōu)解集或條件最優(yōu)解集為 Dso值得特別注意的是，我們不一定對(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)化問題最優(yōu)解的性質(zhì)多重優(yōu)化問題的最優(yōu)解與原多目標(biāo)最優(yōu)化問題的最優(yōu)解也有著密切的內(nèi)在關(guān)系。下面的定理揭示了兩者之間的相互

58、關(guān)系。定理 2:設(shè)原多目標(biāo)最優(yōu)化問題的最優(yōu)解存在，則多重優(yōu)化問題第一重優(yōu)化：minfh(x1,X2，,xn)其中尤為，fs中的某一函數(shù)解集為 Di第二重優(yōu)化：min 人(為？2，,Xn)其中 fi2為 fi/,fs中的某一函數(shù)解集為 D2依次類推第 s 重優(yōu)化：minfi(Xi,X2,Xn)其中九為 fi/,fs中的某一函數(shù)解集為 Ds的最優(yōu)解必存在，且為原多目標(biāo)最優(yōu)化問題的最優(yōu)解。定理的證明留給讀者自己練習(xí)。例 3：求解多目標(biāo)優(yōu)化問題maX(Xy)和 maX(y2X)解：?jiǎn)栴}涉及兩個(gè)目標(biāo)函數(shù)，可應(yīng)用多重優(yōu)化方法求解。(1)求解第一重優(yōu)化：maX(Xy)的解集為 D(x,y)|xyi,x0,y

59、0,此時(shí) max(xy)i(2)求解第二重優(yōu)化：max(y2x)(3)易知原問題最優(yōu)解存在(可以通過作圖驗(yàn)證)，所以最優(yōu)解為 x0,yi,此時(shí) max(xy)i,max(y2x)i。5.4目標(biāo)關(guān)聯(lián)函數(shù)方法在多目標(biāo)最優(yōu)化問題數(shù)學(xué)模型中，如果我們只是選定某一個(gè)目標(biāo)函數(shù)(稱為主目標(biāo))做為得解為 x0,yi,此時(shí) max(y2x)i0目標(biāo)，而固定其余目標(biāo)函數(shù)(稱為次目標(biāo))在允許取值范圍內(nèi)為常數(shù)，則得到下列單目標(biāo)優(yōu)化數(shù)學(xué)模型：minfh(Xi,X2,xn)其中九為 fi,f2,fs中的某一函數(shù)fik(Xi,x2,Xn)即 k2,3,s，其中 iij,柒為 1,2,聲的某排列如果上述問題有解，則 minf

60、i1(Xi,X2,Xn)與其余目標(biāo)函數(shù)的取值有關(guān)。目標(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é)模型：(D 目標(biāo)關(guān)聯(lián)函數(shù)定義目標(biāo)關(guān)聯(lián)函數(shù)定義：選取目標(biāo)函數(shù) minfi(Xi,X2,Xn)作為主目標(biāo)，minf2(Xi,X2,Xn)作為次目標(biāo)，固定 f2(Xi,X2,Xn)t,則得到單目標(biāo)優(yōu)化數(shù)學(xué)模型：記最優(yōu)值 minfi(Xi,X2,人)為 F,則 F 為 t 的函數(shù)，即 FF(t),稱此函數(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ù)。類似地，