多目標(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)險問題第六章最優(yōu)化問題數(shù)學(xué)模型§ 1 最優(yōu)化問題1. 1最優(yōu)化問題概念(1)最優(yōu)化問題在工業(yè)、農(nóng)業(yè)、交

2、通運(yùn)輸、商業(yè)、國防、建筑、通信、政府機(jī)關(guān)等各部門各領(lǐng)域的實(shí)際工作中，我們經(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)

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

4、h(X)A0或h(X)<0。這兩種約束條件最優(yōu)化問題最優(yōu)解的存在性較復(fù)雜。(4)目標(biāo)函數(shù)在最優(yōu)化問題中，與變量有關(guān)的待求其極值(或最大值最小值)的函數(shù)稱為目標(biāo)函數(shù)。目標(biāo)函數(shù)常用f(X)=f(Xi,X2，Xn)表示。當(dāng)目標(biāo)函數(shù)為某問題的效益函數(shù)時，問題即為求極大值；當(dāng)目標(biāo)函數(shù)為某問題的費(fèi)用函數(shù)時，問題即為求極小值等等。求極大值和極小值問題實(shí)際上沒有原則上的區(qū)別，因?yàn)榍骹(X)的極小值，也就是要求-f(X)的極大值，兩者的最優(yōu)值在同一點(diǎn)取到2. 2最優(yōu)化問題分類最優(yōu)化問題種類繁多，因而分類的方法也有許多。可以按變量的性質(zhì)分類，按有無約束條件分類，按目標(biāo)函數(shù)的個數(shù)分類等等。一般來說，變量可以分

5、為確定性變量，隨機(jī)變量和系統(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)最優(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)輪

6、換法步長加速法多維搜索法，方向加速法單純形法隨機(jī)搜索法'最速下降法壬勿t小蟾t詳、#I擬牛頓法無約束梯度法共軻梯度法有約束梯度法3變尺度法力行方向法梯度投影法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é)，計算機(jī)科學(xué)以及各專業(yè)領(lǐng)域等等，是一個十分復(fù)雜的問題，然而它卻是需要我們重點(diǎn)關(guān)心的問題之一。怎樣研究分析求解這類問題呢？其中最關(guān)鍵的是建立數(shù)學(xué)模型和求解數(shù)學(xué)模型。一般來說，應(yīng)用最優(yōu)化方法解決實(shí)際問題可分為四個步驟進(jìn)行：步驟1:

7、建立模型提出最優(yōu)化問題，變量是什么？約束條件有那些？目標(biāo)函數(shù)是什么？建立最優(yōu)化問題數(shù)學(xué)模型：確定變量，建立目標(biāo)函數(shù)，列出約束條件一一建立模型。步驟2:確定求解方法分析模型，根據(jù)數(shù)學(xué)模型的性質(zhì)，選擇優(yōu)化求解方法一一確定求解方法。步驟3:計算機(jī)求解編程序（或使用數(shù)學(xué)計算軟件）,應(yīng)用計算機(jī)求最優(yōu)解一一計算機(jī)求解。步驟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é)模型由某實(shí)際問

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

9、的例子：求函數(shù)f(x1,x2,x3)=x1x3xn在約束條件條件xi+x3+xn=2008,xi>0,i=1,2,，n下的最大值和取得最大值的點(diǎn)。線性規(guī)劃問題數(shù)學(xué)模型由某實(shí)際問題設(shè)立變量，建立一個目標(biāo)函數(shù)和若干個約束條件，目標(biāo)函數(shù)和約束條件都是變量的線性函數(shù)，而且變量是非負(fù)的，這樣的求函數(shù)最大值最小其標(biāo)準(zhǔn)數(shù)學(xué)模型為:目標(biāo)函數(shù)約束條件目標(biāo)函數(shù)約束條件值問題，我們稱為線性最優(yōu)化問題，簡稱為線性規(guī)劃問題minf(xi,x2,.，xn)=cxiax2Cnxnaiixi82x2aimxn=bii=1,2,mxi-0矩陣形式：minf(X)=CTXAX=BX-0其中X=(Xi，X2，xn)T,C=(

10、Ci,C2,，Cn)T,B=(，達(dá),，bm)T在線性規(guī)劃問題中，關(guān)于約束條件我們必須注意以下幾個問題。注1:非負(fù)約束條件xi>0(i=1,2,，n),一般來說這是實(shí)際問題要求的需要。如果約束條件為為至di,我們作變量替換Zi=xi-di至0;如果約束條件為XiEdi,我們作變量替換Zi=di-為至0。注2:在線性規(guī)劃的標(biāo)準(zhǔn)數(shù)學(xué)模型中，約束條件為等式。如果約束條件不是等式，我們引入松馳變量，化不等式約束條件為等式約束條件。情況1:若約束條件為ai1x1+ai2x2+aimxn>bi,引入松馳變量原約束條件變?yōu)閍MXi+ai2X2+amXnZi=bi。情況2:若約束條件為aiiXi+a

11、i2X2+amXn<bi,引入松馳變量原約束條件變?yōu)閍MXi-ai2X2-amXn,Zi=6在其它最優(yōu)化問題中，我們也常常采取上述方法化不等式約束條件為等式約束條件。實(shí)際問題中，我們經(jīng)常遇到兩類特殊的線性規(guī)劃問題。一類是：所求變量要求是非負(fù)整數(shù)，稱為整數(shù)規(guī)劃問題；另一類是所求變量要求只取0或1,稱為0-1規(guī)劃問題。例如：整數(shù)規(guī)劃問題x2-3.13s.t.22x1+34x2至285。X120,X2至0且為整數(shù)又例如：0-1規(guī)劃問題maxz=3x1-2x2+5x3X十2x2-x3E2X+4x2+x3<4s.t.x1,x2,x3=0或1。Xx2m34x2x3£6非線性規(guī)劃問題數(shù)

