最優(yōu)化2(非線性 多目標(biāo))

1、5.5.非線性規(guī)劃模型非線性規(guī)劃模型 前面介紹了線性規(guī)劃問題，即目標(biāo)函數(shù)和約前面介紹了線性規(guī)劃問題，即目標(biāo)函數(shù)和約束條件都是線性函數(shù)的規(guī)劃問題，但在實(shí)際工作束條件都是線性函數(shù)的規(guī)劃問題，但在實(shí)際工作中，還常常會(huì)遇到另一類更一般的規(guī)劃問題，即中，還常常會(huì)遇到另一類更一般的規(guī)劃問題，即目標(biāo)函數(shù)和約束條件中至少有一個(gè)是非線性函數(shù)目標(biāo)函數(shù)和約束條件中至少有一個(gè)是非線性函數(shù)的規(guī)劃問題，即非線性規(guī)劃問題的規(guī)劃問題，即非線性規(guī)劃問題. . 事實(shí)上，客觀世界中的問題許多是非線事實(shí)上，客觀世界中的問題許多是非線性的，給予線性大多是近似的，是在作了科性的，給予線性大多是近似的，是在作了科學(xué)的假設(shè)和簡(jiǎn)化后得到的學(xué)的

2、假設(shè)和簡(jiǎn)化后得到的. 為了利用線性的知為了利用線性的知識(shí)，許多非線性問題常進(jìn)行線性化處理識(shí)，許多非線性問題常進(jìn)行線性化處理. 但在但在實(shí)際問題中，有一些是不能進(jìn)行線性化處理實(shí)際問題中，有一些是不能進(jìn)行線性化處理的，否則將嚴(yán)重影響模型對(duì)實(shí)際問題近似的的，否則將嚴(yán)重影響模型對(duì)實(shí)際問題近似的可依賴型可依賴型. 由于非線性規(guī)劃問題在計(jì)算上常是困難的，由于非線性規(guī)劃問題在計(jì)算上常是困難的，理論上的討論也不能像線性規(guī)劃那樣給出簡(jiǎn)潔的理論上的討論也不能像線性規(guī)劃那樣給出簡(jiǎn)潔的結(jié)果形式和全面透徹的結(jié)論結(jié)果形式和全面透徹的結(jié)論. 這點(diǎn)又限制了非這點(diǎn)又限制了非線性規(guī)劃的應(yīng)用，所以，在數(shù)學(xué)建模時(shí)，要進(jìn)行線性規(guī)劃的應(yīng)

3、用，所以，在數(shù)學(xué)建模時(shí)，要進(jìn)行認(rèn)真的分析，對(duì)實(shí)際問題進(jìn)行合理的假設(shè)、簡(jiǎn)化，認(rèn)真的分析，對(duì)實(shí)際問題進(jìn)行合理的假設(shè)、簡(jiǎn)化，首先考慮用線性規(guī)劃模型，若線性近似誤差較大首先考慮用線性規(guī)劃模型，若線性近似誤差較大時(shí)，則考慮用非線性規(guī)劃時(shí)，則考慮用非線性規(guī)劃.非線性規(guī)劃問題的標(biāo)準(zhǔn)形式為非線性規(guī)劃問題的標(biāo)準(zhǔn)形式為：min ( )( )0,1,2,. .( )0,1,2,ijf xgxims thxjr非線性規(guī)劃模型按約束條件可分為以下三類：非線性規(guī)劃模型按約束條件可分為以下三類： 無約束非線性規(guī)劃模型：無約束非線性規(guī)劃模型： 等式約束非線性規(guī)劃模型：等式約束非線性規(guī)劃模型：min ( )nf xxRmin

4、( ). . ( )0,1,2,jf xst h xjr 不等式約束非線性規(guī)劃模型：不等式約束非線性規(guī)劃模型：1)1) 無約束的非線性規(guī)劃問題無約束的非線性規(guī)劃問題. .針對(duì)上述三類非線性規(guī)劃模型，其常用求解的基針對(duì)上述三類非線性規(guī)劃模型，其常用求解的基本思路可歸納如下：本思路可歸納如下： min ( ). . ( )0,1,2,if xst g xim 在下降迭代算法中，搜索方向起著關(guān)鍵的作在下降迭代算法中，搜索方向起著關(guān)鍵的作用，而當(dāng)搜索方向確定后，步長(zhǎng)又是決定算法好用，而當(dāng)搜索方向確定后，步長(zhǎng)又是決定算法好壞的重要因素壞的重要因素. 非線性規(guī)劃只含一個(gè)變量，即一非線性規(guī)劃只含一個(gè)變量，即

