《二次规划求解方法探讨(共8页).doc》由会员分享,可在线阅读,更多相关《二次规划求解方法探讨(共8页).doc(8页珍藏版)》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、精选优质文档-倾情为你奉上二次规划求解方法探讨 李骥昭1 刘义山2(1.平顶山工业职业技术学院文化教育部1 河南 平顶山 ; 2.平顶山工业职业技术学院文化教育部2 河南 平顶山 )摘要:文章推广与应用了二次非线性规划模型的基础理论及算法。在线性规划模型中,活动对目标函数的贡献与活动水平成比例关系,因而目标函数是决策变量的线性函数,而在实际问题中,往往遇到活动对目标函数的贡献与活动水平不成比例关系的情形,即目标函数不是决策变量的线性函数,而是二次非线性函数,我们可以利用K-T条件并转化为等价求解相应的线性规划问题。经过分析可以得到结论,目标函数变成了线性函数,但约束函数中有一个非线性函数,这时
2、问题仍然是非线性的。应用Excel规划求解工具解这个模型后我们知道如果投资者愿意承担多一点的风险,就可以获得更大的收益。关键词:非线性规划,线性规划,目标函数,决策变量,模型中图分类:O226 文献标识:A0 引言非线性规划是运筹学的一个重要分支,它在管理科学、系统控制等诸多领域有广泛应用。非线性规划的任一算法都不能仅仅考察可行域极点的目标函数值来寻优。非线性规划的最优点可能在其可行域的任一点达到,即最优解可能在极点,或边介点或内点达到。在非线性规划问题中,其变量取值受到多个约束条件的限制,对其求解,一方面要使目标函数每次选代要逐次下降,且还要保持解的可行性。这就给寻找最优解带来更大的困难。为
3、使求解能较顺利进行,一般采用将约束条件转化为无约束条件,化为较简单问题来处理1。1 预备知识1.1 相关概念,相关定理若使得则称此约束条件是的不起作用约束;起作用约束:若使得,则称此约束条件是的起作用约束2。可行方向:若的实数,使得,均有,则称方向P是的一个可行方向;当必为的一个可行方向;下降方向:若使得均有,则称P为的一个下降方向。当必为的下降方向;可行下降方向:若又且则称P是的可行下降方向3相关定理,若是非线性规划的一个局部极小点,目标函数在可微,且在处可微,又处连续,则在点不存在可行下降方向,则不存在P同时满足且1.1.1 K-T 条件若非线性规划有极小点,且点与各起作用约束的梯度线性无
4、关,则存在使下述条件成立4:或可改写为:若是非线性规划的极小点,且点所起作用的约束梯度和线性无关,则存在向量和使得下述条件成立51.1.2 例如利用K-T 条件求解可以把上式改写成以下形式K-T 条件如下则有 即 考虑下面几种情况:2 二次规划求解方法2.1 二次规划转化问题探讨目标函数为二次函数,约束均用线性形式给出的非线性规划问题称为二次规划,二次规划求解方法较多,下面介绍利用K-T条件并转化为等价求解相应的线性规划问题的方法6,7。设二次规划问题 (2) 其中维正定或半正定矩阵。式(2)等价表述为 其中,。因为令 令 据K-T条件 有整理得又有求所得解为原二次规划的解.为了求解(3),可
5、引进辅助规划如下若求得最优解2.2股票投资问题一个投资者考虑将其资金投入到三支股票中去,这三支股票是:河南科技、北方通讯、南方交通。通过市场分析和统计预测,他整理出有关数据,如表所示 表1 三支股票五年的收益率和和五年的协方差 股票名称五年期望收益率(%) 五年协方差(%平方)河南科技北方通讯南方交通河南科技北方通讯南方交通9264411803611036120-30110-30140这个投资者想要将投资组合中股票收益的标准差最小化以降低投资风险,并希望五年后的期望收益率要达到65%以上。下面我们来分析一下这个问题。设H、N、S分别表示投资者将其资金投入到河南科技、北方通讯、南方交通三支股票中
6、的比例,那么这个问题可以描述为:最小标准差满足如下约束:1) 比例:H+N+S=1.02) 目标收益:0.92H+0.64N+0.41S0.653) 非负约束:H,N,S0目标是将标准差最小化,再加上三个约束条件,第一个约束是指投资者所投资的各个股票的比例之和必须是1;第二个约束是指这个投资组合五年的投资收益率至少要有65%;第三个约束是指对每支股票的投资比例不可能是负数。下面我们将这个模型未完成的部分也就是目标函数分析一下,以便完成这个模型。令随机变量分别为河南科技、北方通讯、南方交通三支股票五年的投资收益率,那么投资组合在五年期的收益率R为 我们应用上面这一等式来求投资组合的方差,可得将表
7、中的数据代入此式得方差=所以投资组合的标准差为:标准差=将这一表达式代入前面的模型中,得到此问题完整的数学模型为注意这个问题的约束是三个决策变量的线性函数,而且目标函数则是非线性的,我们可以用Excel规划求解来解这个模型。求解后得到计算结果是:购买河南科技23.51%、北方通讯52.22%、南方交通24.27%,标准差是8.04%。从另一方面考虑,投资者可能想使收益最大化,而让表示风险的标准差的大小作为约束,比如说,让标准差最大不超过12%,那么最优化问题变为 这时,目标函数变成了线性函数,但约束函数中有一个非线性函数,这时问题仍然是非线性的。应用Excel规划求解工具解这个模型后我们知道如
8、果投资者愿意承担多一点的风险,就可以获得更大的收益,根据结果可知,投资者将其85.93%的资金投入到河南科技中、将14.07%的资金投入到北方通讯中、不购买南方交通的股票,可在一定风险下获得最大收益率,最大收益率为88.06%.3 结束语 经过分析可以得到结论,对于非线性规划问题,其变量取值受到多个约束条件的限制,对其求解,一方面要使目标函数每次选代要逐次下降,且还要保持解的可行性。这就给寻找最优解带来更大的困难。为使求解能顺利进行,一般采用约束条件转化为无约束条件,化为较简单问题来处理。参考文献: 1 张维迎. 博弈论与信息经济学.上海:上海人民出版社,1996.2 邓成梁.运筹学的原理和方
9、法.武汉:华中理工大学出版社,19963 谢识予.经济博弈论.上海:复旦大学出版社,20024 韩伯棠.管理运筹学.北京:清华大学出版社,20005 施锡铨.博弈论.上海:上海财经大学出版社,2002.6 王周宏,王能超,钟毅芳. 求解一般半正定二次规划的数值稳定方法J. 华中科技大学学报:自然科学版,2002,24(4):203-205.7 滕召波,张世永,陈华富,何光中. 非线性规划一般约束条件的SQP方法J. 电子科技大学学报,2001,35(1):123-126.8 刘纲,黄宗明. 一种基于动态序列二次规划的模型修正修正方法J. 重庆大学学报,2008,31(1):107-109.9
10、李辉,丁桦. 结构动力模型修正方法研究进展J. 力学进展,2005,35(2):170-180.Quadratic programming solution method is discussedLiJiZhao 1 LiuYiShan 2(1. Pingdingshan industry vocational college culture ministry of education 1 henan pingdingshan; 2. Pingdingshan industry vocational college culture ministry of education 2 henan p
11、ingdingshan )Abstract: the articles purpose is to make the two times the basic theory of nonlinear programming model and algorithm are popularized and applied. In linear programming model, the activities of the objective function and activity level of contribution proportional relation, thus the obj
12、ective function is the decision variables linear function, and in the actual problem, often meet activities on the objective function of the contribution and activity level disproportionate to the circumstances of the relationship, that is, the objective function is not the decision variables linear
13、 function, but second nonlinear function, we can use K-T conditions and translated into equivalent to solve the corresponding linear programming problem. After analysis can come to the conclusion, the objective function into linear function, but constraint function has a nonlinear function, and then problems still is non-linear. Application programming solver tool Excel solution this model we know that if investors are willing to take a little more risk, can get a bigger profit. Keywords: nonlinear programming, linear programming, the objective function, the decision variables, model 专心-专注-专业