12、學(xué)模型由某實(shí)際問題設(shè)立變量，建立一個目標(biāo)函數(shù)和若干個約束條件，如果目標(biāo)函數(shù)或約束條件表達(dá)式中有變量的非線性函數(shù)，那么，這樣的求函數(shù)最大值最小值問題，我們稱為非線性規(guī)劃最優(yōu)化問題，簡稱為非線性規(guī)劃問題。其數(shù)學(xué)模型為：minf(X1,X2，Xn)目標(biāo)函數(shù)gi(X1,X2,Xn)=0i=1,2,m約束條件其中目標(biāo)函數(shù)或約束條件中有變量的非線性函數(shù)。例如：非線性規(guī)劃問題minf(x,y)=(x-1)2y4(x,y)=x+y-2，03o9(x,y)=y«0上述最優(yōu)化問題中，目標(biāo)函數(shù)是非線性函數(shù)，故稱為非線性規(guī)劃問題。前面介紹的四種最優(yōu)化數(shù)學(xué)模型都只有一個目標(biāo)函數(shù)，稱為單目標(biāo)最優(yōu)化問題，簡稱為最

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

14、條件極值問題。經(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)。這是一個無約束條件極值問題，經(jīng)典的極值理論如下。定理1(極值必要條件)：設(shè)n元函數(shù)f(X)=f(x,X2，Xn)具有偏導(dǎo)數(shù),則f(X)在X=X處取得極值的必要條件為：|XM=0i=1,2,，n。XX-Xi定理在此不給出證明，讀者可自己參看有關(guān)資料。注1:對于一元函數(shù)上述定理當(dāng)然成立，只是偏導(dǎo)數(shù)應(yīng)為導(dǎo)數(shù)；注2:定理只是在偏導(dǎo)數(shù)

15、存在的前提下的必要條件。如果函數(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)=VX2+y2在點(diǎn)(0,0)處偏導(dǎo)數(shù)不存在，但在這一點(diǎn)處函數(shù)仍然取得極小值零。函數(shù)f(X,y)=X3+y5在點(diǎn)(0,0)處偏導(dǎo)數(shù)存在，且偏導(dǎo)數(shù)都等于零，但在這一點(diǎn)處函數(shù)不取極值。定理1的作用在于，求出函數(shù)的可能極值點(diǎn)，然后，我們再研究這些點(diǎn)是否取得極值。對于許多實(shí)際問題來說，函數(shù)一定能夠取得極大值或極小值，而函數(shù)的可能極值點(diǎn)(滿足必要條件的點(diǎn))又只有一點(diǎn)，則這一點(diǎn)當(dāng)然是函數(shù)取得極大值或極小值的點(diǎn)。對于一

16、般函數(shù)而言，我們怎樣判定函數(shù)在某點(diǎn)是否取極值？是極大值？還是極小值？我們有下面的極值的充分條件定理。定理2(極值充分條件)：設(shè)n元函數(shù)f(X)=f(Xi，X2，Xn)具有二階偏導(dǎo)數(shù)，則f(X)在X=X*處取得極值的充分條件為:(1)i=2,3,，n;f|*=0-1X義-為一(2)黑塞矩陣?ffx；:2f：X2二X1；：2f-X1：X2If：x；?fX1-xnIfX2：Xn在X=X處正止或負(fù)止;(3)短f<cXncX1Ifxx：X2If-2Xn黑塞矩陣在X=X本章內(nèi)容簡要講解理論,處正定時，函數(shù)取極小值；負(fù)定時，函數(shù)取極大值。注重實(shí)際應(yīng)用，對于許多經(jīng)典的定理都不進(jìn)行證明，讀者可自己參看有關(guān)

17、資料。例1:求函數(shù)f(%,X2,X3)=2x26x；4x2+2x1x2+2x2x3的極值。解：(1)根據(jù)極值存在的必要條件，確定可能取得極值的點(diǎn):開fFf=-4x,2x2,=-12x22x,2x3,=-8x32x2-：X1/：X3.干干二f,一令=0,斛行(x),x2,x3)=(0,0,0)。：X1：X2僅3(2)根據(jù)極值存在的充分條件，確定(Xi，X2，X3)=(O,0,0)是否是極值點(diǎn):計算-2Xi-4-2X2;2f=-12,二=-8;X3：2f二2,-X1-x2.224:2;'XfX3二X2X34-420、函數(shù)的黑塞矩陣為172f(0,0,0)=2-122<02咒20-12

18、2=320<0；2-8-4一一一42一因?yàn)?<0,=44>0,22-120所以黑塞矩陣負(fù)定，故函數(shù)在（X1,X2,X3）=（0,0,0）處取得極大值f（0,0,0）=02.2等式約束條件極值下面我們研究的是有若干個等式約束條件下，一個目標(biāo)函數(shù)的極值問題，其數(shù)學(xué)模型為：目標(biāo)函數(shù)約束條件minf(xl,Xn)s.t.gi(X1,X2,Xn)=0i=1,2,m拉格朗日（Lagrange）乘數(shù)法:(1)令mLf(X1,x2,xn)-igi(X1,X2,xn)i1稱為上述問題的拉格朗日乘數(shù)函數(shù)，稱A為拉格朗日乘數(shù)。（2）設(shè)f（X1，X2，XnMDgi（X1,X2，Xn）均可微，則得到方

