一般非線性規(guī)劃-電子科技大學課件

線性規(guī)劃第8章最優(yōu)化方法無約束規(guī)劃非線性規(guī)劃線性規(guī)劃第8章最優(yōu)化方法無約束規(guī)劃非線性規(guī)劃1實驗目的實驗內容2、掌握用數(shù)學軟件包求解線性規(guī)劃問題。1、了解線性規(guī)劃的基本內容。3、實驗作業(yè)。2、用數(shù)學軟件包求解線性規(guī)劃問題。1、兩個引例。實驗目的實驗內容2、掌握用數(shù)學軟件包求解線性規(guī)劃問題。1、了2問題一：

任務分配問題：某車間有甲、乙兩臺機床，可用于加工三種工件。假定這兩臺車床的可用臺時數(shù)分別為800和900，三種工件的數(shù)量分別為400、600和500，且已知用三種不同車床加工單位數(shù)量不同工件所需的臺時數(shù)和加工費用如下表。問怎樣分配車床的加工任務，才能既滿足加工工件的要求，又使加工費用最低？兩個引例問題一：任務分配問題：某車間有甲、乙兩臺機床，可用于3解

設在甲車床上加工工件1、2、3的數(shù)量分別為x1、x2、x3，在乙車床上加工工件1、2、3的數(shù)量分別為x4、x5、x6?？山⒁韵戮€性規(guī)劃模型：

解答解設在甲車床上加工工件1、2、3的數(shù)量分別為x1、x4問題二：

某廠生產(chǎn)甲、乙兩種產(chǎn)品，已知制成一噸產(chǎn)品甲需用資源A3噸資源B4m3；制成一噸產(chǎn)品乙需用資源A2噸，資源B6m3，資源C7個單位。若一噸產(chǎn)品甲和乙的經(jīng)濟價值分別為7萬元和5萬元，三種資源的限制量分別為90噸、200m3和210個單位。試應生產(chǎn)這兩種產(chǎn)品各多少噸才能使創(chuàng)造的總經(jīng)濟價值最高？（p153，例8-2）解：這是個最優(yōu)化問題，其目標為經(jīng)濟價值最高，約束條件為三種資源的數(shù)量有限，決策為生產(chǎn)甲、乙產(chǎn)品的數(shù)量。令生產(chǎn)產(chǎn)品甲的數(shù)量為x1，生產(chǎn)產(chǎn)品乙的數(shù)量為x2。由題意可以建立如下的線性規(guī)劃模型。問題二：某廠生產(chǎn)甲、乙兩種產(chǎn)品，已知制成一噸產(chǎn)品甲需用5故目標函數(shù)為：約束條件為：故目標函數(shù)為：約束條件為：6問題2線性規(guī)劃模型：解答返回問題2線性規(guī)劃模型：解答返回71.線性規(guī)劃的標準形式：用單純法求解時，常將標準形式化為：2.線性規(guī)劃的基本算法——單純形法線性規(guī)劃的基本算法——單純形法1.線性規(guī)劃的標準形式：用單純法求解時，常將標準形式化為：28引入松弛變量x3,x4,x5,將不等式化為等式,即單純形標準形:引入松弛變量x3,x4,x5,將不等式化為等式,即單9用MATLAB優(yōu)化工具箱解線性規(guī)劃minz=cX

1、模型：命令：x=linprog（c，A，b）

2、模型：minz=cX

命令：x=linprog（c，A，b，Aeq,beq）注意：若沒有不等式：存在，則令A=[]，b=[].用MATLAB優(yōu)化工具箱解線性規(guī)劃minz=cX103、模型：minz=cX

VLB≤X≤VUB命令：[1]x=linprog（c，A，b，Aeq,beq,VLB，VUB）

[2]x=linprog（c，A，b，Aeq,beq,VLB，VUB,X0）

