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

2、到求函數(shù)的極值或最大值最小值問(wèn)題，這一類(lèi)問(wèn)題我們稱(chēng)之為最優(yōu)化問(wèn)題。而求解最優(yōu)化問(wèn)題的數(shù)學(xué)方法被稱(chēng)為最優(yōu)化方法。它主要解決最優(yōu)生產(chǎn)計(jì)劃、最優(yōu)分配、最佳設(shè)計(jì)、最優(yōu)決策、最優(yōu)管理等求函數(shù)最大值最小值問(wèn)題。最優(yōu)化問(wèn)題的目的有兩個(gè)：求出滿(mǎn)足一定條件下，函數(shù)的極值或最大值最小值；求出取得極值時(shí)變量的取值。最優(yōu)化問(wèn)題所涉及的內(nèi)容種類(lè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)題中涉及的變量為X1,X2,xn；我們常常也用X(X1,X2,

3、Xn)表示。(3)約束條件在最優(yōu)化問(wèn)題中，求目標(biāo)函數(shù)的極值時(shí)，變量必須滿(mǎn)足的限制稱(chēng)為約束條件。例如，許多實(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ō)有兩種：等式約束條件gMX)0,i1,2,m不等式約束條件h(X)0,i1,2,r或”)0,i1,2,r注：在最優(yōu)化問(wèn)題研究中，由于解的存在性十分復(fù)雜，一般來(lái)說(shuō)，我們不考慮不等式約束條件h(X)0或h(X)00這兩種約束條件最優(yōu)化問(wèn)題最優(yōu)解的存在性較復(fù)雜。(4)目標(biāo)函數(shù)在最優(yōu)化問(wèn)題中，與變量有關(guān)

4、的待求其極值(或最大值最小值)的函數(shù)稱(chēng)為目標(biāo)函數(shù)。目標(biāo)函數(shù)常用f(X)f(Xi,X2,4)表示。當(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í)際上沒(méi)有原則上的區(qū)別，因?yàn)榍骹(X)的極小值，也就是要求f(X)的極大值，兩者的最優(yōu)值在同一點(diǎn)取到。2 .2最優(yōu)化問(wèn)題分類(lèi)最優(yōu)化問(wèn)題種類(lèi)繁多，因而分類(lèi)的方法也有許多。可以按變量的性質(zhì)分類(lèi)，按有無(wú)約束條件分類(lèi)，按目標(biāo)函數(shù)的個(gè)數(shù)分類(lèi)等等。一般來(lái)說(shuō)，變量可以分為確定性變量，隨機(jī)變量和系統(tǒng)變量等等，相對(duì)應(yīng)的最優(yōu)化問(wèn)題分別稱(chēng)為：普通最優(yōu)化問(wèn)題，統(tǒng)計(jì)最優(yōu)化問(wèn)題和系統(tǒng)最優(yōu)化問(wèn)題。按有無(wú)約束

5、條件分類(lèi)：無(wú)約束最優(yōu)化問(wèn)題，有約束最優(yōu)化問(wèn)題。按目標(biāo)函數(shù)的個(gè)數(shù)分類(lèi)：?jiǎn)文繕?biāo)最優(yōu)化問(wèn)題，多目標(biāo)最優(yōu)化問(wèn)題。按約束條件和目標(biāo)函數(shù)是否是線性函數(shù)分類(lèi)：線性最優(yōu)化問(wèn)題(線性規(guī)劃)，非線性最優(yōu)化問(wèn)題(非線性規(guī)劃)。按約束條件和目標(biāo)函數(shù)是否是時(shí)間的函數(shù)分類(lèi)：靜態(tài)最優(yōu)化問(wèn)題和動(dòng)態(tài)最優(yōu)化問(wèn)題(動(dòng)態(tài)規(guī)劃)。按最優(yōu)化問(wèn)題求解方法分類(lèi)：無(wú)約束解析法(間接法)古典微分法古典變分法有約束極大值原理庫(kù)恩圖克定理維搜索法數(shù)值算法(直接法)多維搜索法斐波那西法黃金分割法插值法坐標(biāo)輪換法步長(zhǎng)加速法方向加速法單純形法隨機(jī)搜索法無(wú)約束梯度法數(shù)值算法(梯度法)有約束梯度法最速下降法擬牛頓法共軻梯度法變尺度法可行方向法梯度投影法化有約

6、束為無(wú)約束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)化問(wèn)題的求解步驟和數(shù)學(xué)模型(1)最優(yōu)化問(wèn)題的求解步驟最優(yōu)化問(wèn)題的求解涉及到應(yīng)用數(shù)學(xué)，計(jì)算機(jī)科學(xué)以及各專(zhuān)業(yè)領(lǐng)域等等，是一個(gè)十分復(fù)雜的問(wèn)題，然而它卻是需要我們重點(diǎn)關(guān)心的問(wèn)題之一。怎樣研究分析求解這類(lèi)問(wèn)題呢？其中最關(guān)鍵的是建立數(shù)學(xué)模型和求解數(shù)學(xué)模型。一般來(lái)說(shuō)，應(yīng)用最優(yōu)化方法解決實(shí)際問(wèn)題可分為四個(gè)步驟進(jìn)行：步驟1:建立模型提出最優(yōu)化問(wèn)題，變量是什么？約束條件有那些？目標(biāo)函數(shù)是什么？建立最優(yōu)化問(wèn)題數(shù)學(xué)模型：確定變量，建立目標(biāo)函數(shù)，列出約束條件一一建立模型。步驟2:確定求解方法分析模型，根據(jù)

