四川理工学院

《运筹学课程设计》报告

学    生：雷鹏程  李杰  熊伟

          杨治文  文钊

专    业：统计学

班    级：20122

指导教师：兰  恒  友

           

四川理工学院理学院

二O一 四 年十一月

四川理工学院理学院

课程设计任务书

专    业：      统  计   学      班  级：     20122  

课程名称：                 运筹学课程设计              

学生姓名：雷鹏程   李杰   熊伟   文钊   杨治文                                     

时    间：    2014     年    11   月    12     日

一、   课程设计题目

带步长因子Newton算法研究

二、   课程设计条件

1. 参考文献：

[1] 刁在筠、刘桂真、宿洁、马建华编著. 运筹学（第三版）[M]. 北京: 高等教育出版社, 2007.

[2] 孙文瑜等, 最优化方法(第二版)[M]. 北京: 高等教育出版社, 2010.

[3] 王红梅. 算法设计与分析[M]. 北京: 清华大学出版社, 2006.

2. 安排12学时（11周三8:15-11:50，18:50-21:50；11周五10:20-11:50, 14:30-16:00）上机（统计20121 N1S3-1011/统计20122 N1S3-1007），指导老师指导。

三、   设计任务

理解巩固课程理论教学的知识，培养学生的实践动手能力。具体任务：掌握带步长因子Newton法的思想及迭代步骤；已知：，用带步长因子Newton法编程求

四、   设计说明书（或论文）内容

摘要、问题描述、具体理论知识点、具体实例、程序清单、程序实现、参考文献、总结、小组成员分工合作清单。

五、   进度计划（列出完成项目设计内容、编程等具体起始日期）

11月10-11日图书馆或网络查资料，11月11-12日，根据资料整理出基础理论与实例；11月12-14日上机12学时，编程并上机实现；11月21日前完成设计报告并上缴纸质文档及其电子文档。

带步长因子Newton算法研究模型

摘  要

本文主要研究带歩长因子的Newton算法，针对本文问题，我们采用了Newton法的思想与计算步骤，但是为了克服Newton法中初始点的选取以及当目标函数存在严重非线性时迭代过程中不一定收敛的缺陷，所以本文在迭代过程中引入了步长因子和一维搜索加以解决，然后运用一维搜索找到了最优步长因子。经过这种带歩长因子的Newton方法解决这个无约束最优化问题。

关键词：Newton法，迭代，带歩长因子Newton法。

目    录

一、问题提出.............................................................. 1

二、设计思路和步骤........................................................ 2

三、程序设计.............................................................. 3

3.1问题分析........................................................... 3

3.2 算法设计.......................................................... 3

3.3 算法框图.......................................................... 3

3.4 程序编制.......................................................... 4

四、结果分析.............................................................. 6

4.1设计结果........................................................... 6

4.2 进一步讨论和验证.................................................. 7

五、收获和总结............................................................ 7

六、结束语................................................................ 9

6.1设计的优缺点....................................................... 9

6.2设计工作展望....................................................... 9

参考文献................................................................. 10

附  录................................................................... 11

一、问题提出

非线性规划研究的对象是非线性函数的数值最优化问题，其理论和方法涉及许多方面，例如军事、经济、管理、生产过程中自动化和产品优化设计等都有重要应用。在求解一个非线性归化问题就是希望求得它的整体最优解和整体最优值，但很多情况下，我们往往很难实现，而只能得到它的局部最优解和局部最优值。由于大型计算机的普遍使用，使我们有可能找到多个满足条件的的解，或多个局部最优解后，从中选取一个最优解，因此非线性规划的问题的最优解要依据具体的类型问题和采用具体的算法而定。所以我们提出下面这个非线性规划问题：已知：，用带步长因子Newton法求：

二、设计思路和步骤

2.1设计思路

对于此次课程设计，我们组的设计思路是：

1.得到设计题目之后，我们对题目进行了分析与研究，队员对题目的发表自己的思路，每个人对题目进行了书面解答，增加了对题目的解题思路加深印象。

2.然后对每个组员进行了分工。

3.每个队员对自己的任务进行了整理和书写。

4.最后大家一起每个队员整合后的资料进行的修改和发表看法。

2.2设计步骤

1.查阅关于Newton法方面的相关资料，参考刁在筠《运筹学第三版》的Newton法的思想与计算步骤结合席少霖《非线性规划》的关于一维搜索及其Newton法的讲解找到带步长因子Newton算法的计算步骤。

2.根据算法步骤画出算法框图参考文献资料编写出带步长因子Newton法的matlab程序。

3.对计算出的答案进行了验证与推广，并且计算多个初始点的极值相比较，对程序的和算法步骤进行验证。

4.最后对于带步长因子Newton算法研究的论文进行整理，整合出最终的论文。

三、程序设计

   

3.1问题分析

带步长因子Newton法的基本思想：参考刁在筠《运筹学（第三版）》,带步长因子牛顿法的迭代方向依然与牛顿法一样，采用牛顿方向：

但每次迭代需沿此方向作一位搜索，求其最优步长因子，使得