19、程組（3）若（X1,X2，Xn,兀，九2，九m）是上述方程組的解，則點(diǎn)（X1，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)（X1,%,，£）是否為最優(yōu)點(diǎn)通?？捎蓡栴}的實(shí)際意義決定。例2：求表面積為定值a2,而體積為最大的長方體的體積。解：設(shè)長方體的三棱長為x,y,z,體積為V;建立數(shù)學(xué)模型如下：maxV=xyz構(gòu)造拉格朗日

20、乘數(shù)函數(shù)L（x,y,z）=xyz+凝2xy+2yz+2xza2）,則有解得x=y=z=gamaxV=a3為所求。6362.3不等式約束條件極值對于不等式約束條件極值問題:目標(biāo)函數(shù)minf的為，Xn)s.t.gi(X1,X2,Xn)0i=1,2,m約束條件我們有與拉格朗日乘數(shù)法密切相關(guān)的方法庫恩圖克定理。定理3(庫恩圖克定理)：對于上述不等式約束條件極值問題，設(shè)f(x1,X2，4)m和gi(x1,X2，Xn)均可微，令L=f(x1,X2，Xn)+Z上igi(x1,X2,',Xn)i4假設(shè)九i存在，則在最優(yōu)點(diǎn)X=X=(XX2，Xn)處，必滿足下述條件:(D%;:Xjj=1,2,，n；(2)

21、gi(Xi,X2,出)£0i=1,2,，m;(3)、gi(Xi,X2,Xn)=0i=1,2,m;(4)根據(jù)庫恩圖克定理我們可以求解許多不等式約束條件極值問題，值得注意的是應(yīng)用庫恩一圖克定理求解不等式約束條件極值問題，定理并沒有解決最優(yōu)解的存在性問題，因此，我們必須另行判斷。例3:求解最優(yōu)化問題(最優(yōu)解存在)解：構(gòu)造函數(shù)L(x,y,z)=(x1)2+y+%(x+y2)+%(y),比口=2(x1)+%=0改根據(jù)庫恩圖克定理則有=1+A上2=0cy%(x+y-2)=0&2y=01-0,2-0解得:X=1y=0,%=0,%=1；所求最優(yōu)解為(x,y)=(1,0),最優(yōu)值為0。

22、7;33.1線性規(guī)劃線性規(guī)劃設(shè)線性規(guī)劃標(biāo)準(zhǔn)數(shù)學(xué)模型為:minf(X1,x2,xn)=c1x1c2x2+cnxn目標(biāo)函數(shù)二s.t.1aixiai2x2amxn=bi=1,2,mi=1,2,n矩陣形式：minf(X)=CTX-約束條件目標(biāo)函數(shù)約束條件AX二BX.0其中X=(x1，x2，xn)T,C=(Ci，C2,，cn)T,B=(b1,b2,，bm)T線性規(guī)劃問題的求解有一整套理論體系，一般來說，應(yīng)用單純形法求解。此方法盡管比較復(fù)雜，然而在計算機(jī)上實(shí)現(xiàn)并不困難。解線性規(guī)劃問題的單純形法已在許多數(shù)學(xué)計算軟件中實(shí)現(xiàn)，我們求解線性規(guī)劃問題可根據(jù)需要，應(yīng)用數(shù)學(xué)計算軟件求解即可。在此，我們不系統(tǒng)研究其理論，

23、只是簡單介紹線性規(guī)劃的窮舉法和單純形法的基本思想。3.2線性規(guī)劃的窮舉法(1)窮舉法基本原理和步驟步驟1:將線性規(guī)劃問題化成矩陣的標(biāo)準(zhǔn)形式，設(shè)系數(shù)矩陣的秩R(A)=m,則對應(yīng)線性方程組的基礎(chǔ)解系自由變量的個數(shù)為n-m個。步驟2:窮舉法求解：令。=%=.一=為65)=0,解得對應(yīng)線性方程組一組解為(x1,x2，xn)；對應(yīng)目標(biāo)函數(shù)值為f(x1,x2，xn)=fi。從n個變量x中選n-m個作為自由變量，令它們的值為0,可得至UCm=C；組解。步驟3:確定最優(yōu)解：如果最優(yōu)解存在，則上述求解得到的對應(yīng)Cm=C：個目標(biāo)函數(shù)值中，最小者(或最大者)即為所求最小(或最大)最優(yōu)值，對應(yīng)的解為最優(yōu)解。步驟4:證

