管理運籌學06非線性規(guī)劃課件

第六章非線性規(guī)劃非線性規(guī)劃問題及其數(shù)學模型極值問題凸規(guī)劃一維搜索無約束極值問題約束極值問題2/6/202311.非線性規(guī)劃問題及其數(shù)學模型非線性規(guī)劃問題舉例：

Example1：第82頁例6-1

Example2：第82頁例6-2非線性規(guī)劃問題的數(shù)學模型非線性規(guī)劃問題的圖示2/6/202321.1非線性規(guī)劃問題舉例Example1:某商店經(jīng)銷A、B兩種產(chǎn)品，售價分別為20和380元。據(jù)統(tǒng)計，售出一件A產(chǎn)品的平均時間為0.5小時，而售出一件B產(chǎn)品的平均時間與其銷售的數(shù)量成正比，表達式為1+0.2n。若該商店總的營業(yè)時間為1000小時，試確定使其營業(yè)額最大的營業(yè)計劃。

2/6/202331.1非線性規(guī)劃問題舉例Example2:在層次分析（AnalyticHierarchyProcess,簡記為AHP）中，為進行多屬性的綜合評價，需要確定每個屬性的相對重要性，即它們的權(quán)重。為此，將各屬性進行兩兩比較，從而得出如下判斷矩陣：

2/6/202351.1非線性規(guī)劃問題舉例

a11…a1nJ=……,

an1…ann其中：aij是第i個屬性與第j個屬性的重要性之比。2/6/202361.1非線性規(guī)劃問題舉例現(xiàn)需要從判斷矩陣求出各屬性的權(quán)重，為使求出的權(quán)重向量W在最小二乘意義上能最好地反映判斷矩陣的估計，由aij=wi/wj可得：2/6/202371.2非線性規(guī)劃問題的數(shù)學模型由于，,“≤”不等式僅乘“-1”即可轉(zhuǎn)換為“≥”不等式；因此上述數(shù)學模型具有一般意義。又因為等價于兩個不等式：;,因此非線性規(guī)劃的數(shù)學模型也可以表示為：2/6/202391.3非線性規(guī)劃問題的圖示若令其目標函數(shù)f(X)=c,目標函數(shù)成為一條曲線或一張曲面；通常稱為等值線或等值面。此例，若設(shè)f(X)=2和f(X)=4可得兩個圓形等值線，見下圖：2/6/2023101.3非線性規(guī)劃問題的圖示由左圖可見,等值線f(X)=2和約束條件直線6-6相切，切點D即為此問題的最優(yōu)解，X*=(3,3)，其目標函數(shù)值f(X*)=2。3232066x1x2f(X)=4f(X)=22/6/2023111.3非線性規(guī)劃問題的圖示[注]線性規(guī)劃存在最優(yōu)解，最優(yōu)解只能在其可行域的邊緣上（特別能在可行域的頂點上）得到；而非線性規(guī)劃的最優(yōu)解（如果存在）則可能在可行域的任意一點上得到。2/6/2023132.極值問題局部極值與全局極值極值點存在的條件凸函數(shù)和凹函數(shù)凸函數(shù)的性質(zhì)函數(shù)凸性的判定2/6/2023142.1局部極值與全局極值線性規(guī)劃最優(yōu)解全局最優(yōu)解非線性規(guī)劃局部最優(yōu)解未必全局最優(yōu)2/6/202315全局極值對于X,X*∈R均有不等式f(X)≥f(X*)，則稱X*為f(X)在R上的全局極小點，f(X*)為全局極小值；對于X,X*∈R均有不等式f(X)>f(X*)，則稱X*為f(X)在R上的嚴格全局極小點，f(X*)為嚴格全局極小值。2/6/2023172.2極值點存在的條件必要條件設(shè)R是En上的一個開集，f(X)在R上有一階連續(xù)偏導數(shù)，且在點取得局部極值，則必有

