非線性規(guī)劃管理運(yùn)籌學(xué)李軍

2024/11/511.非線性規(guī)劃問(wèn)題及其數(shù)學(xué)模型非線性規(guī)劃問(wèn)題舉例：

Example1：第82頁(yè)例6-1

Example2：第82頁(yè)例6-2非線性規(guī)劃問(wèn)題的數(shù)學(xué)模型非線性規(guī)劃問(wèn)題的圖示2024/11/521.1非線性規(guī)劃問(wèn)題舉例Example1:

某商店經(jīng)銷A、B兩種產(chǎn)品，售價(jià)分別為20和380元。據(jù)統(tǒng)計(jì)，售出一件A產(chǎn)品的平均時(shí)間為0.5小時(shí)，而售出一件B產(chǎn)品的平均時(shí)間與其銷售的數(shù)量成正比，表達(dá)式為1+0.2n。若該商店總的營(yíng)業(yè)時(shí)間為1000小時(shí)，試確定使其營(yíng)業(yè)額最大的營(yíng)業(yè)計(jì)劃。

2024/11/531.1非線性規(guī)劃問(wèn)題舉例[解]設(shè)x1和x2分別為商店經(jīng)銷A、B兩種產(chǎn)品的件數(shù)，于是有如下數(shù)學(xué)模型：

2024/11/541.1非線性規(guī)劃問(wèn)題舉例Example2:

在層次分析（AnalyticHierarchyProcess,簡(jiǎn)記為AHP）中，為進(jìn)行多屬性的綜合評(píng)價(jià)，需要確定每個(gè)屬性的相對(duì)重要性，即它們的權(quán)重。為此，將各屬性進(jìn)行兩兩比較，從而得出如下判斷矩陣：

2024/11/551.1非線性規(guī)劃問(wèn)題舉例

a11…a1nJ=……,

an1…ann其中：aij是第i個(gè)屬性與第j個(gè)屬性的重要性之比。2024/11/561.1非線性規(guī)劃問(wèn)題舉例

現(xiàn)需要從判斷矩陣求出各屬性的權(quán)重，為使求出的權(quán)重向量W在最小二乘意義上能最好地反映判斷矩陣的估計(jì)，由aij=wi/wj可得：2024/11/571.2非線性規(guī)劃問(wèn)題的數(shù)學(xué)模型s.t.

其中是n維歐氏空間En中的向量點(diǎn)。2024/11/581.2非線性規(guī)劃問(wèn)題的數(shù)學(xué)模型

由于，,“≤”不等式僅乘“-1”即可轉(zhuǎn)換為“≥”不等式；因此上述數(shù)學(xué)模型具有一般意義。又因?yàn)榈葍r(jià)于兩個(gè)不等式：;,因此非線性規(guī)劃的數(shù)學(xué)模型也可以表示為：2024/11/591.3非線性規(guī)劃問(wèn)題的圖示

若令其目標(biāo)函數(shù)f(X)=c,目標(biāo)函數(shù)成為一條曲線或一張曲面；通常稱為等值線或等值面。此例，若設(shè)f(X)=2和f(X)=4可得兩個(gè)圓形等值線，見下圖：2024/11/5101.3非線性規(guī)劃問(wèn)題的圖示

由左圖可見,等值線f(X)=2和約束條件直線6-6相切，切點(diǎn)D即為此問(wèn)題的最優(yōu)解，X*=(3,3)，其目標(biāo)函數(shù)值f(X*)=2。3232066x1x2f(X)=4f(X)=22024/11/5111.3非線性規(guī)劃問(wèn)題的圖示

