数学建模优化问题.pptx

《数学建模优化问题.pptx》由会员分享，可在线阅读，更多相关《数学建模优化问题.pptx（45页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。

1、整数规划(IP)决策变量(全部或部分)为整数Integer programming 整数线性规划(ILP)，整数非线性规划(INLP)纯整数规划(PIP),混合整数规划(MIP)Pure(mixed)Integer programming 一般整数规划，0-1（整数）规划Zero-one programming离散优化discrete optimization或组合优化combinatorial optimization一般优化问题概述第1页/共45页 无约束最优化问题无约束最优化问题求解无约束最优化问题的的基本思想*无约束最优化问题的基本算法返回第2页/共45页标准形式：求解无约束最优化问题

2、的基本思想求解的基本思想 (以二元函数为例)531连续可微第3页/共45页第4页/共45页多局部极小 唯一极小(全局极小)第5页/共45页搜索过程最优点 (1 1)初始点 (-1 1)-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.90 0.0030.990.991E-40.9990.9981E-50.9997 0.9998 1E-8返回第6页/共45页无约束优化问题的基本算法 最速下降法是一种最基本的算法，它在最优化方法中占有重要地位.最速

3、下降法的优点是工作量小，存储变量较少,初始点要求不高；缺点是收敛慢，最速下降法适用于寻优过程的前期迭代或作为间插步骤，当接近极值点时，宜选用别种收敛快的算法.1 1最速下降法（共轭梯度法）算法步骤：第7页/共45页2 2牛顿法算法步骤：如果f是对称正定矩阵A的二次函数，则用牛顿法经过一次迭代就可达到最优点,如不是二次函数，则牛顿法不能一步达到极值点，但由于这种函数在极值点附近和二次函数很近似,因此牛顿法的收敛速度还是很快的.牛顿法的收敛速度虽然较快，但要求Hessian矩阵要可逆，要计算二阶导数和逆矩阵，就加大了计算机计算量和存储量.第8页/共45页MatlabMatlab优化工具箱简介1.M

