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

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

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

約束條件s.t.(subjectto)滿(mǎn)足于決策變量用符號(hào)來(lái)表示可控制的因素一般形式第六頁(yè)，共四十五頁(yè)，2022年，8月28日求解方法：?jiǎn)渭冃畏ê蛢?nèi)點(diǎn)法用MATLAB優(yōu)化工具箱解線(xiàn)性規(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)注意:若沒(méi)有不等式：Ax<=b存在，則令A(yù)=[],b=[]第七頁(yè)，共四十五頁(yè)，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]若沒(méi)有等式約束,則令A(yù)eq=[],beq=[].[2]其中X0表示初始點(diǎn)形式4

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

返回最優(yōu)解ｘ及ｘ處的目標(biāo)函數(shù)值fval第八頁(yè)，共四十五頁(yè)，2022年，8月28日解編寫(xiě)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)第九頁(yè)，共四十五頁(yè)，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(...);標(biāo)準(zhǔn)型為第十頁(yè)，共四十五頁(yè)，2022年，8月28日第十一頁(yè)，共四十五頁(yè)，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)第十二頁(yè)，共四十五頁(yè)，2022年，8月28日非線(xiàn)性規(guī)劃基本概念如果目標(biāo)函數(shù)或約束條件中至少有一個(gè)是非線(xiàn)性函數(shù)時(shí)的最優(yōu)化問(wèn)題就叫做非線(xiàn)性規(guī)劃問(wèn)題

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

把滿(mǎn)足問(wèn)題中條件的解稱(chēng)為可行解（或可行點(diǎn)），所有可行點(diǎn)的集合稱(chēng)為可行集（或可行域）．記為D．即

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

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

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

1.罰函數(shù)法

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

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

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=[]；第十七頁(yè)，共四十五頁(yè)，2022年，8月28日非線(xiàn)性規(guī)劃的網(wǎng)格搜索二元函數(shù)舉例Minf(x1,x2)s.t.a<x1<bc<x2<d其中f(x1,x2)為連續(xù)函數(shù)。第十八頁(yè)，共四十五頁(yè)，2022年，8月28日求解思路先建立目標(biāo)函數(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)化問(wèn)題。第十九頁(yè)，共四十五頁(yè)，2022年，8月28日多目標(biāo)優(yōu)化X為連續(xù)型決策空間Pareto解，非劣解第二十頁(yè)，共四十五頁(yè)，2022年，8月28日第二十一頁(yè)，共四十五頁(yè)，2022年，8月28日第二十二頁(yè)，共四十五頁(yè)，2022年，8月28日第二十三頁(yè)，共四十五頁(yè)，2022年，8月28日(4).轉(zhuǎn)化為單目標(biāo)

minf1(x)

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

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

由于a是任意給定的風(fēng)險(xiǎn)度，到底怎樣給定沒(méi)有一個(gè)準(zhǔn)則，不同的投資者有不同的風(fēng)險(xiǎn)度.我們從a=0開(kāi)始，以步長(zhǎng)△a=0.001進(jìn)行循環(huán)搜索，編制程序如下：第三十二頁(yè)，共四十五頁(yè)，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')第三十三頁(yè)，共四十五頁(yè)，2022年，8月28日計(jì)算結(jié)果：第三十四頁(yè)，共四十五頁(yè)，2022年，8月28日結(jié)果分析4.在a=0.006附近有一個(gè)轉(zhuǎn)折點(diǎn)，在這一點(diǎn)左邊，風(fēng)險(xiǎn)增加很少時(shí)，利潤(rùn)增長(zhǎng)很快.在這一點(diǎn)右邊，風(fēng)險(xiǎn)增加很大時(shí)，利潤(rùn)增長(zhǎng)很緩慢，所以對(duì)于風(fēng)險(xiǎn)和收益沒(méi)有特殊偏好的投資者來(lái)說(shuō)，應(yīng)該選擇曲線(xiàn)的拐點(diǎn)作為最優(yōu)投資組合，大約是a*=0.6%，Q*=20%，所對(duì)應(yīng)投資方案為:

風(fēng)險(xiǎn)度收益x0

x1

x2x3

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

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

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

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

.在各工地用量必須滿(mǎn)足和各料場(chǎng)運(yùn)送量不超過(guò)日儲(chǔ)量的條件下，使總的噸千米數(shù)最小，這是線(xiàn)性規(guī)劃問(wèn)題．線(xiàn)性規(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

第三十八頁(yè)，共四十五頁(yè)，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)第三十九頁(yè)，共四十五頁(yè)，2022年，8月28日計(jì)算結(jié)果為：x=[3．00005．00000．00007．00000．00001．00000．00000．00004．00000．00006．000010．0000]’fval=136．2275第四十頁(yè)，共四十五頁(yè)，2022年，8月28日改建兩個(gè)新料場(chǎng)的情形:改建兩個(gè)新料場(chǎng)，要同時(shí)確定料場(chǎng)的位置(xj,yj)和運(yùn)送量Xij，在同樣條件下使總噸千米數(shù)最?。@是非線(xiàn)性規(guī)劃問(wèn)題．非線(xiàn)性規(guī)劃模型為：第四十一頁(yè)，共四十五頁(yè)，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

先編寫(xiě)M文件liaoch．m定義目標(biāo)函數(shù)．取初值為線(xiàn)性規(guī)劃的計(jì)算結(jié)果及臨時(shí)料場(chǎng)的坐標(biāo):

x0=[35070100406105127]';再編寫(xiě)主程序第四十二頁(yè)，共四十五頁(yè)，2022年，8月28日f(shuō)unctionf=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;第四十三頁(yè)，共四十五頁(yè)，2022年，8月28日clear%x0=[35070100406105127]';%x0=[3.00005.00000.07077.000000.929