數(shù)學(xué)建模通識第十講優(yōu)化

數(shù)學(xué)建模通識第十講優(yōu)化第一頁，共四十五頁，2022年，8月28日優(yōu)化模型四要素決策變量目標函數(shù)（盡量簡單、光滑）約束條件（建模的關(guān)鍵）求解方法（MATLAB,LINDO/LINGO）第二頁，共四十五頁，2022年，8月28日優(yōu)化模型分類線性規(guī)劃模型（目標函數(shù)和約束條件都是線性函數(shù)的優(yōu)化問題）非線性規(guī)劃模型（目標函數(shù)或者約束條件是非線性的函數(shù)）整數(shù)規(guī)劃（決策變量是整數(shù)值得規(guī)劃問題）多目標規(guī)劃（具有多個目標函數(shù)的規(guī)劃問題）目標規(guī)劃（具有不同優(yōu)先級的目標和偏差的規(guī)劃問題）動態(tài)規(guī)劃（求解多階段決策問題的最優(yōu)化方法）第三頁，共四十五頁，2022年，8月28日線性規(guī)劃任務(wù)分配問題

某車間有甲、乙兩臺機床，可用于加工三種工件。假定這兩臺車床的可用臺時數(shù)分別為800和900，三種工件的數(shù)量分別為400、600和500，且已知用三種不同車床加工單位數(shù)量不同工件所需的臺時數(shù)和加工費用如下表。問怎樣分配車床的加工任務(wù)，才能既滿足加工工件的要求，又使加工費用最低？第四頁，共四十五頁，2022年，8月28日設(shè)在甲車床上加工工件1、2、3的數(shù)量分別為x1、x2、x3，在乙車床上加工工件1、2、3的數(shù)量分別為x4、x5、x6?？山⒁韵戮€性規(guī)劃模型第五頁，共四十五頁，2022年，8月28日組成:目標函數(shù)Maxf或Minf

約束條件s.t.(subjectto)滿足于決策變量用符號來表示可控制的因素一般形式第六頁，共四十五頁，2022年，8月28日求解方法：單純形法和內(nèi)點法用MATLAB優(yōu)化工具箱解線性規(guī)劃形式1:minz=cxs.t.Ax<=b

命令：x=linprog(c，A，b)形式2

minz=cx

s.t.Ax<=bAeqx=beq

命令：x=linprog(c，A，b，Aeq,beq)注意:若沒有不等式：Ax<=b存在，則令A(yù)=[],b=[]第七頁，共四十五頁，2022年，8月28日形式3

minz=cx

s.t.Ax<=bAeqx=beqVLB≤X≤VUB命令:[1]x=linprog（c，A，b，Aeq,beq,VLB，VUB）[2]x=linprog（c，A，b，Aeq,beq,VLB，VUB,X0）注意：[1]若沒有等式約束,則令A(yù)eq=[],beq=[].[2]其中X0表示初始點形式4

命令：[x,fval]=linprog(…)

返回最優(yōu)解ｘ及ｘ處的目標函數(shù)值fval第八頁，共四十五頁，2022年，8月28日解編寫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)第九頁，共四十五頁，2022年，8月28日二次規(guī)劃用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(...);標準型為第十頁，共四十五頁，2022年，8月28日第十一頁，共四十五頁，2022年，8月28日輸入命令：

H=2*[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)第十二頁，共四十五頁，2022年，8月28日非線性規(guī)劃基本概念如果目標函數(shù)或約束條件中至少有一個是非線性函數(shù)時的最優(yōu)化問題就叫做非線性規(guī)劃問題

一般形式其中x為n維列向量,f,gi,hj為實值函數(shù).第十三頁，共四十五頁，2022年，8月28日

把滿足問題中條件的解稱為可行解（或可行點），所有可行點的集合稱為可行集（或可行域）．記為D．即

D={x|gi(x)>=0,hj(x)=0,i=1,…,m,j=1,…,l}

對于優(yōu)化問題,有局部最有解和全局最有解之分.

非線性規(guī)劃的基本解法

1.罰函數(shù)法

2.近似規(guī)劃法標準型為Minf(x)s.t.Ax<=bAeqx=beqG(x)<=0Ceq(x)=0VLB=<x<=VUB