在此例中，約束對(duì)最優(yōu)解發(fā)生了影響，若以代替原約束，則非線性規(guī)劃的最優(yōu)解是，即圖中的C點(diǎn)，此時(shí)。由于最優(yōu)點(diǎn)位于可行域的內(nèi)部，故事實(shí)上約束并未發(fā)揮作用，問(wèn)題相當(dāng)一個(gè)無(wú)約束極值問(wèn)題。2024/11/5121.3非線性規(guī)劃問(wèn)題的圖示[注]線性規(guī)劃存在最優(yōu)解，最優(yōu)解只能在其可行域的邊緣上（特別能在可行域的頂點(diǎn)上）得到；而非線性規(guī)劃的最優(yōu)解（如果存在）則可能在可行域的任意一點(diǎn)上得到。2024/11/5132.極值問(wèn)題局部極值與全局極值極值點(diǎn)存在的條件凸函數(shù)和凹函數(shù)凸函數(shù)的性質(zhì)函數(shù)凸性的判定2024/11/5142.1局部極值與全局極值線性規(guī)劃最優(yōu)解全局最優(yōu)解非線性規(guī)劃局部最優(yōu)解未必全局最優(yōu)2024/11/515局部極值對(duì)于

X-X*<均有不等式f(X)≥f(X*)，則稱X*為f(X)在R上的局部極小點(diǎn)，f(X*)為局部極小值；對(duì)于

X-X*<

均有不等式f(X)>f(X*)，則稱X*為f(X)在R上的嚴(yán)格局部極小點(diǎn)，f(X*)為嚴(yán)格局部極小值；2024/11/516全局極值對(duì)于X,X*∈R均有不等式f(X)≥f(X*)，則稱X*為f(X)在R上的全局極小點(diǎn)，f(X*)為全局極小值；對(duì)于X,X*∈R均有不等式f(X)>f(X*)，則稱X*為f(X)在R上的嚴(yán)格全局極小點(diǎn)，f(X*)為嚴(yán)格全局極小值。2024/11/5172.2極值點(diǎn)存在的條件必要條件設(shè)R是En上的一個(gè)開集，f(X)在R上有一階連續(xù)偏導(dǎo)數(shù)，且在點(diǎn)取得局部極值，則必有

或2024/11/518必要條件

為函數(shù)f(X)在X*點(diǎn)處的梯度。由數(shù)學(xué)分析可知，的方向?yàn)閄*點(diǎn)處等值面（等值線）的法線方向，沿這一方向函數(shù)值增加最快，如圖所示。2024/11/519必要條件

滿足的點(diǎn)稱為平穩(wěn)點(diǎn)或駐點(diǎn)。極值點(diǎn)一定是駐點(diǎn)；但駐點(diǎn)不一定是極值點(diǎn)。

2024/11/520充分條件充分條件設(shè)R是En上的一個(gè)開集，f(X)在R上具有二階連續(xù)偏導(dǎo)數(shù)，對(duì)于，若且對(duì)任何非零向量有：則X*為f(X)的嚴(yán)格局部極小點(diǎn)。稱為f(X)在點(diǎn)X*處的海賽（Hesse）矩陣。2024/11/521充分條件2024/11/522充分條件（充分條件）等價(jià)于：如果函數(shù)f(X)在X*點(diǎn)的梯度為零且海賽矩陣正定，則X*為函數(shù)f(X)的嚴(yán)格局部極小點(diǎn)。2024/11/5232.3凸函數(shù)和凹函數(shù)

設(shè)f(X)為定義在En中某一凸集R上的函數(shù)，若對(duì)于任何實(shí)數(shù)

（0<

<1）以及R中的任意兩點(diǎn)X(1)和X(2)

，恒有：則稱f(X)為定義在R上的凸函數(shù)；若上式為嚴(yán)格不等式，則稱f(X)為定義在R上的嚴(yán)格凸函數(shù)。改變不等號(hào)的方向，即可得到凹函數(shù)和嚴(yán)格凹函數(shù)的定義。2024/11/524凸函數(shù)和凹函數(shù)示意圖X(1)X(2)f(X)X凸函數(shù)X(1)X(2)f(X)X凹函數(shù)2024/11/525非凹非凸函數(shù)示意圖f(X(2))f(X(1))