7、數(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é)模型的類(lèi)型密切相關(guān)，因而我們有必要對(duì)最優(yōu)化問(wèn)題的數(shù)學(xué)模型有所掌握。一般來(lái)說(shuō)，最優(yōu)化問(wèn)題的常見(jiàn)數(shù)學(xué)模型有以下幾種：無(wú)約束最優(yōu)化問(wèn)題數(shù)學(xué)模型由某實(shí)際問(wèn)題設(shè)立變量，建立一個(gè)目標(biāo)函數(shù)且無(wú)約束條件，這樣的求函數(shù)極值或最大值最小值問(wèn)題，我們稱(chēng)為無(wú)約束最優(yōu)化問(wèn)題。其數(shù)學(xué)模型為：minf(xi，X2，,Xn)目標(biāo)函數(shù)例如：求一元函數(shù)y

8、f(x)和二元函數(shù)zf(x,y)的極值。又例如：求函數(shù)f(x1,x2,x3)3x124x26x；2x1x24x1x32x2x3的極值和取得極值的點(diǎn)。有約束最優(yōu)化問(wèn)題數(shù)學(xué)模型由某實(shí)際問(wèn)題設(shè)立變量，建立一個(gè)目標(biāo)函數(shù)和若干個(gè)約束條件(等式或不等式)，這樣的求函數(shù)極值或最大值最小值問(wèn)題，我們稱(chēng)為有約束最優(yōu)化問(wèn)題。其數(shù)學(xué)模型為：gi(xi，x2,Xn)0i1,2,m約束條件有約束最優(yōu)化問(wèn)題的例子：求函數(shù)f(Xi,X2,X3)X1X3Xn在約束條件條件XiX3Xn2008,Xi0,i1,2,n下的最大值和取得最大值的點(diǎn)。線性規(guī)劃問(wèn)題數(shù)學(xué)模型由某實(shí)際問(wèn)題設(shè)立變量，建立一個(gè)目標(biāo)函數(shù)和若干個(gè)約束條件，目標(biāo)函數(shù)和

9、約束條件都是變量的線性函數(shù)，而且變量是非負(fù)的，這樣的求函數(shù)最大值最小值問(wèn)題，我們稱(chēng)為線性最優(yōu)化問(wèn)題，簡(jiǎn)稱(chēng)為線性規(guī)劃問(wèn)題。其標(biāo)準(zhǔn)數(shù)學(xué)模型為：minf(x1,x2,Xn)c1X1c2X2cnXn目標(biāo)函數(shù)2仙1a2X2xi0aimXnbii1,2,m約束條件目標(biāo)函數(shù)約束條件矩陣形式：minf(X)CTXAXBX0其中X(X1,X2,Xn)，C(C1,C2,Cn)T,B(兒也，,bm)T在線性規(guī)劃問(wèn)題中，關(guān)于約束條件我們必須注意以下幾個(gè)問(wèn)題。注1:非負(fù)約束條件Xi0(i1,2,n),一般來(lái)說(shuō)這是實(shí)際問(wèn)題要求的需要如果約束條件為Xid我們作變量替換ZiXidi0;如果約束條件為Xid我們作變量替換Zid

10、iXi0o注2:在線性規(guī)劃的標(biāo)準(zhǔn)數(shù)學(xué)模型中，約束條件為等式。如果約束條件不是等式，我們引入松馳變量，化不等式約束條件為等式約束條件。情況1:若約束條件為ai1x1ai2x2aimxnbi,引入松馳變量原約束條件變?yōu)閍MX1ai2X2amXn乙bi。情況2:若約束條件為ai1X1ai2X2aXnbi,引入松馳變量原約束條件變?yōu)閍MX1ai2X2aimXnZibi在其它最優(yōu)化問(wèn)題中，我們也常常采取上述方法化不等式約束條件為等式約束條件。實(shí)際問(wèn)題中，我們經(jīng)常遇到兩類(lèi)特殊的線性規(guī)劃問(wèn)題。一類(lèi)是：所求變量要求是非負(fù)整數(shù)，稱(chēng)為整數(shù)規(guī)劃問(wèn)題；另一類(lèi)是所求變量要求只取0或1,稱(chēng)為0-1規(guī)劃問(wèn)題。例如：整數(shù)規(guī)劃

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

12、x,y)xy20og2(x,y)y0上述最優(yōu)化問(wèn)題中，目標(biāo)函數(shù)是非線性函數(shù)，故稱(chēng)為非線性規(guī)劃問(wèn)題。前面介紹的四種最優(yōu)化數(shù)學(xué)模型都只有一個(gè)目標(biāo)函數(shù)，稱(chēng)為單目標(biāo)最優(yōu)化問(wèn)題，簡(jiǎn)稱(chēng)為最優(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)題，我們稱(chēng)為多目標(biāo)最優(yōu)化問(wèn)題。其數(shù)學(xué)模型為：minfi(Xi,x2,%)i1,2,s目標(biāo)函數(shù)gigE,Xn)0i1,2,m約束條件上述模型中有s個(gè)目標(biāo)函數(shù)，m個(gè)等式約束條件。例如：“生產(chǎn)商如何使得產(chǎn)值最大而且消耗資源最少問(wèn)題”“投資商如何使得投資收益最大而且風(fēng)險(xiǎn)最小問(wèn)

