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

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

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

約束條件s.t.(subjectto)滿足于決策變量用符號來表示可控制的因素一般形式第六頁，共四十五頁，2022年，8月28日求解方法：單純形法和內點法用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=[],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]若沒有等式約束,則令Aeq=[],beq=[].[2]其中X0表示初始點形式4

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

返回最優(yōu)解ｘ及ｘ處的目標函數值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ī)劃基本概念如果目標函數或約束條件中至少有一個是非線性函數時的最優(yōu)化問題就叫做非線性規(guī)劃問題

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

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

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

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

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

1.罰函數法

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

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

minf1(x)

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

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

由于a是任意給定的風險度，到底怎樣給定沒有一個準則，不同的投資者有不同的風險度.我們從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日計算結果：第三十四頁，共四十五頁，2022年，8月28日結果分析4.在a=0.006附近有一個轉折點，在這一點左邊，風險增加很少時，利潤增長很快.在這一點右邊，風險增加很大時，利潤增長很緩慢，所以對于風險和收益沒有特殊偏好的投資者來說，應該選擇曲線的拐點作為最優(yōu)投資組合，大約是a*=0.6%，Q*=20%，所對應投資方案為:

風險度收益x0

x1

x2x3

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

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

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

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

.在各工地用量必須滿足和各料場運送量不超過日儲量的條件下，使總的噸千米數最小，這是線性規(guī)劃問題．線性規(guī)劃模型為：設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日計算結果為：x=[3．00005．00000．00007．00000．00001．00000．00000．00004．00000．00006．000010．0000]’fval=136．2275第四十頁，共四十五頁，2022年，8月28日改建兩個新料場的情形:改建兩個新料場，要同時確定料場的位置(xj,yj)和運送量Xij，在同樣條件下使總噸千米數最?。@是非線性規(guī)劃問題．非線性規(guī)劃模型為：第四十一頁，共四十五頁，2022年，8月28日設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定義目標函數．取初值為線性規(guī)劃的計算結果及臨時料場的坐標:

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