数学实验课件：实验九非线性函数极值求解

1、1实验九实验九 非线性函数极值求解非线性函数极值求解 2例例1 1（背包问题）（背包问题） 有一徒步旅行者要带一背包，设对背包的有一徒步旅行者要带一背包，设对背包的总重量限制为总重量限制为b千克，今有千克，今有n种物品可供选种物品可供选择，已知第择，已知第j种物品每件重量为种物品每件重量为aj千克，千克，使用价值为使用价值为cj，问旅行者应如何选取这些，问旅行者应如何选取这些物品，使得总价值最大？物品，使得总价值最大？整数线性规划整数线性规划( (Integer Programming, ,IP):): 决策变量取整数值决策变量取整数值 3解解 令令xj表示第表示第j种物品的装入件数，可得背种

2、物品的装入件数，可得背包问题的规划模型为包问题的规划模型为n,j ,xbxa. t . s;xczmaxjnjjjnjjj21011 且为整数且为整数4 从数学角度看，整数规划似乎是线性规划从数学角度看，整数规划似乎是线性规划的一种特殊形式，求解只需在线性规划的的一种特殊形式，求解只需在线性规划的基础上，通过舍入取整，寻找满足整数要基础上，通过舍入取整，寻找满足整数要求的最优解即可。但实际上两者有很大的求的最优解即可。但实际上两者有很大的不同，通过舍入得到的解也不一定就是最不同，通过舍入得到的解也不一定就是最优解，有时甚至不能保证所得到的解是整优解，有时甚至不能保证所得到的解是整数可行解。数可

3、行解。5求解整数线性规划的常用方法求解整数线性规划的常用方法： Gomory割平面法割平面法 分支定界法分支定界法 Lingo软件软件6例例2 2 （指派问题）（指派问题） 有有n n项任务，由项任务，由n n个人来完成，每个人只能个人来完成，每个人只能做一件，第做一件，第i i个人完成第个人完成第j j项任务需要时间项任务需要时间cijcij小时，如何合理安排才能使总用时最小？小时，如何合理安排才能使总用时最小？ 否则否则项任务项任务个人完成第个人完成第派第派第，并令，并令解、引入状态变量解、引入状态变量0ji1ijijxx则总用时表达式为 ninjijijxcf110-1整数规划：变量只取

4、整数规划：变量只取0和和17可得指派问题的规划模型为可得指派问题的规划模型为 10, 2 , 1, 1, 2 , 1, 1.;min1111或或ijnjijniijninjijijxnixnjxtsxcf求解方法：求解方法：Lingo软件，匈牙利算法软件，匈牙利算法,8多目标规划问题多目标规划问题 在很多实际问题中，衡量一个方案的好坏在很多实际问题中，衡量一个方案的好坏标准往往不止一个，这类问题统称为多目标准往往不止一个，这类问题统称为多目标规划问题或多目标最优化问题。标规划问题或多目标最优化问题。 例如后面的例如后面的 综合实例一综合实例一多目标规划问题的求解：多目标规划问题的求解：常用间接

5、解法，常用间接解法，设法将多目标问题转化为单设法将多目标问题转化为单目标问题目标问题9综合实例综合实例 投资的收益和风险投资的收益和风险 市场上有市场上有n n种资产种资产S Si i ( (i=i=1,21,2, ,n,n) )可以选择，可以选择，现用数额为现用数额为M M的相当大的资金作一个时期的投资。的相当大的资金作一个时期的投资。财务人员分析估算出这一时期内购买财务人员分析估算出这一时期内购买S Si i的平均收益的平均收益率为率为r ri i , ,风险损失率为风险损失率为q qi , i , 投资越分散，总的风险投资越分散，总的风险越小，总体风险可用投资的越小，总体风险可用投资的S

6、 Si i中最大的一个风险来中最大的一个风险来度量。度量。 购买购买S Si i时要付交易费，费率时要付交易费，费率p pi i( (不买无须付费不买无须付费).).当购买额不超过给定值当购买额不超过给定值u ui i时，交易费按购买时，交易费按购买u ui i计算计算. .另外，假定同期银行存款利率是另外，假定同期银行存款利率是r r0 0 , ,既无交易费又既无交易费又无风险。无风险。( ( r r0 0=5%)=5%)已知已知n=4n=4时的相关数据如下时的相关数据如下: :10SiriqipiuiS1282.51103S2211.52198S3235.54.552S4252.66.54