24、明解為最優(yōu)解：將最優(yōu)解對應(yīng)的自由變量看成參數(shù)匕工,，.；解對應(yīng)線性方程組得為=bi°+如匕+bi2t2+bi(ne%Gi=1,2,，n。將對應(yīng)線性方程組解xi=bi0bit,bi2t2,，bi(n.)t(n_m),i=1,2,，n代入目標(biāo)函數(shù)得：f=f0,dt1d2t2''d(n_m)t(n_m)。如果di至0,i=1,2，n,則所求為最小值最優(yōu)解；否則，線性規(guī)劃問題無最小值最優(yōu)解如果diE0,i=1,2,，n,則所求為最大值最優(yōu)解；否則，線性規(guī)劃問題無最大值最優(yōu)解。例1:目標(biāo)函數(shù)：maxf(X)=2x1-3x2x3解：約束條件的增廣矩陣為：10100、A=12010

25、,R(A)=3;、01001,令x=x2=0,解得X=(0,0,5,10,4),f(X)=5;令x=x3=0,無解；令x1=x4=0,解得X=(0,5,5,0,-1),不滿足非負(fù)條件，舍去；令x1=x5=0,解得X=(0,4,5,2,0),f(X)=17;令x2=x3=0,解得X=(5,0,0,5,4),f(X)=10;令x2=x4=0,解得X=(10,0,-5,0,4),不滿足非負(fù)條件，舍去；令x2=x5=0,無解；5335令x3=x4=0,解得X=(5,2,0,0,3),f(X)=35;令x3=x5=0,解得X=(5,4,0,-3,0),不滿足非負(fù)條件，舍去；令x4=x5=0,解得X=(2

26、,4,3,0,0),f(X)=19;所以maxf(X)=19,最優(yōu)解為X=(2,4,3,0,0)。證明：令x4=t,x5=s解得x1=2-t+2s彳x2=4-S目標(biāo)函數(shù)f(X)=19-1-s；x3=3t-2sX-0,i=1,5因?yàn)閤4=t,x5=s非負(fù)，所以maxf(X)=19,故最優(yōu)解存在。(2)單純形法基本原理和步驟將線性規(guī)劃問題化成矩陣的標(biāo)準(zhǔn)形式，設(shè)系數(shù)矩陣的秩R(A)=m，則對應(yīng)線性方程組的基礎(chǔ)解系的個數(shù)為nm個，即有nm個自由參數(shù)變量。選取nm個非基變量（自由參數(shù)變量）,不妨假設(shè)為xj=m+1n；解得線性規(guī)劃問題的典式定理1:如果線性規(guī)劃問題的上述典式中所有<0,j=m+1,，

27、n；貝X=（%，%，,0tm。，0）為最優(yōu)解。定理2:如果線性規(guī)劃問題的上述典式中存在某個%#>0,且對應(yīng)月盟E0,i=1,2,，m；則線性規(guī)劃問題無最優(yōu)解。由定理1和定理2知，如果我們選擇適當(dāng)?shù)膎m個非基變量，就可以根據(jù)所求得的典式判斷最優(yōu)解的存在與否，從而求解該線性規(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ī)則，即選取s=minj|%>0,由此確定xs為進(jìn)基。退基規(guī)則：選取這樣的下標(biāo)J,（J表示第i個基變量的下標(biāo)）由此確定Xj

28、r離基。單純形法的基本步驟：步驟1:化線性規(guī)劃問題為標(biāo)準(zhǔn)形式。步驟2:確定基變量，求得基本可行解和典式；是否滿足最優(yōu)解定理或最優(yōu)解不存在定理的條件？判斷最優(yōu)解的情況。步驟3:根據(jù)進(jìn)基規(guī)則和退基規(guī)則，選擇進(jìn)基和退基，進(jìn)行基變換，求得對應(yīng)典式。重復(fù)進(jìn)行基變換，直到求出最優(yōu)解或判斷出無最優(yōu)解為止。例2:解線性規(guī)劃問題解：（1）約束條件的增廣矩陣為：M1100”A=11010,R（A）=3;、62001所以非基變量個數(shù)為兩個。（2）選取X1,X2作為非基變量，X3,X4,X5作為基變量，解得典式為不滿足最優(yōu)解定理和最優(yōu)解不存在定理的條件，故必須進(jìn)行基變換。（3）進(jìn)行基變換選取進(jìn)基：=2A0,%=1&g

29、t;0,根據(jù)s=minj|%A0得X1為進(jìn)基選取退基:二min；,21根據(jù)H=min*|Pis>0,Jr=minJi|-=e,Pis>0得X5為離基"is-is進(jìn)行基變換，求新基的典式：判斷：不滿足最優(yōu)解定理和最優(yōu)解不存在定理的條件，故繼續(xù)進(jìn)行基變換(4)繼續(xù)進(jìn)行基變換選取進(jìn)基:1->0,根據(jù)s=minj|%a0得X2為進(jìn)基。3選取退基:min9,2148aa根據(jù)H=min才_|Pis>0,Jr=minJi|y-=9,Pis>0得X3為離基"is"is進(jìn)行基變換，求新基的典式：滿足最優(yōu)解定理的條件，根據(jù)定理最優(yōu)解為V,119c131X

30、=(一,0,0),minf=o44243.2整數(shù)規(guī)劃設(shè)純整數(shù)線性規(guī)劃數(shù)學(xué)模型為：minf(Xi,X2,Xn)=CXiC2X2CnXn目標(biāo)函數(shù)廣s.t.&iXi-ai2X2.-amXn=biX至0,Xi為整數(shù)i=1,2,mi=1,2,n約束條件這一類問題與一般線性規(guī)劃比較起來，似乎是變簡單了，但實(shí)際上恰恰相反，由于解集是一些離散的整數(shù)點(diǎn)集，使得單純形法失去了應(yīng)用的基礎(chǔ)，求解變得困難而復(fù)雜。整數(shù)線性規(guī)劃目前還缺乏統(tǒng)一的解法，這里只介紹分枝定界法，它是目前求解純整數(shù)線性規(guī)劃和混合整數(shù)線性規(guī)劃最常用的方法，計算機(jī)求解整數(shù)線性規(guī)劃的大多數(shù)程序也是以它為基礎(chǔ)的。分枝定界法：考慮上述純整數(shù)線性規(guī)劃問

