教案要点 文 件 名：051OR03.PPT；搜索论.XLS。带《优选法平话》 上节习题：第三讲 授课班级：计算机系信管031，032班

Presentation on theme: "教案要点 文 件 名：051OR03.PPT；搜索论.XLS。带《优选法平话》 上节习题：第三讲 授课班级：计算机系信管031，032班"— Presentation transcript:

1 教案要点 文 件 名：051OR03.PPT；搜索论.XLS。带《优选法平话》 上节习题：第三讲 授课班级：计算机系信管031，032班
授课内容：搜索论（二） 预备知识：解析几何、微积分 难 点：使用条件，0.618及瞎子爬山法 重 点：几种找极值点的方法：微积分法、0.618法、瞎子爬山法、其它方法，算法及Excel 实现。 下节预习：教材：线性规划的提出及其图解法。

2 优选法 工学院计算机系 绍兴文理学院

3 思考 讨论一下有多少种方法求 ①用计算器、查表、手算…… ②用计算机： 附件计算器 OfficeExcel 用计算机语言编程
③求y=x2-7在[2,3]中的零点。

4 求7的平方根 计算器求 用Windows：附件计算器

5 求7的平方根 用计算机：OfficeExcel 用公式：=SQRT(7)

6 求7的平方根 用计算机：OfficeExcel 用单变量求解、规划求解

7 求7的平方根 用计算机：OfficeExcel 秦九韶法 对分法 作图法逼近

8 求7的平方根 选哪端？ 3 3 2 6 8/3 8/3 1/9 16/3 127/48 127/48 1/2304 127/24 ####
用切线法求y=x2-7在[2,3]中的零点即 。 选哪端？ 3 3 2 6 8/3 8/3 1/9 16/3 127/48 127/48 1/2304 127/24 #### 　 1 　 121922 32257/12192

9 求极值 微积分找极值点 0.618法 瞎子爬山法 后记

10 微积分中的例题 一块边长为a的正方形铁片，四角裁掉四块小正方形后做成一个无盖的长方体铁盒，如何使它的容积最大？ x=?时，V=max
V=(a-2x)2x V = (a-2x)2x, V ’ =(4x3-4ax2+a2x) ’ =12x2-8ax+a2, 令V ’ = 0，得：x = a / 2 或x = a / 6 ，前者不合题意，舍去。 当 x= a / 6 时 max V = 2a3 / 9 x=?时，V=max x=a/6时,V=max

11 找函数的极值 找函数的极值与找导函数的零点有关，我们可以先用上面讲的算法：秦九韶-霍纳法、对分法、切线法、弦线法和联合法等之一找导函数的零点。 其它方法还有分数法、0.618法、抛物线法、分批试验法等。 进一步的研究可以参看《最优化方法》、《优选学》方面的书。 在Excel中怎么做呢？ 用“规划求解”。

12 优选法的实例 单因素优选法：炸油条、蒸馒头： 如蒸馒头的关键技术之一是“发面”，尤其是碱的用量:应在40-120g之间，
北京某毛纺厂染色工艺中原起染温度为40℃,应提高,最高是100℃, 取(40+100)/2=70℃试,好点,再提. 取(70+100)/2=85℃试,过高,降低.

13 优选法的实例 如北京电子管厂钼丝退火温度应介于1400~1600℃最佳温度是多少？ 方法一:1400、1410、1420、1430、
单因素优选法:满意为标准，对分法。 另一类是求极值问题:对分法并不能确定继续试验的方向。 如北京电子管厂钼丝退火温度应介于1400~1600℃最佳温度是多少？ 方法一:1400、1410、1420、1430、 ……1600℃[每隔10℃一试]。 方法二、1400、1450、1500、1550、1600℃[每50℃一试][1450,1500] [1450,1500]中每10℃一试，……。

14 优选法的简介 均分法 来回调试法(淘汰法) 分数法、0.618法、抛物线法、瞎子爬山法、……中外数学家提出许多行之有效的方法及其理论依据。
单因素优选法求极值问题: 均分法 来回调试法(淘汰法) 分数法、0.618法、抛物线法、瞎子爬山法、……中外数学家提出许多行之有效的方法及其理论依据。

15 算法六：0.618法 只要把区间划分得足够小,可假设函数在[a,b]中是“单峰”的。在此我们只准备讨论求极大值。“对分”不行。
但若a<c<d<b, f(c)<c(d),则可抛弃区间[a,c),而在[c,b]中继续寻找。 c d a b

16 算法六：0.618法 为了“可持续发展”,要c,d处于对称的地位,不妨设b-a=1,d-a=x,则b-d=1-x,还希望: 1-x x c

17 算法六：0.618法 第一个试验点:(大-小)×0.618+小；下一个试验点：大+小-中
此法又叫“黄金分割法”，尤其适用于连函数表达式都不知道的情况。 是当年华罗庚推广 “优选法”的 重点之一. a b c d

18 算法七:瞎子爬山法 对于多元函数，尤其是连函数表达式都不知道的情况求极值的一个方法叫：“瞎子爬山法”。
以求二元函数极大值为例：从(a,b)出发确定步长h,比较周围四点的函数值f(a,b+h), f(a,b-h),f(a+h,b),f(a-h,b),朝其中最大的一点前进一步，然后在新点的四周（只需找三点）再加比较，确定下一步往哪里走……。由于此法酷似“瞎子爬山”故有此名。

19 算法七:瞎子爬山法 用“瞎子爬山法”求二元函数z=f(x,y)
=-0.3x2-0.6xy-0.9y2+0.42x+0.78y+0.799的极值：

20 算法七:瞎子爬山法 如果每次都不是光在正东、南、西、北四面，而是加上东南、东北、西南、西北共八方比较，即比较：f(a+h,b), f(a+h,b+h),f(a,b+h),f(a-h,b+h),f(a-h,b), f(a-h,b-h),f(a,b-h),f(a+h,b-h)后决定前进方向，这样登顶可能更快，另外如果两次都选了西北方向(山脊)，可以考虑加长步长，而如果八方都没有更好了可以考虑步长减半，这叫“变步长” 。这些是 “瞎子爬山法”的改进。

21 算法八:抛物线法 0.618法只比较两点的好坏，历史的数据已弃置不用了，改进的方法之一：三点x1<x2<x3,可以定了曲线上的三点： (x1,f(x1)), (x2,f(x2)), (x3,f(x3))。 而过这三点的抛物线[插值公式]是：

22 算法八:抛物线法 当f(x2)最大时，该抛物线开口向下，它的顶点是： f(x4)也较大，若不满意再找三点作抛物线，求它的顶点……。

23 用Excel的解法 利用函数MAX和MIN可以找到一批单元格中最大(小)者。利用“规划求解”也可解决大量求“条件极值”的问题。

24 课堂练习 班级 姓名 学号_______ 求y=x2-2在[0,2]中的零点即 。 解写成分数形式，精确到1/10000。

25 求2的平方根 用切线法求y=x2-2在[1,2]中的零点即 。 选哪端？ 2 2 2 4 3/2 3/2 1/4 3 17/12 17/12 1/144 17/6 577/408 1.4142 1/4082

26 作业 求5的立方根； 求 sin x = 0在[3,4]中的一个根； 求 cos x = x 在[0,1]中的一个根.
预习线性规划的图解法.