13、題”等都是多目標(biāo)最優(yōu)化問(wèn)題。2經(jīng)典最優(yōu)化方法經(jīng)典最優(yōu)化方法包括無(wú)約束條件極值問(wèn)題和等式約束條件極值問(wèn)題兩種，不等式約束條件極值問(wèn)題可以化為等式約束條件極值問(wèn)題。經(jīng)典的極值理論：首先，根據(jù)可微函數(shù)取極值的必要條件確定可能極值點(diǎn)；其次，根據(jù)函數(shù)取極值的充分條件判斷是否取極值？是極大值？還是極小值？這種方法已經(jīng)幾百年的歷史了。2.1無(wú)約束條件極值設(shè)n元函數(shù)f(X)f(Xi，X2，,Xn),求f(X)的極值和取得極值的點(diǎn)。這是一個(gè)無(wú)約束條件極值問(wèn)題，經(jīng)典的極值理論如下。定理1(極值必要條件)：設(shè)n元函數(shù)f(X)f(x1,x2,xn)具有偏導(dǎo)數(shù)，則f(X)在XX*處取得極值的必要條件為：fXilxi1,

14、2,n定理在此不給出證明，讀者可自己參看有關(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ù)不取極定理1的作用在于，求出函數(shù)的可能極值點(diǎn)，然后，我們?cè)傺芯窟@些點(diǎn)是否取得極值。對(duì)于許多實(shí)際問(wèn)題來(lái)說(shuō)，函數(shù)一定能夠取