31、題，目標(biāo)函數(shù)(1)解對應(yīng)線性規(guī)劃問題minf(Xi,X2,Xn)=CXiC2X2CnXns.t/9i1Xi+ai2X2+-+amXn=卜i=1,2,mi=1,2,n約束條件若無最優(yōu)解，則原純整數(shù)線性規(guī)劃問題無最優(yōu)解;若有最優(yōu)解，最優(yōu)點(diǎn)(X1,X2，Xn),目標(biāo)函數(shù)最優(yōu)值Z0二f(Xi,X2，Xn)。若最優(yōu)點(diǎn)(Xi,X2，Xn)全為整數(shù)，則為原純整數(shù)線性規(guī)劃問題的最優(yōu)解;若最優(yōu)點(diǎn)（x1,x2，xn）不全為整數(shù)，則進(jìn)行下一步。（2）定界和分枝定界：M0minf（x1,x2,xn）：;z0=m0其中Mo取原純整數(shù)線性規(guī)劃問題中，滿足約束條件的某一整數(shù)可行解所對應(yīng)的目標(biāo)函數(shù)值。原純整數(shù)線性規(guī)劃問題的最

32、優(yōu)解必須滿足定界條件。分枝：選?。▁1,x2，xn）中一個不為整數(shù)所對應(yīng)的xk分枝，Ri和R2稱為對應(yīng)線性規(guī)劃問題的兩枝，也是兩個新線性規(guī)劃問題的約束條件。顯然，原純整數(shù)線性規(guī)劃問題的最優(yōu)解滿足Ri或R2。（3）對R和R2進(jìn)行剪枝和分枝解Ri對應(yīng)的線性規(guī)劃問題，對其進(jìn)行剪枝和分枝：若無最優(yōu)解，則原純整數(shù)線性規(guī)劃問題在Ri內(nèi)無最優(yōu)解。不需要對該區(qū)域繼續(xù)討論一一剪枝。若有最優(yōu)解，最優(yōu)點(diǎn)（x1,x2，xn）,目標(biāo)函數(shù)的最優(yōu)值Z1=f（x1,x2，xn）。若Zi=f（x?,xi，x?）AMo,則原純整數(shù)線性規(guī)劃問題在Ri內(nèi)無最優(yōu)解。不需要對該區(qū)域繼續(xù)討論一一剪枝。若最優(yōu)點(diǎn)（丘以，X）全為整數(shù),則可能為

33、原純整數(shù)線性規(guī)劃問題的最優(yōu)解，定界：記M1=f（x,x2，xn）MM0,則Mi之mnf（x1，x?，xn）之m0,本分枝求解結(jié)束。若最優(yōu)點(diǎn)（工,二,，王）不全為整數(shù)，對Ri繼續(xù)進(jìn)行分枝。完全類似，解R2對應(yīng)線性規(guī)劃問題，對其進(jìn)行剪枝和分枝。依此類推，對所有分枝進(jìn)行求解，剪枝，分枝，定界；直至求得最優(yōu)解。（4）最優(yōu)解的確定若某Mk=m0,則為最優(yōu)解，求解結(jié)束。若所有分枝求解結(jié)束，則最后的上界Mk即為最優(yōu)解。例3:應(yīng)用分枝定界法，求解整數(shù)線性規(guī)劃問題解：設(shè)原整數(shù)線性規(guī)劃問題目標(biāo)函數(shù)的最優(yōu)值為z*,（i）求解線性規(guī)劃問題：minz=x1+3x2得最優(yōu)解為x1=8.12,x2=3.13；minz=17

34、.51。'x2之3.13記約束區(qū)域<22x1+34x2±285為R。x1>0,x2>0(2)對R進(jìn)行分枝：選取最優(yōu)解中不是整數(shù)的變量，例如x1，將R分成兩個子區(qū)域R,R2X_9x2,3.13x1M8R:人22x134x2,285x1_0,x2_0x2_3.13R：22x134x2,285(3)定界：確定最優(yōu)值z*的上下界。由(1)中求得的最優(yōu)值知z*至17.51;而z*的上界可由R內(nèi)的任意一個可行解確定，例如，、=7,x2=4即為一個可行解。故z*E19。從而，17.51Ez*E19。(4)在R內(nèi)求最優(yōu)解，得x1=9,x2=3.13;minz=18.39。(

35、5)在R2內(nèi)求最優(yōu)解，得X=8,x2=3.21;minz=17.62。(6)因?yàn)镽1內(nèi)最優(yōu)解不全是整數(shù)，因而必須繼續(xù)對R1分枝：(7)顯然憶內(nèi)無解，剪枝。在R11內(nèi)求最優(yōu)解，得為=9,x2=4;minz=21;為整數(shù)可行解。但因17.51Ez*E19,而21>19,故剪枝。(8)因?yàn)镽2內(nèi)最優(yōu)解不全是整數(shù)，因而必須繼續(xù)對R2分枝：(9)顯然R22內(nèi)無解，剪枝。在R21內(nèi)求最優(yōu)解，得x=6.77,x2=4;minz=18.77。(10)因?yàn)镽21內(nèi)最優(yōu)解不全是整數(shù)，因而必須繼續(xù)對R21分枝：(11)在R212內(nèi)求最優(yōu)解，得x1=6,x2=4.5;minz=19.5。因minz=19.5大于

36、z*的上界，故剪枝。(12)在R211內(nèi)求最優(yōu)解，得為=7,x2=4;minz=19。所求原整數(shù)規(guī)劃問題的最優(yōu)解為:§4最優(yōu)化問題數(shù)值算法x1=7,x2=4；minz=19。最優(yōu)化問題的數(shù)值算法很多，常用的算法多為搜索法，本節(jié)只介紹搜索法的基本思想、無約束最優(yōu)化問題的最速下降法(梯度法)和有約束最優(yōu)化問題的罰函數(shù)法。4.1搜索算法考慮無約束最優(yōu)化問題：minf(xi，X2，xn)我們已經(jīng)討論了這類問題的最優(yōu)解條件，這必須用到函數(shù)的解析性質(zhì)。我們的方法是，先利用必要條件求出平穩(wěn)點(diǎn)，再應(yīng)用充分條件判斷是否是極值點(diǎn)。但是，我們必須求解一個n個變量n個方程的方程組，并且常常是非線性的。這只有