注意：[1]若沒有等式約束:,則令Aeq=[],beq=[].[2]其中X0表示初始點4、命令：[x,fval]=linprog(…)返回最優(yōu)解ｘ及ｘ處的目標函數(shù)值fval.3、模型：minz=cXVLB≤X≤VUB命令：[11解編寫M文件如下：c=[-0.4-0.28-0.32-0.72-0.64-0.6];A=[0.010.010.010.030.030.03;0.02000.0500;00.02000.050;000.03000.08];b=[850;700;100;900];Aeq=[];beq=[];vlb=[0;0;0;0;0;0];vub=[];[x,fval]=linprog(c,A,b,Aeq,beq,vlb,vub)解編寫M文件如下：12解:編寫M文件如下：c=[-7-5];A=[32;46;07];b=[90;200;210];Aeq=[];beq=[];vlb=[0,0];vub=[inf,inf];[x,fval]=linprog(c,A,b,Aeq,beq,vlb,vub)問題2解答解:編寫M文件如下：問題2解答13S.t.改寫為：例3問題一的解答

問題S.t.改寫為：例3問題一的解答問題14編寫M文件如下:f=[1391011128];A=[0.41.110000000.51.21.3];b=[800;900];Aeq=[100100010010001001];beq=[400600500];vlb=zeros(6,1);vub=[];[x,fval]=linprog(f,A,b,Aeq,beq,vlb,vub)編寫M文件如下:15結果:x=0.0000600.00000.0000400.00000.0000500.0000fval=1.3800e+004即在甲機床上加工600個工件2,在乙機床上加工400個工件1、500個工件3，可在滿足條件的情況下使總加工費最小為13800。結果:16結果為：x=14.000024.0000fval=-218.0000

注：有些實際問題可能會有一個約束條件：決策變量只能取整數(shù)，如x1、x2取整數(shù)。這類問題實際上是整數(shù)線性規(guī)劃問題。如果把它當成一個線性規(guī)劃來解，求得其最優(yōu)解剛好是整數(shù)時，故它就是該整數(shù)規(guī)劃的最優(yōu)解。若用線性規(guī)劃解法求得的最優(yōu)解不是整數(shù)，將其取整后不一定是相應整數(shù)規(guī)劃的最優(yōu)解，這樣的整數(shù)規(guī)劃應用專門的方法求解（如割平面法、分支定界法）。結果為：注：有些實際問題可能會有一個約束條件：決策變量只17實驗作業(yè)某廠生產(chǎn)甲乙兩種口味的飲料,每百箱甲飲料需用原料6千克,工人10名,可獲利10萬元;每百箱乙飲料需用原料5千克,工人20名,可獲利9萬元.今工廠共有原料60千克,工人150名,又由于其他條件所限甲飲料產(chǎn)量不超過8百箱.問如何安排生產(chǎn)計劃,即兩種飲料各生產(chǎn)多少使獲利最大.進一步討論:1)若投資0.8萬元可增加原料1千克,問應否作這項投資.2)若每百箱甲飲料獲利可增加1萬元,問應否改變生產(chǎn)計劃.返回實驗作業(yè)某廠生產(chǎn)甲乙兩種口味的飲料,每百箱甲飲料需用原料618無約束最優(yōu)化數(shù)學實驗電子科技大學應用數(shù)學學院無約束最優(yōu)化數(shù)學實驗電子科技大學應用數(shù)學學院19實驗目的實驗內容2、掌握用數(shù)學軟件包求解無約束最優(yōu)化問題。1、了解無約束最優(yōu)化基本算法。1、無約束優(yōu)化基本思想及基本算法。4、實驗作業(yè)。3、用MATLAB求解無約束優(yōu)化問題。2、MATLAB優(yōu)化工具箱簡介實驗目的實驗內容2、掌握用數(shù)學軟件包求解無約束最優(yōu)化問題。120無約束最優(yōu)化問題求解無約束最優(yōu)化問題的的基本思想*無約束最優(yōu)化問題的基本算法返回無約束最優(yōu)化問題求解無約束最優(yōu)化問題的的基本思想*無約束最21標準形式：求解無約束最優(yōu)化問題的基本思想求解的基本思想(以二元函數(shù)為例)531連續(xù)可微標準形式：求解無約束最優(yōu)化問題的基本思想求解的基本思想22一般非線性規(guī)劃-電子科技大學課件23多局部極小唯一極小(全局極小)多局部極小唯一極小24搜索過程最優(yōu)點(11)初始點(-11)-114.00-0.790.583.39-0.530.232.60-0.180.001.500.09-0.030.980.370.110.470.590.330.200.800.630.050.950.900.0030.990.991E-40.9990.9981E-50.99970.99981E-8返回搜索過程最優(yōu)點(11)-114.00-0.790.25無約束優(yōu)化問題的基本算法

最速下降法是一種最基本的算法，它在最優(yōu)化方法中占有重要地位.最速下降法的優(yōu)點是工作量小，存儲變量較少,初始點要求不高；缺點是收斂慢，最速下降法適用于尋優(yōu)過程的前期迭代或作為間插步驟，當接近極值點時，宜選用別種收斂快的算法.

1．最速下降法（共軛梯度法）算法步驟：無約束優(yōu)化問題的基本算法最速下降法是一種最基本的算法，262．牛頓法算法步驟：如果f是對稱正定矩陣A的二次函數(shù)，則用牛頓法經(jīng)過一次迭代就可達到最優(yōu)點,如不是二次函數(shù)，則牛頓法不能一步達到極值點，但由于這種函數(shù)在極值點附近和二次函數(shù)很近似,因此牛頓法的收斂速度還是很快的.牛頓法的收斂速度雖然較快，但要求Hessian矩陣要可逆，要計算二階導數(shù)和逆矩陣，就加大了計算機計算量和存儲量.2．牛頓法算法步驟：如果f是對稱正定矩陣A的二次函數(shù)273．擬牛頓法3．擬牛頓法28一般非線性規(guī)劃-電子科技大學課件29返回返回30Matlab優(yōu)化工具箱簡介1.MATLAB求解優(yōu)化問題的主要函數(shù)Matlab優(yōu)化工具箱簡介1.MATLAB求解優(yōu)化問題的主要312.優(yōu)化函數(shù)的輸入變量