其中x為n維變元向量，G(x)與Ceq(x)均為非線性函數(shù)組成的向量，其它變量的含義與線性規(guī)劃、二次規(guī)劃中相同.第十四頁，共四十五頁，2022年，8月28日用Matlab求解上述問題，基本步驟分三步：1.首先建立M文件fun.m,定義目標函數(shù)f(x):functionf=fun(X);f=f(x);2.若約束條件中有非線性約束:G(x)或Ceq(x),則建立M文件nonlcon.m定義函數(shù)G(x)與Ceq(x):function[G,Ceq]=nonlcon(X)G=...Ceq=...第十五頁，共四十五頁，2022年，8月28日3.建立主程序.非線性規(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(...)注意[1]fmincon函數(shù)提供了大型優(yōu)化算法和中型優(yōu)化算法。默認時，若在fun函數(shù)中提供了梯度（options參數(shù)的GradObj設(shè)置為’on’），并且只有上下界存在或只有等式約束，fmincon函數(shù)將選擇大型算法。當(dāng)既有等式約束又有梯度約束時，使用中型算法。[2]fmincon函數(shù)的中型算法使用的是序列二次規(guī)劃法。在每一步迭代中求解二次規(guī)劃子問題，并用BFGS法更新拉格朗日Hessian矩陣。[3]fmincon函數(shù)可能會給出局部最優(yōu)解，這與初值x0的選取有關(guān)第十六頁，共四十五頁，2022年，8月28日先建立M文件fun2.m,

functionf=fun2(x);f=exp(x(1))*(4*x(1)^2+2*x(2)^2+4*x(1)*x(2)+2*x(2)+1);再建立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];ceq=[]；第十七頁，共四十五頁，2022年，8月28日非線性規(guī)劃的網(wǎng)格搜索二元函數(shù)舉例Minf(x1,x2)s.t.a<x1<bc<x2<d其中f(x1,x2)為連續(xù)函數(shù)。第十八頁，共四十五頁，2022年，8月28日求解思路先建立目標函數(shù)的m函數(shù)文件，名字可記為fun。N1=1000；N2=1000;h1=（b-a）/N1;h2=（d-c）/N2;f0=inf;xo=[ac];fori=0:N1forj=0:N2f=fun(a+i*h1,b+j*h2);iff<f0,xo=[a+i*h1,b+j*h2];f0=f;endendEnd此種方法不易用于較高維函數(shù)優(yōu)化問題。第十九頁，共四十五頁，2022年，8月28日多目標優(yōu)化X為連續(xù)型決策空間Pareto解，非劣解第二十頁，共四十五頁，2022年，8月28日第二十一頁，共四十五頁，2022年，8月28日第二十二頁，共四十五頁，2022年，8月28日第二十三頁，共四十五頁，2022年，8月28日(4).轉(zhuǎn)化為單目標

minf1(x)

s.t.fi(x)<ki第二十四頁，共四十五頁，2022年，8月28日極大極小與極小極大問題第二十五頁，共四十五頁，2022年，8月28日第二十六頁，共四十五頁，2022年，8月28日應(yīng)用實例1:投資的收益和風(fēng)險問題提出：市場上有n種資產(chǎn)Si(i=1,2,…,n)可以選擇,現(xiàn)用數(shù)額為M的相當(dāng)大的資金作一個時期的投資。這n種資產(chǎn)在這一時期內(nèi)購買Si的平均收益率為ri，風(fēng)險損失率為qi，投資越分散，總的風(fēng)險越小，總體風(fēng)險可用投資的Si中最大的一個風(fēng)險來度量。購買Si時要付交易費(費率pi)，當(dāng)購買額不超過給定值ui時，交易費按購買ui計算。另外，假定同期銀行存款利率是r0，既無交易費又無風(fēng)險。（r0=5%）

Siri（%）qi（%）pi（%）ui（元）S1282.51103S2211.52198S3235.54.552S4252.66.540第二十七頁，共四十五頁，2022年，8月28日試給該公司設(shè)計一種投資組合方案，即用給定達到資金M，有選擇地購買若干種資產(chǎn)或存銀行生息，使凈收益盡可能大，使總體風(fēng)險盡可能小。第二十八頁，共四十五頁，2022年，8月28日模型的建立與分析第二十九頁，共四十五頁，2022年，8月28日第三十頁，共四十五頁，2022年，8月28日第三十一頁，共四十五頁，2022年，8月28日模型1的求解

由于a是任意給定的風(fēng)險度，到底怎樣給定沒有一個準則，不同的投資者有不同的風(fēng)險度.我們從a=0開始，以步長△a=0.001進行循環(huán)搜索，編制程序如下：第三十二頁，共四十五頁，2022年，8月28日a=0;c=[-0.05-0.27-0.19-0.185-0.185];Aeq=[11.011.021.0451.065];beq=[1];A=[00.025000;000.01500;0000.0550;00000.026];while(1.1-a)>1b=[a;a;a;a];vlb=[0,0,0,0,0];vub=[];[x,val]=linprog(c,A,b,Aeq,beq,vlb,vub);ax=x'Q=-valplot(a,Q,'.')，axis([00.100.5])，holdona=a+0.001;endxlabel('a'),ylabel('Q')第三十三頁，共四十五頁，2022年，8月28日計算結(jié)果：第三十四頁，共四十五頁，2022年，8月28日結(jié)果分析4.在a=0.006附近有一個轉(zhuǎn)折點，在這一點左邊，風(fēng)險增加很少時，利潤增長很快.在這一點右邊，風(fēng)險增加很大時，利潤增長很緩慢，所以對于風(fēng)險和收益沒有特殊偏好的投資者來說，應(yīng)該選擇曲線的拐點作為最優(yōu)投資組合，大約是a*=0.6%，Q*=20%，所對應(yīng)投資方案為:

