PowerPoint 演示文稿

Size: px

Start display at page:

Download "PowerPoint 演示文稿"

豆卞
5 years ago
Views:

1 数学建模 Mathematcal Modelng

2 非线性规划模型非线性规划的实例与定义线性规划与非线性规划的区别 3 非线性规划的 matlab 解法 4 应用实例

3 非线性规划的实例与定义例某企业有 n 个项目可供选择投资, 并且至少要对其中一个项目投资已知该企业拥有总资金 A 元, 投资于第 (=,...,n) 个项目需花资金元试选择最佳投资方案 a 元, 并预计可收益 b 求解设投资决策变量为, 决定投资第个项目,, 决定不投资第个项目,..., n

4 求解投资总额 : a n 投资总收益 : n b 该公司至少要对一个项目投资总的投资金额不能超过总资金 A n a A (,..., n) 或 ( ),,..., n 最佳投资方案 : 投资额最小, 总收益最大数学模型 ma Q n n b a s t. n a A ( ),.,..., n

5 定义在一组等式或不等式约束下, 求一个函数的最大 ( 小 ) 值问题, 其中至少有一个非线性函数, 这类问题称为非线性规划问题一般形式 h s. t. g mn f ( ) ( ) ( ),, 目标函数,..., q,..., p 等式约束不等式约束 (NP) 其中 [... n ] T 决策变量 g (,..., p) 和 (,..., q) h 约束函数解题步骤 () 确定供选方案 () 提出追求目标 (3) 给出价值标准 (4) 寻求限制条件

6 线性规划与非线性规划的区别线性规划 : 如果最优解存在, 那么最优解只能在其可行域的边界上达到 ( 特别是可行域的顶点上达到 ) 非线性规划 : 如果最优解存在, 那么最优解可能在其可行域的任意一点达到

7 3 非线性规划的 matlab 解法数学模型 mn f ( ) A B Aeq Beq C( ) Ceq( ) f () A, B, Aeq, Beq C( ), Ceq( ) 标量函数相应维数的矩阵和向量非线性向量函数 matlab 命令 X=FMINCON(FUN,XO,A,B,Aeq,Beq,LB,UB,NONLCON,OPTIONS) X 初始值 A,B,Aeq,Beq 线性约束 LB,UB 上下界 NONLCON 用 M 文件定义的非线性向量函数 C(),Ceq() OPTIONS 定义优化参数