使用優(yōu)化函數(shù)或優(yōu)化工具箱中其它優(yōu)化函數(shù)時,輸入變量見下表:2.優(yōu)化函數(shù)的輸入變量使用優(yōu)化函數(shù)或優(yōu)化工具箱中其它優(yōu)323.優(yōu)化函數(shù)的輸出變量下表:3.優(yōu)化函數(shù)的輸出變量下表:334．控制參數(shù)options的設置(3)MaxIter:允許進行迭代的最大次數(shù),取值為正整數(shù).Options中常用的幾個參數(shù)的名稱、含義、取值如下:(1) Display:顯示水平.取值為’off’時,不顯示輸出;取值為’iter’時,顯示每次迭代的信息;取值為’final’時,顯示最終結果.默認值為’final’.(2) MaxFunEvals:允許進行函數(shù)評價的最大次數(shù),取值為正整數(shù).4．控制參數(shù)options的設置Options中常用的幾個參34例：opts=optimset(‘Display’,’iter’,’TolFun’,1e-8)該語句創(chuàng)建一個稱為opts的優(yōu)化選項結構,其中顯示參數(shù)設為’iter’,TolFun參數(shù)設為1e-8.控制參數(shù)options可以通過函數(shù)optimset創(chuàng)建或修改。命令的格式如下：(1)options=optimset(‘optimfun’)創(chuàng)建一個含有所有參數(shù)名,并與優(yōu)化函數(shù)optimfun相關的默認值的選項結構options.（2）options=optimset(‘param1’,value1,’param2’,value2,...)創(chuàng)建一個名稱為options的優(yōu)化選項參數(shù),其中指定的參數(shù)具有指定值,所有未指定的參數(shù)取默認值.(3)options=optimset(oldops,‘param1’,value1,’param2’,value2,...)創(chuàng)建名稱為oldops的參數(shù)的拷貝,用指定的參數(shù)值修改oldops中相應的參數(shù).返回例：opts=optimset(‘Display’,’ite35用Matlab解無約束優(yōu)化問題其中（3）、（4）、（5）的等式右邊可選用（1）或（2）的等式右邊。函數(shù)fminbnd的算法基于黃金分割法和二次插值法，它要求目標函數(shù)必須是連續(xù)函數(shù)，并可能只給出局部最優(yōu)解。常用格式如下：（1）x=fminbnd(fun,x1,x2)（2）x=fminbnd(fun,x1,x2，options)（3）[x，fval]=fminbnd（...）（4）[x，fval，exitflag]=fminbnd（...）（5）[x，fval，exitflag，output]=fminbnd（...）用Matlab解無約束優(yōu)化問題其中（3）、（4）、（36

主程序為:f='2*exp(-x).*sin(x)';fplot(f,[0,8]);%作圖語句

[xmin,ymin]=fminbnd(f,0,8)f1='-2*exp(-x).*sin(x)';[xmax,ymax]=fminbnd(f1,0,8)主程序為:37例2對邊長為3米的正方形鐵板，在四個角剪去相等的正方形以制成方形無蓋水槽，問如何剪法使水槽的容積最大？p156，例8-1解先編寫M文件fminbndtest.m如下:functionf=myfun(x)f=-(3-2*x).^2*x;主程序調用fminbnd:[x,fval]=fminbnd('fminbndtest',0,1.5);xmax=xfmax=-fval運算結果為:xmax=0.5000,fmax=2.0000.即剪掉的正方形的邊長為0.5米時水槽的容積最大,最大容積為2立方米.例2對邊長為3米的正方形鐵板，在四個角剪去相等的正方形以38命令格式為:（1）x=fminunc（fun,X0）；或x=fminsearch（fun,X0）（2）x=fminunc（fun,X0，options）；或x=fminsearch（fun,X0，options）（3）[x，fval]=fminunc（...）；或[x，fval]=fminsearch（...）（4）[x，fval，exitflag]=fminunc（...）；或[x，fval，exitflag]=fminsearch（5）[x，fval，exitflag，output]=fminunc（...）；或[x，fval，exitflag，output]=fminsearch（...）2、多元函數(shù)無約束優(yōu)化問題標準型為：minF(X)命令格式為:2、多元函數(shù)無約束優(yōu)化問題標準型39[3]fminunc為中型優(yōu)化算法的步長一維搜索提供了兩種算法，由options中參數(shù)LineSearchType控制：LineSearchType=’quadcubic’(缺省值)，混合的二次和三次多項式插值；LineSearchType=’cubicpoly’，三次多項式插使用fminunc和fminsearch可能會得到局部最優(yōu)解.說明:fminsearch是用單純形法尋優(yōu).fminunc的算法見以下幾點說明：[1]fminunc為無約束優(yōu)化提供了大型優(yōu)化和中型優(yōu)化算法。由options中的參數(shù)LargeScale控制：LargeScale=’on’(默認值),使用大型算法LargeScale=’off’(默認值),使用中型算法[2]fminunc為中型優(yōu)化算法的搜索方向提供了4種算法，由options中的參數(shù)HessUpdate控制：HessUpdate=’bfgs’（默認值），擬牛頓法的BFGS公式；HessUpdate=’dfp’，擬牛頓法的DFP公式；HessUpdate=’steepdesc’，最速下降法[3]fminunc為中型優(yōu)化算法的步長一維搜索提供了兩種40例3minf(x)=(4x12+2x22+4x1x2+2x2+1)*exp(x1)1、編寫M-文件fun1.m:functionf=fun1(x)f=exp(x(1))*(4*x(1)^2+2*x(2)^2+4*x(1)*x(2)+2*x(2)+1);

2、輸入M文件myprg3.m如下:x0=[-1,1];x=fminunc('fun1',x0);y=fun1(x)

3、運行結果:x=0.5000-1.0000y=1.3029e-10例3minf(x)=(4x12+2x22+4x1x2+2412.畫出Rosenbrock函數(shù)的等高線圖,輸入命令：contour(x,y,z,20)holdonplot(-1.2,2,'o');text(-1.2,2,'startpoint')plot(1,1,'o')text(1,1,'solution')2.畫出Rosenbrock函數(shù)的等高線圖,輸入命令：423.用fminsearch函數(shù)求解輸入命令:f='100*(x(2)-x(1)^2)^2+(1-x(1))^2';[x,fval,exitflag,output]=fminsearch(f,[-1.22])運行結果:x=1.00001.0000fval=1.9151e-010exitflag=1output=iterations:108funcCount:202algorithm:'Nelder-Meadsimplexdirectsearch'3.用fminsearch函數(shù)求解輸入命令:運行結果:434.

用fminunc函數(shù)(1)建立M-文件fun1.m

functionf=fun1(x)f=100*(x(2)-x(1)^2)^2+(1-x(1))^2(2)求解主程序oldoptions=optimset('fminunc')options=optimset(oldoptions,'LargeScale','off')

options11=optimset(options,'HessUpdate','dfp')[x11,fval11,exitflag11,output11]=fminunc('fun1',[-1.22],options11)4.用fminunc函數(shù)(1)建立M-文件fun1.m44Rosenbrock函數(shù)不同算法的計算結果可以看出，最速下降法的結果最差.因為最速下降法特別不適合于從一狹長通道到達最優(yōu)解的情況.Rosenbrock函數(shù)不同算法的計算結果可以看出，最速下45實驗作業(yè)實驗作業(yè)46一般非線性規(guī)劃-電子科技大學課件47數(shù)學實驗非線性規(guī)劃

電子科技大學應用數(shù)學學院數(shù)學實驗非線性規(guī)劃電子科技大學應用數(shù)學學院48實驗目的實驗內容2、掌握用數(shù)學軟件求解優(yōu)化問題。1、直觀了解非線性規(guī)劃的基本內容。1、非線性規(guī)劃的基本理論。3、實驗作業(yè)。2、用數(shù)學軟件求解非線性規(guī)劃。實驗目的實驗內容2、掌握用數(shù)學軟件求解優(yōu)化問題。1、直觀了解49非線性規(guī)劃的基本概念非線性規(guī)劃非線性規(guī)劃的基本概念非線性規(guī)劃50

定義

如果目標函數(shù)或約束條件中至少有一個是非線性函數(shù)時的最優(yōu)化問題就叫做非線性規(guī)劃問題．非現(xiàn)性規(guī)劃的基本概念

一般形式:

（1）其中，是定義在En上的實值函數(shù)，簡記:

其它情況:求目標函數(shù)的最大值或約束條件為小于等于零的情況，都可通過取其相反數(shù)化為上述一般形式．定義如果目標函數(shù)或約束條件中至少有一51

定義1把滿足問題（1）中條件的解稱為可行解（或可行點），所有可行點的集合稱為可行集（或可行域）．記為D．即問題(1)可簡記為．定義2對于問題(1)，設，若存在,使得對一切，且，都有，則稱X*是f(X)在D上的局部極小值點（局部最優(yōu)解）．特別地當時，若，則稱X*是f(X)在D上的嚴格局部極小值點（嚴格局部最優(yōu)解）．定義3對于問題(1),設,對任意的,都有則稱X*是f(X)在D上的全局極小值點（全局最優(yōu)解）．特別地當時，若，則稱X*是f(X)在D上的嚴格全局極小值點（嚴格全局最優(yōu)解）．定義2對于問題(1)，設52

罰函數(shù)法

罰函數(shù)法基本思想是通過構造罰函數(shù)把約束問題轉化為一系列無約束最優(yōu)化問題，進而用無約束最優(yōu)化方法去求解．這類方法稱為序列無約束最小化方法．簡稱為SUMT法．其一為SUMT外點法，其二為SUMT內點法．罰函數(shù)法罰函數(shù)法基本思想是通過構造罰函數(shù)把約束問題53其中T(X,M)稱為罰函數(shù)，M稱為罰因子，帶M的項稱為罰項，這里的罰函數(shù)只對不滿足約束條件的點實行懲罰：當時，滿足各，故罰項=0，不受懲罰．當時，必有的約束條件，故罰項>0，要受懲罰．SUTM外點法其中T(X,M)稱為罰函數(shù)，M稱為罰因子，帶M的項稱54罰函數(shù)法的缺點是：每個近似最優(yōu)解Xk往往不是容許解，而只能近似滿足約束，在實際問題中這種結果可能不能使用；在解一系列無約束問題中，計算量太大，特別是隨著Mk的增大，可能導致錯誤．1、任意給定初始點X0，取M1>1，給定允許誤差，令k=1；2、求無約束極值問題的最優(yōu)解，設為Xk=X(Mk)，即；3、若存在，使，則取Mk>M()令k=k+1返回（2），否則，停止迭代．得最優(yōu)解.計算時也可將收斂性判別準則改為.SUTM外點法(罰函數(shù)法)的迭代步驟罰函數(shù)法的缺點是：每個近似最優(yōu)解Xk往往不是容許解，55SUTM內點法（障礙函數(shù)法）SUTM內點法（障礙函數(shù)法）56內點法的迭代步驟內點法的迭代步驟57用MATLAB軟件求解,其輸入格式如下:

1. x=quadprog(H,C,A,b);2. x=quadprog(H,C,A,b,Aeq,beq);3. x=quadprog(H,C,A,b,Aeq,beq,VLB,VUB);4. x=quadprog(H,C,A,b,Aeq,beq,VLB,VUB,X0);5. x=quadprog(H,C,A,b,Aeq,beq,VLB,VUB,X0,options);6. [x,fval]=quaprog(...);7. [x,fval,exitflag]=quaprog(...);8. [x,fval,exitflag,output]=quaprog(...);1、二次規(guī)劃用MATLAB軟件求解,其輸入格式如下:1、二次規(guī)劃58例1

minf(x1,x2)=-2x1-6x2+x12-2x1x2+2x22s.t.x1+x2≤2-x1+2x2≤2x1≥0,x2≥01、寫成標準形式：2、輸入命令：

H=[1-1;-12];c=[-2;-6];A=[11;-12];b=[2;2];Aeq=[];beq=[];VLB=[0;0];VUB=[];[x,z]=quadprog(H,c,A,b,Aeq,beq,VLB,VUB)3、運算結果為：

x=0.66671.3333z=-8.2222s.t.例1minf(x1,x2)=-2x1-6x2+x159

1.首先建立M文件fun.m,定義目標函數(shù)F（X）:functionf=fun(X);f=F(X);2、一般非線性規(guī)劃

其中X為n維變元向量，G(X)與Ceq(X)均為非線性函數(shù)組成的向量，其它變量的含義與線性規(guī)劃、二次規(guī)劃中相同.用Matlab求解上述問題，基本步驟分三步：1.首先建立M文件fun.m,定義目標函數(shù)F（X）:2、603.建立主程序.非線性規(guī)劃求解的函數(shù)是fmincon,命令的基本格式如下：

(1)x=fmincon(‘fun’,X0,A,b)

(2)x=fmincon(‘fun’,X0,A,b,Aeq,beq)

(3)x=fmincon(‘fun’,X0,A,b,Aeq,beq,VLB,VUB)

(4)x=fmincon(‘fun’,X0,A,b,Aeq,beq,VLB,VUB,’nonlcon’)(5)x=fmincon(‘fun’,X0,A,b,Aeq,beq,VLB,VUB,’nonlcon’,options)

(6)[x,fval]=fmincon(...)

(7)[x,fval,exitflag]=fmincon(...)(8)[x,fval,exitflag,output]=fmincon(...)輸出極值點M文件迭代的初值參數(shù)說明變量上下限3.建立主程序.非線性規(guī)劃求解的函數(shù)是fmincon,命令61注意：[1]fmincon函數(shù)提供了大型優(yōu)化算法和中型優(yōu)化算法。默認時，若在fun函數(shù)中提供了梯度（options參數(shù)的GradObj設置為’on’），并且只有上下界存在或只有等式約束，fmincon函數(shù)將選擇大型算法。當既有等式約束又有梯度約束時，使用中型算法。[2]fmincon函數(shù)的中型算法使用的是序列二次規(guī)劃法。在每一步迭代中求解二次規(guī)劃子問題，并用BFGS法更新拉格朗日Hessian矩陣。[3]fmincon函數(shù)可能會給出局部最優(yōu)解，這與初值X0的選取有關。注意：621、寫成標準形式：

s.t.

2x1+3x26s.tx1+4x25x1,x20例21、寫成標準形式：2x1+3x2632、先建立M-文件fun3.m:

functionf=fun3(x);f=-x(1)-2*x(2)+(1/2)*x(1)^2+(1/2)*x(2)^23、再建立主程序youh2.m：x0=[1;1];A=[23;14];b=[6;5];Aeq=[];beq=[];VLB=[0;0];VUB=[];[x,fval]=fmincon('fun3',x0,A,b,Aeq,beq,VLB,VUB)4、運算結果為：x=0.76471.0588fval=-2.02942、先建立M-文件fun3.m:3、再建立主程序youh2641．先建立M文件fun4.m,定義目標函數(shù):

functionf=fun4(x);f=exp(x(1))*(4*x(1)^2+2*x(2)^2+4*x(1)*x(2)+2*x(2)+1);x1+x2=0s.t.1.5+x1x2-x1-x20-x1x2–10

0例32．再建立M文件mycon.m定義非線性約束：function[g,ceq]=mycon(x)g=[x(1)+x(2);1.5+x(1)*x(2)-x(1)-x(2);-x(1)*x(2)-10];1．先建立M文件fun4.m,定義目標函數(shù):653．主程序為:x0=[-1;1];A=[];b=[];Aeq=[11];beq=[0];vlb=[];vub=[];[x,fval]=fmincon('fun4',x0,A,b,Aeq,beq,vlb,vub,'mycon')3.運算結果為：

x=-1.22501.2250fval=1.89513．主程序為:3.運算結果為：66例4

1．先建立M-文件fun.m定義目標函數(shù):functionf=fun(x);f=-2*x(1)-x(2);2．再建立M文件mycon2.m定義非線性約束：function[g,ceq]=mycon2(x)g=[x(1)^2+x(2)^2-25;x(1)^2-x(2)^2-7];例41．先建立M-文件673.主程序fxx.m為:x0=[3;2.5];VLB=[00];VUB=[510];[x,fval,exitflag,output]=fmincon('fun',x0,[],[],[],[],VLB,VUB,'mycon2')3.主程序fxx.m為:684.運算結果為:x=4.00003.0000fval=-11.0000exitflag=1output=iterations:4funcCount:17stepsize:1algorithm:[1x44char]firstorderopt:[]cgiterations:[]4.運算結果為:69練習練習70線性規(guī)劃第8章最優(yōu)化方法無約束規(guī)劃非線性規(guī)劃線性規(guī)劃第8章最優(yōu)化方法無約束規(guī)劃非線性規(guī)劃71實驗目的實驗內容2、掌握用數(shù)學軟件包求解線性規(guī)劃問題。1、了解線性規(guī)劃的基本內容。3、實驗作業(yè)。2、用數(shù)學軟件包求解線性規(guī)劃問題。1、兩個引例。實驗目的實驗內容2、掌握用數(shù)學軟件包求解線性規(guī)劃問題。1、了72問題一：

任務分配問題：某車間有甲、乙兩臺機床，可用于加工三種工件。假定這兩臺車床的可用臺時數(shù)分別為800和900，三種工件的數(shù)量分別為400、600和500，且已知用三種不同車床加工單位數(shù)量不同工件所需的臺時數(shù)和加工費用如下表。問怎樣分配車床的加工任務，才能既滿足加工工件的要求，又使加工費用最低？兩個引例問題一：任務分配問題：某車間有甲、乙兩臺機床，可用于73解

設在甲車床上加工工件1、2、3的數(shù)量分別為x1、x2、x3，在乙車床上加工工件1、2、3的數(shù)量分別為x4、x5、x6。可建立以下線性規(guī)劃模型：

解答解設在甲車床上加工工件1、2、3的數(shù)量分別為x1、x74問題二：

某廠生產(chǎn)甲、乙兩種產(chǎn)品，已知制成一噸產(chǎn)品甲需用資源A3噸資源B4m3；制成一噸產(chǎn)品乙需用資源A2噸，資源B6m3，資源C7個單位。若一噸產(chǎn)品甲和乙的經(jīng)濟價值分別為7萬元和5萬元，三種資源的限制量分別為90噸、200m3和210個單位。試應生產(chǎn)這兩種產(chǎn)品各多少噸才能使創(chuàng)造的總經(jīng)濟價值最高？（p153，例8-2）解：這是個最優(yōu)化問題，其目標為經(jīng)濟價值最高，約束條件為三種資源的數(shù)量有限，決策為生產(chǎn)甲、乙產(chǎn)品的數(shù)量。令生產(chǎn)產(chǎn)品甲的數(shù)量為x1，生產(chǎn)產(chǎn)品乙的數(shù)量為x2。由題意可以建立如下的線性規(guī)劃模型。問題二：某廠生產(chǎn)甲、乙兩種產(chǎn)品，已知制成一噸產(chǎn)品甲需用75故目標函數(shù)為：約束條件為：故目標函數(shù)為：約束條件為：76問題2線性規(guī)劃模型：解答返回問題2線性規(guī)劃模型：解答返回771.線性規(guī)劃的標準形式：用單純法求解時，常將標準形式化為：2.線性規(guī)劃的基本算法——單純形法線性規(guī)劃的基本算法——單純形法1.線性規(guī)劃的標準形式：用單純法求解時，常將標準形式化為：278引入松弛變量x3,x4,x5,將不等式化為等式,即單純形標準形:引入松弛變量x3,x4,x5,將不等式化為等式,即單79用MATLAB優(yōu)化工具箱解線性規(guī)劃minz=cX

1、模型：命令：x=linprog（c，A，b）

2、模型：minz=cX

命令：x=linprog（c，A，b，Aeq,beq）注意：若沒有不等式：存在，則令A=[]，b=[].用MATLAB優(yōu)化工具箱解線性規(guī)劃minz=cX803、模型：minz=cX

VLB≤X≤VUB命令：[1]x=linprog（c，A，b，Aeq,beq,VLB，VUB）

[2]x=linprog（c，A，b，Aeq,beq,VLB，VUB,X0）

注意：[1]若沒有等式約束:,則令Aeq=[],beq=[].[2]其中X0表示初始點4、命令：[x,fval]=linprog(…)返回最優(yōu)解ｘ及ｘ處的目標函數(shù)值fval.3、模型：minz=cXVLB≤X≤VUB命令：[81解編寫M文件如下：c=[-0.4-0.28-0.32-0.72-0.64-0.6];A=[0.010.010.010.030.030.03;0.02000.0500;00.02000.050;000.03000.08];b=[850;700;100;900];Aeq=[];beq=[];vlb=[0;0;0;0;0;0];vub=[];[x,fval]=linprog(c,A,b,Aeq,beq,vlb,vub)解編寫M文件如下：82解:編寫M文件如下：c=[-7-5];A=[32;46;07];b=[90;200;210];Aeq=[];beq=[];vlb=[0,0];vub=[inf,inf];[x,fval]=linprog(c,A,b,Aeq,beq,vlb,vub)問題2解答解:編寫M文件如下：問題2解答83S.t.改寫為：例3問題一的解答

問題S.t.改寫為：例3問題一的解答問題84編寫M文件如下:f=[1391011128];A=[0.41.110000000.51.21.3];b=[800;900];Aeq=[100100010010001001];beq=[400600500];vlb=zeros(6,1);vub=[];[x,fval]=linprog(f,A,b,Aeq,beq,vlb,vub)編寫M文件如下:85結果:x=0.0000600.00000.0000400.00000.0000500.0000fval=1.3800e+004即在甲機床上加工600個工件2,在乙機床上加工400個工件1、500個工件3，可在滿足條件的情況下使總加工費最小為13800。結果:86結果為：x=14.000024.0000fval=-218.0000

注：有些實際問題可能會有一個約束條件：決策變量只能取整數(shù)，如x1、x2取整數(shù)。這類問題實際上是整數(shù)線性規(guī)劃問題。如果把它當成一個線性規(guī)劃來解，求得其最優(yōu)解剛好是整數(shù)時，故它就是該整數(shù)規(guī)劃的最優(yōu)解。若用線性規(guī)劃解法求得的最優(yōu)解不是整數(shù)，將其取整后不一定是相應整數(shù)規(guī)劃的最優(yōu)解，這樣的整數(shù)規(guī)劃應用專門的方法求解（如割平面法、分支定界法）。結果為：注：有些實際問題可能會有一個約束條件：決策變量只87實驗作業(yè)某廠生產(chǎn)甲乙兩種口味的飲料,每百箱甲飲料需用原料6千克,工人10名,可獲利10萬元;每百箱乙飲料需用原料5千克,工人20名,可獲利9萬元.今工廠共有原料60千克,工人150名,又由于其他條件所限甲飲料產(chǎn)量不超過8百箱.問如何安排生產(chǎn)計劃,即兩種飲料各生產(chǎn)多少使獲利最大.進一步討論:1)若投資0.8萬元可增加原料1千克,問應否作這項投資.2)若每百箱甲飲料獲利可增加1萬元,問應否改變生產(chǎn)計劃.返回實驗作業(yè)某廠生產(chǎn)甲乙兩種口味的飲料,每百箱甲飲料需用原料688無約束最優(yōu)化數(shù)學實驗電子科技大學應用數(shù)學學院無約束最優(yōu)化數(shù)學實驗電子科技大學應用數(shù)學學院89實驗目的實驗內容2、掌握用數(shù)學軟件包求解無約束最優(yōu)化問題。1、了解無約束最優(yōu)化基本算法。1、無約束優(yōu)化基本思想及基本算法。4、實驗作業(yè)。3、用MATLAB求解無約束優(yōu)化問題。2、MATLAB優(yōu)化工具箱簡介實驗目的實驗內容2、掌握用數(shù)學軟件包求解無約束最優(yōu)化問題。190無約束最優(yōu)化問題求解無約束最優(yōu)化問題的的基本思想*無約束最優(yōu)化問題的基本算法返回無約束最優(yōu)化問題求解無約束最優(yōu)化問題的的基本思想*無約束最91標準形式：求解無約束最優(yōu)化問題的基本思想求解的基本思想(以二元函數(shù)為例)531連續(xù)可微標準形式：求解無約束最優(yōu)化問題的基本思想求解的基本思想92一般非線性規(guī)劃-電子科技大學課件93多局部極小唯一極小(全局極小)多局部極小唯一極小94搜索過程最優(yōu)點(11)初始點(-11)-114.00-0.790.583.39-0.530.232.60-0.180.001.500.09-0.030.980.370.110.470.590.330.200.800.630.050.950.900.0030.990.991E-40.9990.9981E-50.99970.99981E-8返回搜索過程最優(yōu)點(11)-114.00-0.790.95無約束優(yōu)化問題的基本算法

最速下降法是一種最基本的算法，它在最優(yōu)化方法中占有重要地位.最速下降法的優(yōu)點是工作量小，存儲變量較少,初始點要求不高；缺點是收斂慢，最速下降法適用于尋優(yōu)過程的前期迭代或作為間插步驟，當接近極值點時，宜選用別種收斂快的算法.

1．最速下降法（共軛梯度法）算法步驟：無約束優(yōu)化問題的基本算法最速下降法是一種最基本的算法，962．牛頓法算法步驟：如果f是對稱正定矩陣A的二次函數(shù)，則用牛頓法經(jīng)過一次迭代就可達到最優(yōu)點,如不是二次函數(shù)，則牛頓法不能一步達到極值點，但由于這種函數(shù)在極值點附近和二次函數(shù)很近似,因此牛頓法的收斂速度還是很快的.牛頓法的收斂速度雖然較快，但要求Hessian矩陣要可逆，要計算二階導數(shù)和逆矩陣，就加大了計算機計算量和存儲量.2．牛頓法算法步驟：如果f是對稱正定矩陣A的二次函數(shù)973．擬牛頓法3．擬牛頓法98一般非線性規(guī)劃-電子科技大學課件99返回返回100Matlab優(yōu)化工具箱簡介1.MATLAB求解優(yōu)化問題的主要函數(shù)Matlab優(yōu)化工具箱簡介1.MATLAB求解優(yōu)化問題的主要1012.優(yōu)化函數(shù)的輸入變量

使用優(yōu)化函數(shù)或優(yōu)化工具箱中其它優(yōu)化函數(shù)時,輸入變量見下表:2.優(yōu)化函數(shù)的輸入變量使用優(yōu)化函數(shù)或優(yōu)化工具箱中其它優(yōu)1023.優(yōu)化函數(shù)的輸出變量下表:3.優(yōu)化函數(shù)的輸出變量下表:1034．控制參數(shù)options的設置(3)MaxIter:允許進行迭代的最大次數(shù),取值為正整數(shù).Options中常用的幾個參數(shù)的名稱、含義、取值如下:(1) Display:顯示水平.取值為’off’時,不顯示輸出;取值為’iter’時,顯示每次迭代的信息;取值為’final’時,顯示最終結果.默認值為’final’.(2) MaxFunEvals:允許進行函數(shù)評價的最大次數(shù),取值為正整數(shù).4．控制參數(shù)options的設置Options中常用的幾個參104例：opts=optimset(‘Display’,’iter’,’TolFun’,1e-8)該語句創(chuàng)建一個稱為opts的優(yōu)化選項結構,其中顯示參數(shù)設為’iter’,TolFun參數(shù)設為1e-8.控制參數(shù)options可以通過函數(shù)optimset創(chuàng)建或修改。命令的格式如下：(1)options=optimset(‘optimfun’)創(chuàng)建一個含有所有參數(shù)名,并與優(yōu)化函數(shù)optimfun相關的默認值的選項結構options.（2）options=optimset(‘param1’,value1,’param2’,value2,...)創(chuàng)建一個名稱為options的優(yōu)化選項參數(shù),其中指定的參數(shù)具有指定值,所有未指定的參數(shù)取默認值.(3)options=optimset(oldops,‘param1’,value1,’param2’,value2,...)創(chuàng)建名稱為oldops的參數(shù)的拷貝,用指定的參數(shù)值修改oldops中相應的參數(shù).返回例：opts=optimset(‘Display’,’ite105用Matlab解無約束優(yōu)化問題其中（3）、（4）、（5）的等式右邊可選用（1）或（2）的等式右邊。函數(shù)fminbnd的算法基于黃金分割法和二次插值法，它要求目標函數(shù)必須是連續(xù)函數(shù)，并可能只給出局部最優(yōu)解。常用格式如下：（1）x=fminbnd(fun,x1,x2)（2）x=fminbnd(fun,x1,x2，options)（3）[x，fval]=fminbnd（...）（4）[x，fval，exitflag]=fminbnd（...）（5）[x，fval，exitflag，output]=fminbnd（...）用Matlab解無約束優(yōu)化問題其中（3）、（4）、（106

主程序為:f='2*exp(-x).*sin(x)';fplot(f,[0,8]);%作圖語句

[xmin,ymin]=fminbnd(f,0,8)f1='-2*exp(-x).*sin(x)';[xmax,ymax]=fminbnd(f1,0,8)主程序為:107例2對邊長為3米的正方形鐵板，在四個角剪去相等的正方形以制成方形無蓋水槽，問如何剪法使水槽的容積最大？p156，例8-1解先編寫M文件fminbndtest.m如下:functionf=myfun(x)f=-(3-2*x).^2*x;主程序調用fminbnd:[x,fval]=fminbnd('fminbndtest',0,1.5);xmax=xfmax=-fval運算結果為:xmax=0.5000,fmax=2.0000.即剪掉的正方形的邊長為0.5米時水槽的容積最大,最大容積為2立方米.例2對邊長為3米的正方形鐵板，在四個角剪去相等的正方形以108命令格式為:（1）x=fminunc（fun,X0）；或x=fminsearch（fun,X0）（2）x=fminunc（fun,X0，options）；或x=fminsearch（fun,X0，options）（3）[x，fval]=fminunc（...）；或[x，fval]=fminsearch（...）（4）[x，fval，exitflag]=fminunc（...）；或[x，fval，exitflag]=fminsearch（5）[x，fval，exitflag，output]=fminunc（...）；或[x，fval，exitflag，output]=fminsearch（...）2、多元函數(shù)無約束優(yōu)化問題標準型為：minF(X)命令格式為:2、多元函數(shù)無約束優(yōu)化問題標準型109[3]fminunc為中型優(yōu)化算法的步長一維搜索提供了兩種算法，由options中參數(shù)LineSearchType控制：LineSearchType=’quadcubic’(缺省值)，混合的二次和三次多項式插值；LineSearchType=’cubicpoly’，三次多項式插使用fminunc和fminsearch可能會得到局部最優(yōu)解.說明:fminsearch是用單純形法尋優(yōu).fminunc的算法見以下幾點說明：[1]fminunc為無約束優(yōu)化提供了大型優(yōu)化和中型優(yōu)化算法。由options中的參數(shù)LargeScale控制：LargeScale=’on’(默認值),使用大型算法LargeScale=’off’(默認值),使用中型算法[2]fminunc為中型優(yōu)化算法的搜索方向提供了4種算法，由options中的參數(shù)HessUpdate控制：HessUpdate=’bfgs’（默認值），擬牛頓法的BFGS公式；HessUpdate=’dfp’，擬牛頓法的DFP公式；HessUpdate=’steepdesc’，最速下降法[3]fminunc為中型優(yōu)化算法的步長一維搜索提供了兩種110例3minf(x)=(4x12+2x22+4x1x2+2x2+1)*exp(x1)1、編寫M-文件fun1.m:functionf=fun1(x)f=exp(x(1))*(4*x(1)^2+2*x(2)^2+4*x(1)*x(2)+2*x(2)+1);

2、輸入M文件myprg3.m如下:x0=[-1,1];x=fminunc('fun1',x0);y=fun1(x)

3、運行結果:x=0.5000-1.0000y=1.3029e-10例3minf(x)=(4x12+2x22+4x1x2+21112.畫出Rosenbrock函數(shù)的等高線圖,輸入命令：contour(x,y,z,20)holdonplot(-1.2,2,'o');text(-1.2,2,'startpoint')plot(1,1,'o')text(1,1,'solution')2.畫出Rosenbrock函數(shù)的等高線圖,輸入命令：1123.用fminsearch函數(shù)求解輸入命令:f='100*(x(2)-x(1)^2)^2+(1-x(1))^2';[x,fval,exitflag,output]=fminsearch(f,[-1.22])運行結果:x=1.00001.0000fval=1.9151e-010exitflag=1output=iterations:108funcCount:202algorithm:'Nelder-Meadsimplexdirectsearch'3.用fminsearch函數(shù)求解輸入命令:運行結果:1134.

用fminunc函數(shù)(1)建立M-文件fun1.m

functionf=fun1(x)f=100*(x(2)-x(1)^2)^2+(1-x(1))^2(2)求解主程序oldoptions=optimset('fminunc')options=optimset(oldoptions,'LargeScale','off')

options11=optimset(options,'HessUpdate','dfp')[x11,fval11,exitflag11,output11]=fminunc('fun1',[-1.22],options11)4.用fminunc函數(shù)(1)建立M-文件fun1.m114Rosenbrock函數(shù)不同算法的計算結果可以看出，最速下降法的結果最差.因為最速下降法特別不適合于從一狹長通道到達最優(yōu)解的情況.Rosenbrock函數(shù)不同算法的計算結果可以看出，最速下115實驗作業(yè)實驗作業(yè)116一般非線性規(guī)劃-電子科技大學課件117數(shù)學實驗非線性規(guī)劃

電子科技大學應用數(shù)學學院數(shù)學實驗非線性規(guī)劃電子科技大學應用數(shù)學學院118實驗目的實驗內容2、掌握用數(shù)學軟件求解優(yōu)化問題。1、直觀了解非線性規(guī)劃的基本內容。1、非線性規(guī)劃的基本理論。3、實驗作業(yè)。2、用數(shù)學軟件求解非線性規(guī)劃。實驗目的實驗內容2、掌握用數(shù)學軟件求解優(yōu)化問題。1、直觀了解119非線性規(guī)劃的基本概念非線性規(guī)劃非線性規(guī)劃的基本概念非線性規(guī)劃120

定義

如果目標函數(shù)或約束條件中至少有一個是非線性函數(shù)時的最優(yōu)化問題就叫做非線性規(guī)劃問題．非現(xiàn)性規(guī)劃的基本概念

一般形式:

（1）其中，是定義在En上的實值函數(shù)，簡記:

其它情況:求目標函數(shù)的最大值或約束條件為小于等于零的情況，都可通過取其相反數(shù)化為上述一般形式．定義如果目標函數(shù)或約束條件中至少有一121

定義1把滿足問題（1）中條件的解稱為可行解（或可行點），所有可行點的集合稱為可行集（或可行域）．記為D．即問題(1)可簡記為．定義2對于問題(1)，設，若存在,使得對一切，且，都有，則稱X*是f(X)在D上的局部極小值點（局部最優(yōu)解）．特別地當時，若，則稱X*是f(X)在D上的嚴格局部極小值點（嚴格局部最優(yōu)解）．定義3對于問題(1),設,對任意的,都有則稱X*是f(X)在D上的全局極小值點（全局最優(yōu)解）．特別地當時，若，則稱X*是f(X)在D上的嚴格全局極小值點（嚴格全局最優(yōu)解）．定義2對于問題(1)，設122

罰函數(shù)法

罰函數(shù)法基本思想是通過構造罰函數(shù)把約束問題轉化為一系列無約束最優(yōu)化問題，進而用無約束最優(yōu)化方法去求解．這類方法稱為序列無約束最小化方法．簡稱為SUMT法．其一為SUMT外點法，其二為SUMT內點法．罰函數(shù)法罰函數(shù)法基本思想是通過構造罰函數(shù)把約束問題123其中T(X,M)稱為罰函數(shù)，M稱為罰因子，帶M的項稱為罰項，這里的罰函數(shù)只對不滿足約束條件的點實行懲罰：當時，滿足各，故罰項=0，不受懲罰．當時，必有的約束條件，故罰項>0，要受懲罰．SUTM外點法其中T(X,M)稱為罰函數(shù)，M稱為罰因子，帶M的項稱124罰函數(shù)法的缺點是：每個近似最優(yōu)解Xk往往不是容許解，而只能近似滿足約束，在實際問題中這種結果可能不能使用；在解一系列無約束問題中，計算量太大，特別是隨著Mk的增大，可能導致錯誤．1、任意給定初始點X0，取M1>1，給定允許誤差，令k=1；2、求無約束極值問題的最優(yōu)解，設為Xk=X(Mk)，即；3、若存在，使，則取Mk>M()令k=k+1返回（2），否則，停止迭代．得最優(yōu)解.計算時也可將收斂性判別準則改為.SUTM外點法(罰函數(shù)法)的迭代步驟罰函數(shù)法的缺點是：每個近似最優(yōu)解Xk往往不是容許解，125SUTM內點法（障礙函數(shù)法）SUTM內點法（障礙函數(shù)法）126內點法的迭代步驟內點法的迭代步驟127用MATLAB軟件求解,其輸入格式如下:

1. x=quadprog(H,C,A,b);2. x=quadprog(H,C,A,b,Aeq,beq);3. x=quadprog(H,C,A,b,Aeq,beq,VLB,VUB);4. x=quadprog(H,C,A,b,Aeq,beq,VLB,VUB,X0);5. x=quadprog(H,C,A,b,Aeq,beq,VLB,VUB,X0,options);6. [x,fval]=quaprog(...);7. [x,fval,exitflag]=quaprog(...);8. [x,fval,exitflag,output]=quaprog(...);1、二次規(guī)劃用MATLAB軟件求解,其輸入格式如下:1、二次規(guī)劃128例1

minf(x1,x2)=-2x1-6x2+x12-2x1x2+2x22s.t.x1+x2≤2-x1+2x2≤2x1≥0,x2≥01、寫成標準形式：2、輸入命令：

H=[1-1;-12];c=[-2;-6];A=[11;-12];b=[2;2];Aeq=[];beq=[];VLB=[0;0];VUB=[];[x,z]=quadprog(H,c,A,b,Aeq,beq,VLB,VUB)3、運算結果為：

x=0.66671.3333z=-8.2222s.t.例1minf(x1,x2)=-2x1-6x2+x1129

1.首先建立M文件