运筹学第7节.ppt

《运筹学第7节.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第七节一维搜索一维搜索要求沿射线X(k+1)=X(k)+λkP(k)搜索，使目标函数f(X)极小：一维搜索性质：在搜索方向上所得到的最优点处的梯度和该搜索方向正交。一、斐波那契法（分数法）设y=f(x)是区间[a,b]上的下单峰函数，在此区间内，有唯一极小点t*。单峰函数：在定义域内只有一个极值点的连续函数。下单峰函数：在定义域内只有一个极小值点的连续函数。在区间[a,t*]中严格单调下降，而在区间[t*,b]中严格单调上升，则称为区间[a,b]上的下单峰函数。上单峰函数：在定义域内只有一个极大值点的连续函数。在区间[a

2、,t*]中严格单调上升，而在区间[t*,b]中严格单调下降，则称为区间[a,b]上的上单峰函数。在区间[a,b]内任取两点a1和b1，a1

3、点t*必在区间[a,b1]内。f(a1)≥f(b1)，极小点t*必在区间[a1,b]内。只要在区间[a,b]内任取两个不同点，并算出它们的函数值加以比较，就可以把搜索区间所小为[a1,b]或[a1,b]，因为所小后的区间仍包含极小点。只要在区间[a,b]内任取两个不同点，并算出它们的函数值加以比较，就可以把搜索区间缩小为[a1,b]或[a1,b]。要进一步缩小搜索区间，只需在缩小后的区间内再取一点，并与f(a1)或f(b1)，比较函数值大小。按照上述方法，随着计算函数值次数的增加，区间变得越来越小，从而越接近极小点。由此

4、看出：区间缩短率和函数值计算次数之间存在一定的关系。在区间内插入两点，并计算函数值进行比较，从而可将搜索区间缩小，其后只需在缩小后的区间内插入一点即可将搜索区间进一步缩小。aba1b1[a,b1][a1,b]f(a1)f(b1)在[a1,b]内再插入一点同f(b1)比较，从而使[a1,b]进一步缩小。下面来讨论区间缩短率和函数值计算次数之间的关系。1.递推公式令Fn表示计算n个函数值能将区间长度缩短为1的最大原区间长度，则F

5、0=1：因为不计算任何函数值不能够使区间缩小，故原区间长度必须是1。F1=1：因为每次要缩小搜索区间都要计算两次函数值，而只计算一次函数值无法将区间缩短，故原区间长度必须是1。下面来讨论长度为2个单位长度的区间需要插入几个点才能缩短为1。01a1b1[a,b1][a1,b][a,b1]+[a1,b]>[a,b]缩小后的区间一般要大于原区间的一半01a1b1[a,b1][a1,b]ε足够小，缩小后的区间可接近原区间的一半中间点中间点-ε中间点+ε对称搜索法长度为2的区间缩短到1需要插入2个点。①②03缩小后的区间可接近1中

6、间点①②③中间点2对称搜索法长度为3的区间需要插入几个点才能缩短为1。区间缩小为2，可采取区间长度为2的插入方法长度为3的区间缩短到1需要插入3个点。长度为2的区间缩短到1需要插入2个点。长度为3的区间缩短到1需要插入3个点。F2=2：插入2个点可使长度缩短为1的最大原区间长度为2。04长度为4的区间缩短到1需要插入4个点。①中间点3对称搜索法长度为4的区间需要插入几个点才能缩短为1。区间缩小为3，可采取长度为3的插入方法长度为3的区间缩短到1需要插入3个点。长度为4的区间缩短到1需要插入4个点。F3=3：插入3个点可使

7、长度缩短为1的最大原区间长度为3。05长度为5的区间缩短到1也只需要插入4个点。①中间点3对称搜索法长度为5的区间需要插入几个点才能缩短为1。区间缩小为3，可采取长度为3的插入方法06长度为6的区间缩短到1也只需要插入5个点。①中间点4对称搜索法长度为6的区间需要插入几个点才能缩短为1。区间缩小为4，可采取长度为4的插入方法长度为4的区间缩短到1需要插入4个点。F4=5：插入4个点可使长度缩短为1的最大原区间长度为5。长度为5的区间缩短到1需要插入4个点。长度为6的区间缩短到1需要插入5个点。F0=1F1=1F2=2F3

8、=3F4=5Fn=Fn-1+Fn-2，n≥2n0123456789101112Fn1123581321345589144233斐波那契数2.缩短率最大长度为Fn的区间经过插入n个点并比较其函数值后可缩短为1，称1/Fn为最大缩短率。从而长度为L的区间经过插入n个点并比较其函数值后，其区间最大可缩短为：L/Fn长度为L