15、得極大值或極小值，而函數(shù)的可能極值點(diǎn)(滿(mǎ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(xi,x2,xn)具有二階偏導(dǎo)數(shù)，則f(X)在XX*處取得極值的充分條件為：(Df|XX*0i2,3,n；xi(2)黑塞矩陣2fxi22fx2xi2fxix22f2-x2xixnx2xn*4、L*、X處正止或負(fù)止;2fxnxi2fxxx2(3)黑塞矩陣在XX*處正定時(shí)，函數(shù)取極小值；負(fù)定時(shí)，函數(shù)取極大值。本章內(nèi)容簡(jiǎn)要講解理論，注重實(shí)際應(yīng)

16、用，對(duì)于許多經(jīng)典的定理都不進(jìn)行證明，讀者可自己參看有關(guān)資料。例i:求函數(shù)f函？2?3)2x26x24x322xix22x2x3的極值。解：(i)根據(jù)極值存在的必要條件，確定可能取得極值的點(diǎn):fxi4xi2x2,fx2i2x22為2x3,fx38x32x2令fff0,解得(為乃)(0,0,0)xix2x3(2)根據(jù)極值存在的充分條件，確定(xi,x2,x3)(0,0,0)是否是極值點(diǎn):2f計(jì)算-4X14,2f-2X212,2fX38；2f2,2f2f2；XiX2XiX3X2X3函數(shù)的黑塞矩陣為2f(0,0,0)2122212440,2122所以黑塞矩陣負(fù)定,故函數(shù)在(為？2,%)(0,0,0)處

17、取得極大值f(0,0,0)0。2.2等式約束條件極值下面我們研究的是有若干個(gè)等式約束條件下，一個(gè)目標(biāo)函數(shù)的極值問(wèn)題，其數(shù)學(xué)模型為:minf(X1,X2,Xn)目標(biāo)函數(shù)stgi(X1,X2,Xn)01,2,m約束條件拉格朗日(Lagrange)乘數(shù)法：(1)令Lf(x，X2,Xmigi(X1,X2,i1稱(chēng)為上述問(wèn)題的拉格朗日乘數(shù)函數(shù)，稱(chēng)i為拉格朗日乘數(shù)。)均可微，則得到方程組(2)設(shè)faL，內(nèi))和gi(x1，X2,x(3)若(X1,X2,Xn,1,2,m)是上述方程組的解，則點(diǎn)(X1,X2,Xn)可能為該問(wèn)題的最優(yōu)點(diǎn)。拉格朗日(Lagrange)乘數(shù)法的本質(zhì)是：將求有約束條件極值問(wèn)題轉(zhuǎn)化為求無(wú)條

18、件極值問(wèn)題；所求得的點(diǎn)，即是取得極值的必要條件點(diǎn)。拉格朗日乘數(shù)法沒(méi)有解決極值的存在性問(wèn)題，但是，如果拉格朗日乘數(shù)函數(shù)具有二階連續(xù)偏導(dǎo)數(shù)，我們也可以應(yīng)用黑案矩陣來(lái)判定函數(shù)是否取得極值。在具體問(wèn)題中，點(diǎn)(X1,XL,X?)是否為最優(yōu)點(diǎn)通常可由問(wè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,z)xyz(2xy2yz2xza2),則有解得-amaxV6、,636為所求。2.3不等式約束條件極值對(duì)于不等式約束條件極值問(wèn)題:目標(biāo)函數(shù)minf(xi,X2，,Xn)s.t.gi

19、(Xi,X2,Xn)0i1,2,m約束條件我們有與拉格朗日乘數(shù)法密切相關(guān)的方法庫(kù)恩圖克定理。定理3(庫(kù)恩圖克定理)：對(duì)于上述不等式約束條件極值問(wèn)題，設(shè)f(Xi，X2，,4)和gi(Xi,X2,Xn)均可微，令Lf(X1,X2,Xn)假設(shè)i存在，則在最優(yōu)點(diǎn)XX(Dfxj_gIXj(2) gi(X1,X2,Xn)0(3) igi(X1,X2,Xn)0migi(X1，X2，,Xn)i1(%,x2,xn)處，必滿(mǎn)足下述條件:j1.2,n；i1,2,m；i1,2,m;(4)i0根據(jù)庫(kù)恩一圖克定理我們可以求解許多不等式約束條件極值問(wèn)題，值得注意的是應(yīng)用庫(kù)恩一圖克定理求解不等式約束條件極值問(wèn)題，定理并沒(méi)有解

20、決最優(yōu)解的存在性問(wèn)題，因此，我們必須另行判斷。例3:求解最優(yōu)化問(wèn)題(最優(yōu)解存在)解：構(gòu)造函數(shù)L(x,y,z)(x1)2y1(xy2)2(y),2(x1)10x-y1120根據(jù)庫(kù)恩圖克定理則有y1(xy2)02y010,20解得：X1,y0,10,21；所求最優(yōu)解為(X,y)(1,0),最優(yōu)值為03線性規(guī)劃3. 1線性規(guī)劃設(shè)線性規(guī)劃標(biāo)準(zhǔn)數(shù)學(xué)模型為：minf(x1,X2,Xn)C1X1C2X2cnxn目標(biāo)函數(shù)aiiXi2X2s.t.xi0aimXnbii1,2,mi1,2,n約束條件矩陣形式：minf(X)CTX目標(biāo)函數(shù)其中AXBX0約束條件X(Xi,X2,Xn)，C(Ci,C2,Cn)T,B(b

21、i,b2,bm)T線性規(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ù)矩陣的秩R(A)m,則對(duì)應(yīng)線性方程組的基Xi(nm)0,解得對(duì)應(yīng)線性方程組一組解為礎(chǔ)解系自由變量的個(gè)數(shù)為nm個(gè)步驟2:窮舉法求解：令X1%(X1,X2,Xn)；對(duì)應(yīng)目標(biāo)函數(shù)值為f(X,X

22、2,Xn)工。從n個(gè)變量X中選nm個(gè)作為自由變量，令它們的值為0,可得到CnmCn1m組解。步驟3：確定最優(yōu)解：如果最優(yōu)解存在，則上述求解得到的對(duì)應(yīng)Cnmcn1m個(gè)目標(biāo)函數(shù)值中,最小者(或最大者)即為所求最小(或最大)最優(yōu)值，對(duì)應(yīng)的解為最優(yōu)解。步驟4:證明解為最優(yōu)解：將最優(yōu)解對(duì)應(yīng)的自由變量看成參數(shù)t1,t2,t(nm)；解對(duì)應(yīng)線性方程組得Xb0bi1t1bi2t2b(nm)t(nm),i1,2,n。將對(duì)應(yīng)線性方程組解Xbi0bi1t1bi2t2bi(nm)t(nm),i1,2,n代入目標(biāo)函數(shù)得：ff0Md2t2d(nm)t(nm)。如果d0,i1,2,n，則所求為最小值最優(yōu)解；否則，線性規(guī)劃問(wèn)

23、題無(wú)最小值最優(yōu)解。如果di0,i1,2,n，則所求為最大值最優(yōu)解；否則，線性規(guī)劃問(wèn)題無(wú)最大值最優(yōu)解。例1:目標(biāo)函數(shù)：maXf(X)2x13x2x3解：約束條件的增廣矩陣為：10100A12010,R(A)3;01001令X1X2(0,0,5,10,4),f(X)5;令XiX30,無(wú)解;令XiX4(0,5,5,0,1),不滿(mǎn)足非負(fù)條件，舍去;令XiX50,解得X(0,4,5,2,0),f(X)17;令X2X30,解得X(5,0,0,5,4),f(X)10；令X2X40,解得X(10,0,5,0,4),不滿(mǎn)足非負(fù)條件，舍去;令X2X50,無(wú)解；令XX40,解得X(5,5,0,0,3),f(X)更；

24、222令X3X50,解得X(5,4,0,3,0),不滿(mǎn)足非負(fù)條件，舍去；令X4x50,解得X(2,4,3,0,0),f(X)19；所以maxf(X)19,最優(yōu)解為X(2,4,3,0,0)。證明：令X4t,X5s解得X12t2sx24s目標(biāo)函數(shù)f(X)19ts;X33t2sX0,i1,5因?yàn)閄4t,X5s非負(fù)，所以maxf(X)19,故最優(yōu)解存在。(2)單純形法基本原理和步驟將線性規(guī)劃問(wèn)題化成矩陣的標(biāo)準(zhǔn)形式，設(shè)系數(shù)矩陣的秩R(A)m,則對(duì)應(yīng)線性方程組的基礎(chǔ)解系的個(gè)數(shù)為nm個(gè)，即有nm個(gè)自由參數(shù)變量。選取nm個(gè)非基變量(自由參數(shù)變量)，不妨假設(shè)為Xj,jm1,n；解得線性規(guī)劃問(wèn)題的典式定理1:如果

25、線性規(guī)劃問(wèn)題的上述典式中所有j0,jm1,n；則X(1,2,m,0,0)為最優(yōu)解。定理2:如果線性規(guī)劃問(wèn)題的上述典式中存在某個(gè)mk0,且對(duì)應(yīng)i(mk)0,i1,2,m;則線性規(guī)劃問(wèn)題無(wú)最優(yōu)解。由定理1和定理2知，如果我們選擇適當(dāng)?shù)膎m個(gè)非基變量，就可以根據(jù)所求得的典式判斷最優(yōu)解的存在與否，從而求解該線性規(guī)劃問(wèn)題。單純形法的思想是：選擇適當(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è)基變量的

26、下標(biāo))由此確定XJr離基。單純形法的基本步驟：步驟1:化線性規(guī)劃問(wèn)題為標(biāo)準(zhǔn)形式。步驟2:確定基變量，求得基本可行解和典式；是否滿(mǎn)足最優(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)約束條件的增廣矩陣為：11100A110162000,R(A)3;1所以非基變量個(gè)數(shù)為兩個(gè)(2)選取X1,X2作為非基變量，X3,X4,X5作為基變量，解得典式為不滿(mǎn)足最優(yōu)解定理和最優(yōu)解不存在定理的條件，故必須進(jìn)行基變換(3)進(jìn)行基變換選取進(jìn)基：120,210

27、,根據(jù)sminj|j0得Xi為進(jìn)基選取退基:521mini，216，is0得X5為離基選取進(jìn)基:選取退基:12-0,根據(jù)s392121叫丁,金minj|j0得X2為進(jìn)基。根據(jù)min|is0,JrminJi|Lisis進(jìn)行基變換，求新基的典式：判斷：不滿(mǎn)足最優(yōu)解定理和最優(yōu)解不存在定理的條件，故繼續(xù)進(jìn)行基變換(4)繼續(xù)進(jìn)行基變換is0得X3為離基根據(jù)min1is0,JrminJi|1isis進(jìn)行基變換，求新基的典式：滿(mǎn)足最優(yōu)解定理的條件，根據(jù)定理最優(yōu)解為1191(了,4。210),minf313.2整數(shù)規(guī)劃設(shè)純整數(shù)線性規(guī)劃數(shù)學(xué)模型為:minf(x1，x2,Xn)C1X1C2X2cnxn目標(biāo)函數(shù),a

28、i1X1s.t.Xi2X2aimXnbi0,X為整數(shù)i1,2,mi1,2,n約束條件這一類(lèi)問(wèn)題與一般線性規(guī)劃比較起來(lái)，似乎是變簡(jiǎn)單了，但實(shí)際上恰恰相反，由于解集是一些離散的整數(shù)點(diǎn)集，使得單純形法失去了應(yīng)用的基礎(chǔ)，求解變得困難而復(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)題ai1X1ai2X2s.t.Xi0minf(X1,X2,Xn)C1X1C2X2CnXn目標(biāo)函數(shù)約束條件aimXnbii1,2,mi1,2,

29、n若無(wú)最優(yōu)解，則原純整數(shù)線性規(guī)劃問(wèn)題無(wú)最優(yōu)解；若有最優(yōu)解，最優(yōu)點(diǎn)(X1,X2,Xn),目標(biāo)函數(shù)最優(yōu)值Z0f(X1,X2,Xn)。若最優(yōu)點(diǎn)(X1,X2,Xn)全為整數(shù)，則為原純整數(shù)線性規(guī)劃問(wèn)題的最優(yōu)解;若最優(yōu)點(diǎn)(Xi，X2，,%)不全為整數(shù)，則進(jìn)行下一步(2)定界和分枝定界：M0minf(x1,x2,xn)z0m0其中M。取原純整數(shù)線性規(guī)劃問(wèn)題中，滿(mǎn)足約束條件的某一整數(shù)可行解所對(duì)應(yīng)的目標(biāo)函數(shù)值。原純整數(shù)線性規(guī)劃問(wèn)題的最優(yōu)解必須滿(mǎn)足定界條件。分枝：選取(x1,x2,xn)中一個(gè)不為整數(shù)所對(duì)應(yīng)的xk分枝，R1和R2稱(chēng)為對(duì)應(yīng)線性規(guī)劃問(wèn)題的兩枝，也是兩個(gè)新線性規(guī)劃問(wèn)題的約束條件。顯然，原純整數(shù)線性規(guī)劃問(wèn)

30、題的最優(yōu)解滿(mǎn)足R或R2。(3)對(duì)電和2進(jìn)行剪枝和分枝解R1對(duì)應(yīng)的線性規(guī)劃問(wèn)題，對(duì)其進(jìn)行剪枝和分枝：若無(wú)最優(yōu)解，則原純整數(shù)線性規(guī)劃問(wèn)題在R內(nèi)無(wú)最優(yōu)解。不需要對(duì)該區(qū)域繼續(xù)討論一一剪枝若有最優(yōu)解，最優(yōu)點(diǎn)(x1,x2,xn),目標(biāo)函數(shù)的最優(yōu)值Z1f(X1,x2,xn)若乙f(Xi，X2,Xn)M。，則原純整數(shù)線性規(guī)劃問(wèn)題在Ri內(nèi)無(wú)最優(yōu)解。不需要對(duì)該區(qū)域繼續(xù)討論剪枝。若最優(yōu)點(diǎn)(X1,X2,xn)全為整數(shù)，則可能為原純整數(shù)線性規(guī)劃問(wèn)題的最優(yōu)解，定界：記M1f(x1,x2,xn)M。，則Miminf(x1，X2,Xn)m。，本分枝求解結(jié)束。若最優(yōu)點(diǎn)(X；X；,Xj不全為整數(shù)，對(duì)Ri繼續(xù)進(jìn)行分枝。完全類(lèi)似，解

31、R2對(duì)應(yīng)線性規(guī)劃問(wèn)題，對(duì)其進(jìn)行剪枝和分枝。依此類(lèi)推，對(duì)所有分枝進(jìn)行求解，剪枝，分枝，定界；直至求得最優(yōu)解。(4)最優(yōu)解的確定若某Mkm。，則為最優(yōu)解，求解結(jié)束。若所有分枝求解結(jié)束，則最后的上界Mk即為最優(yōu)解。例3:應(yīng)用分枝定界法，求解整數(shù)線性規(guī)劃問(wèn)題解：設(shè)原整數(shù)線性規(guī)劃問(wèn)題目標(biāo)函數(shù)的最優(yōu)值為z*,(1)求解線性規(guī)劃問(wèn)題：minzx13x2得最優(yōu)解為Xi8.12,X23.13；minz17.51。3.13記約束區(qū)域22x134x2285為R0,x20(2)對(duì)R進(jìn)行分枝：選取最優(yōu)解中不是整數(shù)的變量，例如”,將R分成兩個(gè)子區(qū)域R1,R2x19x23.1322x134X22850,X2034X2285

32、0,X20x18x23.13(3)定界：確定最優(yōu)值z(mì)*的上下界。由(1)中求得的最優(yōu)值知z*17.51;而z*的上界可由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ù)，因而必須繼續(xù)對(duì)R分枝：(7)顯然R12內(nèi)無(wú)解，剪枝。在內(nèi)求最優(yōu)解，得x19,x24;minz21;為整數(shù)可行解。但因17.51z*19,而2119,故剪枝。(8)因?yàn)镽2內(nèi)最優(yōu)解不全是整數(shù)，因而必須繼續(xù)對(duì)R2分枝：