或2/6/202318必要條件為函數(shù)f(X)在X*點處的梯度。由數(shù)學分析可知，的方向為X*點處等值面（等值線）的法線方向，沿這一方向函數(shù)值增加最快，如圖所示。2/6/202319充分條件充分條件設(shè)R是En上的一個開集，f(X)在R上具有二階連續(xù)偏導數(shù)，對于，若且對任何非零向量有：則X*為f(X)的嚴格局部極小點。稱為f(X)在點X*處的海賽（Hesse）矩陣。2/6/202321充分條件2/6/202322充分條件（充分條件）等價于：如果函數(shù)f(X)在X*點的梯度為零且海賽矩陣正定，則X*為函數(shù)f(X)的嚴格局部極小點。2/6/202323凸函數(shù)和凹函數(shù)示意圖X(1)X(2)f(X)X凸函數(shù)X(1)X(2)f(X)X凹函數(shù)2/6/202325非凹非凸函數(shù)示意圖f(X(2))f(X(1))X(1)+(1-)X(2)X(1)X(2)f(X)X非凸非凹函數(shù)2/6/2023262.5函數(shù)凸性的判定根據(jù)凸函數(shù)的定義進行判定；根據(jù)一階條件進行判定；根據(jù)二階條件進行判定；2/6/202329一階條件設(shè)R為En上的開凸集，f(X)在R上具有一階連續(xù)偏導數(shù)，則f(X)為R上的凸函數(shù)的充分必要條件是，對于屬于R的任意兩個不同點X(1)和X(2)恒有：2/6/202330二階條件設(shè)R為En上的開凸集，f(X)在R上具有二階連續(xù)偏導數(shù)，則f(X)為R上的凸函數(shù)的充分必要條件是：f(X)的海賽矩陣H(X)在R上處處半正定（ZTH(X)Z≥0）。2/6/2023313.凸規(guī)劃凸規(guī)劃的定義下降迭代算法2/6/2023323.1凸規(guī)劃的定義考慮非線性規(guī)劃：假定其中f(X)為凸函數(shù)，gj(X)為凹函數(shù)（-gj(X)為凸函數(shù)），這樣的非線性規(guī)劃稱為凸規(guī)劃。2/6/2023333.1凸規(guī)劃的定義凸規(guī)劃：可行域是凸集、局部最優(yōu)即為全局最優(yōu)；若為嚴格凸函數(shù)，最優(yōu)解若存在必唯一。2/6/2023343.2下降迭代算法基本思想：給定一個初始估計解X(0)，然后按某種規(guī)則（即算法）找出一個比X(0)更好的解X(1)，如此遞推即可得到一個解的序列{X(k)}，若這一解的序列有極限X*，即則稱X*為最優(yōu)解。2/6/2023353.2下降迭代算法基本問題：遞推步驟的有限性，一般說很難得到精確解，當滿足所要求的精度時即可停止迭代而得到一個近似解。2/6/2023363.2下降迭代算法下降算法：若產(chǎn)生的解序列{X(k)}能使目標函數(shù)f(X(k))逐步減少，就稱此算法為下降算法?！跋陆怠钡囊蠛苋菀诐M足，因此它包括了很多具體的算法。2/6/2023373.2下降迭代算法若從X(k)出發(fā)沿任何方向移動都不能使目標函數(shù)值下降，則X(k)是一個局部極小點；若從X(k)出發(fā)至少存在一個方向能使目標函數(shù)下降，則可選定某一下降方向P(k)，沿這一方向前進一步，得到下一個點X(k+1)。沿P(k)方向前進一步相當于在射線上選定新的點,其中P(k)為搜索方向，為步長。2/6/2023383.2下降迭代算法確定搜索方向P(k)是關(guān)鍵的一步，各種算法的區(qū)別主要在于確定搜索方向P(k)的方法不同。步長的選定一般都是以使目標函數(shù)在搜索方向上下降最多為依據(jù)的，稱為最佳步長，即沿射線求目標函數(shù)的極小值由于確定步長是通過求以為變量的一元函數(shù)的極小點來實現(xiàn)的，故稱這一過程為一維搜索。2/6/2023394.一維搜索一維搜索即沿某一已知方向求目標函數(shù)的極小點，一維搜索的方法很多，在此只介紹斐波那契法和黃金分割法。2/6/2023404.1斐波那契法

一維搜索過程是建立在一個被稱為斐波那契數(shù)序列基礎(chǔ)上的。斐波那契數(shù)序列是具有如下遞推關(guān)系的無窮序列：F0=F1=1Fn=Fn-1+Fn-2，n=2,3,…n012345678Fn1123581321342/6/2023414.1斐波那契法斐波那契法成功地實現(xiàn)了單峰函數(shù)極值范圍的縮減。設(shè)某一單峰函數(shù)在[a,b]上有一極小點x*，在此區(qū)間內(nèi)任意取兩點a1和b1，使a1<b1，計算其函數(shù)值可能出現(xiàn)以下兩種情況：(1)f(a1)＜f(b1)，如圖(1)所示；此時極小點x*必在期間[a,b1]內(nèi)。(2)f(a1)≥f(b1)，如圖(2)所示；此時極小點x*必在期間[a1,b]內(nèi)。2/6/2023424.1斐波那契法f(x)oaa1

x*b1bx圖(1)2/6/2023434.1斐波那契法f(x)oaa1

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

，可以證明這兩個數(shù)列收斂于同一個極限。2/6/2023494.2黃金分割法以不變的區(qū)間縮減率，代替斐波那契法每次不同的縮減率，就得到了黃金分割法。黃金分割法是一種等速對稱的搜索方法，每次試點均取在區(qū)間長度的倍和倍處。2/6/202350黃金分割法例(第92頁例6-7)例6-7：求二次函數(shù)f(x)=3x2-21x-1在區(qū)間[0,20]上的極小點，要求縮短后的區(qū)間長度不大于原區(qū)間長