風(fēng)險度收益x0

x1

x2x3

x40.00600.201900.24000.40000.10910.22123.曲線上的任一點都表示該風(fēng)險水平的最大可能收益和該收益要求的最小風(fēng)險.對于不同風(fēng)險的承受能力，選擇該風(fēng)險水平下的最優(yōu)投資組合.2.當(dāng)投資越分散時，投資者承擔(dān)的風(fēng)險越小，這與題意一致.即:

冒險的投資者會出現(xiàn)集中投資的情況，保守的投資者則盡量分散投資.1.風(fēng)險大，收益也大.第三十五頁，共四十五頁，2022年，8月28日應(yīng)用實例2：供應(yīng)與選址

某公司有6個建筑工地要開工，每個工地的位置（用平面坐標系a，b表示，距離單位：km）及水泥日用量d(t)由下表給出．目前有兩個臨時料場位于A(5,1)，B(2,7)，日儲量各有20t．假設(shè)從料場到工地之間均有直線道路相連．（1）試制定每天的供應(yīng)計劃，即從A，B兩料場分別向各工地運送多少水泥，可使總的噸千米數(shù)最小．（2）為了進一步減少噸千米數(shù)，打算舍棄兩個臨時料場，改建兩個新的，日儲量各為20t，問應(yīng)建在何處，節(jié)省的噸千米數(shù)有多大？第三十六頁，共四十五頁，2022年，8月28日

建立模型記工地的位置為(ai，bi)，水泥日用量為di，i=1,…,6;料場位置為(xj，yj)，日儲量為ej，j=1,2；料場j向工地i的運送量為Xij．當(dāng)用臨時料場時決策變量為：Xij，當(dāng)不用臨時料場時決策變量為：Xij，xj，yj．第三十七頁，共四十五頁，2022年，8月28日使用臨時料場的情形:使用兩個臨時料場A(5,1)，B(2,7)．求從料場j向工地i的運送量Xij

.在各工地用量必須滿足和各料場運送量不超過日儲量的條件下，使總的噸千米數(shù)最小，這是線性規(guī)劃問題．線性規(guī)劃模型為：設(shè)X11=X1,X21=X2,,X31=X3,X41=X4,X51=X5,,X61=X6X12=X7,X22=X8,,X32=X9,X42=X10,X52=X11,,X62=X12

第三十八頁，共四十五頁，2022年，8月28日cleara=[1.258.750.55.7537.25];b=[1.250.754.7556.57.75];d=[3547611];x=[52];y=[17];e=[2020];fori=1:6forj=1:2aa(i,j)=sqrt((x(j)-a(i))^2+(y(j)-b(i))^2);endendCC=[aa(:,1);aa(:,2)]';A=[111111000000000000111111];B=[20;20];Aeq=[100000100000010000010000001000001000000100000100000010000010000001000001];beq=[d(1);d(2);d(3);d(4);d(5);d(6)];VLB=[000000000000];VUB=[];x0=[123010010101];[xx,fval]=linprog(CC,A,B,Aeq,beq,VLB,VUB,x0)第三十九頁，共四十五頁，2022年，8月28日計算結(jié)果為：x=[3．00005．00000．00007．00000．00001．00000．00000．00004．00000．00006．000010．0000]’fval=136．2275第四十頁，共四十五頁，2022年，8月28日改建兩個新料場的情形:改建兩個新料場，要同時確定料場的位置(xj,yj)和運送量Xij，在同樣條件下使總噸千米數(shù)最小．這是非線性規(guī)劃問題．非線性規(guī)劃模型為：第四十一頁，共四十五頁，2022年，8月28日設(shè)X11=X1,X21=X2,X31=X3,X41=X4,X51=X5,,X61=X6

X12=X7,X22=X8,X32=X9,X42=X10,X52=X11,X62=X12

x1=X13,y1=X14,x2=X15,y2=X16

先編寫M文件liaoch．m定義目標函數(shù)．取初值為線性規(guī)劃的計算結(jié)果及臨時料場的坐標:

x0=[35070100406105127]';再編寫主程序第四十二頁，共四十五頁，2022年，8月28日functionf=liaoch(x)a=[1.258.750.55.7537.25];b=[1.250.754.7556.57.75];d=[3547611];e=[2020];f1=0;fori=1:6s(i)=sqrt((x(13)-a(i))^2+(x(14)-b(i))^2);f1=s(i)*x(i)+f1;endf2=0;fori=7:12s(i)=sqrt((x(15)-a(i-6))^2+(x(16)-b(i-6))^2);f2=s(i)*x(i)+f2;endf=f1+f2;第四十三頁，共四十五頁，2022年，8月28日clear%x0=[35070100406105127]';%x0=[3.00005.00000.07077.000000.929