33、(9)顯然R22內(nèi)無(wú)解，剪枝。在&1內(nèi)求最優(yōu)解，得X16.77,X24;minz18.77。(10)因?yàn)镽21內(nèi)最優(yōu)解不全是整數(shù)，因而必須繼續(xù)對(duì)R21分枝：(11)在&12內(nèi)求最優(yōu)解，得x16,x24.5;minz19.5。因minz19.5大于z*的上界，故剪枝。(12)在1內(nèi)求最優(yōu)解，得X17,X24;minz19。所求原整數(shù)規(guī)劃問(wèn)題的最優(yōu)解為：x17,x24；minz19。4最優(yōu)化問(wèn)題數(shù)值算法最優(yōu)化問(wèn)題的數(shù)值算法很多，常用的算法多為搜索法，本節(jié)只介紹搜索法的基本思想、無(wú)約束最優(yōu)化問(wèn)題的最速下降法(梯度法)和有約束最優(yōu)化問(wèn)題的罰函數(shù)法。4. 1搜索算法考慮無(wú)約束最優(yōu)化問(wèn)題：minf(x1,

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

35、列Xk收斂；(2)點(diǎn)列Xk收斂到目標(biāo)函數(shù)f(X)的極小值點(diǎn)。(2)搜索算法的基本步驟：選定初始點(diǎn)X。(越接近最優(yōu)點(diǎn)越好)，允許誤差0,令k0o假定已得非最優(yōu)點(diǎn)Xk,則選取一個(gè)搜索方向Sk,滿(mǎn)足：目標(biāo)函數(shù)f(X)下降，或gradf(Xk)?Sk0。選定搜索步長(zhǎng)k0,Xk1XkkSk,滿(mǎn)足：f(Xk1)f(XkkSk)f(Xk)。判斷Xk1是否是最優(yōu)點(diǎn)或是滿(mǎn)足要求的近似解。假定給定精度要求為0,常用確定求近似解搜索結(jié)束的方法有:|gradf(Xk1)|梯度模確定法；|f(Xki)f(Xk)|目標(biāo)函數(shù)差值絕對(duì)誤差法；|Xk1Xk|相鄰搜索點(diǎn)絕對(duì)誤差法。如果Xki滿(mǎn)足給定精度要求，則搜索完成，近似最優(yōu)

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

37、長(zhǎng)法。固定步長(zhǎng)法(簡(jiǎn)單算法)是選取k。為固定值。方法簡(jiǎn)單，但是有時(shí)不能保證目標(biāo)函數(shù)的下降性質(zhì)。最優(yōu)步長(zhǎng)法(一維搜索算法)是選取k使得，這是一個(gè)關(guān)于單變量的函數(shù)求極小值問(wèn)題，這樣確定的步長(zhǎng)稱(chēng)為最優(yōu)步長(zhǎng)。變步長(zhǎng)法(可接受點(diǎn)算法)是任意選取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)的選取問(wèn)題。(4)搜索算法的收斂性：搜索算法的收斂性是指，由某算法得到的點(diǎn)列XJ能夠在有限步驟內(nèi)收斂到目標(biāo)函數(shù)f(X)的最優(yōu)

