![非線性規(guī)劃的基本概念和基本原理_第1頁](http://file4.renrendoc.com/view/3280ea506bcb981cd03e60cac04c4577/3280ea506bcb981cd03e60cac04c45771.gif)
![非線性規(guī)劃的基本概念和基本原理_第2頁](http://file4.renrendoc.com/view/3280ea506bcb981cd03e60cac04c4577/3280ea506bcb981cd03e60cac04c45772.gif)
![非線性規(guī)劃的基本概念和基本原理_第3頁](http://file4.renrendoc.com/view/3280ea506bcb981cd03e60cac04c4577/3280ea506bcb981cd03e60cac04c45773.gif)
![非線性規(guī)劃的基本概念和基本原理_第4頁](http://file4.renrendoc.com/view/3280ea506bcb981cd03e60cac04c4577/3280ea506bcb981cd03e60cac04c45774.gif)
![非線性規(guī)劃的基本概念和基本原理_第5頁](http://file4.renrendoc.com/view/3280ea506bcb981cd03e60cac04c4577/3280ea506bcb981cd03e60cac04c45775.gif)
版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進行舉報或認領(lǐng)
文檔簡介
非線性規(guī)劃的基本概念和基本原理1第一頁,共五十一頁,編輯于2023年,星期二7.1數(shù)學模型和基本概念非線性規(guī)劃是運籌學中包含內(nèi)容最多,應(yīng)用最廣泛的一個分支,計算遠比線性規(guī)劃復雜。2第二頁,共五十一頁,編輯于2023年,星期二一、數(shù)學模型例某單位擬建一排廠房,廠房建筑平面如圖所示。由于資金及材料的限制,圍墻及隔墻的總長度不能超過80米。為使建筑面積最大,應(yīng)如何選擇長寬尺寸?分析:設(shè)長為米,寬為米,則有
f(x)為非線性函數(shù)3第三頁,共五十一頁,編輯于2023年,星期二例設(shè)某物理過程具有如下規(guī)律用試驗法。現(xiàn)要確定參數(shù)使所得試驗點構(gòu)成的曲線與理論曲線誤差平方和為最小,且滿足
非負。4第四頁,共五十一頁,編輯于2023年,星期二非線性規(guī)劃:目標函數(shù)或(和)約束條件為非線性函數(shù)的規(guī)劃。分析:
f(x)為非線性函數(shù),求最小。5第五頁,共五十一頁,編輯于2023年,星期二一般模型Minf(X)s.t.hi(X)=0(i=1,2,….m)(P)
gj(X)0(j=1,2….l)XEnf(X)hi(X)gj(X)為En上的實函數(shù)。或6第六頁,共五十一頁,編輯于2023年,星期二二、基本概念1、全局極值和局部極值
為目標函數(shù),為可行域。若存在,,都有,則稱為該問題的全局極小點,
為全局極小值。
為目標函數(shù),為可行域。若有,,都有,則稱為該問題的嚴格全局極小點,
為嚴格全局極小值。
7第七頁,共五十一頁,編輯于2023年,星期二若存在,令,都有,
則稱為該問題的局部極小點,為局部極小值。
若存在,令,都有,
則稱為該問題的嚴格局部極小點,為嚴格局部極小值。
相應(yīng)不等式反號,得到相應(yīng)極大點,極大值定義。8第八頁,共五十一頁,編輯于2023年,星期二定義如果X滿足(P)的約束條件
hi(X)=0(i=1,2,….m)gj(X)0(j=1,2….l)
則稱XEn
為(P)的一個可行解。記(P)的所有可行解的集合為D,D稱為(P)可行域。9第九頁,共五十一頁,編輯于2023年,星期二定義
X*稱為(P)的一個(整體)最優(yōu)解,如果X*D,滿足
f(X)f(X*),X
D。
定義
X*稱為(P)的一個(局部)最優(yōu)解,如果X*D,且存在一個X*的鄰域N(X*,)=XEnX-X*<
,>0滿足
f(X)f(X*),X
DN(X*,)
10第十頁,共五十一頁,編輯于2023年,星期二f(X)局部最優(yōu)解整體最優(yōu)解11第十一頁,共五十一頁,編輯于2023年,星期二2.梯度向量f(X)=gradf(X)=(f/x1,f/x2,…..,f/xn)T區(qū)間內(nèi)連續(xù)的梯度的性質(zhì):①在某點的f(X(0))必與函數(shù)過該點的等值面的切平面相垂直。②梯度方向是函數(shù)值增加最快的方向(函數(shù)變化率最大的方向)負梯度方向是函數(shù)值減小最快的方向。12第十二頁,共五十一頁,編輯于2023年,星期二13第十三頁,共五十一頁,編輯于2023年,星期二3、海賽(Hesse)矩陣
2f(X)=H(X)2f/x12
2f/x1x2…..2f/x1xn2f/x2x12f/x22
…..2f/x2xn……..2f/xnx1
2f/xnx2…..2f/xn2=14第十四頁,共五十一頁,編輯于2023年,星期二2f(X)是對稱矩陣。(f(X)二階偏導數(shù)連續(xù)時,混合偏導數(shù)和取導數(shù)的順序無關(guān))f(X)是二次函數(shù),則可寫成
f(X)=1/2XTAX+BTX+C則2f(X)=A(與X的位置無關(guān))15第十五頁,共五十一頁,編輯于2023年,星期二4、正定矩陣、負定、半定、不定正定:特征值>0;各階主子式>0(Ai>0)半正定:特征值≥0;detA=0,Ai≥0負定:特征值<0;Ai<0(i為奇),Ai>0(i為偶)半負定:特征值≤0;detA=0,Ai≤0(i為奇),Ai≥0(i為偶)不定:特征值有>
0及<
0;除了上述情況外即為不定。16第十六頁,共五十一頁,編輯于2023年,星期二例:判定正定性解:17第十七頁,共五十一頁,編輯于2023年,星期二例:判定正定性解:18第十八頁,共五十一頁,編輯于2023年,星期二作業(yè):P2004.4(1)19第十九頁,共五十一頁,編輯于2023年,星期二7.2無約束問題的極值條件例求解如下非線性規(guī)劃問題o262620第二十頁,共五十一頁,編輯于2023年,星期二分析:
非線性規(guī)劃的最優(yōu)解可能在可行域的任一點達到。o226621第二十一頁,共五十一頁,編輯于2023年,星期二若H(x)為正定,該駐點X*是嚴格局部極小值點;若H(x)為負定,該駐點X*是嚴格局部極大值點;若H(x)為半正定(半負定),則進一步觀察它在該點某鄰域內(nèi)的情況,可能是可能不是;如果H(x)不定的,該駐點X*就不是f(X)極值點。一、用海賽矩陣判斷駐點的性質(zhì)22第二十二頁,共五十一頁,編輯于2023年,星期二二、極值點的必要條件和充分條件最優(yōu)性條件的研究是非線性規(guī)劃理論研究的一個中心問題。為什么要研究最優(yōu)性條件?本質(zhì)上把可行解集合的范圍縮小。它是許多算法設(shè)計的基礎(chǔ)。23第二十三頁,共五十一頁,編輯于2023年,星期二無約束問題的最優(yōu)性條件(P1)Minf(X)XEn
定理3(一階必要條件)
設(shè)f(X)在X*點可微,則X*為(P1)的一個局部極值點,一定有f(X*)=gradf(X*)=0(X*稱為駐點)24第二十四頁,共五十一頁,編輯于2023年,星期二無約束問題的最優(yōu)性條件(P1)Minf(X)XEn
定理4(二階必要條件)
設(shè)f(X)在X*點二階可微,如果X*為(P1)的一個局部極小點,則有f(X*)=0和H(X*
)為半正定。25第二十五頁,共五十一頁,編輯于2023年,星期二無約束問題的最優(yōu)性條件(P1)Minf(X)XEn
定理5(二階充分條件)
設(shè)f(X)在X*點二階可微,如果f(X*)=0和H(X*)為正定,則X*為(P1)的一個嚴格局部極小點。26第二十六頁,共五十一頁,編輯于2023年,星期二例
Minf(X)=2x12+5x22+x32+
2x2x3
+
2x1x3-
6x2+3XE3
解:f(X)=(4x1+
2x3,10x2+
2x3–
6,2x1+
2x2+
2x3
)=0駐點x*=(1,1,-2)H(X)=2f(X)=02010222227第二十七頁,共五十一頁,編輯于2023年,星期二H(X)=2f(X)=020102222各階主子式:4>0,=40>04
0010020102222
=24>0H(X)正定,X*=(1,1,-2),f(X*)=028第二十八頁,共五十一頁,編輯于2023年,星期二例利用極值條件解無約束非線性規(guī)劃問題解因為
,
令即求得到4個駐點:
,和不是極小點;
是極小點。29第二十九頁,共五十一頁,編輯于2023年,星期二凸集概念:
設(shè)D是n維線性空間En的一個點集,若D中的任意兩點x(1),x(2)的連線上的一切點x仍在D中,則稱D為凸集。即:若D中的任意兩點x(1),x(2)
∈D,任意0<<1使得x=x(1)+(1-)x(2)∈D,則稱D為凸集7.3凸函數(shù)與凸規(guī)劃30第三十頁,共五十一頁,編輯于2023年,星期二一、凸函數(shù)的定義幾何解釋31第三十一頁,共五十一頁,編輯于2023年,星期二f(X)X32第三十二頁,共五十一頁,編輯于2023年,星期二f(X)Xf(X1)f(X2)X1X233第三十三頁,共五十一頁,編輯于2023年,星期二f(X)Xf(x1)
+(1-)f(x2)f(X1)f(X2)X1X2x1+(1-)x2f(x1+(1-)x2)34第三十四頁,共五十一頁,編輯于2023年,星期二f(X)Xf(x1)
+(1-)f(x2)f(X1)f(X2)X1X2x1+(1-)x2f(x1+(1-)x2)任意兩點的函數(shù)值的連線上的點都在曲線的上方35第三十五頁,共五十一頁,編輯于2023年,星期二線性函數(shù)既是凸函數(shù),又是凹函數(shù)。如果-f(X)為R上的(嚴格)凸函數(shù),則f(X)為R上的(嚴格)凹函數(shù).36第三十六頁,共五十一頁,編輯于2023年,星期二二.凸函數(shù)的性質(zhì)
性質(zhì)1設(shè)都是定義在凸集R上的凸函數(shù),那么仍是在凸集R上的凸函數(shù)。性質(zhì)2設(shè)是定義在凸集S上的凸函數(shù),那么對任意實數(shù),集合是S的凸子集。性質(zhì)3f(x)是凸集R上凸函數(shù),則f(x)在R上局部極小點就是全局極小點,且極小點的集合是凸集。
37第三十七頁,共五十一頁,編輯于2023年,星期二三、凸函數(shù)的判別38第三十八頁,共五十一頁,編輯于2023年,星期二例39第三十九頁,共五十一頁,編輯于2023年,星期二作業(yè):P2004.6(1)(2)40第四十頁,共五十一頁,編輯于2023年,星期二定理6(充要條件):若是二階連續(xù)可微的凸函數(shù),則是全局極小點。類似地,若二階連續(xù)可微的嚴格凸函數(shù),則是惟一全局極小點。四、凸函數(shù)極值點的充要條件41第四十一頁,共五十一頁,編輯于2023年,星期二解無約束問題的算法:求f(X)的駐點X*,若是凸函數(shù),得到最優(yōu)解。否則,轉(zhuǎn)下一步。在駐點X*處,計算H(x)。根據(jù)H(x)來判斷該駐點X*是否是極值點。42第四十二頁,共五十一頁,編輯于2023年,星期二例
求極值f(X)=x1+
2x3+x2x3-x12-x22-x32XE3
解:f(X)=(1-2x1,x3-2x2,2+x2-
2x3)=0駐點x*=(1/2,2/3,4/3)H(X)=xxf(X)=-2000-2101-243第四十三頁,共五十一頁,編輯于2023年,星期二H(X)=xxf(X)=各階主子式:-2<0,=4>0-2
00-2=-6<0-2000-2101-2-2000-2101-2
H(X)負定,f(X)
是凹函數(shù)X*=(1/2,2/3,4/3)為極大值點。f(X*)=f(1/2,2/3,4/3)=19/1244第四十四頁,共五十一頁,編輯于2023年,星期二
五、凸規(guī)劃下述問題為凸規(guī)劃.求凸函數(shù)
溫馨提示
- 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會有圖紙預覽,若沒有圖紙預覽就沒有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 人人文庫網(wǎng)僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負責。
- 6. 下載文件中如有侵權(quán)或不適當內(nèi)容,請與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。
最新文檔
- 二零二五年度企業(yè)員工食宿補貼與職業(yè)發(fā)展合同
- 二零二五年度兼職心理咨詢師非全日制勞動合同書
- 二零二五年度監(jiān)事企業(yè)內(nèi)部控制體系完善勞動合同
- 2025年度知識產(chǎn)權(quán)許可違約責任規(guī)范合同
- 2025年度資產(chǎn)代持與資產(chǎn)評估與資產(chǎn)保全服務(wù)合同
- 二零二五年度特色商業(yè)街區(qū)車位租賃轉(zhuǎn)讓合同
- 二零二五年度私人借款與月子中心服務(wù)合同
- 2025【合同范本】贈與合同的定義性質(zhì)與
- 2025合同模板電氣設(shè)備維修、保養(yǎng)合同范本
- 7《健康看電視》第一課時(說課稿)-統(tǒng)編版道德與法治四年級上冊
- 人教版三下勞動項目四《蒸蛋羹》教學設(shè)計
- 質(zhì)量為綱-華為公司質(zhì)量理念與實踐
- 部編版六年級語文下冊第一單元大單元教學任務(wù)單
- 2023徐金桂“徐徐道來”(行政法知識點)版
- 《事故汽車常用零部件修復與更換判別規(guī)范》
- 物業(yè)管理如何實現(xiàn)降本增效
- JBT 1306-2024 電動單梁起重機(正式版)
- 信息科技重大版 七年級下冊 互聯(lián)網(wǎng)應(yīng)用與創(chuàng)新 第一單元單元教學設(shè)計 互聯(lián)網(wǎng)創(chuàng)新應(yīng)用
- 高中政治必刷題 高考真題 必修3《政治與法治》(原卷版)
- 2024年輔警招聘考試試題庫含完整答案(各地真題)
- 2024年執(zhí)業(yè)醫(yī)師考試-醫(yī)師定期考核(人文醫(yī)學)筆試參考題庫含答案
評論
0/150
提交評論