5、一維非線性規(guī)劃可以用一維搜索方法求得最優(yōu)解，維非線性規(guī)劃可以用一維搜索方法求得最優(yōu)解，一維搜索方法主要有進(jìn)退法和黃金分割法一維搜索方法主要有進(jìn)退法和黃金分割法. 二維二維的非線性規(guī)劃也可以像解線性規(guī)劃那樣用圖形求的非線性規(guī)劃也可以像解線性規(guī)劃那樣用圖形求解解. 對(duì)于二維非線性規(guī)劃，使用搜索方法是要用對(duì)于二維非線性規(guī)劃，使用搜索方法是要用到梯度的概念，最常用的搜索方法就是最速下降到梯度的概念，最常用的搜索方法就是最速下降法法.2)2) 只有等式約束的非線性規(guī)劃問題通?？捎孟挥械仁郊s束的非線性規(guī)劃問題通常可用消元法、拉格朗日乘子法或反函數(shù)法，將其化為元法、拉格朗日乘子法或反函數(shù)法，將其化為無約束

6、問題求解無約束問題求解. .3)3) 具有不等式約束的非線性規(guī)劃問題解起來很具有不等式約束的非線性規(guī)劃問題解起來很復(fù)雜，求解這一類問題，通常將不等式化為復(fù)雜，求解這一類問題，通常將不等式化為等式約束，再將約束問題化為無約束問題，等式約束，再將約束問題化為無約束問題，用線性逼近的方法將非線性規(guī)劃問題化為線用線性逼近的方法將非線性規(guī)劃問題化為線性規(guī)劃問題性規(guī)劃問題. 下面介紹一個(gè)簡(jiǎn)單的非線性規(guī)劃問題的下面介紹一個(gè)簡(jiǎn)單的非線性規(guī)劃問題的例子，其中的一些約束條件是等式，這類非線例子，其中的一些約束條件是等式，這類非線性規(guī)劃問題可用拉格朗日方法求解性規(guī)劃問題可用拉格朗日方法求解. 例7（石油最優(yōu)儲(chǔ)存方法

7、）有一石油運(yùn)輸公司，（石油最優(yōu)儲(chǔ)存方法）有一石油運(yùn)輸公司，為了減少開支，希望作個(gè)節(jié)省石油的存儲(chǔ)空間為了減少開支，希望作個(gè)節(jié)省石油的存儲(chǔ)空間. .但要求存儲(chǔ)的石油能滿足客戶的要求但要求存儲(chǔ)的石油能滿足客戶的要求. .為簡(jiǎn)化問為簡(jiǎn)化問題，假設(shè)只經(jīng)營(yíng)兩種油，各種符號(hào)表示的意義題，假設(shè)只經(jīng)營(yíng)兩種油，各種符號(hào)表示的意義如表如表4 4所示所示. .其中供給率指石油公司供給客戶的其中供給率指石油公司供給客戶的速度速度. .表表4 4 各種符號(hào)表示意義表各種符號(hào)表示意義表第第i i種油的存儲(chǔ)量種油的存儲(chǔ)量第第i i種油的價(jià)格種油的價(jià)格第第i i種油的供給率種油的供給率第第i i種油的每單位的存儲(chǔ)費(fèi)用種油的每單

8、位的存儲(chǔ)費(fèi)用第第i i種油的每單位的存儲(chǔ)空間種油的每單位的存儲(chǔ)空間總存儲(chǔ)公式總存儲(chǔ)公式iaibihitTix由由歷史數(shù)據(jù)得到的經(jīng)驗(yàn)公式為歷史數(shù)據(jù)得到的經(jīng)驗(yàn)公式為 : :且提供數(shù)據(jù)如表且提供數(shù)據(jù)如表5 5所示：所示：1 11 12 2221212121 122min ( ,)22. . ( ,)abh xa bh xf x xxxst g x xt xt xT表表5 5 數(shù)據(jù)表數(shù)據(jù)表已知總存儲(chǔ)空間已知總存儲(chǔ)空間24T 代入數(shù)據(jù)后得到的模型為：代入數(shù)據(jù)后得到的模型為：模型求解：模型求解：拉格朗日函數(shù)的形式為：拉格朗日函數(shù)的形式為： 121212122720min ( ,)0.250.10. 242

