非线性规划讲稿12交通系统工程ppt培训课件

《非线性规划讲稿12交通系统工程ppt培训课件》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、交通系统工程2021/9/20线性规划：目标函数线性函数约束条件非线性规划：目标函数非线性函数线性函数约束条件第四章非线性规划2021/9/20数学规划问题的分类若f(x),gi(x),hj(x)为线性函数，即为线性规划(LP)；若f(x),gi(x),hj(x)至少一个为非线性，即为非线性规划(NLP)；对于非线性规划，若没有gi(x),hj(x)即X=Rn,称为无约束非线性规划或无约束最优化问题；否则称为约束非线性规划或约束最优化问题。2021/9/20X*=(1,1)X2X102121X2X102121线性规划：如果最优解存在，它一定存在于其可行域的边界上…非

2、线性规划：如果最优解存在，它未必一定存在于其可行域的边界上，也可以出现在可行域的内部…2021/9/20例:2021/9/20三角形表示的是可行域同心圆表示的是目标函数的等值线最优解为（1/2，1/2）最优值为1/21/21/22021/9/20非线性规划方法概述微分学方法的局限性：实际的问题中，函数可能是不连续或者不可微的。需要解复杂的方程组，而方程组到目前仍没有有效的算法。实际的问题可能含有不等式约束，微分学方法不易处理。2021/9/20数值方法的基本思路：迭代给定初始点x0根据x0,依次迭代产生点列{xk}{xk}的最后一点为最优解{xk}有限{xk}无限{

3、xk}收敛于最优解2021/9/20迭代格式:xkxk+1pk称pk为第k轮搜索方向，tk为第k轮沿pk方向的步长。产生tk和pk的不同方法，形成了不同的算法。2021/9/20一、无约束的数学模型解法：一维搜索法(无约束极小点问题)最速下降法（无约束最优化问题）牛顿法拟牛顿法……2021/9/20一维搜索方法单峰函数值得注意的是单峰函数不一定可导，也不一定连续；严格凸函数及其许多推广都是单峰函数；另外，单峰函数有一个性质——通过在区间内相异两点函数值的计算就能划定极小点的位置。单峰函数举例2021/9/20搜索区间2021/9/20一维搜索方法搜索法发展的理由：在许多实

4、际问题中，目标函数不满足凸性，于是促使人们考虑直接从函数的特性出发，对局部最优解进行搜索。基本结构：初始点t(0)确定移动方向t(k)精度检查YN停止2021/9/20一维搜索方法——基本原理（1）通过比较搜索区间内两点的函数值，逐步缩短搜索区间。比如：（2）控制缩短率（每次留下的区间与原区间长度之比）的变化，使整体效益最佳。如何控制缩短率？？上述两个问题是有联系的。2021/9/20但由于事先不能估计t*的确切位置，于是考虑采取下面的对策：使所选点在搜索区间内处于对称位置——取点对称原则，这样无论去掉哪一段区间都差别不大。为了使搜索区间缩短的快一些，希望每次从原搜索区间

5、中去掉的部分大一些。假定选的两个内点偏向一侧，其中，则可能去掉较大的一段区间2021/9/20在上述原则下，为使去掉的区间长一些，就一次而论，应使两点尽量靠近区间中点，这样无论去掉哪一侧，都可使区间缩短近一半，但是，由于此次留下的内点相当靠近留下的区间的一侧，下一步再按对称原则增选内点时，在去掉的区间部分必然较小，总体效益不好。于是考虑采取如下对策，区间缩短率固定。由于取点对称，区间缩短率>0.5。按照取点对称和缩短率恒定两条原则，计算缩短率。2021/9/20区间缩小比例的确定：区间缩短比例为(t2-a)/(b-a)缩短比例为(b-t1)/(b-a)缩短比例满足：每次

6、插入搜索点使得两个区间[a,t2]和[t1,b]相等；每次迭代都以相等的比例缩小区间。0.618法t1t2ababt1t2退出前一页后一页一维搜索方法——0.618法2021/9/20确定[a,b],计算探索点t1=a+0.382(b-a)t2=a+0.618(b-a)是否是停止，输出t1否以[a,t2]为新的搜索区间是停止，输出t2否以[t1,b]为新的搜索区间退出前一页后一页如果给定下单峰区间[a,b]及控制误差，0.618法解题步骤如下：2021/9/20例：解：t1t230t1、第一轮：t1=1.146,t2=1.854t2－0>0.5退出前一页后一页2021/

7、9/202、第二轮：t2=1.146,t1=0.708t2－0=1.146>0.53、第三轮：t1=0.438,t2=0.708b-t1=1.146-0.438>0.51.8540tt2t11.4160tt2t1退出前一页后一页2021/9/204、第四轮：t2=0.876,t1=0.708b-t1=1.146-0.708<0.5输出：t*=t2=0.876为最优解，最优值为-0.079801.416tt1t2退出前一页后一页2021/9/20一般来说，0.618法的计算步骤如下：2021/9/200.618法中采用进退算法求