38、點(diǎn)或能夠在有限步驟內(nèi)達(dá)到滿(mǎn)足精度要求的目標(biāo)函數(shù)f(X)的最優(yōu)點(diǎn)的近似值。顯然，只有具有收斂性質(zhì)的算法才有意義。搜索算法的收斂速度：作為一個(gè)好的算法，還必須要求它以較快的速度收斂于最優(yōu)解。階收斂定義：對(duì)于收斂于最優(yōu)解X*的序列Xk,若存在與k無(wú)關(guān)的數(shù)0和i,當(dāng)k從某個(gè)k。開(kāi)始時(shí)，有|XkiX*|XkX*|成立，則稱(chēng)序列Xk收斂的階為,或稱(chēng)階收斂當(dāng)1時(shí)，稱(chēng)迭代序列Xk為線性收斂；當(dāng)12時(shí)，稱(chēng)迭代序列Xk為超線性收斂；當(dāng)2時(shí)，稱(chēng)迭代序列Xk為二階收斂。一般來(lái)說(shuō)，線性收斂是比較慢的，而二階收斂則是很快的，超線性收斂介于二者之間。如果一個(gè)算法具有超線性以上的收斂速度，我們就認(rèn)為是一個(gè)好的算法了。4.2無(wú)

39、約束最優(yōu)化問(wèn)題的梯度法無(wú)約束最優(yōu)化問(wèn)題的計(jì)算方法很多。無(wú)約束最優(yōu)化問(wèn)題的計(jì)算方法分為兩大類(lèi)：一類(lèi)是解析法，包括經(jīng)典最優(yōu)化方法，最速下降法(梯度法)，共腕梯度法，牛頓法和變尺度法等。另一類(lèi)是直接法，包括坐標(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就曾提出，從任意給定點(diǎn)出發(fā)，函數(shù)沿哪個(gè)方向下降最快的問(wèn)題。這個(gè)問(wèn)題已從理論上解決了，即沿著函

40、數(shù)在該點(diǎn)的負(fù)梯度方向前進(jìn)時(shí)，函數(shù)下降最快。這就是最速下降法的理論根據(jù)。最速下降法的搜索步驟：步驟1:選定初始點(diǎn)Xo(越接近最優(yōu)點(diǎn)越好)，允許誤差0,令k00步驟2：假定已得非最優(yōu)點(diǎn)Xk,計(jì)算梯度gradf(Xk),選取搜索方向Skgradf(Xk)步驟3:選定搜索步長(zhǎng)k0,Xk1XkkSk,滿(mǎn)足：f(Xkk&)minf(XkSk)。0步驟4:判斷Xk1是否是最優(yōu)點(diǎn)或是滿(mǎn)足要求的近似解。根據(jù)精度要求，檢驗(yàn)是否滿(mǎn)足收斂性判斷準(zhǔn)則：|gradf(Xk1)|或|f(Xk1)f(Xk)|或|Xk1X*如果Xk1滿(mǎn)足給定精度要求，則搜索完成，近似最優(yōu)點(diǎn)為X*Xk1；如果Xk1不滿(mǎn)足給定精度要求，令kk1返

41、回(2)繼續(xù)搜索。例1:應(yīng)用最速下降法求解minf(X)x225x2。解：(1)選定初始點(diǎn)X。(2,2),允許誤差0.2,置k:0收斂判斷準(zhǔn)則|f(Xk1)f(Xk)|。(2)計(jì)算梯度gradf(Xk),選取搜索方向Skgradf(Xk)gradf(Xk)2x1,50x2|xXk,Sk2x1,50x2|XXk第一點(diǎn)搜索計(jì)算：gradf(Xo)4,100,S。4,100)(3)選定搜索步長(zhǎng)k0,XkiXkkSk,滿(mǎn)足：第一點(diǎn)搜索計(jì)算：求最優(yōu)步長(zhǎng)解得00.02。(4)判斷Xki是否是最優(yōu)點(diǎn)或是滿(mǎn)足要求的近似解。第一點(diǎn)搜索計(jì)算：Xi(1.92,0)驗(yàn)證收斂判斷準(zhǔn)則|f(Xi)f(X0)|100.31