9、4f x xxxxxstxx 121212( , )( ,)( ,)L x xf x xg x xT即即: :121212122720( , )0.250.102424L x xxxxxxx21122212270.2520200.104024240LxxLxxLxx 對(duì)對(duì) 求各個(gè)變量的偏導(dǎo)數(shù)，并令它們等求各個(gè)變量的偏導(dǎo)數(shù)，并令它們等于零，得于零，得: : 12( , )L x x解這個(gè)線性方程組得：解這個(gè)線性方程組得：12125.0968,3.4516,0.3947,( ,)12.71xxf x x從而可得最小值是從而可得最小值是 . 12.716 6、多目標(biāo)規(guī)劃模型、多目標(biāo)規(guī)劃模型 在許多實(shí)

10、際問題中，衡量一個(gè)方案的好壞標(biāo)在許多實(shí)際問題中，衡量一個(gè)方案的好壞標(biāo)準(zhǔn)往往不止一個(gè)，例如設(shè)計(jì)一個(gè)導(dǎo)彈，既要射程準(zhǔn)往往不止一個(gè)，例如設(shè)計(jì)一個(gè)導(dǎo)彈，既要射程最遠(yuǎn)，又要燃料最省，還要精度最高最遠(yuǎn)，又要燃料最省，還要精度最高. 這一類問題這一類問題統(tǒng)稱為統(tǒng)稱為多目標(biāo)最優(yōu)化問題多目標(biāo)最優(yōu)化問題或或多目標(biāo)規(guī)劃問題多目標(biāo)規(guī)劃問題. 我們我們先來看一個(gè)生產(chǎn)計(jì)劃的例子先來看一個(gè)生產(chǎn)計(jì)劃的例子.123,x xx我們希望購(gòu)買我們希望購(gòu)買DVDDVD的總數(shù)量最小，即的總數(shù)量最小，即 :1001minjjzy由此，可以得到問題三的雙目標(biāo)整數(shù)線性規(guī)劃模型由此，可以得到問題三的雙目標(biāo)整數(shù)線性規(guī)劃模型如下：如下： 10011

11、000 100111000 10011100011001min1max27000100030.951.61,100301,1000. .1,10001,100011,10001,jjijijijijijijjiijijijijijzywc xxxyjxzis txcijxij 或 100011,10001,100ijziyj或取整 10011000 100111000110011000 10011min100030.951.61,100301,1000. .1270001,10001,100011,10001,1jjijijijjiijijijijijijijijzyxxyjxzis tc x

12、xcijxij 或 00011,10001,100ijziyj或 取整表表6 6 當(dāng)當(dāng) 時(shí)最小購(gòu)買量的時(shí)最小購(gòu)買量的 值值(1,2,.,100)jyj DVDDVD編號(hào)編號(hào)D01D01D02D02D03D03D04D04D05D05D06D06D07D07D08D08D09D09D10D10最少購(gòu)買量最少購(gòu)買量1414212117172424121217171919212122221414DVDDVD編號(hào)編號(hào)D11D11D12D12D13D13D14D14D15D15D16D16D17D17D18D18D19D19D20D20最少購(gòu)買量最少購(gòu)買量181818181717171717172424

13、1818161618182323DVDDVD編號(hào)編號(hào)D21D21D22D22D23D23D24D24D25D25D26D26D27D27D28D28D29D29D30D30最少購(gòu)買量最少購(gòu)買量2020181822221414181817171515121216162424DVDDVD編號(hào)編號(hào)D31D31D32D32D33D33D34D34D35D35D36D36D37D37D38D38D39D39D40D40最少購(gòu)買量最少購(gòu)買量1919222220201919222222221313171717171717DVDDVD編號(hào)編號(hào)D41D41D42D42D43D43D44D44D45D45D46D

