《教案要点》PPT课件

1、教案要点,文 件 名：051OR02.PPT；搜索论.XLS 上节习题：051ORL01.PPT 授课时间：第二讲 授课内容：搜索论（一） 预备知识：解析几何、微积分 难 点：迭代公式、使用条件、比较 重 点：几种找零点的方法：秦九韶法、对分法、切线法、弦线法、联合法、其它方法，算法及Excel 实现。 下节预习：找极值点的方法网站、参考书）。 复习可行解、基可行解，基及非基变量。,搜索论(Search Theory),绍兴文理学院工学院计算机系,搜索论,何谓搜索论 搜索论的应用 搜索策略 找零点,找极值点 0.618法 瞎子爬山法 后记,何谓“搜索论”,搜索论是顺应第二次世界大战中战争的需要

2、而出现的运筹学分支。主要研究在资源和探测手段受到限制的情况下，设计寻找某种目标的最优方案，及有关的理论和方法。 在第二次世界大战中，同盟国的空军和海军针对轴心国的潜艇活动，研究如何甄别、舰队运输和兵力如何部署等的过程中产生的。 战后搜索论在实际应用中也取得了不少成效，例如二十世纪六十年代，美国寻找在大西洋失踪的核潜艇“打谷者号”和“蝎子号”，以及在地中海寻找丢失的氢弹，都是成功应用搜索论的范例。,搜索论的应用,美军寻找在大西洋失踪的两艘核潜艇 美军寻找丢失的氢弹 找油田 找故障点 找零点 找极值点,找油田的应用,地质结构（李四光） 打探井 人造地震法,无功而返,有油,是水,搜索故障点,找漏气点

3、、断路点 编程中DEBUG 找暗堡、防空阵地 雷达、声纳 医生对病人诊断 文字校对,让计算机来算,找函数的零点,预备知识 秦九韶法 对分法 切线法,弦线法 联合法 其它方法 实际例子,预备知识,y=f(x)是闭区间a,b上的连续函数,在区间两端异号即：f(a)f(b)0, 则 有零点。,在开区间内必,a,(a,f(a),b,(b,f(b),会在端点吗？,不会！,零点唯一吗？,未必！,零点有奇数个吗？,未必！,函数与导数,连续函数在闭区间两端异号则 必有零点。,一个函数在它的导数不变号的区间内 。,在开区间内,函数y=f(x)在(x0,f(x0)处的切线斜率是：,严格单调,函数y=f(x)在(x

4、0,f(x0)处的切线方程是：,f(x0),y=f(x0)+ ? (x-x0),f(x0),函数与导数,连续函数在闭区间两端异号则 必有零点。,一个函数在它的导数不变号的区间内 。,在开区间内,严格单调,两点(x1,y1),(x2,y2)连线方程是：,函数y=f(x)在(x0,f(x0)处的切线方程是：,找函数的零点,算法一:秦九韶-霍纳法：区间a,b上连续函数f(x)若两端函数值f(a)f(b)0 (异号),则其内至少有一个零点。区间十等分。 如3,4中有根，查3.1,3.2,3.9处的函数值，若有一点为0或绝对值足够小则找到，否则这十个小区间中必有一个两端的函数值是异号的。在此小区间中继续

5、，即把它再十等分。直到有一个分点的函数值为0或绝对值足够小，或小区间的长度已足够短的时取中点，结束。,找函数的零点,算法二:对分法:若连续函数f(x)在区间a,b两端函数值f(a)f(b)0(异号),则其内至少有一个零点。区间对分 S1:令x(a+b)/2,若b-a,转S4,否则转S2; S2:若f(x)=0,转S4 ,否则转S3; S3:若f(x)f(a)0,令bx,否则令ax,转S1; S4:输出x,结束。,算法三：切线法,函数y=f(x)在x=a处的切线斜率：,a,(a,f(a),c=a-f(a)/f(a),f (a),切线过点(a,f(a),其方程是：,函数y=f(x)在x=a处的切线

6、与x轴的交点的纵坐标:,y-f(a)=f (a)(x-a),横坐标:,0,这个c往往比a更靠近零点.,算法三：切线法,选一端引切线，与x轴的交点会更“好”些！,算法三：切线法,选一端a引切线，与x轴的交点的横坐标c:,以c为新的a继续做，直到f(a)足够靠近0了为止。,算法三：切线法,S1:若f(a)f”(a)0,则ab, 转S2; S2:若|f(a)|,转S4; S3:aa-f(a)/f(a),转S2; S4:输出a,结束。,算法三：切线法,f(x)=x3+2x2-3x-7在1.8,1.9, f”(x)=6x+40,f(1.8)=0.088, 应从b起,但f(a)很接近0,从a起。,算法四：

7、弦线法,函数y=f(x)在区间a,b的两端异号，连接点(a,f(a),(b,f(b)的线段(弦)：,弦与x轴交于点(c,0)：,c点为新的b继续。,算法四：弦线法,画连接点(a,f(a),(b,f(b)的线段(弦),与x轴交于点(c,0);,若f(c)与f(a)异号,以a,c为新的区间继续做,。,算法四：弦线法,选一端引弦线,与x轴的交点替换另一端！,算法四：弦线法,缺点：有一头停滞不进。,f(b)f”(b)0,选b点：,算法五：联合法,如图同时用弦线法从左边，用切线法从右边，联合“夹攻”。,算法五：联合法,如f(a)f(b)0,从b出发。 具体算法： S1:若b-a,令x(a+b)/2,转S

8、3,否则转S2; S2:令ab-f(b)(b-a)/(f(b)-f(a), bb-f(b)/f(b),转S1; S3:输出x,结束。,找函数的零点,找函数的零点前面我们介绍了五种算法：秦九韶-霍纳法、对分法、切线法、弦线法和联合法。 其它还有抛物线法、林士谔-赵访熊法(劈因子法)、下降法等。进一步的研究可以参看计算方法方面的书。 在Excel中怎么做呢？用上述五种算法、用单变量求解、规划求解等。,思考,讨论一下有多少种方法求,用计算器、查表、手算 用计算机： 附件计算器 OfficeExcel 用计算机语言编程 求y=x2-7在2,3中的零点。,求7的平方根,计算器求,用计算机：附件计算器,用Excel的解法,利用函数MAX和MIN可以找到一批单元格中最大(小)者。利用“规划求解”也可解决大量求极值的问题。,求7的平方根,用计算机：OfficeExcel,用公式：=SQRT(7),求7的平方根,用计算机：OfficeExcel,用单变量求解、规划求解,求7的平方根,用计算机：OfficeExcel,秦九韶法 对分法 作图法逼近,求7的平方根,用切线法求y=x2-7在2,3中的零点即 。,3,2,6,8/3,8/3,1/9,16/3,127/48,127/48,1