42、0.02,不滿(mǎn)足，繼續(xù)搜索依次類(lèi)推，直到搜索到最優(yōu)解或滿(mǎn)足精度要求為止搜索計(jì)算列表如下：搜索步長(zhǎng)k搜索方向Sk搜索點(diǎn)Xk函數(shù)值f(Xk)X2(0,0)為最優(yōu)解4.3罰函數(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)解存在。若記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ì)于

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

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

45、x12x；Mk(x21)2求罰函數(shù)的最優(yōu)解：應(yīng)用解析法2x1,T-2x22mk(x21)X1x2令上述兩式等于零，解得x10,x21 Mk令Mk得x10,x21為所求最優(yōu)解。2 2)不等式約束最優(yōu)化問(wèn)題的罰函數(shù)法對(duì)于，不等式約束最優(yōu)化問(wèn)題假定上述不等式約束最優(yōu)化問(wèn)題的最優(yōu)解存在。由于不等式約束條件gi(X)0,i1,2,m等價(jià)于等式約束條件因而，上述不等式約束最優(yōu)化問(wèn)題可以轉(zhuǎn)化為問(wèn)題類(lèi)似問(wèn)題(1)構(gòu)造罰函數(shù)則將上述等式約束最優(yōu)化問(wèn)題的求解轉(zhuǎn)化為下面無(wú)約束最優(yōu)化問(wèn)題的求解：定理3:若對(duì)于某確定數(shù)M0,無(wú)約束最優(yōu)化問(wèn)題的最優(yōu)解X*D,則X*必為原不等式約束最優(yōu)化問(wèn)題的最優(yōu)解，其中DX|gi(X)0

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

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