37、在特殊的情況下，才能求出它的精確解。在一般情況下，都不能用解析法求得精確解。更何況許多實(shí)際問題中，函數(shù)的解析表達(dá)式很難得到。因此，我們必須尋求一些切合實(shí)際問題的行之有效的數(shù)值解法。搜索算法就是我們常用的方法。(1)搜索算法的基本思想：假定目標(biāo)函數(shù)f(X)極小值問題。首先，確定目標(biāo)函數(shù)f(X)的初始點(diǎn)Xo；然后，按照一定規(guī)則產(chǎn)生一個點(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)越好),允許誤差o>O,令k=0。假定已得非最優(yōu)點(diǎn)Xk,則選取一個搜索方向sk,滿足：目標(biāo)函數(shù)f(X

38、)下降，或gradf(Xk)V<0。選定搜索步長入>0,X+=Xk+限晟，滿足：f(X1)=f(Xk+MSk)-f(Xk)。判斷Xk書是否是最優(yōu)點(diǎn)或是滿足要求的近似解。假定給定精度要求為o>0,常用確定求近似解搜索結(jié)束的方法有：|gradf(Xki)卜：；梯度模確定法；|f(Xki)-f(Xk)卜：；目標(biāo)函數(shù)差值絕對誤差法；|Xk1-Xk|一一相鄰搜索點(diǎn)絕對誤差法。如果Xk書滿足給定精度要求，則搜索完成，近似最優(yōu)點(diǎn)為X*%Xk書；如果Xk書不滿足給定精度要求，令k=k+1返回(2)繼續(xù)搜索。注意1:我們的搜索算法一般得到的都是局部最優(yōu)解注意2:確定求近似解搜索結(jié)束的方法還有目

39、標(biāo)函數(shù)差值相對誤差法;If(Xk.i)-f(Xk)|If(Xk)|相鄰搜索點(diǎn)相對誤差法(3)搜索算法的關(guān)鍵因素：從搜索算法的基本步驟中，我們知道，搜索算法的關(guān)鍵因素為：一是搜索方向，二是搜索步長。搜索方向的選擇，一般考慮既要使它盡可能的指向極小值點(diǎn)，又要不至于花費(fèi)太多的計算量搜索步長的選擇，既要確保目標(biāo)函數(shù)的下降性質(zhì)，又要考慮近似解的精度要求，還要考慮算法的計算量，問題十分復(fù)雜。常用方法有，固定步長法，最優(yōu)步長法和變步長法。固定步長法(簡單算法)是選取如下0為固定值。方法簡單，但是有時不能保證目標(biāo)函數(shù)的下降性質(zhì)。最優(yōu)步長法(一維搜索算法)是選取人使得，這是一個關(guān)于單變量K的函數(shù)求極小值問題，這

40、樣確定的步長稱為最優(yōu)步變步長法(可接受點(diǎn)算法)是任意選取k只要使得f(Xk書)Mf(Xk)即可。這種選取步長的方法，確保了目標(biāo)函數(shù)的下降性質(zhì)，盡管每次選取的步長不是最優(yōu)的，但實(shí)踐證明，方法能達(dá)到更好的數(shù)值效果。總之，當(dāng)搜索方向確定以后，步長就是決定最優(yōu)化算法好壞的重要因素，因此，我們必須特別注重步長的選取問題。(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ì)的算法才有意義搜索算法的收斂速度：作為一個好的算法，還必須要求它以較快的速度收斂于

41、最優(yōu)解a階收斂定義：對于收斂于最優(yōu)解X*的序列Xk,若存在與k無關(guān)的數(shù)0<P(收和a21,當(dāng)k從某個k0開始時，有|Xki-X*|</Xk-X*L則稱序列Xk收斂的階為a,或稱a階收斂當(dāng)口=1時，稱迭代序列Xk為線性收斂；當(dāng)1cum2時，稱迭代序列Xk為超線性收斂；當(dāng)a=2時，稱迭代序列XJ為二階收斂一般來說，線性收斂是比較慢的，而二階收斂則是很快的，超線性收斂介于二者之間。如果一個算法具有超線性以上的收斂速度，我們就認(rèn)為是一個好的算法了。4.2無約束最優(yōu)化問題的梯度法無約束最優(yōu)化問題的計算方法很多。無約束最優(yōu)化問題的計算方法分為兩大類：一類是解析法，包括經(jīng)典最優(yōu)化方法，最速下降法

42、(梯度法)，共腕梯度法，牛頓法和變尺度法等。另一類是直接法，包括坐標(biāo)輪換法，步長加速法，方向加速法和單純形法等。所謂解析法就是在方法的計算過程中，應(yīng)用到了函數(shù)的解析性質(zhì)(可導(dǎo)性質(zhì)等)；所謂直接法就是在方法的計算過程中，僅僅涉及目標(biāo)函數(shù)值的計算，而不涉及函數(shù)導(dǎo)數(shù)等解析性質(zhì)。我們在這里只介紹最速下降法(梯度法)。最速下降法理論根據(jù)：早在1847年，法國著名數(shù)學(xué)家Cauchy就曾提出，從任意給定點(diǎn)出發(fā)，函數(shù)沿哪個方向下降最快的問題。這個問題已從理論上解決了，即沿著函數(shù)在該點(diǎn)的負(fù)梯度方向前進(jìn)時，函數(shù)下降最快。這就是最速下降法的理論根據(jù)。最速下降法的搜索步驟：步驟1:選定初始點(diǎn)Xo(越接近最優(yōu)點(diǎn)越好),

43、允許誤差50,令k=0。步驟2:假定已得非最優(yōu)點(diǎn)Xk,計算梯度gradf(Xk),選取搜索方向Sk=-gradXk)步驟3:選定搜索步長標(biāo)0,X«=Xk+刈£,滿足：“Xk+、Sk)=min“Xk十九4)。步驟4:判斷Xk書是否是最優(yōu)點(diǎn)或是滿足要求的近似解。根據(jù)精度要求，檢驗(yàn)是否滿足收斂性判斷準(zhǔn)則：|gradf(Xk+)|?；騶f(Xc)-f(Xk)|名或|Xk書-Xk|如果Xk中滿足給定精度要求，則搜索完成，近似最優(yōu)點(diǎn)為X*定Xk書;如果Xk書不滿足給定精度要求，令k=k+1返回(2)繼續(xù)搜索例1:應(yīng)用最速下降法求解minf(X)=x；+25x；。解：(1)選定初始點(diǎn)X0