14、46D47D47D48D48D49D49D50D50最少購(gòu)買量最少購(gòu)買量32322020161621212222161620201515202020200.95續(xù)上表DVDDVD編號(hào)編號(hào)D51D51D52D52D53D53D54D54D55D55D56D56D57D57D58D58D59D59D60D60最少購(gòu)買量最少購(gòu)買量2424171719191717191918181919171720202121DVDDVD編號(hào)編號(hào)D61D61D62D62D63D63D64D64D65D65D66D66D67D67D68D68D69D69D70D70最少購(gòu)買量最少購(gòu)買量16161919191920201

15、71719191717212120201919DVDDVD編號(hào)編號(hào)D71D71D72D72D73D73D74D74D75D75D76D76D77D77D78D78D79D79D80D80最少購(gòu)買量最少購(gòu)買量2121222215152020151514141212171719191717DVDDVD編號(hào)編號(hào)D81D81D82D82D83D83D84D84D85D85D86D86D87D87D88D88D89D89D90D90最少購(gòu)買量最少購(gòu)買量1818101014141212212113132222151513131717DVDDVD編號(hào)編號(hào)D91D91D92D92D93D93D94D94D95

16、D95D96D96D97D97D98D98D99D99D100D100最少購(gòu)買量最少購(gòu)買量2424171715151414252515152222202011112222 我們利用規(guī)劃模型求得每種我們利用規(guī)劃模型求得每種DVDDVD的購(gòu)買量后，需要的購(gòu)買量后，需要對(duì)其進(jìn)行可行性校驗(yàn)，測(cè)試此結(jié)果是否可以滿足對(duì)其進(jìn)行可行性校驗(yàn)，測(cè)試此結(jié)果是否可以滿足一個(gè)月內(nèi)比例為一個(gè)月內(nèi)比例為95%95%的會(huì)員得到他想看的的會(huì)員得到他想看的DVDDVD，且，且具有盡可能大的總體滿意度具有盡可能大的總體滿意度. .校驗(yàn)方法：校驗(yàn)方法： （一）根據(jù)訂單和求得的（一）根據(jù)訂單和求得的DVDDVD購(gòu)買數(shù)量，利用購(gòu)買數(shù)量，

17、利用問題二的規(guī)劃模型進(jìn)行第一次分配，對(duì)分配情況：?jiǎn)栴}二的規(guī)劃模型進(jìn)行第一次分配，對(duì)分配情況：租賃的會(huì)員，租賃的會(huì)員，DVDDVD的分配情況，剩余的各種的分配情況，剩余的各種DVDDVD數(shù)數(shù)量作記錄；同時(shí)將已租賃的會(huì)員在滿意指數(shù)矩陣量作記錄；同時(shí)將已租賃的會(huì)員在滿意指數(shù)矩陣的指數(shù)全變?yōu)榈闹笖?shù)全變?yōu)? 0，即不考慮對(duì)其進(jìn)行第二次分配，即不考慮對(duì)其進(jìn)行第二次分配. . （二）隨機(jī)從第一次得到（二）隨機(jī)從第一次得到DVDDVD的會(huì)員中抽取的會(huì)員中抽取60%60%，將這部分人所還回的將這部分人所還回的DVDDVD與第一次分配余下的與第一次分配余下的DVDDVD合合在一起，作為第二次分配時(shí)各種在一起，作為

18、第二次分配時(shí)各種DVDDVD的現(xiàn)有量的現(xiàn)有量. .然后，然后，利用問題二的利用問題二的0-10-1線性規(guī)劃模型對(duì)第一次未分配到線性規(guī)劃模型對(duì)第一次未分配到DVDDVD的會(huì)員進(jìn)行第二次分配；的會(huì)員進(jìn)行第二次分配； （三）統(tǒng)計(jì)出經(jīng)過兩次分配后，得到（三）統(tǒng)計(jì)出經(jīng)過兩次分配后，得到DVDDVD的會(huì)的會(huì)員的比例，若大于員的比例，若大于95%95%，則此次分配成功，則此次分配成功. .利用這利用這種算法進(jìn)行多次隨機(jī)模擬，若大多數(shù)情況下可以種算法進(jìn)行多次隨機(jī)模擬，若大多數(shù)情況下可以使得到使得到DVDDVD的會(huì)員大于的會(huì)員大于95%95%，則認(rèn)為模型三是合理，則認(rèn)為模型三是合理的的. .校驗(yàn)結(jié)果：校驗(yàn)結(jié)果： 因