数学建模通识第十讲优化

数学建模通识第十讲优化第一页，共四十五页，2022年，8月28日优化模型四要素决策变量目标函数（尽量简单、光滑）约束条件（建模的关键）求解方法（MATLAB,LINDO/LINGO）第二页，共四十五页，2022年，8月28日优化模型分类线性规划模型（目标函数和约束条件都是线性函数的优化问题）非线性规划模型（目标函数或者约束条件是非线性的函数）整数规划（决策变量是整数值得规划问题）多目标规划（具有多个目标函数的规划问题）目标规划（具有不同优先级的目标和偏差的规划问题）动态规划（求解多阶段决策问题的最优化方法）第三页，共四十五页，2022年，8月28日线性规划任务分配问题

某车间有甲、乙两台机床，可用于加工三种工件。假定这两台车床的可用台时数分别为800和900，三种工件的数量分别为400、600和500，且已知用三种不同车床加工单位数量不同工件所需的台时数和加工费用如下表。问怎样分配车床的加工任务，才能既满足加工工件的要求，又使加工费用最低？第四页，共四十五页，2022年，8月28日设在甲车床上加工工件1、2、3的数量分别为x1、x2、x3，在乙车床上加工工件1、2、3的数量分别为x4、x5、x6。可建立以下线性规划模型第五页，共四十五页，2022年，8月28日组成:目标函数Maxf或Minf

约束条件s.t.(subjectto)满足于决策变量用符号来表示可控制的因素一般形式第六页，共四十五页，2022年，8月28日求解方法：单纯形法和内点法用MATLAB优化工具箱解线性规划形式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(…)

返回最优解ｘ及ｘ处的目标函数值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日二次规划用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日非线性规划基本概念如果目标函数或约束条件中至少有一个是非线性函数时的最优化问题就叫做非线性规划问题

一般形式其中x为n维列向量,f,gi,hj为实值函数.第十三页，共四十五页，2022年，8月28日

把满足问题中条件的解称为可行解（或可行点），所有可行点的集合称为可行集（或可行域）．记为D．即

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

对于优化问题,有局部最有解和全局最有解之分.

非线性规划的基本解法

1.罚函数法

2.近似规划法标准型为Minf(x)s.t.Ax<=bAeqx=beqG(x)<=0Ceq(x)=0VLB=<x<=VUB

其中x为n维变元向量，G(x)与Ceq(x)均为非线性函数组成的向量，其它变量的含义与线性规划、二次规划中相同.第十四页，共四十五页，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.建立主程序.非线性规划求解的函数是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函数提供了大型优化算法和中型优化算法。默认时，若在fun函数中提供了梯度（options参数的GradObj设置为’on’），并且只有上下界存在或只有等式约束，fmincon函数将选择大型算法。当既有等式约束又有梯度约束时，使用中型算法。[2]fmincon函数的中型算法使用的是序列二次规划法。在每一步迭代中求解二次规划子问题，并用BFGS法更新拉格朗日Hessian矩阵。[3]fmincon函数可能会给出局部最优解，这与初值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日非线性规划的网格搜索二元函数举例Minf(x1,x2)s.t.a<x1<bc<x2<d其中f(x1,x2)为连续函数。第十八页，共四十五页，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此种方法不易用于较高维函数优化问题。第十九页，共四十五页，2022年，8月28日多目标优化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进行循环搜索，编制程序如下：第三十二页，共四十五页，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附近有一个转折点，在这一点左边，风险增加很少时，利润增长很快.在这一点右边，风险增加很大时，利润增长很缓慢，所以对于风险和收益没有特殊偏好的投资者来说，应该选择曲线的拐点作为最优投资组合，大约是a*=0.6%，Q*=20%，所对应投资方案为:

风险度收益x0

x1

x2x3

x40.00600.201900.24000.40000.10910.22123.曲线上的任一点都表示该风险水平的最大可能收益和该收益要求的最小风险.对于不同风险的承受能力，选择该风险水平下的最优投资组合.2.当投资越分散时，投资者承担的风险越小，这与题意一致.即:

冒险的投资者会出现集中投资的情况，保守的投资者则尽量分散投资.1.风险大，收益也大.第三十五页，共四十五页，2022年，8月28日应用实例2：供应与选址

某公司有6个建筑工地要开工，每个工地的位置（用平面坐标系a，b表示，距离单位：km）及水泥日用量d(t)由下表给出．目前有两个临时料场位于A(5,1)，B(2,7)，日储量各有20t．假设从料场到工地之间均有直线道路相连．（1）试制定每天的供应计划，即从A，B两料场分别向各工地运送多少水泥，可使总的吨千米数最小．（2）为了进一步减少吨千米数，打算舍弃两个临时料场，改建两个新的，日储量各为20t，问应建在何处，节省的吨千米数有多大？第三十六页，共四十五页，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

.在各工地用量必须满足和各料场运送量不超过日储量的条件下，使总的吨千米数最小，这是线性规划问题．线性规划模型为：设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，在同样条件下使总吨千米数最小．这是非线性规划问题．非线性规划模型为：第四十一页，共四十五页，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定义目标函数．取初值为线性规划的计算结果及临时料场的坐标:

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