8 例,, ) ( mn s t f %fun.m functon f=fun(); f=sum(.^)+8; 定义目标函数求解非线性规划问题 matlab 解法

9 定义非线性约束条件 %fun.m functon [g,h]=fun(); g=[-()^+()-(3)^ ()+()^+(3)^3-]; h=[-()-()^+ ()+*(3)^-3]; 主程序文件 %eample.m clear;clc; optons=optmset('largescale','off'); [,y]=fmncon('fun',rand(3,),[],[],[],[],zeros(3,),[],'fun',optons) 运行结果 = y =.65 最小值

10 求解非线性规划的基本迭代格式记 (NP) 的可行域为 K 若 * f ( * ) f ( ), K K, 并且 * 则称是 (NP) 的整体最优解, f ( * ) 是 (NP) 的整体最优值若 K, 并且 f ( * ) f ( ), K, * * * 则称是 (NP) 的严格整体最优解, f ( * ) 是 (NP) 的严格整体最优值若 * * K, 并且存在的邻域 ( * ), 使 f ( * ) f ( ), N ( * N ) K * 则称是 (NP) 的局部最优解, f ( * ) 是 (NP) 的局部最优值若 * * K, 并且存在的邻域 ( * ), 使 f ( * ) f ( ), N ( * N ) K * 则称是 (NP) 的严格局部最优解, f ( * ) 是 (NP) 的严格局部最优值

11 基本思想从一个选定的初始点出发, 按照某一特定的迭代规则产生一个点列 { }, 使得当 { } 是有穷点列时, 其最后一个点是 (NP) 的最优解 ; 当 { } 是无穷点列时, 它有极限点, 并且其极限点是 (NP) 的最优解 n R 基本迭代格式 n n 设 R 是某迭代方法的第轮迭代点, R 是第 + 轮迭代点 t n 其中 t R, p R, p 方向 : p 第轮搜索方向 t 沿 p 方向的步长 p 基本迭代格式

12 n ( ) R, p, 若存在, 使 f ( tp) f ( ), t (, ) 称向量 p是 f在点处的下降方向 n () R, p, 若存在 t, 使 tp K, 称向量 p是在点处关于 K的可行方向 ( ) () 函数 f在点处关于 K的可行下降方向求解 (NP) 的一般步骤 () 选取初始点, 令 : () 构造搜索方向, 依照一定规划, 构造 f 在点处关于 K 的可行下降方向作为搜索方向 (3) 寻求搜索步长以为起点沿搜索方向 p 寻求适当的步长 t, 使目标函数值有某种意义的下降 (4) 求出下一个迭代点按迭代格式 () 求出 t 若已满足某种终止条件, 停止迭代 (5) 以代替, 回到 () 步 p

13 4 应用实例无约束极值问题解析法梯度法 Newton 法例 3 例 4 直接法 Powell 法例 5 二次规划例 6 约束极值问题罚函数法例 7

14 例 3( 梯度法 ) 求解无约束非线性规划问题, ) ( T mn f ( ) 5 T (,) 其中, 要求选取初始点解题步骤 () 选取初始数据选取初始点, 给定终止误差, 令 : f ( () 求梯度向量计算, 若, 停止迭代, 输出否则进行(3) (3) 构造负梯度方向取 p f (4) 进行一维搜索, 求, 使得 t t 令, 转 () p, : ) f ( ) ( f ( ) t p ) mn t f ( tp )

15 matlab 解法基本迭代格式负梯度方向 t p T p f ( ) (,5) 定义函数 f() 及其梯度列向量 %detaf.m functon [f,df]=detaf(); f=()^+5*()^; df=[*() 5*()]; 编写主程序文件 eample3.m %eample3.m clear;clc; =[;]; [f,g]=detaf(); whle norm(g)>. p=-g/norm(g); t=.;f=detaf(+t*p); whle f>f t=t/; f=detaf(+t*p); end =+t*p; [f,g]=detaf(); end,f 运行结果 =.e-6 * f =.389e-3

16 例 4(Newton 法 ) 用 Newton 法求解 mn f ( ) 初始点 T (,) 解题步骤 () 选取初始数据选取初始点, 给定终止误差, 令 : f ( ) () 求梯度向量计算 f ( ), 若, 停止迭代, 输出否则进行(3) (3) 构造 Newton 方向计算 [ f ( )], 取 p (4) 求下一迭代点令, 转 () p, : [ f ( )] f ( )

17 matlab 解法 3 3 f ) [4 ] 编写 M 文件 nwfun.m ( 4 4 f 3 %nwfun.m functon [f,df,df]=nwfun(); f=()^4+5*()^4+()^*()^; df=[4*()^3+*()*()^;*()^3+*()^*()]; df=[*()^+*()^,4*()*() 4*()*(),3*()^+*()^]; 编写主程序文件 eample4_.m %eample4_.m clear;clc; =[;]; [f,g,g]=nwfun(); whle norm(g)>. p=-nv(g)*g; =+p; [f,g,g]=nwfun(); end, f T

18 运行结果 = f =.36e-9 改进 : 采用变步长法提高计算精度 %eample4_.m clear;clc; =[;]; [f,g,g]=nwfun(); whle norm(g)>. p=-nv(g)*g;p=p/norm(p); t=.;f=nwfun(+t*p); whle f>f t=t/;f=nwfun(+t*p); end =+t*p; [f,g,g]=nwfun(); end,f 运行结果 = f =.548e-

19 例 5( 直接法 ) 思想基本搜索, 加速搜索, 调整搜索方向解题步骤

21 利用 matlab 求无约束极值问题在 matlab 工具箱中, 用于求解无约束极值问题的函数有 fmnunc 和 fmnsearch 求函数极小值命令 fmnunc [X,FVAL]=FMINUNC(FUN,X,OPTIONS,P,P,...) 求多元函数极值命令 fmnsearch [X,FVAL,EXITFLAG,OUTPUT]=FMINSEARCH(FUN,X,OPTIONS,P,P,...) X 极小点,FVAL 极小值

22 例 6( 二次规划 ) 若某非线性规划的目标函数为自变量的二次函数, 约束条件又全是线性的, 就称这种规划为二次规划数学模型 mn T H A b s. t. Aeq beq f T H 实对称矩阵 f,b 列向量 A 相应维数的矩阵 matlab 中求解二次规划的命令 [X,FVAL]= QUADPROG(H,f,A,b,Aeq,beq,LB,UB,X,OPTIONS) 其中 X 是决策向量的值,FVAL 是目标函数在处的值

23 求解二次规划, ) ( mn s t f h=[4,-4;-4,8]; f=[-6;-3]; a=[,;4,]; b=[3;9]; [,value]=quadprog(h,f,a,b,[],[],zeros(,)) matlab 解法编写 M 文件 eample6.m 运行结果 =.95.5 value = -.5

24 例 7( 罚函数法 ) 基本思想 : 利用约束函数作出适当的罚函数, 由此构造出带参数的增广目标函数, 把问题转化为无约束非线性规划问题两种形式 : 外罚函数法, 内罚函数法考虑以下问题 mn f ( ) g s. t. h m ( ) ( ) ( ),,..., r,,..., s, m,..., t 取一个充分大的数 M>, 构造函数 P(, M ) f ( ) M 则以增广目标函数 mn P(, M) r ma( g( ),) Mmn( h ( ),) M P(, M ) s 为目标函数的无约束极值问题的最优解也是原问题的最优解 t ( )

25 求下列非线性规划 mn f ( ) 8 s. t., 编写 M 文件 test.m %test.m functon g=test(); M=5; f=()^+()^+8; g=f-m*sum(mn([';zeros(,)]))-... M*mn(()^-(),)+M*abs(-()-()^+); 在命令窗口中输入 [,y]=fmnunc('test',rand(,)) 运行结果 = y =.848

26 在 Matlab 优化工具箱中用于求解约束最优化问题的函数 ()fmnbnd 函数用途 : 求单变量非线性函数在区间上的极小值 mn f ( ), [, ] 格式 :[X,FVAL]=FMINBND(FUN,,,OPTIONS) ()fsemnf 函数用途 : 求解 mn{ F( ) C( ), Ceq( ), PHI(, w) } A B s. t. Aeq Beq 格式 :X=FSEMINF(FUN,X,NTHETA,SEMINFCON,A,B,Aeq,Beq) (3)fmnma 函数用途 : 求解 mn ma F( ) F A b Aeq Beq s. t. C( ) Ceq( ) LB UB 格式 :X=FMINIMAX(FUN,X,A,B,Aeq,Beq,LB,UB,NONLCON)

27 数模试题举例在约 m 市容的某边长 6m 的正方形区域内有若干架飞机作水平飞行当一架欲进入该区域的飞机到达区域边缘时要立即计算并判断是否会与区域内的飞机发生碰撞如果会碰撞, 则应计算如何调整各架 ( 包括新进入的 ) 飞机飞行的方向角假定条件如下 : () 不碰撞的标准为任意两架飞机的距离大于 8m; () 飞机飞行方向角调整的幅度不应超过 3 度 ; (3) 所有飞机飞行速度均为每小时 8m; (4) 进入该区域的飞机在到达区域边缘时, 与区域内飞机的距离在 6m 以上 ; (5) 最多需考虑 6 架飞机 ; (6) 不必考虑飞机离开此区域后的状况

28 设该区域 4 个顶点的座标为 (,),(6,),(6,6),(,6) 记录数据见下表飞机编号横坐标纵坐标方向角 ( 度 ) 新进入 5

29 引进如下记号 : D a 为飞行管理区域的边长 ; 为飞行管理区域, 取直角坐标系使其为 ; 为飞机飞行速度,a=8m/h; (, y ) ( ( t), y ( t)) 为第架飞机的初始位置 ; 为第架飞机在 t 时刻的位置 ;, D, D 为第架飞机的原飞行方向角, 即飞行方向与轴夹角 ; 6 6 为第架飞机的方向角调整, ; 为第架飞机调整后的飞行方向角

30 将飞机视为不动而飞机以相对速度相对于飞机运动 ) sn sn, cos cos ( a a a a v v v v,cos sn sn a v,cos cos sn a 相对飞行方向角

31 两架飞机的初始距离为 r ( ) ( ) ( y y arcsn r 8 () 则只要当相对飞行方向角满足时, 两架飞机不可能碰撞 ) : 调整前第架飞机相对于第架飞机的相对速度与这两架飞机连线的夹角两架飞机不碰撞的条件 ( ) 其中 mn arg ( m e y n m e ) ( m n y n )

32 以所有飞机的调整量绝对值之和最小为目标函数,,...,6, 3,,...,6,,, ) (.. mn 6 s t

33 %eample7.m clear;clc; =[ ]; y=[ ]; q=[ ]; y=[; y]; d=dst(y); % 求矩阵各个列向量之间的距离 d(fnd(d==))=nf; a=asnd(8./d) % 以度为单位的反函数 y=+*y y=ep(*q*p/8) for m=:6 for n=:6 f n~=m b(m,n)=angle((y(n)-y(m))/(y(m)-y(n))); end end end b=b*8/p dlmwrte('tt.tt',a,'delmter', '\t','newlne','pc'); fd=fopen('tt.tt','a'); fwrte(fd,'~','char'); % 往纯文本文件中写 LINGO 数据的分割符 dlmwrte('tt.tt',b,'delmter', '\t','newlne','pc','-append','roffset', )

34 运行结果 a = b =

35 上述飞行管理的数学规划模型可如下输入 LINGO 求解 model: sets: plane/..6/:delta; ln(plane,plane):alpha,beta; endsets data: 需要在 alpha 的数据后面加上分隔符 "~"; enddata @for(ln(,) lpha(,)); end 求得的最优解为,,, 其他调整角度为

<4D F736F F D20B5DAC8FDD5C22020B7C7CFDFD0D4B9E6BBAE2E646F63>

<4D F736F F D20B5DAC8FDD5C22020B7C7CFDFD0D4B9E6BBAE2E646F63> 第三章非线性规划非线性规划. 非线性规划的实例与定义如果目标函数或约束条件中包含非线性函数, 就称这种规划问题为非线性规划问题一般说来, 解非线性规划要比解线性规划问题困难得多而且, 也不象线性规划有单纯形法这一通用方法, 非线性规划目前还没有适于各种问题的一般算法, 各个方法都有自己特定的适用范围下面通过实例归纳出非线性规划数学模型的一般形式, 介绍有关非线性规划的基本概念例投资决策问题