X(1)+(1-

)X(2)X(1)X(2)f(X)X非凸非凹函數(shù)2024/11/5262.4凸函數(shù)的性質(zhì)設(shè)f(X)為定義在凸集R上的凸函數(shù)，則對(duì)于任意實(shí)數(shù)

≥0

,函數(shù)

f(X)也是定義在R上的凸函數(shù)。設(shè)f1(X)和f

2(X)為定義在凸集R上的兩個(gè)凸函數(shù)，則其和f(X)=f1(X)+f

2(X)仍然是定義在R上的凸函數(shù)。設(shè)f(X)為定義在凸集R上的凸函數(shù)，則對(duì)于任意實(shí)數(shù)

,集合S

={X|X∈R,f(X)≤

}是凸集。2024/11/5272.4凸函數(shù)的性質(zhì)設(shè)f(X)為定義在凸集R上的凸函數(shù)，則它的任一極小點(diǎn)就是它在R上的最小點(diǎn)（全局極小點(diǎn)）；而且它的極小點(diǎn)形成一個(gè)凸集。設(shè)f(X)為定義在凸集R上的可微凸函數(shù)，若它存在點(diǎn)X*∈R，使得對(duì)于所有的X∈R有▽f(X*)T(X-X*)≥0，則X*是f(X)在R上的最小點(diǎn)（全局極小點(diǎn)）。2024/11/5282.5函數(shù)凸性的判定根據(jù)凸函數(shù)的定義進(jìn)行判定；根據(jù)一階條件進(jìn)行判定；根據(jù)二階條件進(jìn)行判定；2024/11/529一階條件

設(shè)R為En上的開凸集，f(X)在R上具有一階連續(xù)偏導(dǎo)數(shù)，則f(X)為R上的凸函數(shù)的充分必要條件是，對(duì)于屬于R的任意兩個(gè)不同點(diǎn)X(1)和X(2)恒有：2024/11/530二階條件

設(shè)R為En上的開凸集，f(X)在R上具有二階連續(xù)偏導(dǎo)數(shù)，則f(X)為R上的凸函數(shù)的充分必要條件是：f(X)的海賽矩陣H(X)在R上處處半正定（ZTH(X)Z≥0

）。2024/11/5313.凸規(guī)劃凸規(guī)劃的定義下降迭代算法2024/11/5323.1凸規(guī)劃的定義

考慮非線性規(guī)劃：假定其中f(X)為凸函數(shù)，gj(X)為凹函數(shù)（-gj(X)為凸函數(shù)），這樣的非線性規(guī)劃稱為凸規(guī)劃。2024/11/5333.1凸規(guī)劃的定義

凸規(guī)劃：可行域是凸集、局部最優(yōu)即為全局最優(yōu)；若為嚴(yán)格凸函數(shù)，最優(yōu)解若存在必唯一。2024/11/5343.2下降迭代算法基本思想：給定一個(gè)初始估計(jì)解X(0)，然后按某種規(guī)則（即算法）找出一個(gè)比X(0)更好的解X(1)

，如此遞推即可得到一個(gè)解的序列{X(k)}，若這一解的序列有極限X*

，即則稱X*為最優(yōu)解。2024/11/5353.2下降迭代算法基本問(wèn)題：遞推步驟的有限性，一般說(shuō)很難得到精確解，當(dāng)滿足所要求的精度時(shí)即可停止迭代而得到一個(gè)近似解。2024/11/5363.2下降迭代算法下降算法：若產(chǎn)生的解序列{X(k)}能使目標(biāo)函數(shù)f(X(k))逐步減少，就稱此算法為下降算法?！跋陆怠钡囊蠛苋菀诐M足，因此它包括了很多具體的算法。2024/11/5373.2下降迭代算法若從X(k)出發(fā)沿任何方向移動(dòng)都不能使目標(biāo)函數(shù)值下降，則X(k)是一個(gè)局部極小點(diǎn)；若從X(k)出發(fā)至少存在一個(gè)方向能使目標(biāo)函數(shù)下降，則可選定某一下降方向P(k)