44、=(2,2),允許誤差8=0.2,置k:=0收斂判斷準(zhǔn)則|f(Xk+)-f(Xk)|名。(2)計算梯度gradf(X。，選取搜索方向Sk=-gradf(Xk)graQXI=2x1,50x2)|x3，Sk=-2x1,-50x21|x%第一點(diǎn)搜索計算：gradf(Xo)=4,100,So=-4,-100)(3)選定搜索步長嬴>0,X«=Xk+嬴sk,滿足：第一點(diǎn)搜索計算：求最優(yōu)步長解得乂電0.02。(4)判斷Xk書是否是最優(yōu)點(diǎn)或是滿足要求的近似解。第一點(diǎn)搜索計算：Xi=(1.92,0)驗(yàn)證收斂判斷準(zhǔn)則|f(Xi)f(X。)卜100.31%0.02,不滿足，繼續(xù)搜索依次類推，直到搜索

45、到最優(yōu)解或滿足精度要求為止搜索計算列表如下：搜索步長Ak搜索方向Sk搜索點(diǎn)Xk函數(shù)值f(Xk)X2=(0,0)為最優(yōu)解4.3罰函數(shù)法對于約束最優(yōu)化問題也有許多種方法，本段只介紹把約束最優(yōu)化問題轉(zhuǎn)化為無約束最優(yōu)化問題的一種求解方法一一罰函數(shù)法。分為等式約束最優(yōu)化問題和不等式約束最優(yōu)化問題兩種情況討論。(1) 等式約束最優(yōu)化問題的罰函數(shù)法首先，考慮等式約束最優(yōu)化問題假定上述等式約束最優(yōu)化問題的最優(yōu)解存在。若記D=X|gi(X)=0,i=1,2,，m,XwRn),m構(gòu)造輔助函數(shù)T(X,M)=f(X)+MZgi(X)2罰函數(shù)i1其中M>0(罰因子)是一個充分大的正數(shù)。定理1:若對于某確定數(shù)M&g

46、t;0,無約束最優(yōu)化問題的最優(yōu)解X*wD,則X*必為原等式約束最優(yōu)化問題的最優(yōu)解。m證明：設(shè)無約束最優(yōu)化問題minT(X,M)=f(X)Mxgi(X)2iT的最優(yōu)解X*wD,則有:gi（x）=0而當(dāng)XwD時，T(X,M)=f(X)所以minf(X)=minT(X,M)=T(X*,M)=f(X*)即X*為原等式約束最優(yōu)化問題的最優(yōu)解。定理2:設(shè)f(X)和g.X)=0,i=1,2,，m均為連續(xù)函數(shù)，若對于任意正數(shù)M>0,無約束最優(yōu)化問題的最優(yōu)解X*(M)皂D,且limX*(M)=X*,M:：則limX*(M)=X*為原等式約束最優(yōu)化問題的最優(yōu)解。MF定理2的證明請參看有關(guān)參考資料。根據(jù)定理1

47、和定理2,我們就可以將通過構(gòu)造罰函數(shù)的方法化為無約束最優(yōu)化問題求解，這種方法稱為罰函數(shù)法。罰函數(shù)法的步驟：(等式約束最優(yōu)化問題罰函數(shù)法)m步驟1：構(gòu)造罰函數(shù)T(X,M)=f(X)+MZgi(X)2,i1選定M1>0,允許誤差s>0,令k：=1;步驟2:求無約束問題minT(X,Mk)的最優(yōu)解Xk；步驟3:判斷Xk是否是最優(yōu)點(diǎn)或是滿足要求的近似解。根據(jù)精度要求，檢驗(yàn)是否滿足收斂性判斷準(zhǔn)則：m2或“gi(Xk)i1如果滿足收斂性判斷準(zhǔn)則，則X*定X：,結(jié)束搜索；否則，令k:=k+1,取Mk+AMkA0,返回(2),繼續(xù)搜索。下面我們通過一個簡單的例子來說明等式約束最優(yōu)化問題的罰函數(shù)法。

