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

实验九非线性函数极值求解

例1（背包问题）

有一徒步旅行者要带一背包，设对背包的总重量限制为b千克，今有n种物品可供选择，已知第j种物品每件重量为aj千克，使用价值为cj，问旅行者应如何选取这些物品，使得总价值最大？整数线性规划(IntegerProgramming,IP):

决策变量取整数值

解令xj表示第j种物品的装入件数，可得背包问题的规划模型为从数学角度看，整数规划似乎是线性规划的一种特殊形式，求解只需在线性规划的基础上，通过舍入取整，寻找满足整数要求的最优解即可。但实际上两者有很大的不同，通过舍入得到的解也不一定就是最优解，有时甚至不能保证所得到的解是整数可行解。求解整数线性规划的常用方法：

Gomory割平面法分支定界法

Lingo软件例2（指派问题）

有n项任务，由n个人来完成，每个人只能做一件，第i个人完成第j项任务需要时间cij小时，如何合理安排才能使总用时最小？则总用时表达式为0-1整数规划：变量只取0和1可得指派问题的规划模型为求解方法：Lingo软件，匈牙利算法,多目标规划问题在很多实际问题中，衡量一个方案的好坏标准往往不止一个，这类问题统称为多目标规划问题或多目标最优化问题。例如后面的综合实例一多目标规划问题的求解：常用间接解法，设法将多目标问题转化为单目标问题综合实例－投资的收益和风险

市场上有n种资产Si(i=1,2,…,n)可以选择，现用数额为M的相当大的资金作一个时期的投资。财务人员分析估算出这一时期内购买Si的平均收益率为ri,风险损失率为qi,投资越分散，总的风险越小，总体风险可用投资的Si中最大的一个风险来度量。购买Si时要付交易费，费率pi(不买无须付费).当购买额不超过给定值ui时，交易费按购买ui计算.另外，假定同期银行存款利率是r0,既无交易费又无风险。(r0=5%)已知n=4时的相关数据如下:SiriqipiuiS1282.51103S2211.52198S3235.54.552S4252.66.540

试给该公司设计一种投资组合方案，即用给定达到资金M,有选择地购买若干种资产或存银行生息，使净收益尽可能大，使总体风险尽可能小。数学建模的四个步骤合理假设模型建立模型求解解释验证

记住16字！基本假设1.投资数额M相当大,为了便于计算，假设M=1;2.投资越分散，总的风险越小；3.总体风险Si用投资项目中最大的一个风险来度量；4.n种资产Si之间是相互独立的；5.在投资的这一时期内,ri,pi,qi,r0为定值，不受意外因素影响；6.净收益和总体风险只受ri,pi,qi影响，不受其他因素干扰。符号规定Si——第i种投资项目，如股票，债券ri,pi,qi——分别为Si的平均收益率,风险损失率，交易费率ui——Si的交易定额,r0——同期银行利率xi——投资项目Si的资金,a

——投资风险度Q——总体收益,∆Q——总体收益的增量

模型的建立与分析1.总体风险用所投资的Si中最大的一个风险来衡量,即max{qixi|i=1，2,…n}2．购买Si所付交易费是一个分段函数,即

pixixi>ui

交易费=piuixi≤ui而题目所给定的定值ui(单位:元)相对总投资M很小,piui更小,可以忽略不计,这样购买Si的净收益为(ri-pi)xi模型的建立与分析净收益尽可能大建立模型总体风险尽可能小多目标规划问题模型转化

方法一:固定风险水平，优化收益

在实际投资中，投资者承受风险的程度不一样，若给定风险一个界限a，使最大的一个风险qixi/M≤a，可找到相应的投资方案。

模型一线性规划模型模型转化

方法二:固定盈利水平，极小化风险

若投资者希望总盈利至少达到水平k以上，在风险最小的情况下寻找相应的投资组合。

模型二线性规划模型模型转化---方法3线性加权

投资者在权衡资产风险和预期收益两方面时，希望选择一个令自己满意的投资组合。因此对风险、收益赋予权重s（0＜s≤1)，s称为投资偏好系数.

模型三线性规划模型模型一的求解将具体数据代入,模型一如下:

由于a是任意给定的风险度，到底怎样给定没有一个准则，不同的投资者有不同的风险度。我们从a=0开始，以步长△a=0.001进行循环搜索，编制程序如下：a=0;while(1.1-a)>1c=[-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];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=%.4f\n',a,x(1),x(2),x(3),x(4),x(5),Q)plot(a,Q,'.')axis([00.100.5]);holdona=a+0.001;endxlabel('a'),ylabel('Q')计算结果：模型一结果分析1.风险大，收益也大。2.当投资越分散时，投资者承担的风险越小，这与题意一致。即:

冒险的投资者会出现集中投资的情况，保守的投资者则尽量分散投资。3.曲线上的任一点都表示该风险水平的最大可能收益和该收益要求的最小风险。对于不同风险的承受能力，选择该风险水平下的最优投资组合。4.在a=0.006附近有一个转折点，在这一点左边，风险增加很少时，利润增长很快。在这一点右边，风险增加很大时，利润增长很缓慢，所以对于风险和收益没有特殊偏好的投资者来说，应该选择曲线的拐点作为最优投资组合，大约是a*=0.6%，Q*=20%，此时风险度为0.0060收益为0.2019,

所对应投资方案为:x0x1x2x3x400.24000.40000.10910.2212非线性规划目标函数和约束条件中至少有一个是非线性函数的规划问题，称为非线性规划。事实上，客观事件中的问题许多都是非线性的，在做了科学的假设和简化后，被近似认为是线性的。但也有一些是不能进行线性化处理的。求解：Lingo软件，Lindo软件1无约束最优化在生活和工作中，只要解决问题的方法不是唯一的，就存在最优化问题。最优化方法就是专门研究从多个方案中科学合理的提取出最佳方案的科学。从数学角度讲，最优化问题就是求一个函数的最大或最小值问题，而最大值可以转化为求最小值，所以最优化问题的一般形式为对于无约束变量，matlab提供了指令可供调用：（1）一元函数极值

x=fminbnd(fun,x1,x2)[x,fval]=fminbnd(fun,x1,x2)（2）多元函数极值

x=fminsearch(fun,x0)或者x=fminunc(fun,x0)

%给定初值x0，求得fun函数的局部极小值点。加fval返回极小值。(1)多元函数的约束极值问题

x=fmincon(‘fun’,x0,A,b,aeq,beq,vlb,vub,’nonlcon’)其中目标函数f(x)通过m文件fun.m定义，’nonlcon’是m文件nonlcon.m，表示约束条件中的非线性约束g(x)<=0或ceq(x)=0.2有约束最优化解首先定义非线性约束函数function[g,ceq]=nonlcon(x)g=[];ceq=x(1)^2+x(2)^2-x(3);其次编写程序如下：x0=[0;0;0];A=[];b=[];aeq=[111];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')（2）二次多元函数的约束极值x=quadprog(H,c,A,b,aeq,beq,vlb,vub)动态规划模型动态规划所研究的对象是多阶段对策问题，是在20世纪50年代初期由美国数学家R.Bellman等人提出的一类规划模型.动态规划是现代管理领域的一种重要的决策方法，其主要应用有最优路径问题、资源分配问题、投资决策问题、生产计划与库存问题、排序问题、货物装载问题以及生产过程中的最优控制问题.多阶段决策问题是指一类活动过程，它可以分为若干个相互联系的阶段，在每个阶段都需要做出决策，这个决策不仅决定这一阶段的效益，而且决定下一阶段的初始状态，每个阶段的决策确定以后，就得到一个决策序列，称为策略.多阶段决策问题就是求一个策略，使各阶段的效益的总和达到最优.例10．有一辆汽车要把货物从城运到城，而从城到城必须经过一些城市，整段路程可分为若干个阶段，而每个阶段又有若干个城市可供选择，选取怎样的路线才能使路程最短？假定从城到城的所有路线如下图所示：342121647654图1从A城到E城的路线其中是可供选择的城市，途中的数字表示两城之间的距离（以10千米为单位）.MATLAB优化工具箱能求解的优化模型优化工具箱3.0(MATLAB7.0R14)连续优化离散优化无约束优化非线性极小fminunc非光滑(不可微)优化fminsearch非线性方程(组)fzerofsolve全局优化暂缺非线性最小二乘lsqnonlinlsqcurvefit线性规划linprog纯0-1规划bintprog一般IP(暂缺)非线性规划fminconfminimaxfgoalattainfseminf上下界约束fminbndfminconlsqnonlinlsqcurvefit约束线性最小二乘lsqnonneglsqlin约束优化二次规划quadprog线性规划问题的软件解法本次上机任务：实验九

练习2、3中，每个练习选一题

下面两题选一题1一奶制品工厂用牛奶生产A1，A2两种初级奶制品，它们可以直接出售，也可以分别加工成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。工厂现有的加工能力为每周总共