最优化思想—黄金分割和优选法课件

1、温州大学数学与信息科学学院 黄忠裕2012年12月16日浙江省中小学教师专业发展培训项目高中数学知识拓展指导 选修3-1：数学史选讲 选修3-2：信息安全与密码 选修3-3：球面上的几何 选修3-4：对称与群 选修3-5：欧拉公式与闭曲面分类 选修3-6：三等分角与数域扩充 选修4-1：几何证明选讲 选修4-6：初等数论初步 选修4-2：矩阵与变换 选修4-7：优选法与试验设计初步 选修4-3：数列与差分 选修4-8：统筹法与图论初步 选修4-4：坐标系与参数方程 选修4-9：风险与决策 选修4-5：不等式选讲 选修4-10：开关电路与布尔代数 浙江普通高中知识拓展类选修课程实施方案必修拓展课

2、程从国家课程选修模块中选用：数学1-1，数学1-2，数学2-1、数学2-2、数学2-3大学初级课程：微积分、线性代数、空间解析几何 介绍学科最新成果的课程：现代数学概览、分形几何 学科应用性课程：数学史选讲、信息安全与密码、球面上的几何、几何证明选讲、矩阵与变换、数列与差分、坐标系与参数方程、不等式选讲、初等数论初步、优选法与试验设计初步、风险与决策、开关电路与布尔代数、生活中的数学、数学与经济 最优化思想黄金分割和优选法斐波那契数列及其应用斐波那契计算之书兔子问题（1202年）如果每1对成兔每月生1对幼兔，幼兔经过2个月后成为成兔，即开始繁殖，问年初的1对幼兔经过1年后能繁殖成多少对兔子？假

3、定这一过程兔子不发生任何死亡。 由兔子问题抽象得递推关系本月底幼兔总对数=上上个月底兔子总对数所以：本月底兔子总对数=上月底兔子总对数+上上个月底兔子总对数。用un表示第n个月底兔子的总对数 ，则有斐波那契数列。(A.Girard,1634) 为方便，补充定义u0=1。“走楼梯”问题 某人要走一架n个台阶的楼梯，某人每步向上走1个台阶或2个台阶。un表示该人从地面向上走到第n个台阶时所有不同的走法种数，求un。 n阶楼梯的所有走法un1(1)12(11),(2)23(111),(21),(12)34(1111),(211),(121),(112),(22)55(11111),(2111),(1

4、211),(1121),(1112),(221),(212),(122)86n按第一步的走法分类un=un-1+un-2(n3)；u1=1,u2=2。斐波那契数列解法1：n阶楼梯的所有走法un1(1)12(11)； (2)23(111)；(21),(12)34(1111)；(211),(121),(112)；(22)55(11111);(2111),(1211),(1121),(1112)(221),(212),(122)8n贾宪三角形表达式E.Piccioli，1916 De Moivre提出，J.P.M.Binet 1843年证明，世称Binet公式黄金分割率，它是美的标准之一，也是优选法

5、的理论基础。该数列极限为该数列相邻两项之比构成的“比值”数列通项公式黄金分割的美（黄金比0.618）人体各部分的比 肚 脐 ： （头脚） 印堂穴： （口头顶） 肘关节： （肩中指尖） 膝 盖： （髋关节足尖）著名建筑物中各部分的比 埃及的金字塔，高（137米）与底边长（227米）之比为0.629.古希腊的巴特农神殿，塔高与工作厅高之比为3405530.615风景照片中 地平线的位置美观矩形正五角星中的线段比（正五角星很美） 舞台报幕者的最佳站位 在整个舞台宽度的0.618处较美 小说、戏剧、战争的高潮出现：在整个作品的0.618处较好华罗庚先生证明了：黄金分割点具有再生性。 黄金分割点的再生性

6、，是“黄金分割”之所以美的数学依据。黄金分割为什么美为什么不是0.5的分割点让人感觉愉悦，而是0.618的分割点让人感觉愉悦呢？因为0.618的分割点反映了“恰到好处的和谐”。 即： 如果是 的黄金分割点， 是 的黄金分割点， 与 当然关于中点 对称。特殊的是， 又恰是 的黄金分割点。同样，如果 是 的黄金分割点，则 又恰是 的黄金分割点，等等，一直延续下去 。（再生）0.618优选法（黄金分割法）问题：做2千克大米的干饭，放多少水最好吃？（1000g-2000g)“饭好吃f(x)”是“放水量x”的函数；但不知其具体表达式，或即使知道但太复杂；函数f(x)有何特点？单峰（谷）函数不能用数学方法

