《教案要点》PPT课件.ppt

《《教案要点》PPT课件.ppt》由会员分享，可在线阅读，更多相关《《教案要点》PPT课件.ppt（33页珍藏版）》请在三一办公上搜索。

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

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

3、声纳医生对病人诊断文字校对,让计算机来算,找函数的零点,预备知识秦九韶法对分法切线法,弦线法联合法其它方法实际例子,预备知识,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)在(x0,f(x0)处的切线方程是：,f(x0),y=f(x0)+?(x-x0

4、),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或绝对值足够小则找到，否则这十个小区间中必有一个两端的函数值是异号的。在此小区间中继续，即把它再十等分。直到有一个分点的函数值为0或绝对值足够小，或小区间的长度已足够短

5、的时取中点，结束。,找函数的零点,算法二:对分法:若连续函数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处的切线与x轴的交点的纵坐标:,y-f(a)=f(a)(x-a),横坐标:,0,这个c往往比a更靠近零

6、点.,算法三：切线法,选一端引切线，与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起。,算法四：弦线法,函数y=f(x)在区间a,b的两端异号，连接点(a,f(a),(b,f(b)的线段(弦)：,弦与x轴

7、交于点(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,转S3,否则转S2;S2:令ab-f(b)(b-a)/(f(b)-f(a),bb-f(b)/f(b),转S1;S3:

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

9、用计算机：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/2304,127/24,#,2.645751,32257/12192,选哪端？,3,1 121922,补充作业,分别用五种算法：秦九韶-霍纳法、对分法、切线法、弦线法和联合法找如下函数在指定区间内的零点。y=xsinx-0.7在6,7y=x3+3x2-2x-9在1,2,