，沿這一方向前進(jìn)一步，得到下一個(gè)點(diǎn)X(k+1)

。沿P(k)方向前進(jìn)一步相當(dāng)于在射線上選定新的點(diǎn),其中P(k)為搜索方向，為步長(zhǎng)。2024/11/5383.2下降迭代算法確定搜索方向P(k)是關(guān)鍵的一步，各種算法的區(qū)別主要在于確定搜索方向P(k)的方法不同。步長(zhǎng)的選定一般都是以使目標(biāo)函數(shù)在搜索方向上下降最多為依據(jù)的，稱為最佳步長(zhǎng)，即沿射線求目標(biāo)函數(shù)的極小值由于確定步長(zhǎng)是通過(guò)求以為變量的一元函數(shù)的極小點(diǎn)來(lái)實(shí)現(xiàn)的，故稱這一過(guò)程為一維搜索。2024/11/5394.一維搜索

一維搜索即沿某一已知方向求目標(biāo)函數(shù)的極小點(diǎn)，一維搜索的方法很多，在此只介紹斐波那契法和黃金分割法。2024/11/5404.1斐波那契法

一維搜索過(guò)程是建立在一個(gè)被稱為斐波那契數(shù)序列基礎(chǔ)上的。斐波那契數(shù)序列是具有如下遞推關(guān)系的無(wú)窮序列：F0=F1=1Fn=Fn-1+Fn-2，n=2,3,…n012345678Fn1123581321342024/11/5414.1斐波那契法斐波那契法成功地實(shí)現(xiàn)了單峰函數(shù)極值范圍的縮減。設(shè)某一單峰函數(shù)在[a,b]上有一極小點(diǎn)x*，在此區(qū)間內(nèi)任意取兩點(diǎn)a1和b1，使a1<b1

，計(jì)算其函數(shù)值可能出現(xiàn)以下兩種情況：

(1)f(a1)＜

f(b1)，如圖(1)所示；此時(shí)極小點(diǎn)x*必在期間[a,b1]內(nèi)。

(2)f(a1)≥

f(b1)，如圖(2)所示；此時(shí)極小點(diǎn)x*必在期間[a1,b]內(nèi)。2024/11/5424.1斐波那契法f(x)oaa1

x*b1bx圖(1)2024/11/5434.1斐波那契法f(x)oaa1

x*b1bx圖(2)2024/11/5444.1斐波那契法只要在區(qū)間[a,b]內(nèi)任意取兩點(diǎn)a1和b1，使a1<b1并計(jì)算其函數(shù)值加以比較，就可以把搜索區(qū)間[a,b]縮減成[a,b1]或[a1,b]。若要繼續(xù)縮小搜索期間[a,b1]或[a1,b]，只需在期間內(nèi)再取一點(diǎn)算出其函數(shù)值并與f(a1)或f(b1)加以比較即可。由此可見，計(jì)算函數(shù)的次數(shù)越多，搜索期間就縮得越小，即區(qū)間的縮短率（縮短后的區(qū)間長(zhǎng)度與原區(qū)間長(zhǎng)度之比）與函數(shù)的計(jì)算次數(shù)有關(guān)。2024/11/545斐波那契法的具體步驟1.根據(jù)相對(duì)精度或絕對(duì)精度，確定試點(diǎn)個(gè)數(shù)；2.確定兩個(gè)試點(diǎn)的位置a1、b1（對(duì)稱搜索）；Fn-2Fn-1aba1b1Fn-2Fn-12024/11/546斐波那契法的具體步驟3.計(jì)算函數(shù)值和并比較其大小，從而縮減搜索區(qū)間；4.重復(fù)2、3兩步，直到得到近似最小點(diǎn)。2024/11/547斐波那契法例(第90頁(yè)例6-6)例6-6：用斐波那契法求函數(shù)f(x)=3x2-12x+10的近似極小點(diǎn)和極小值，要求縮短后的區(qū)間不大于初始區(qū)間[1,4]的0.05倍。2024/11/5484.2黃金分割法

用斐波那契法以