将牛顿法的迭代公式改为：此即带步长因子牛顿法的迭代公式。

称为步长因子，通过牛顿方向进行一维获得。当目标函数的Hesse矩阵处于正定时，带步长因子牛顿法能保证每次迭代的目标函数值均为下降，从而保持了二次收敛的特性

3.2 算法设计

步1：选取初始点，取初始点,终止误差,维数n，令：=0。

步2：计算，若,若满足，停止迭代，输出，

否则进行步3。

步3：计算处的，并求其逆。

步4：计算牛顿方向，然后沿牛顿方向进行一维搜索求出最优  步长，使得

 ，然后令k+1k 转步2

3.3 算法框图

 

                              

 

3.4 程序编制

function y=objfunc(x)

y=60-10*x(1)-4*x(2)+x(1)^2+x(2)^2-x(1)*x(2)

>>xmin=fminsearch(‘objfunc’,[0 0])

>>xmin=fminsearch(‘objfunc’,[1 1])

>> syms x y;

z=60-10*x-4*y+x^2+y^2-x*y

ezsurf(x,y,z)

z =60-10*x-4*y+x^2+y^2-x*y

四、结果分析

4.1设计结果

选取初始点为

图一 Matlab程序计算图

由matlab计算得到该问题的极小值点：

目标函数极小值：

由matlab得到该函数收敛图：

图二 目标函数收敛图

4.2 进一步讨论和验证

讨论：（1）当正定时,只要，那么Newton方向定为下降方向，。

     （2）若为不正定但非奇异，且Newton方向为，使，那么

为下降方向，此时改取。

     （3）若或者奇异，此时采用负梯方向，即取。

推广：在实际生产生活中会涉及到一些无约束最优化问题，使用带步长因子的Newton法能够很好的解决其计算量大及复杂的数学问题，推广到多元函数中也可以找到多元函数的最小值。

五、收获和总结

5.1 小组总结

通过此次课程设计，使我们更加扎实的掌握了有关Newton法及其带步长因子Newton算法方面的知识，在设计过程中虽然遇到了一些问题，但经过一次又一次的思考，一遍又一遍的检查终于找出了原因所在，也暴露出了前期我在这方面的知识欠缺和经验不足。实践出真知，通过亲自动手制作，使我们掌握的知识不再是纸上谈兵。在这学期的运筹学课程设计实验课中，不仅培养了独立思考、动手操作的能力，而且在各种其它能力上也都有了提高。更重要的是，在实验课上，我们学会了很多学习的方法。而这是日后最实用的，真的是受益匪浅。要面对社会的挑战，只有不断的学习、实践，再学习、再实践。这对于我们的将来也有很大的帮助。实验过程中，也对团队精神的进行了考察，让我们在合作起来更加默契，在成功后一起体会喜悦的心情。果然是团结就是力量，只有互相之间默契融洽的配合才能换来最终完美的结果。

5.2 个人总结

在此次课程设计中，杨治文查阅了相关Newton法的一些文献资料，知道了如何查找相关的资料文献，同时对牛顿法的思想与算法步骤有所了解。李杰在此次的课程设计中知道了论文的书写格式，知道书写一篇论文的重要性，还明白了如何写一篇好的论文，可能这次论文的书写会有一些问题，但是我在文钊的协助下学会如何运用文字和数学符号去表达数学知识。熊伟知道如何计算Newton的简单的计算题，并且明白了带步长因子Newton法的思想与算法步骤，对于一些简单的函数问题能够计算出最优解。雷鹏程身为组长在此次的课程设计中展示出了组长应有的责任，队员的分工与问题分析起到了关键作用，他总结每个队员对于问题的分析，最后主要提出了这次带步长因子Newton算法的计算步骤，并且学习了如何简单的编写一些matlab程序来解答此次问题，主要解决了这次的课程设计，在设计中提出了自己一些看法与意见。回顾起此课程设计，至今仍感慨颇多，从理论到实践，学到很多很多的东西，同时不仅可以巩固了以前所学过的知识，而且学到了很多在书本上所没有学到过的知识。通过这次课程设计使我懂得了理论与实际相结合是很重要的，只有理论知识是远远不够的，只有把所学的理论知识与实践相结合起来，从理论中得出结论，才能真正为社会服务，从而提高自己的实际动手能力和独立思考的能力。在设计的过程中遇到问题，可以说得是困难重重，但可喜的是最终都得到了解决。 

六、结束语

6.1设计的优缺点

设计优点：而牛顿法不仅使用函数的一阶导数，还进一步利用了二阶导数，较好的考虑了梯度的变化趋势，因而能够更全面的确定合适的搜索方向，加快收敛速度。牛顿法具有二次收敛性，对于正定的二次函数应用牛顿法只要一次迭代即可达到极小点。对于目标函数二次性态好或者初始点取在极值附近时，收敛速度快。