7、0 试给该公司设计一种投资组合方案，即用给试给该公司设计一种投资组合方案，即用给定达到资金定达到资金M,M,有选择地购买若干种资产或存有选择地购买若干种资产或存银行生息，使净收益尽可能大，使总体风险银行生息，使净收益尽可能大，使总体风险尽可能小。尽可能小。11数学建模的四个步骤数学建模的四个步骤 合理假设合理假设 模型建立模型建立 模型求解模型求解 解释验证解释验证 记住记住16字！字！12基本假设1.1.投资数额投资数额M相当大相当大, ,为了便于计算，假设为了便于计算，假设M=1;=1;2.投资越分散，总的风险越小；投资越分散，总的风险越小；3.总体风险总体风险Si 用投资项目中最大的一个

8、风险来度量；用投资项目中最大的一个风险来度量；4.n种资产种资产 Si 之间是相互独立的；之间是相互独立的；5.在投资的这一时期内在投资的这一时期内, ,ri , pi , qi , r0为定值，不受意为定值，不受意外因素影响；外因素影响；6.净收益和总体风险只受净收益和总体风险只受ri , pi , qi影响，不受其他影响，不受其他因素干扰。因素干扰。13符号规定符号规定 Si 第第i种投资项目，如股票，债券种投资项目，如股票，债券 ri ,pi ,qi 分别为分别为Si的平均收益率的平均收益率, ,风险损风险损失率，交易费率失率，交易费率 ui Si的交易定额的交易定额, , r0 同期银

9、行利率同期银行利率 xi 投资项目投资项目Si的资金的资金, , a 投资风险度投资风险度 Q总体收益总体收益, , Q总体收益的增量总体收益的增量14 模型的建立与分析模型的建立与分析1.总体风险用所投资的总体风险用所投资的Si中最大的一个风险中最大的一个风险来衡量来衡量,即即max qixi|i=1，2,n2购买购买Si所付交易费是一个分段函数所付交易费是一个分段函数,即即 pixi xiui 交易费交易费 = piui xiui 而题目所给定的定值而题目所给定的定值ui(单位单位:元元)相对总投相对总投资资M很小很小, piui更小更小,可以忽略不计可以忽略不计,这样购这样购买买Si的净

