规划模型专题二非线性规划精选文档.ppt
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_05.gif)
《规划模型专题二非线性规划精选文档.ppt》由会员分享,可在线阅读,更多相关《规划模型专题二非线性规划精选文档.ppt(60页珍藏版)》请在得力文库 - 分享文档赚钱的网站上搜索。
1、规划模型专题二非线性规划本讲稿第一页,共六十页第一部分第一部分 非线性规划非线性规划v 前面有老师介绍了线性规划问题,典型前面有老师介绍了线性规划问题,典型的问题的问题“下料问题下料问题”、“运输问题运输问题”等,这等,这些问题都比较简单。但实际中的问题不仅仅些问题都比较简单。但实际中的问题不仅仅是简单的线性规划问题,可能是比较繁杂的是简单的线性规划问题,可能是比较繁杂的非线性规划问题。非线性规划问题。下面我们从一个竞赛题目出发,以理解非下面我们从一个竞赛题目出发,以理解非线性规划的定义、建模过程及其求解过程。线性规划的定义、建模过程及其求解过程。本讲稿第二页,共六十页 在约在约1万米的高空的
2、某边长为万米的高空的某边长为160km的正方形区的正方形区域内,经常有若干架飞机作水平飞行,区域内每架域内,经常有若干架飞机作水平飞行,区域内每架飞机的位置和速度向量均由计算机记录其数据,以飞机的位置和速度向量均由计算机记录其数据,以便进行飞行管理。当一架欲进入该区域的飞机到达便进行飞行管理。当一架欲进入该区域的飞机到达区域边缘时,计算机记录其数据后,要立即计算并区域边缘时,计算机记录其数据后,要立即计算并判断是否会发生碰撞。若会发生碰撞,则应计算如判断是否会发生碰撞。若会发生碰撞,则应计算如何调整各架飞机(包括新进入的飞机)飞行的方向何调整各架飞机(包括新进入的飞机)飞行的方向角,以避免碰撞
3、,且使飞机的调整的幅度尽量小,角,以避免碰撞,且使飞机的调整的幅度尽量小,例例1 1995年全国数学建模年全国数学建模A题:飞行管理问题题:飞行管理问题一、例题讲解一、例题讲解本讲稿第三页,共六十页该题比较有意思的一句话是:该题比较有意思的一句话是:“使调整弧度最小使调整弧度最小”开放性的一句话,没有限制得很死,较灵活,开放性的一句话,没有限制得很死,较灵活,给参赛者的创新空间比较大一些,使得构建模型给参赛者的创新空间比较大一些,使得构建模型的目标函数表现形式很多,再加上模型求解方法的目标函数表现形式很多,再加上模型求解方法(算法)的多样性,从而可以呈现出五花八门的论(算法)的多样性,从而可以
4、呈现出五花八门的论文。文。本讲稿第四页,共六十页v不碰撞的标准为任意两架飞机的距离大于不碰撞的标准为任意两架飞机的距离大于8km;假设条件:假设条件:v飞机飞行的方向角调整幅度不应超过飞机飞行的方向角调整幅度不应超过 ;v(因飞机飞行的速度变化不大)所有飞机的飞行(因飞机飞行的速度变化不大)所有飞机的飞行 速度速度 v 均为均为800km/h;有时需要通过查阅文献、资料给出合理假设有时需要通过查阅文献、资料给出合理假设注:注:本讲稿第五页,共六十页v进入该区域的飞机在到达区域边缘时,与区域内进入该区域的飞机在到达区域边缘时,与区域内 飞机的距离应在飞机的距离应在60km以上;以上;v最多需考虑
5、六架飞机;最多需考虑六架飞机;v不必考虑飞机离开此区域后的状况。不必考虑飞机离开此区域后的状况。根据当年竞赛题目给出的数据,可以验证新进根据当年竞赛题目给出的数据,可以验证新进入的飞机与区域内的飞机的距离超过入的飞机与区域内的飞机的距离超过60公里。公里。根据当年竞赛题目给出的数据,可以验证区域根据当年竞赛题目给出的数据,可以验证区域内的飞机不超过架内的飞机不超过架(包括新进入的包括新进入的)。本讲稿第六页,共六十页v个人的想法不同,队友之间争执不下的情况下,若时间允个人的想法不同,队友之间争执不下的情况下,若时间允许,都可一一写到论文中去,建立的模型一、模型二许,都可一一写到论文中去,建立的
6、模型一、模型二;或者经讨论后,选择一个认为更合理的。费或者经讨论后,选择一个认为更合理的。费时较多的是计算(那时侯是自己编程解时较多的是计算(那时侯是自己编程解NLP)v现在看来,无论是构建模型,还是计算,都不太难。现在看来,无论是构建模型,还是计算,都不太难。v本例题未给出数据,将重点放在如何构建模型上本例题未给出数据,将重点放在如何构建模型上本讲稿第七页,共六十页解:解:(1)不考虑飞机的尺寸,用点代表飞机;不考虑飞机的尺寸,用点代表飞机;(2)已在区域内的已在区域内的5架飞机按给定的方向角作架飞机按给定的方向角作 直线飞行,则必不会碰撞,也不会发生直线飞行,则必不会碰撞,也不会发生 意外
7、;意外;(应该根据题目中所给出的数据简应该根据题目中所给出的数据简 单的单的 验证一下验证一下)(3)飞机调整方向角的过程可在瞬间完成飞机调整方向角的过程可在瞬间完成,(不不 计调整方向所花费的时间计调整方向所花费的时间)。为解决该问题,补充假设:为解决该问题,补充假设:本讲稿第八页,共六十页变量、参数的符号假设变量、参数的符号假设(为了建模)(为了建模)在区域内飞行在区域内飞行飞飞时间(可以根据数据算出来)时间(可以根据数据算出来)本讲稿第九页,共六十页说明:说明:用初等数学的知识即可完成,用初等数学的知识即可完成,思考:思考:在哪个时间段某两架飞机可能相撞?在哪个时间段某两架飞机可能相撞?
8、In fact,我们只需考虑两架飞机我们只需考虑两架飞机同时同时在区域内在区域内飞行时的情况,也就是说,飞行时的情况,也就是说,才是同在区域内的状况。才是同在区域内的状况。记为记为本讲稿第十页,共六十页根据题目条件,需计算第根据题目条件,需计算第 架飞机之间架飞机之间的的最短距离最短距离本讲稿第十一页,共六十页为此,我们可以给出原问题的模型如下:为此,我们可以给出原问题的模型如下:思考:思考:是否还有其他的表达形式?是否还有其他的表达形式?非线性规非线性规划模型划模型分别从目标函数和约束条件角度思考分别从目标函数和约束条件角度思考本讲稿第十二页,共六十页首先思考一下目标函数是否有其它的表达?首
9、先思考一下目标函数是否有其它的表达?同学们首先想到的可能是同学们首先想到的可能是Oh,Sorry!有正有负有正有负抵消抵消本讲稿第十三页,共六十页最小一乘最小一乘 法法最小二乘最小二乘 法法 因最小一乘法带绝对值,不好计算,以上两式,因最小一乘法带绝对值,不好计算,以上两式,比较而言,后者较好。比较而言,后者较好。为为了了避避免免抵抵消消or本讲稿第十四页,共六十页有的队员这样考虑:有的队员这样考虑:令为令为 ,转化为二次规划转化为二次规划用到经验模型中确定参数的近似准则用到经验模型中确定参数的近似准则:就所有飞机而言,就所有飞机而言,让调整弧度最大的让调整弧度最大的即即尽可能小,尽可能小,C
10、hebshavf 准则准则本讲稿第十五页,共六十页 全国数学建模竞赛开展之初全国数学建模竞赛开展之初,竞赛题大多是竞赛题大多是优化类型的题目优化类型的题目,那时的计算机性能没有现在好那时的计算机性能没有现在好,速度也没有现在快速度也没有现在快,因此在模型的计算方面花的因此在模型的计算方面花的培训时间比较多。培训时间比较多。虽然目前可供选择的软件比较多,但是必虽然目前可供选择的软件比较多,但是必要的优化知识是必须掌握的。要的优化知识是必须掌握的。本讲稿第十六页,共六十页其次讨论一下约束条件是否有其它表达?其次讨论一下约束条件是否有其它表达?若考虑区域内不发生碰撞若考虑区域内不发生碰撞(若时间允许
11、,也可若时间允许,也可以考虑出了区域的情况,另外建模以考虑出了区域的情况,另外建模)、错层飞行、错层飞行(飞高或者飞低避免碰撞飞高或者飞低避免碰撞),进行模型的进一步改,进行模型的进一步改进,重点应放在解决问题的方法上。进,重点应放在解决问题的方法上。本讲稿第十七页,共六十页本讲稿第十八页,共六十页 无论选择哪一种表达,怎样考虑约束条件,目无论选择哪一种表达,怎样考虑约束条件,目标函数都不可能是线性的。标函数都不可能是线性的。现在看来,那年的题目建模不难,只是在现在看来,那年的题目建模不难,只是在条件的考虑上和建模中目标函数的表达方面较条件的考虑上和建模中目标函数的表达方面较难一点。但在当时不
12、然。难一点。但在当时不然。是一个带不等式约束的非线性规划问题。是一个带不等式约束的非线性规划问题。而且不可能转化成线性的形式。而且不可能转化成线性的形式。本讲稿第十九页,共六十页 若目标函数或约束条件中含有非线性函数,则若目标函数或约束条件中含有非线性函数,则称这种模型问题为称这种模型问题为非线性规划非线性规划(Non-Linear Prog-ramming),简记为),简记为NLP。NLP的一般形式的一般形式 其中,其中,中至少有一个是中至少有一个是 非线性函数。非线性函数。本讲稿第二十页,共六十页 无约束极值问题是无约束极值问题是NLP的一种特殊形式的一种特殊形式如如数据拟合的最小二乘问题
13、就是一个无约束极数据拟合的最小二乘问题就是一个无约束极值问题。值问题。其思想是:观察点(实验数据点)到曲线的其思想是:观察点(实验数据点)到曲线的距离的平方之和最小距离的平方之和最小二、无约束极值问题二、无约束极值问题本讲稿第二十一页,共六十页理论上无约束极值问题可化成求解理论上无约束极值问题可化成求解 即解一个即解一个 n 元方程组,且往往是非线性方程元方程组,且往往是非线性方程组。组。而一般说来,非线性方程组的求解并不比求而一般说来,非线性方程组的求解并不比求无约束极值容易。无约束极值容易。本讲稿第二十二页,共六十页求解无约束极值问题的基本方法:求解无约束极值问题的基本方法:迭代法迭代法
14、从一个给定的初始可行点从一个给定的初始可行点 出发,依次出发,依次产生一个可行点列产生一个可行点列的一个极小值点的一个极小值点,恰好是恰好是使得某个使得某个基本思路:基本思路:或或收敛于收敛于,称具有这种性质的算法称具有这种性质的算法是是收敛的收敛的.本讲稿第二十三页,共六十页由由迭代到迭代到时时,记记即即其中向量其中向量为为搜索方向搜索方向,实数实数称为称为步长步长,确定以后确定以后,由由可唯一地确定可唯一地确定从从出发就可确定点列出发就可确定点列本讲稿第二十四页,共六十页迭代的方法很多迭代的方法很多,各种迭代法的区别在于选取各种迭代法的区别在于选取的方式不同的方式不同,而而尤为关键尤为关键
15、.一般要求一般要求递减递减,具有这种性质的算法叫做具有这种性质的算法叫做下降下降算法算法.下面介绍的迭代法均为下降算法下面介绍的迭代法均为下降算法本讲稿第二十五页,共六十页若已得若已得下降得最多下降得最多,并确定了并确定了的可行下降方向的可行下降方向上选取步长上选取步长则在射线则在射线使使且使且使即求即求求求的过程称为的过程称为一维搜索一维搜索.1.下降算法下降算法本讲稿第二十六页,共六十页于是一维搜索归结为求解一维无约束极值问题于是一维搜索归结为求解一维无约束极值问题:其算法有其算法有Newton法、平分法、黄金分割法法、平分法、黄金分割法(0.618法)、分数法(法)、分数法(Fibona
16、cci法)、抛物线法)、抛物线法(二次插值法)等,法(二次插值法)等,前两种算法需计算前两种算法需计算的导数,的导数,后三种算法只需计算后三种算法只需计算的函数值。的函数值。下面仅介绍下面仅介绍Newton法,对其他方法的了解可参法,对其他方法的了解可参考有关书籍。考有关书籍。本讲稿第二十七页,共六十页按按 给定初始可行点给定初始可行点 和控制误差和控制误差 ,迭代格式迭代格式迭代,迭代,当当时,时,即求得即求得的最优解的近似解的最优解的近似解停止计算。停止计算。Newton 法介绍法介绍本讲稿第二十八页,共六十页 一个好的算法必须以较快的速度收敛到一个好的算法必须以较快的速度收敛到最优解。最
17、优解。设算法产生的点列设算法产生的点列收敛于最优解收敛于最优解若存在若存在及及使使则称则称为为 p 阶收敛的。阶收敛的。该算法也是该算法也是 p 阶收敛的。阶收敛的。本讲稿第二十九页,共六十页 称为称为线性收敛;线性收敛;当当且且时,时,称为称为超线性收敛;超线性收敛;当当时,时,称为称为平方收敛;平方收敛;当当时,时,本讲稿第三十页,共六十页一个算法是否收敛,一个算法是否收敛,往往与往往与的选取有关的选取有关 若当若当充分接近充分接近时,时,由算法产生的点列由算法产生的点列才收敛于才收敛于则称该算法为具有局部收敛则称该算法为具有局部收敛性的算法;性的算法;若对若对则称该算法为具有全局收敛性的
18、算法。则称该算法为具有全局收敛性的算法。由算法产生由算法产生 的点列的点列均收敛均收敛于于本讲稿第三十一页,共六十页 Newton法是平方收敛的,具有局部收敛性;法是平方收敛的,具有局部收敛性;抛物线法是超线性收敛的,具有全局收敛性;平抛物线法是超线性收敛的,具有全局收敛性;平分法、黄金分割法、分数法是线性收敛的,具有分法、黄金分割法、分数法是线性收敛的,具有全局收敛性。全局收敛性。常见一维搜索算法的收敛性常见一维搜索算法的收敛性本讲稿第三十二页,共六十页当当具有多个极小值点时,具有多个极小值点时,则算法求得则算法求得的往往是的往往是的一个局部极小值点。的一个局部极小值点。此时可此时可改变改变
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 规划 模型 专题 非线性 精选 文档
![提示](https://www.deliwenku.com/images/bang_tan.gif)
限制150内