大学数学建模电子教案.ppt
《大学数学建模电子教案.ppt》由会员分享,可在线阅读,更多相关《大学数学建模电子教案.ppt(185页珍藏版)》请在三一文库上搜索。
1、数学建模电子教案,重庆邮电大学 数理学院 沈世云,第二篇 规划论模型,第二章 线性规划 第三章 整数规划 第四章 无约束非线性规划 第五章 约束非线性规划 第六章 规划模型的MATLAB解法 第七章 动态规划,第五章 约束非线性规划,5.1 最优性条件,5.2 非线性规划案例,本章主要考察带有约束条件的非线性规划问题。,称问题(MP)为数学规划(Mathematical Programming)。,(MP),称 为不等式约束, 为等式约束。,称集合 为问题(MP)的可行域。,若问题(MP)中的 是凸函数, 是线性函数,则称问题(MP)为凸规划。,5.1.1 不等式约束问题的最优性条件,5.1
2、最优性条件,定义5.1.1 设 ,若对某个 有 ,称 为点 处的起作用约束,也称为有效约束,积极约束(Active Constraint)。,记 为起作用约束下标集,简记为 。,5.1 最优性条件,若 ,则称 为点 处的不起作用约束。其几何意义如图所示。在 处, 是起作用约束, 是不起作用约束。在 处 均是不起作用约束。,5.1 最优性条件,例5.1 用图解法求下列问题的最优解,指出最优解处的起作用约束及目标函数的最优值。,(1),(2),解: (1)原问题可以化为:,5.1 最优性条件,最优解 ,最优值 。 在 处是起作用约束。,如图所示。,5.1 最优性条件,(2)原问题可化为,最优解 ,
3、最优值 。 在 处是起作用约束。,5.1 最优性条件,定理5.1.1(Fritz-John必要条件) 设 在 处可微, 在 处连续,若 是不等式约束问题(1)的最优解,则存在不全为零的数 使,5.1 最优性条件,解:在 处 是起作用约束,即,且,取 ,便有Fritz-John条件成立。,5.1 最优性条件,在Fritz-John必要条件中,若 则Fritz-John条件中就没有目标函数的信息了,这样的Fritz-John条件就没有多大的价值,为了保证 ,需对约束条件加以适当的限制条件,称之为约束规格(Constraint qualification)。在非线性规划的研究中,有着各种不同的约束规
4、格,如果增加起作用约束的梯度向量线性无关的约束规格,就得出著名Kuhn-Tucker条件。它是Kuhn和Tucker在1951年提出的,简称为K-T条件。,5.1 最优性条件,定理5.1.2(Kuhn-Tucker必要条件) 设 在 处可微, 在处连续, 线性无关,若 是不等式约束问题(5.1.1)的局部最优解,则存在 使,5.1 最优性条件,解:经验证 是可行点,由于在 处只有 是起作用约束,此时有,5.1 最优性条件,在 处, 均是起作用约束,且 是线性无关,由,有方程组,解之有,故 是K-T点。,5.1 最优性条件,证明:由定理的条件,显然可行域是凸集,由是凸函数,再由定理1.3.2,有
5、,又由K-T条件,存在 ,使,5.1 最优性条件,由 是凸函数有,即,即 是(5.1.1)的全局最优解。,5.1 最优性条件,5.1.2 等式约束问题的最优性条件,(5.1.1)的结论可平移到(5.1.3)中来,并得到(5.1.2)的相应结论。(5.1.2)也可采用Lagrange乘数法来求解。,5.1 最优性条件,定义5.1.3 对等式约束问题(5.1.2),设存在数 称,为等式约束问题(5.1.2)的Lagrange函数。其中 称为Lagrange乘子, ;记,5.1 最优性条件,称 为的Jacobi矩阵。,5.1 最优性条件,定义5.1.4 若 满足: ,则 称为等式约束问题(5.3)的
6、Lagrange点。,定理5.1.4(必要条件) 设等式约束问题(5.1.2)中 在 处的某个邻域内可微, 的Jacobi矩阵在 处的秩为 ,若 是(5.1.2)的局部最优解,则存在 使,5.1 最优性条件,定理5.1.5(充分条件) 设等式约束问题(5.1.2)中 二阶连续可微,若存在 使得,其中 ; 则 是等式约束问题(5.1.2)的严格局部最优解。,5.1 最优性条件,例5.1.4 求解,解:原问题可化为:,有,5.1 最优性条件,令 有,设向量 满足 , 则有,而此时,由定理4.5知是问题的严格局部最优解。,4.1 最优性条件,5.1.3 混合约束问题的最优性条件,记,5.1 最优性条
7、件,5.1 最优性条件,在定理4.1.6中,若还有条件, 在点 处可微,则Fritz-John条件可改写为,4.1 最优性条件,定理5.1.7 (Kuhn-Tucker必要条件) 设混合约束问题中的 在点 处可微, 在点 处连续, 在点 处连续可微,且 线性无关,若 是 的局部最优解,则存在 使,5.1 最优性条件,在定理5.1.7中若还有条件 在点 处可微,则K-T条件可改写为:,5.1 最优性条件,定理5.1.8(充分条件) 设混合约束问题(5.1.4)中的 在点 处可微,若 满足(5.1.4)的K-T条件,并且 是凸函数, 是线性函数,则 是(5.1.4)的全局最优解。,5.1 最优性条
8、件,例4.5 求解,解:,4.1 最优性条件,由K-T条件有:,5.1 最优性条件,解此方程组有解,由于 是凸函数, 是线性函数,而且 是K-T点,故由定理4.1.8知 是问题的全局最优解。,5.1 最优性条件,5.2 非线性规划建模实例,飞行管理问题,1、问题提出,在约10000m高空的某边长为160km的正方形区域内,经常有若干架飞机作水平飞行。区域内每架飞机的位置和速度均由计算机记录其数据,以便进行飞行管理。当一架欲进入该区域的飞机到达区域边缘时,记录其数据后,要立即计算并判断是否会与区域内的飞机发生碰撞。如果会碰撞,则应计算如何调整各架(包括新进入的)飞机飞行的方向角,以避免碰撞。现假
9、定条件如下:(1)不碰撞的标准为任意两架飞机的距离大于8km;(2)飞机飞行方向角调整的幅度不应超过 ;(3)所有飞机飞行速度均为800km每小时;(4)进入该区域的飞机在到达区域边缘时,与区域内飞机的距离应在60km以上;(5)最多需考虑6架飞机;(6)不必考虑飞机立刻此区域后的状况。,5、计算结果,第六章 规划模型的 MATLAB求解,6.1 用MATLAB优化工具箱解线性规划,命令:x=linprog(c,A,b),2、模型:min z=cX,命令:x=linprog(c,A,b,Aeq,beq),注意:若没有不等式: 存在,则令A= ,b= .,命令:1 x=linprog(c,A,b
10、,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.,解 编写M文件xxgh1.m如下: c=-0.4 -0.28 -0.32 -0.72 -0.64 -0.6; A=0.01 0.01 0.01 0.03 0.03 0.03;0.02 0 0 0.05 0 0;0 0.02 0 0 0.05 0;0 0 0.03 0 0 0.08; b=850;700;100;9
11、00; Aeq=; beq=; vlb=0;0;0;0;0;0; vub=; x,fval=linprog(c,A,b,Aeq,beq,vlb,vub),To Matlab (xxgh1),解: 编写M文件xxgh2.m如下: c=6 3 4; A=0 1 0; b=50; Aeq=1 1 1; beq=120; vlb=30,0,20; vub=; x,fval=linprog(c,A,b,Aeq,beq,vlb,vub),To Matlab (xxgh2),例3,编写M文件xxgh3.m如下: f = 13 9 10 11 12 8; A = 0.4 1.1 1 0 0 0 0 0 0 0
12、.5 1.2 1.3; b = 800; 900; Aeq=1 0 0 1 0 0 0 1 0 0 1 0 0 0 1 0 0 1; beq=400 600 500; vlb = zeros(6,1); vub=; x,fval = linprog(f,A,b,Aeq,beq,vlb,vub),To Matlab (xxgh3),结果: x = 0.0000 600.0000 0.0000 400.0000 0.0000 500.0000 fval =1.3800e+004 即在甲机床上加工600个工件2,在乙机床上加工400个工件1、500个工件3,可在满足条件的情况下使总加工费最小为138
13、00。,6.2 用Matlab解无约束优化问题,其中(3)、(4)、(5)的等式右边可选用(1)或(2)的等式右边。 函数fminbnd的算法基于黄金分割法和二次插值法,它要求目标函数必须是连续函数,并可能只给出局部最优解。,常用格式如下: (1)x= fminbnd (fun,x1,x2) (2)x= fminbnd (fun,x1,x2 ,options) (3)x,fval= fminbnd(.) (4)x,fval,exitflag= fminbnd(.) (5)x,fval,exitflag,output= fminbnd(.),To Matlab(wliti1),主程序为wliti
14、1.m: f=2*exp(-x).*sin(x); fplot(f,0,8); %作图语句 xmin,ymin=fminbnd (f, 0,8) f1=-2*exp(-x).*sin(x); xmax,ymax=fminbnd (f1, 0,8),例2 对边长为3米的正方形铁板,在四个角剪去相等的正方形以制成方形无盖水槽,问如何剪法使水槽的容积最大?,解,先编写M文件fun0.m如下: function f=fun0(x) f=-(3-2*x).2*x;,主程序为wliti2.m: x,fval=fminbnd(fun0,0,1.5); xmax=x fmax=-fval,运算结果为: xma
15、x = 0.5000,fmax =2.0000.即剪掉的正方形的边长为0.5米时水槽的容积最大,最大容积为2立方米.,To Matlab(wliti2),命令格式为: (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
16、(5)x,fval,exitflag,output= fminunc(.); 或x,fval,exitflag,output= fminsearch(.),2、多元函数无约束优化问题,标准型为:min F(X),3 fminunc为中型优化算法的步长一维搜索提供了两种算法, 由options中参数LineSearchType控制: LineSearchType=quadcubic(缺省值),混合的二次和三 次多项式插值; LineSearchType=cubicpoly,三次多项式插,使用fminunc和 fminsearch可能会得到局部最优解.,说明:,fminsearch是用单纯形法寻优
17、. fminunc的算法见以下几点说明:,1 fminunc为无约束优化提供了大型优化和中型优化算法。由options中的参数LargeScale控制: LargeScale=on(默认值),使用大型算法 LargeScale=off(默认值),使用中型算法,2 fminunc为中型优化算法的搜索方向提供了4种算法,由 options中的参数HessUpdate控制: HessUpdate=bfgs(默认值),拟牛顿法的BFGS公式; HessUpdate=dfp,拟牛顿法的DFP公式; HessUpdate=steepdesc,最速下降法,例3 min f(x)=(4x12+2x22+4x1
18、x2+2x2+1)*exp(x1),To Matlab(wliti3),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、输入M文件wliti3.m如下: x0=-1, 1; x=fminunc(fun1,x0) y=fun1(x),3、运行结果: x= 0.5000 -1.0000 y = 1.3028e-10,To Matlab (wliti31),To Matlab (wliti32),1. 为获得直观认识,先画出Rosenbrock 函数的三维图形,
19、 输入以下命令: x,y=meshgrid(-2:0.1:2,-1:0.1:3); z=100*(y-x.2).2+(1-x).2; mesh(x,y,z),2. 画出Rosenbrock 函数的等高线图,输入命令: contour(x,y,z,20) hold on plot(-1.2,2, o ); text(-1.2,2,start point) plot(1,1,o) text(1,1,solution),3.用fminsearch函数求解,To Matlab(wliti41),输入命令: f=100*(x(2)-x(1)2)2+(1-x(1)2; x,fval,exitflag,ou
20、tput=fminsearch(f, -1.2 2),运行结果: x =1.0000 1.0000 fval =1.9151e-010 exitflag = 1 output = iterations: 108 funcCount: 202 algorithm: Nelder-Mead simplex direct search,用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
21、,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(.);,1、二次规划,例1 min f(x1,x2)=-2x1-6x2+x12-2x1x2+2x22 s.t. x1+x22 -x1+2x22 x10, x20,MATLAB(youh1),1、写成标准形式:,2、 输入命令: H=1 -1; -1 2; c=-2
22、 ;-6;A=1 1; -1 2;b=2;2; Aeq=;beq=; VLB=0;0;VUB=; x,z=quadprog(H,c,A,b,Aeq,beq,VLB,VUB),3、运算结果为: x =0.6667 1.3333 z = -8.2222,s.t.,1. 首先建立M文件fun.m,定义目标函数F(X): function f=fun(X); f=F(X);,2、一般非线性规划,其中X为n维变元向量,G(X)与Ceq(X)均为非线性函数组成的向量,其它变量的含义与线性规划、二次规划中相同.用Matlab求解上述问题,基本步骤分三步:,3. 建立主程序.非线性规划求解的函数是fminco
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 大学 数学 建模 电子 教案
链接地址:https://www.31doc.com/p-3830004.html