10、收益为的净收益为(ri-pi)xi 15模型的建立与分析模型的建立与分析净收益尽可能大净收益尽可能大建立模型建立模型)max(min)(max0iiiniiixqxpr nixMxptsiinii, 2 , 1, 0)1(.0总体风险尽可能小总体风险尽可能小多目标规划问题多目标规划问题16模型转化模型转化方法一方法一:固定风险水平，优化收益固定风险水平，优化收益 在实际投资中，投资者承受风险的程度不在实际投资中，投资者承受风险的程度不一样，若给定风险一个界限一样，若给定风险一个界限a，使最大的一，使最大的一个风险个风险 qi xi / Ma，可找到相应的投资方案。，可找到相应的投资方案。ini

11、iixpr 0)(max nixMxpMaxqtsiiniiii, 2 , 1, 0)1(.0 模型一模型一线性规划模型线性规划模型17模型转化模型转化方法二方法二:固定盈利水平，极小化风险固定盈利水平，极小化风险 若投资者希望总盈利至少达到水平若投资者希望总盈利至少达到水平k以上，以上，在风险最小的情况下寻找相应的投资组合。在风险最小的情况下寻找相应的投资组合。)max(miniixq nixMxpKxprtsiiniiiniii, 2 , 1, 0)1()(.00 模型二模型二线性规划模型线性规划模型18模型转化模型转化-方法方法3 3线性加权线性加权 投资者在权衡资产风险和预期收益两投资

12、者在权衡资产风险和预期收益两方面时，希望选择一个令自己满意的方面时，希望选择一个令自己满意的投资组合。因此对风险、收益赋予权投资组合。因此对风险、收益赋予权重重s（0s1)，s称为投资偏好系数称为投资偏好系数. iniiiiixprsxqs0)()1()max(min nixMxptsiinii, 2 , 1, 0)1(.0 模型三模型三线性规划模型线性规划模型19模型一的求解模型一的求解 将具体数据代入将具体数据代入,模型一如下模型一如下: minf = (-0.05, -0.27, -0.19, -0.185, -0.185) (x0 x1 x2 x3 x 4 ) T x0 + 1.01x

13、1 + 1.02x2 +1.045x3 +1.065x4 =1 s.t. 0.025x1 a 0.015x2 a 0.055x3 a 0.026x4a xi 0 (i = 0,1,.4) 由于由于a是任意给定的风险度，到底怎样给定没有一是任意给定的风险度，到底怎样给定没有一个准则，不同的投资者有不同的风险度。我们从个准则，不同的投资者有不同的风险度。我们从a=0开始，以步长开始，以步长a=0.001进行循环搜索，编制程序如进行循环搜索，编制程序如下：下：20a=0;while(1.1-a)1 c=-0.05 -0.27 -0.19 -0.185 -0.185; Aeq=1 1.01 1.02

14、1.045 1.065; beq=1; A=0 0.025 0 0 0;0 0 0.015 0 0;0 0 0 0.055 0;0 0 0 0 0.026; b=a;a;a;a; vlb=0,0,0,0,0;vub=; x,val=linprog(c,A,b,Aeq,beq,vlb,vub); Q=-val;fprintf(a=%.4f,x=%.4f %.4f %.4f %.4f %.4f ,Q=%.4fn,a,x(1),x(2),x(3),x(4),x(5),Q) plot(a,Q,.) axis(0 0.1 0 0.5); hold on a=a+0.001;end xlabel(a),y

15、label(Q)21a = 0.0030 x = 0.4949 0.1200 0.2000 0.0545 0.1154 Q = 0.1266a = 0.0060 x = 0 0.2400 0.4000 0.1091 0.2212 Q = 0.2019a = 0.0080 x = 0.0000 0.3200 0.5333 0.1271 0.0000 Q = 0.2112a = 0.0100 x = 0 0.4000 0.5843 0 0 Q =0.2190a = 0.0200 x = 0 0.8000 0.1882 0 0 Q =0.2518 a = 0.0400 x = 0.0000 0.99

16、01 0.0000 0 0 Q =0.2673计算结果：计算结果：22模型一结果分析模型一结果分析1.1.风险大，收益也大。风险大，收益也大。2.2.当投资越分散时，投资者承担的风险越当投资越分散时，投资者承担的风险越小，这与题意一致。即小，这与题意一致。即: : 冒险的投资者会出现集中投资的情况，冒险的投资者会出现集中投资的情况，保守的投资者则尽量分散投资。保守的投资者则尽量分散投资。3.3.曲线上的任一点都表示该风险水平的最曲线上的任一点都表示该风险水平的最大可能收益和该收益要求的最小风险。大可能收益和该收益要求的最小风险。对于不同风险的承受能力，选择该风险对于不同风险的承受能力，选择该风

17、险水平下的最优投资组合。水平下的最优投资组合。234 4.在在a=0.006a=0.006附近有一个转折点，在这一点左边，附近有一个转折点，在这一点左边，风险增加很少时，利润增长很快。在这一点右风险增加很少时，利润增长很快。在这一点右边，风险增加很大时，利润增长很缓慢，所以边，风险增加很大时，利润增长很缓慢，所以对于风险和收益没有特殊偏好的投资者来说，对于风险和收益没有特殊偏好的投资者来说，应该选择曲线的拐点作为最优投资组合，应该选择曲线的拐点作为最优投资组合， 大约是大约是a a* *=0.6%=0.6%，Q Q* *=20% =20% ，此时，此时风险度为风险度为 0.0060 收益为收益

18、为 0.2019,所对应投资方案为所对应投资方案为: : x0 x1 x2 x3 x4 0 0.2400 0.4000 0.1091 0.221224非线性规划非线性规划 目标函数和约束条件中至少有一个是非线性目标函数和约束条件中至少有一个是非线性函数的规划问题，称为非线性规划。函数的规划问题，称为非线性规划。事实上，客观事件中的问题许多都是非线性的，事实上，客观事件中的问题许多都是非线性的，在做了科学的假设和简化后，被近似认为是在做了科学的假设和简化后，被近似认为是线性的。但也有一些是不能进行线性化处理线性的。但也有一些是不能进行线性化处理的。的。求解：求解：LingoLingo软件，软件，

19、LindoLindo软件软件251 无约束最优化无约束最优化 在生活和工作中，只要解决问题的方法不是唯在生活和工作中，只要解决问题的方法不是唯一的，就存在最优化问题。最优化方法就是专一的，就存在最优化问题。最优化方法就是专门研究从多个方案中科学合理的提取出最佳方门研究从多个方案中科学合理的提取出最佳方案的科学。案的科学。 从数学角度讲，最优化问题就是求一个函数的从数学角度讲，最优化问题就是求一个函数的最大或最小值问题，而最大值可以转化为求最最大或最小值问题，而最大值可以转化为求最小值，所以最优化问题的一般形式为小值，所以最优化问题的一般形式为 xtsxf.)(min26对于无约束变量，对于无约

20、束变量，matlabmatlab提供了指令可供调用：提供了指令可供调用：（1 1）一元函数极值）一元函数极值 x=fminbnd(fun,x1,x2) x,fval=fminbnd(fun,x1,x2)（2 2）多元函数极值）多元函数极值 x=fminsearch(fun,x0) 或者或者 x=fminunc(fun,x0) % % 给定初值给定初值x0 x0，求得，求得funfun函数的局部极小值点。函数的局部极小值点。加加fvalfval返回极小值。返回极小值。否则称为有约束变量。否则称为有约束变量。时，称为无约束变量，时，称为无约束变量，当当为约束集或可行域。为约束集或可行域。为目标函数

21、，为目标函数，是决策变量，是决策变量，其中其中nnnRRxfRx )(27( (1) 1) 多元函数的约束极值问题多元函数的约束极值问题 x=fmincon(fun,x0,A,b,aeq,beq,vlb,vub,nonlcon)min( ), . .( )0( )0Axbaeq xbeqf x s tg xceq xvlbxvub 求求解解其中目标函数其中目标函数f(x)通过通过m文件文件fun.m定义，定义，nonlcon是是m文件文件nonlcon.m，表示约束条件中的，表示约束条件中的非线性约束非线性约束g(x)=0或或ceq(x)=0.2 有约束最优化有约束最优化28解解 首先定义非线

22、性约束函数首先定义非线性约束函数function g,ceq=nonlcon(x)g=;ceq=x(1)2+x(2)2-x(3);其次编写程序如下其次编写程序如下：的最长和最短距离。的最长和最短距离。求原点到曲线求原点到曲线例例 1122zyxzyxx0=0;0;0;A=;b=;aeq=1 1 1;beq=1;vlb=;vub=;f=inline(sqrt(x(1)2+x(2)2+x(3)2);x,d=fmincon(f,x0,A,b,aeq,beq,vlb,vub,nonlcon)29（2）二次多元函数的约束极值）二次多元函数的约束极值1min,2. .TTzx Hxc xAxbs taeq

23、 xbeqvlbxvub x=quadprog(H,c,A,b,aeq,beq,vlb,vub)30动态规划模型动态规划模型 动态规划所研究的对象是多阶段对策问题，是动态规划所研究的对象是多阶段对策问题，是在在2020世纪世纪5050年代初期由美国数学家年代初期由美国数学家R.BellmanR.Bellman等等人提出的一类规划模型人提出的一类规划模型. . 动态规划是现代管理领动态规划是现代管理领域的一种重要的决策方法，其主要应用有最优路域的一种重要的决策方法，其主要应用有最优路径问题、资源分配问题、投资决策问题、生产计径问题、资源分配问题、投资决策问题、生产计划与库存问题、排序问题、货物装

24、载问题以及生划与库存问题、排序问题、货物装载问题以及生产过程中的最优控制问题产过程中的最优控制问题. .31 多阶段决策问题是指一类活动过程，它多阶段决策问题是指一类活动过程，它可以分为若干个相互联系的阶段，在每可以分为若干个相互联系的阶段，在每个阶段都需要做出决策，这个决策不仅个阶段都需要做出决策，这个决策不仅决定这一阶段的效益，而且决定下一阶决定这一阶段的效益，而且决定下一阶段的初始状态，每个阶段的决策确定以段的初始状态，每个阶段的决策确定以后，就得到一个决策序列，称为策略后，就得到一个决策序列，称为策略. . 多阶段决策问题就是求一个策略，使各多阶段决策问题就是求一个策略，使各阶段的效益

25、的总和达到最优阶段的效益的总和达到最优. .32 例例10有一辆汽车要把货物从城运到城，有一辆汽车要把货物从城运到城，而从城到城必须经过一些城市，整段路程而从城到城必须经过一些城市，整段路程可分为若干个阶段，而每个阶段又有若干可分为若干个阶段，而每个阶段又有若干个城市可供选择，选取怎样的路线才能使个城市可供选择，选取怎样的路线才能使路程最短？假定从城到城的所有路线如下路程最短？假定从城到城的所有路线如下图所示：图所示：333421216476542C1DEA1B2B2D1C图图1 1 从从A A城到城到E E城的路城的路线线 其中其中 是可供选择的城市，途中是可供选择的城市，途中的数字表示两城

26、之间的距离（以的数字表示两城之间的距离（以1010千米为单位）千米为单位）. .121212,B B C C D D34MATLAB优化工具箱能求解的优化模型优化工具箱能求解的优化模型优化工具箱优化工具箱3.0 (MATLAB 7.0 R14)连续优化连续优化离散优化离散优化无约束优化无约束优化非线性非线性极小极小fminunc非光滑非光滑(不可不可微微)优化优化fminsearch非线性非线性方程方程(组组)fzerofsolve全局全局优化优化暂缺暂缺非线性非线性最小二乘最小二乘lsqnonlinlsqcurvefit线性规划线性规划linprog纯纯0-1规划规划 bintprog一般一

27、般IP(暂缺暂缺)非线性规划非线性规划fminconfminimaxfgoalattainfseminf上下界约束上下界约束fminbndfminconlsqnonlinlsqcurvefit约束线性约束线性最小二乘最小二乘lsqnonneglsqlin约束优化约束优化二次规划二次规划quadprog35 本次上机任务：本次上机任务：实验九实验九 练习练习2 2、3 3中，每个练习选一题中，每个练习选一题 下面两题下面两题 选一题选一题 36 1 一奶制品工厂用牛奶生产一奶制品工厂用牛奶生产A1，A2两种初级奶制两种初级奶制品，它们可以直接出售，也可以分别加工成品，它们可以直接出售，也可以分别

28、加工成B1，B2两种高级奶制品再出售。按目前技术每桶牛奶两种高级奶制品再出售。按目前技术每桶牛奶可加工成可加工成2kgA1和和3kgA2，每桶牛奶的买入价为，每桶牛奶的买入价为10元，加工费为元，加工费为5元，加工时间为元，加工时间为15h。每千克。每千克A1可深加工成可深加工成0.8kgB1，加工费为，加工费为4元，加工时间为元，加工时间为12h；每千克；每千克A2可深加工成可深加工成0.7kgB2，加工费为，加工费为3元，加工时间为元，加工时间为10h。初级奶制品。初级奶制品A1，A2的售价的售价分别为分别为10元元/kg和和9元元/kg，高级奶制品，高级奶制品B1，B2的售的售价分别为价分别为30元元/kg和和20元元/kg。工厂现有的加工能。工厂现有的加工能力为每周总共力为每周总共2000h。根据市场状况，高级奶制。根据市场状况，高级奶制品的需求量占全部奶制品需求量的品的需求量占全部奶制品需求量的20%至至40%。试在供需平衡的条件下为