4、ATLAB1.MATLAB求解优化问题的主要函数第9页/共45页2.2.优化函数的输入变量 使用优化函数或优化工具箱中其它优化函数时,输入变量见下表:第10页/共45页3.3.优化函数的输出变量下表:第11页/共45页用MatlabMatlab解无约束优化问题 其中（3）、（4）、（5）的等式右边可选用（1）或（2）的等式右边。函数fminbnd的算法基于黄金分割法和二次插值法，它要求目标函数必须是连续函数，并可能只给出局部最优解。常用格式如下：（1）x=fminbnd(x=fminbnd(fun,xfun,x1 1,x,x2 2)（2）x=fminbnd(x=fminbnd(fun,xfun

5、,x1 1,x,x2 2 ，options)options)（3）xx，fval=fminbndfval=fminbnd（.）（4）xx，fvalfval，exitflag=fminbndexitflag=fminbnd（.）（5）xx，fvalfval，exitflagexitflag，output=fminbndoutput=fminbnd（.）第12页/共45页To Matlab(wliti1)主程序为wliti1.m:wliti1.m:f=2*exp(-x).*sin(x);fplot(f,0,8);%作图语句 xmin,ymin=fminbnd(f,0,8)f1=-2*exp(-x)

6、.*sin(x);xmax,ymax=fminbnd(f1,0,8)第13页/共45页例2 2 对边长为3米的正方形铁板，在四个角剪去相等的正方形以制成方形无盖水槽，问如何剪法使水槽的容积最大？解先编写M M文件fun0.mfun0.m如下:function f=fun0(x)f=-(3-2*x).2*x;主程序为wliti2.m:wliti2.m:x,fval=fminbnd(fun0,0,1.5);xmax=x fmax=-fval运算结果为:xmax=0.5000,fmax=2.0000.即剪掉的正方形的边长为0.5米时水槽的容积最大,最大容积为2立方米.To Matlab(wliti2

7、)第14页/共45页 命令格式为:（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、多元函数无约束优

8、化问题标准型为：min F(X)第15页/共45页3 fminunc为中型优化算法的步长一维搜索提供了两种算法，由options中参数LineSearchType控制：LineSearchType=quadcubic(缺省值)，混合的二次和三 次多项式插值；LineSearchType=cubicpoly，三次多项式插使用fminuncfminunc和 fminsearchfminsearch可能会得到局部最优解.说明:fminsearchfminsearch是用单纯形法寻优.fminunc.fminunc的算法见以下几点说明：1 fminunc为无约束优化提供了大型优化和中型优化算法。由op

9、tions中的参数LargeScale控制：LargeScale=on(默认值),使用大型算法LargeScale=off(默认值),使用中型算法2 fminunc为中型优化算法的搜索方向提供了4种算法，由 options中的参数HessUpdate控制：HessUpdate=bfgs（默认值），拟牛顿法的BFGS公式；HessUpdate=dfp，拟牛顿法的DFP公式；HessUpdate=steepdesc，最速下降法第16页/共45页例3 3 min f(x)=(4x12+2x22+4x1x2+2x2+1)*exp(x1)To Matlab(wliti3)1 1、编写M-M-文件 fun

10、1.m:fun1.m:function f=fun1(x)f=exp(x(1)*(4*x(1)2+2*x(2)2+4*x(1)*x(2)+2*x(2)+1);2 2、输入M M文件wliti3.mwliti3.m如下:x0=-1,1;x=fminunc(fun1,x0);y=fun1(x)3 3、运行结果:x=0.5000 -1.0000 y=1.3029e-10第17页/共45页To Matlab(wliti31)To Matlab(wliti32)第18页/共45页3.3.用fminsearchfminsearch函数求解To Matlab(wliti41)输入命令:f=100*(x(2)

11、-x(1)2)2+(1-x(1)2;x,fval,exitflag,output=fminsearch(f,-1.2 2)运行结果:x=1.0000 1.0000fval=1.9151e-010exitflag=1output=iterations:108 funcCount:202 algorithm:Nelder-Mead simplex direct search第19页/共45页4.4.用fminunc fminunc 函数To Matlab(wliti44)(1)建立M-文件fun2.m function f=fun2(x)f=100*(x(2)-x(1)2)2+(1-x(1)2(2

12、)主程序wliti44.m第20页/共45页 Rosenbrock Rosenbrock函数不同算法的计算结果可以看出，最速下降法的结果最差.因为最速下降法特别不适合于从一狭长通道到达最优解的情况.第21页/共45页例5 5 产销量的最佳安排 某厂生产一种产品有甲、乙两个牌号，讨论在产销平衡的情况下如何确定各自的产量，使总利润最大.所谓产销平衡指工厂的产量等于市场上的销量.第22页/共45页基本假设1 1价格与销量成线性关系2 2成本与产量成负指数关系第23页/共45页 模型建立 若根据大量的统计数据,求出系数b1=100,a11=1,a12=0.1,b2=280,a21=0.2,a22=2,

13、r1=30,1=0.015,c1=20,r2=100,2=0.02,c2=30,则问题转化为无约束优化问题：求甲,乙两个牌号的产量x1，x2，使总利润z最大.为简化模型,先忽略成本,并令a12=0,a21=0,问题转化为求:z1=(b1-a11x1)x1+(b2-a22x2)x2 的极值.显然其解为x1=b1/2a11=50,x2=b2/2a22=70,我们把它作为原问题的初始值.总利润为：z z(x x1 1,x,x2 2)=()=(p p1 1-q-q1 1)x x1 1+(+(p p2 2-q-q2 2)x x2 2第24页/共45页 模型求解 1.建立M-文件fun.m:functio

14、n f=fun(x)y1=(100-x(1)-0.1*x(2)-(30*exp(-0.015*x(1)+20)*x(1);y2=(280-0.2*x(1)-2*x(2)-(100*exp(-0.02*x(2)+30)*x(2);f=-y1-y2;2.输入命令:x0=50,70;x=fminunc(fun,x0),z=fun(x)3.计算结果:x=23.9025,62.4977,z=6.4135e+003 即甲的产量为23.9025,乙的产量为62.4977,最大利润为6413.5.To Matlab(wliti5)返回第25页/共45页练习第26页/共45页（1）线性逼近法基本思想：将目标函数

15、和约束函数近似为线性函数，转化为线性规划问题求解，重复这个过程。步骤：给定控制误差0，初始可行点xk,初始步长k0,在xk线性化得线性规划问题：非线性规划有约束问题第27页/共45页 求出此线性规划问题得最优解xk1，检验是否为原问题的的可行解，若是转，否则缩短步长转；判断精度。则取最优解x*=xk+1,停，否则令k=k+1转。非线性规划有约束问题第28页/共45页（2）罚函数法转化为无约束最优化问题：M为足够大的正数。称为罚因子。算法分析：设可行域为S，构造函数：非线性规划有约束问题第29页/共45页 求无约束问题得最优解为X(M),直观看出，只有当X(M)S才可能真正取得极小值，若就加大罚

16、因子M，使X(M)向S逼近，当M时，点列非线性规划有约束问题第30页/共45页计算步骤：（第k次迭代）非线性规划有约束问题第31页/共45页有约束问题matlab解法x,fval=fmincon(myfun,x0,A,b)x,fval=fmincon(myfun,x0,A,b,Aeq,beq)x,fval=fmincon(myfun,x0,A,b,Aeq,beq,lb,ub)x,fval=fmincon(myfun,x0,A,b,Aeq,beq,lb,ub,comfun)缺省的用代替myfun与confun是M-函数的地址具体如:第32页/共45页目标函数：Function f=myfun(x

17、)非线性约束：function c,ceq=confun(x)%Nonlinear inequality constraintsc=c1(x);c2(x);.;%Nonlinear equality constraintsceq=ceq1(x);ceq2(x);.;M-函数第33页/共45页1先建立先建立M文件文件 fun4.m,定义目标函数定义目标函数:function f=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=0 s.t.1.5+x1x2-x1-x2 0 -x1x2 10 0例32再建立M文件myco

18、n.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;第34页/共45页 例4 1先建立M-文件fun.m定义目标函数:function f=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;第35页/共45页应用实例：供应与选址 某公司有6个建筑工地要开工，每个工地的位置（用平面坐标系a，b表示，距离单位：千米）及水泥日用量d(吨)

19、由下表给出。目前有两个临时料场位于A(5,1)，B(2,7)，日储量各有20吨。假设从料场到工地之间均有直线道路相连。（1）试制定每天的供应计划，即从A，B两料场分别向各工地运送多少吨水泥，使总的吨千米数最小。（2）为了进一步减少吨千米数，打算舍弃两个临时料场，改建两个新的，日储量各为20吨，问应建在何处，节省的吨千米数有多大？第36页/共45页（一）、建立模型 记工地的位置为(ai，bi)，水泥日用量为di，i=1,6;料场位置为(xj，yj)，日储量为ej，j=1,2；从料场j向工地i的运送量为Xij。当用临时料场时决策变量为：Xij，当不用临时料场时决策变量为：Xij，xj，yj。第37

20、页/共45页（二）使用临时料场的情形 使用两个临时料场A(5,1)，B(2,7).求从料场j向工地i的运送量为Xij，在各工地用量必须满足和各料场运送量不超过日储量的条件下，使总的吨千米数最小，这是线性规划问题.线性规划模型为：设X11=X1,X21=X 2,X31=X 3,X41=X 4,X51=X 5,X61=X 6X12=X 7,X22=X 8,X32=X 9,X42=X 10,X52=X 11,X62=X 12 编写程序gying1.mMATLAB（gying1）第38页/共45页计算结果为：x=3.0000 5.0000 0.0000 7.0000 0.0000 1.0000 0.0

21、000 0.0000 4.0000 0.0000 6.0000 10.0000fval=136.2275第39页/共45页（三）改建两个新料场的情形 改建两个新料场，要同时确定料场的位置(xj,yj)和运送量Xij，在同样条件下使总吨千米数最小。这是非线性规划问题。非线性规划模型为：第40页/共45页设 X11=X1,X21=X 2,X31=X 3,X41=X 4,X51=X 5,X61=X 6 X12=X 7,X22=X 8,X32=X 9,X42=X 10,X52=X 11,X62=X 12 x1=X13,y1=X14,x2=X15,y2=X16 （1）先编写M文件liaoch.m定义目标

22、函数。MATLAB（liaoch）(2)取初值为线性规划的计算结果及临时料场的坐标:x0=3 5 0 7 0 1 0 0 4 0 6 10 5 1 2 7;编写主程序gying2.m.MATLAB（gying2）第41页/共45页(3)计算结果为：x=3.0000 5.0000 0.0707 7.0000 0 0.9293 0 0 3.9293 0 6.0000 10.0707 6.3875 4.3943 5.7511 7.1867fval=105.4626exitflag=1第42页/共45页(4)若修改主程序gying2.m,取初值为上面的计算结果:x0=3.0000 5.0000 0.0

23、707 7.0000 0 0.9293 0 0 3.9293 0 6.0000 10.0707 6.3875 4.3943 5.7511 7.1867得结果为:x=3.0000 5.0000 0.3094 7.0000 0.0108 0.6798 0 0 3.6906 0 5.9892 10.3202 5.5369 4.9194 5.8291 7.2852fval=103.4760exitflag=1总的吨千米数比上面结果略优.(5)若再取刚得出的结果为初值,却计算不出最优解.MATLAB（gying2）MATLAB（gying2）第43页/共45页(6)若取初值为:x0=3 5 4 7 1 0 0 0 0 0 5 11 5.6348 4.8687 7.2479 7.7499,则计算结果为:x=3.0000 5.0000 4.0000 7.0000 1.0000 0 0 0 0 0 5.0000 11.0000 5.6959 4.9285 7.2500 7.7500fval=89.8835exitflag=1总的吨千米数89.8835比上面结果更好.通过此例可看出fmincon函数在选取初值上的重要性.MATLAB（gying2）返回返回第44页/共45页感谢您的观看！第45页/共45页