48、例2:應(yīng)用罰函數(shù)法求解非線性規(guī)劃問題解：構(gòu)造罰函數(shù)：T(X,Mk)=X2x|Mk(x2-1)2求罰函數(shù)的最優(yōu)解：應(yīng)用解析法工=2x1,T=2x2+2Mk(x2-1)X1：x2令上述兩式等于零，解得x1=0,x2=Mk1Mk令MkT8得Xi=0,X2=1為所求最優(yōu)解。(2) 不等式約束最優(yōu)化問題的罰函數(shù)法對于，不等式約束最優(yōu)化問題假定上述不等式約束最優(yōu)化問題的最優(yōu)解存在。由于不等式約束條件gi(X)之0,i=1,2,，m等價于等式約束條件因而，上述不等式約束最優(yōu)化問題可以轉(zhuǎn)化為問題類似問題(1)構(gòu)造罰函數(shù)則將上述等式約束最優(yōu)化問題的求解轉(zhuǎn)化為下面無約束最優(yōu)化問題的求解:定理3:若對于某確定數(shù)M&

49、gt;0,無約束最優(yōu)化問題的最優(yōu)解X*wD,則X*必為原不等式約束最優(yōu)化問題的最優(yōu)解，其中D=X|gi(X)20,i=1,2,，m,XeRn)0定理4:設(shè)(1)f(X)和g.X)=0,i=1,2,，m均為連續(xù)函數(shù)；(2)原不等式約束最優(yōu)化問題的最優(yōu)解X*存在；(3)數(shù)列Mk滿足0<M1<M2<<Mk<且limMk="；k二(4)對任意MkA0,問題minT(X,M)的最優(yōu)解Xk=X(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(

50、X,M)=f(X)+M£mi0(gi(X)j,i1選定M1>0,允許誤差8A0,令k：=1;步驟2:求無約束問題minT(X,Mk)的最優(yōu)解Xk;步驟3:判斷Xk是否是最優(yōu)點(diǎn)或是滿足要求的近似解。根據(jù)精度要求，檢驗(yàn)是否滿足收斂性判斷準(zhǔn)則：m或"gi(Xk)2>i1.*如果滿足收斂性判斷準(zhǔn)則，則X*定Xk,結(jié)束搜索；否則，令k:=k+1,取Mk卡Mka。，返回(2),繼續(xù)搜索例3:應(yīng)用罰函數(shù)法求解非線性規(guī)劃問題m解：構(gòu)造罰函數(shù)T(X,M)=f(X)Mmi0(gi(X)2i1求T(X,Mk)的極小值點(diǎn)當(dāng)-xi2+X2a。,或xia。時，顯然上兩式不能同時等于零,所以

51、，此時T(X,Mk)不存在極小值點(diǎn)。當(dāng)一x12+x20,x1。時，有令上面兩式等于零:解得T(X,Mk)的極小值點(diǎn)為當(dāng)Mk取不同值時，可得到相應(yīng)的Xk值，計算如下表1101001000-0.25-0.04545-0.004950-0.00049950-0.4375-0.1415-0.004975-0.00049980根據(jù)定理得，原問題的極小值點(diǎn)為X*=(0,0),極小值為f(X*)=0§ 5 多目標(biāo)優(yōu)化問題在許多實(shí)際的最優(yōu)化問題中，常常遇到目標(biāo)函數(shù)是幾個的情況，這一類問題我們稱之為多目標(biāo)優(yōu)化問題。例如，投資方向選擇問題，我們不僅要求投資的收益最大，而且要求投資的風(fēng)險最小。再例如，購買

52、商品問題，我們既要考慮商品的價格，又要考慮商品的質(zhì)量，甚至還要考慮商品的性能等等。所謂多目標(biāo)優(yōu)化問題是指：目標(biāo)函數(shù)是兩個或兩個以上的最優(yōu)化問題。其數(shù)學(xué)模型為：minfi(xi,x2,xn)i=1,2,，s目標(biāo)函數(shù)gi(xi,x2,xn)=0i=1,2,m約束條件例1：求解多目標(biāo)優(yōu)化問題minx2和miny解：易求x=0,y=1時，minx2=0,miny=1。例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ù)多個性和目標(biāo)函數(shù)相互之間的復(fù)雜性質(zhì)決定的。由于目標(biāo)函數(shù)在很多情況下不可能同時達(dá)到最大值

53、或最小值，因而，多目標(biāo)最優(yōu)化問題很少有最優(yōu)解，而實(shí)際問題又要求我們做出決擇，求得一個比較好的解。什么樣的解才是我們需要的解呢？對于同一個問題不同的要求導(dǎo)致不同的求解標(biāo)準(zhǔn)，從而就會得到不同的求解結(jié)果。為此，我們給出多目標(biāo)最優(yōu)化問題的條件最優(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)解。對于一個多目標(biāo)優(yōu)化問題，即使最優(yōu)解存在，要求解它也是十分困難的，特殊情況下，我們也只好用搜索法求解。更何況它常常還不存在最優(yōu)

54、解，因而我們必須尋求其求解條件最優(yōu)解的方法。為了求得滿足我們要求的解，常常不得不設(shè)定一些新的條件，從而求得條件最優(yōu)解。設(shè)定新條件的方法是我們求解多目標(biāo)優(yōu)化問題的基本方法。下面的“單目標(biāo)化方法、多重目標(biāo)函數(shù)方法和目標(biāo)關(guān)聯(lián)函數(shù)方法”都是針對目標(biāo)函數(shù)設(shè)定新條件的方法。5.2單目標(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ù)f=f(f1,f2，fs)滿足性質(zhì)：在約束條件的區(qū)域內(nèi)f(fi,f2,，fs)是fl,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é)模型minf=f(fi,f2,，fs)目標(biāo)函數(shù)gi(Xi,X2,Xn)=0i=1,2,m約束條件步驟3:求解上述單目標(biāo)優(yōu)化數(shù)學(xué)模型得到：單目標(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)解與原多目