设计缺点：应用牛顿法的主要困难是Hesse矩阵可能奇异，或者接近奇异；即使该矩阵是可逆的，它也未必是正定矩阵。此时，导出的牛顿法迭代格式的二次函数不一定有极小值，甚至没有驻点。为了保证目标函数的二次函数是严格凸的，存在极小点，就需要对二次函数的Hesse矩阵进行修正。修正牛顿法的基本思想是：在确定搜索方向时，对Hesse矩阵增加一个矫正矩阵，使之正定，这样可以保证走做方向是目标函数的下降方向。

6.2设计工作展望

通过这次的课程设计，使我们知道带步长因子的Newton法的基本思想和计算步骤，有个这个算法步骤能够很好的解决Newton法中的迭代步长是定的，可以很好的解决在实际问题中的初始点的选取和很好的运用matlab解决一些计算量大而复杂的非线性规划问题。由于计算机的普遍使用，因此在以后的实际生产生活中一些关于Newton法的无约束最优化问题运用计算机能够解决一些棘手数学问题。在未来的实际生活中会得到广泛的运用。

参考文献

[1] 刁在筠、刘桂真、宿洁、马建华编著. 运筹学（第三版）[M]. 北京: 高等教育出版社, 2007.

[2] 席少霖.非线性最优化方法[M].北京：高等教育出版社,1992.

附  录

求目标函数极小值：

function y=objfunc(x)

y=60-10*x(1)-4*x(2)+x(1)^2+x(2)^2-x(1)*x(2)

>>xmin=fminsearch(‘objfunc’,[0 0])

>>xmin=fminsearch(‘objfunc’,[1 1])

目标函数收敛：

>> syms x y;

z=60-10*x-4*y+x^2+y^2-x*y

ezsurf(x,y,z)

z =60-10*x-4*y+x^2+y^2-x*y

 

第二篇：运筹学课程设计1

?实验一操作步骤

§Step1 进入LinDO操作界面

§Step2 按要求输入LP模型 检验输入表达式的正确性：

菜单Reports/ Piture

Formulation

所得结果如下：

进入菜单Reports/ Picture 结果显示：

进入菜单Reports/ Formulation 结果显示：

MAX 4 X1 + 3 X2

SUBJECT TO

2) 2 X1 + 3 X2 + X3 = 24

3) 3 X1 + 2 X2 + X4 = 26

END

§Step3 按运算符健或菜单Slove/Slove，并选择是否进行灵敏度分析？选：否！的结果如下：(给出解释)

进入菜单 Slove/Slove结果显示：

MAX 4 X1 + 3 X2

SUBJECT TO

2) 2 X1 + 3 X2 + X3 = 24

3) 3 X1 + 2 X2 + X4 = 26

END

LP OPTIMUM FOUND AT STEP 2

表示LINDO在（用单纯形法）2次迭代或旋转后得到最优解。

OBJECTIVE FUNCTION VALUE

1) 36.00000

表示最优目标值为36.00000。

VARIABLE VALUE REDUCED COST

X1 6.000000 0.000000

X2 4.000000 0.000000

X3 0.000000 0.200000

X4 0.000000 1.200000

“VALUE”给出最优解中各变量的值。“REDUCE COST”列出最优单纯形表中判别数所在行的变量的系数，表示当变量有微小变动时，目标函数的变化率，其中基变量的reduce cost 值应为0，对于非基变量xj相应的reduce cost值表示xj增加一个单位（此时假定其他非基变量保持不变）时目标函数减小的量（max 型问题）

ROW SLACK OR SURPLUS DUAL PRICES

2) 0.000000 0.200000

3) 0.000000 1.200000

NO. ITERATIONS= 2

“SLACK OR SURPLUS”给出松弛变量的值。

§Step4 菜单Reports/Range,进行灵敏度分析。所得结果如下：(给出解释) 进入菜单Reports/Range 结果显示：

RANGES IN WHICH THE BASIS IS UNCHANGED:

OBJ COEFFICIENT RANGES

VARIABLE CURRENT ALLOWABLE ALLOWABLE

COEF INCREASE DECREASE X1 4.000000 0.500000 2.000000

X2 3.000000 3.000000 0.333333

X3 0.000000 0.200000 INFINITY

X4 0.000000 1.200000 INFINITY

RIGHTHAND SIDE RANGES

ROW CURRENT ALLOWABLE ALLOWABLE

RHS INCREASE DECREASE 2 24.000000 15.000000 6.666667

3 26.000000 10.000000 10.000000

§Step5 菜单Reports/Tableam，先是单纯形表，并与教材中的结果对比。所得结果如下：(给出解释)

进入菜单Reports/Tableau 结果显示：

THE TABLEAU

ROW (BASIS) X1 X2 X3 X4

1 ART 0.000 0.000 0.200 1.200 36.000

2 X2 0.000 1.000 0.600 -0.400 4.000

3 X1 1.000 0.000 -0.400 0.600 6.000

§Step6 菜单Reports/Peruse，所得结果如下：

进入菜单Reports/ Peruse 结果显示：

§Step7 菜单Reports/Show Colum，所得结果如下：(给出解释)

“DUAL PRICE”（对偶价格）列出最优单纯形表中判别数所在行的松弛变量的系数，表示当对应约束有微小变动时，目标函数的变化率，输出结果中对应每一个约束有一个对偶价格