48、0.00049950-0.4375-0.1415-0.004975-0.00049980根據(jù)定理得，原問(wèn)題的極小值點(diǎn)為X*(0,0),極小值為f(X*)05多目標(biāo)優(yōu)化問(wèn)題在許多實(shí)際的最優(yōu)化問(wèn)題中，常常遇到目標(biāo)函數(shù)是幾個(gè)的情況，這一類(lèi)問(wèn)題我們稱(chēng)之為多目標(biāo)優(yōu)化問(wèn)題。例如，投資方向選擇問(wèn)題，我們不僅要求投資的收益最大，而且要求投資的風(fēng)險(xiǎn)最小。再例如，購(gòu)買(mǎi)商品問(wèn)題，我們既要考慮商品的價(jià)格，又要考慮商品的質(zhì)量，甚至還要考慮商品的性能等等。所謂多目標(biāo)優(yōu)化問(wèn)題是指：目標(biāo)函數(shù)是兩個(gè)或兩個(gè)以上的最優(yōu)化問(wèn)題。其數(shù)學(xué)模型為：minfi(x1,x2,xn)i1,2,s目標(biāo)函數(shù)gi(Xi,X2,Xn)0i1,2,m約束

49、條件例1：求解多目標(biāo)優(yōu)化問(wèn)題minX2和miny解：易求x0,y1時(shí)，minx20,miny1。例2:求解多目標(biāo)優(yōu)化問(wèn)題maxx2和miny解：顯然，無(wú)最優(yōu)解。5.1多目標(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)題不同的要求導(dǎo)致不同的求解標(biāo)準(zhǔn)，從而就會(huì)得到不同的求解結(jié)果。為此，我們給出多目標(biāo)最優(yōu)化問(wèn)題的條件最優(yōu)解概念。最優(yōu)解：滿(mǎn)足約束條件

50、且使所有目標(biāo)函數(shù)達(dá)到要求的最大值或最小值的點(diǎn)稱(chēng)為多目標(biāo)優(yōu)化問(wèn)題的最優(yōu)解。可行解：滿(mǎn)足多目標(biāo)優(yōu)化問(wèn)題的約束條件的點(diǎn)稱(chēng)為可行解。條件最優(yōu)解：滿(mǎn)足多目標(biāo)優(yōu)化問(wèn)題的約束條件且滿(mǎn)足根據(jù)需要設(shè)定條件的可行解稱(chēng)為條件最優(yōu)解。對(duì)于一個(gè)多目標(biāo)優(yōu)化問(wèn)題，即使最優(yōu)解存在，要求解它也是十分困難的，特殊情況下，我們也只好用搜索法求解。更何況它常常還不存在最優(yōu)解，因而我們必須尋求其求解條件最優(yōu)解的方法。為了求得滿(mǎn)足我們要求的解，常常不得不設(shè)定一些新的條件，從而求得條件最優(yōu)解。設(shè)定新條件的方法是我們求解多目標(biāo)優(yōu)化問(wèn)題的基本方法。下面的“單目標(biāo)化方法、多重目標(biāo)函數(shù)方法和目標(biāo)關(guān)聯(lián)函數(shù)方法”都是針對(duì)目標(biāo)函數(shù)設(shè)定新條件的方法。5.

51、 2單目標(biāo)化解法將原多目標(biāo)優(yōu)化問(wèn)題多個(gè)目標(biāo)函數(shù)轉(zhuǎn)化成為只有一個(gè)目標(biāo)函數(shù)的單目標(biāo)優(yōu)化問(wèn)題求解的方法稱(chēng)為單目標(biāo)化方法。(1)單目標(biāo)化解法的基本思想步驟1：構(gòu)造一個(gè)新的目標(biāo)函數(shù)ff(fi，f2，,fs)滿(mǎn)足性質(zhì)：在約束條件的區(qū)域內(nèi)f(fi，f2，,fs)是fi,f2,fs的單調(diào)增函數(shù)。特別注意：構(gòu)造新目標(biāo)函數(shù)也可以根據(jù)實(shí)際問(wèn)題，將f(fi，f2，,fs)定義為fi,f2,fs的不減函數(shù)。步驟2：建立單目標(biāo)優(yōu)化數(shù)學(xué)模型minf啟，,fs)目標(biāo)函數(shù)gi(Xi,X2,Xn)0ii,2,m約束條件步驟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)解。

52、(2)單目標(biāo)優(yōu)化問(wèn)題最優(yōu)解的性質(zhì)單目標(biāo)優(yōu)化問(wèn)題的最優(yōu)解與原多目標(biāo)最優(yōu)化問(wèn)題的最優(yōu)解有著密切的內(nèi)在關(guān)系。下面的定理揭示了兩者之間最重要的一種關(guān)系。定理i：設(shè)f(fi,f2，,fs)是fi,f2,fs的單調(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)解為X*,則在該點(diǎn)處，目標(biāo)函數(shù)fi,f2,fs都取得最小值。設(shè)單目標(biāo)最優(yōu)化問(wèn)題的最優(yōu)解為Y*,則在該點(diǎn)處，目標(biāo)函數(shù)f(fi,f2,fs)取得最小值f(Y*)。顯然,i)fi(X*)fi(Y*)ii,2,s2)f(X*)f(Y*)又

53、因?yàn)椋琭/，fs)是fi,f2,fs的單調(diào)增函數(shù)，根據(jù)i)有：f(X*)f(Y*)所以，f(X*)f(Y*),故必有fi(X*)匕(丫*)ii,2,s即Y*為原多目標(biāo)最優(yōu)化問(wèn)題的最優(yōu)解。定理告訴我們：如果多目標(biāo)最優(yōu)化問(wèn)題的最優(yōu)解存在，則只需求解一個(gè)單目標(biāo)最優(yōu)化問(wèn)題就可以得到。但是，如果多目標(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í)，我們稱(chēng)解為單目標(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ù)。權(quán)重優(yōu)化函數(shù)均衡優(yōu)化函數(shù)f(fi,f2,