7、寻找单峰函数的最优点，怎么办？.通过作试验的方法来寻找最佳点。优选法是以最少的试验次数迅速找到最佳点的试验方法。这是最优化一种新的思维方法！问题：做2千克大米的干饭，放多少水最好吃？（1000g-2000g)最“笨”的方法是分别加入1001克，1002克，2000克，做1千次试验，就能发现最佳方案。华罗庚证明了，每次取试验区间的0.618处去做试验的方法，才是最好的，这种优选法称为“黄金分割法”或“0.618法”。18黄金分割法步骤：用一有刻度的纸条表达1000克2000克。 在这纸条长度的0.618的地方C划一条线，也就是按1618克做第一次试验。然后把纸条对折，前一条线落在下一层纸的地方C

8、/，再划一条线（1382克处），再按1382克做第二次试验。 把两次试验结果比较，如果1618克的效果较差（坏点），就把1618克以外的一段纸条剪去，反之就把1382克以外的一段剪去。 再把剩下的纸条对折，纸条上剩下的那条线落在下一层纸的地方C/，再划一条线（黄金分割点），这条线在 1236克处。按1236克C/做第三次试验。把1236克处C/和1382克C/的试验效果比较，如果1236克C/的效果较差，就把1236克C/以外的短的一段纸条剪去。再对折剩下的纸条，找出第四次试验点1472克。按1472克做试验后，与1382克C/的效果比较，再剪去效果较差点以外的短的一段纸条。再对折寻找下一次试

9、验点，一次比一次接近我们的需要，直到达到我们满意的精确度。 注意，每次剪掉的都是效果较差点以外的短纸条，保留下的是效果较好的部分，而每次留下纸条的长度是上次长度的0.618倍。因此，纸条的长度按0.618的k次方倍逐次减小，以指数函数的速度迅速趋于0。所以，“0.618法”可以较快地找到满意的点。 事实上，当纸条长度已经很小时，纸条上的任一个点都可以作为“满意”的点了，因为最优点就在纸条上，你取的点与最优点的误差一定小于纸条的长。1985年6月12日华罗庚先生在日本的最后一场演讲（75岁）“工作到人生的最后一刻”归纳：0.618优选法（黄金分割法）问题：做2千克大米的干饭，应该放多少水？（10

10、00g-2000g)寻找单峰（谷）函数（不知其具体表达式或太复杂）的最优点.通过作试验的方法寻找最佳点优选法是以最少的试验次数迅速找到最佳点的试验方法。操作过程：第一个试验点x1=a+(b-a)0.618，第二个试验点x2=a+b-x1；对比x1,x2处结果，裁去“坏点”外边的部分；以此类推；在确定第n个试点xn时，如果存优范围内相应的好点是xm，那么有xn=小+大-xm.称“加两头，减中间”来确定下1个试点。经过n次试验后留下的区间长为原区间长的0.618n-1（精度）。0.618法试点为什么这样选择？第一、第二次试点选择的原则：1、公平原则；使两个试点关于区间a,b的中点对称2、继承原则每

11、次舍去的区间占舍去前的区间的比例数相同。据上述原则求出第1、第2次试点的位置线段a,b的黄金分割点0.618法（黄金分割法）25 0.618这个“黄金比”能产生“优选法”，这告诉我们，美的东西与有用的东西之间，常常是有联系的。由此再反观0.618的分割点为什么在许多场合都反映了“恰到好处的和谐”。其数学依据就是“黄金分割点的再生性”。数学的美，在于数学思想深刻之美。分数法例：在配置某种清洗液时，需要加入某种材料。经验表明，加入量大于130ml肯定不好。用150ml的锥形量杯计量加入量，该量杯的量程分为15格，每格代表10ml。用试验法找出这种材料的最优加入量。能用0.618法吗？如果用0.61

12、8法，算出的试点不是10ml的整数倍，此法不能用。采用分数法，借助Fibonacci数列来处理。分数法的操作 把实验区间0,130分成13等分，分点依次设为1,2,3,12。选分数8/13作为黄金分割数的近似值。第一个试点为8，第二个为5，若8好，则去掉0,5，剩下5，13；8已试过，在10处做第3个试验，若还是8好，去掉10,13，剩下5，10；在7处做第四个试验，若7比8好，去掉8，10，剩下5，8；在6做第五个试验，如6比7好，则6为最佳点。五次试验后，精度为1/13。 分数法现实中，由于受时间、人力等影响，往往使试验次数受到限制，此时采用分数法可以达到较好的效果。分数法与0.618法的本质是相同的。有两种情况：1.可能的试点总数正好是某一个(Fn+1-1)；2.可能的试点总数大于某一(Fn-1)，而小于(F