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

1、温州大学数学与信息科学学院温州大学数学与信息科学学院 黄忠裕黄忠裕20122012年年1212月月1616日日浙江省中小学教师专业发展培训项目浙江省中小学教师专业发展培训项目高中数学知识拓展指导高中数学知识拓展指导 选修选修3-13-1：数学史选讲：数学史选讲 选修选修3-23-2：信息安全与密码：信息安全与密码 选修选修3-33-3：球面上的几何：球面上的几何 选修选修3-43-4：对称与群：对称与群 选修选修3-53-5：欧拉公式与闭曲面分类：欧拉公式与闭曲面分类 选修选修3-63-6：三等分角与数域扩充：三等分角与数域扩充 选修选修4-14-1：几何证明选讲：几何证明选讲 选修选修4-6

2、4-6：初等数论初步：初等数论初步 选修选修4-24-2：矩阵与变换：矩阵与变换 选修选修4-74-7：优选法与试验设计初步：优选法与试验设计初步 选修选修4-34-3：数列与差分：数列与差分 选修选修4-84-8：统筹法与图论初步：统筹法与图论初步 选修选修4-44-4：坐标系与参数方程：坐标系与参数方程 选修选修4-94-9：风险与决策：风险与决策 选修选修4-54-5：不等式选讲：不等式选讲 选修选修4-104-10：开关电路与布尔代数：开关电路与布尔代数 浙江普通高中知识拓展类选修课程实施方案浙江普通高中知识拓展类选修课程实施方案必修拓展课程从国家课程选修模块中选用：必修拓展课程从国家

3、课程选修模块中选用：数学数学1-11-1，数学，数学1-21-2，数学，数学2-12-1、数学、数学2-22-2、数学、数学2-32-3大学初级课程：大学初级课程：微积分、微积分、线性代数、空间解析几何线性代数、空间解析几何 介绍学科最新成果的课程：介绍学科最新成果的课程：现代数学概览、分形几何现代数学概览、分形几何 学科应用性课程：学科应用性课程：数学史选讲、信息安全与密码、数学史选讲、信息安全与密码、球面上的几何、球面上的几何、几何证明选讲、矩阵与变换、数列与差分、几何证明选讲、矩阵与变换、数列与差分、坐标系与参数方程、坐标系与参数方程、不等式选讲、不等式选讲、初等数论初步、初等数论初步、

4、优选法与试验设计初步、优选法与试验设计初步、风险与决风险与决策、开关电路与布尔代数、策、开关电路与布尔代数、生活中的数学、生活中的数学、数学与经济数学与经济 最优化思想最优化思想黄金分割和优选法黄金分割和优选法斐波那契数列及其应用斐波那契数列及其应用 斐波那契斐波那契计算之书计算之书兔子问题兔子问题（12021202年）年）如果每如果每1 1对成兔每月生对成兔每月生1 1对幼兔，幼兔经对幼兔，幼兔经过过2 2个月后成为成兔，即开始繁殖，个月后成为成兔，即开始繁殖，问年初的问年初的1 1对幼兔经过对幼兔经过1 1年后能繁殖成多年后能繁殖成多少对兔子？少对兔子？假定这一过程兔子不发生任何死亡。假定

5、这一过程兔子不发生任何死亡。由兔子问题抽象得递推关系由兔子问题抽象得递推关系本月底幼兔总对数本月底幼兔总对数=上上个月底兔子总对数上上个月底兔子总对数所以：本月底兔子总对数所以：本月底兔子总对数=上月底兔子总对数上月底兔子总对数+上上个月底兔子总对数。上上个月底兔子总对数。用用u un n表示第表示第n n个月底兔子的总对数个月底兔子的总对数 ，则有，则有)3,2,1(.2,11221nuuuuunnn斐波那契数列。斐波那契数列。(A.Girard,1634)为方便，补充定义为方便，补充定义u0=1。“走楼梯走楼梯”问题问题 某人要走一架某人要走一架n个台阶的楼梯，某人每步个台阶的楼梯，某人每

6、步向上走向上走1个台阶或个台阶或2个台阶。个台阶。un表示该人从地面向上走到第表示该人从地面向上走到第n个台阶时个台阶时所有不同的走法种数，求所有不同的走法种数，求un。nn-1n-24321地面n n阶阶楼梯的所有走法楼梯的所有走法u un n1 1(1)(1)1 12 2(11),(2)(11),(2)2 23 3(111),(21),(12)(111),(21),(12)3 34 4(1111),(211),(121),(112),(22)(1111),(211),(121),(112),(22)5 55 5(11111),(2111),(1211),(1121),(1112),(111

7、11),(2111),(1211),(1121),(1112),(221),(212),(122)(221),(212),(122)8 86 6 n n nn-1n-24321地 面当 地 面 看，在 这 上 面 还 有（n-1）个 台 阶nn-1n-24321地 面当 地 面 看，在 这 上 面 还 有（n-2）个 台 阶按第一步的按第一步的走法分类走法分类un=un-1+un-2(n3)；u1=1,u2=2。斐波那契数列斐波那契数列解法解法1：n n阶阶楼梯的所有走法楼梯的所有走法u un n1 1(1)(1)1 12 2(11)(11)；(2)(2)2 23 3(111)(111)；(2

8、1),(12)(21),(12)3 34 4(1111)(1111)；(211),(121),(112)(211),(121),(112)；(22)(22)5 55 5(11111);(11111);(2111),(1211),(1121),(1112)(2111),(1211),(1121),(1112)(221),(212),(122)(221),(212),(122)8 8 n n CCCu2213044CCCu2314055222110nkuCCCCkknnnnn其中，贾宪三角形表达式贾宪三角形表达式E.Piccioli，1916 1916,138,85,53,32,21,11215)

9、251()251(5111nnnuDe Moivre提出，提出，J.P.M.Binet 1843年证明，世称年证明，世称Binet公式公式黄金分割率，它是美的标准之一，也黄金分割率，它是美的标准之一，也是优选法的理论基础。是优选法的理论基础。该数列极限为该数列极限为该数列相邻两项之比构成该数列相邻两项之比构成的的“比值比值”数列数列)3,2,1(.2,11221nuuuuunnn通项公式通项公式黄金分割的美黄金分割的美（黄金比（黄金比0.618）人体各部分的比人体各部分的比 肚肚 脐脐：（头（头脚）脚）印堂穴：印堂穴：（口（口头顶）头顶）肘关节：肘关节：（肩（肩中指尖）中指尖）膝膝 盖：盖：（

10、髋关节（髋关节足尖）足尖）著名建筑物中各部分的比著名建筑物中各部分的比 埃及的金字塔，高（埃及的金字塔，高（137米）米）与底边长（与底边长（227米）之比为米）之比为0.629.古希腊的巴特农神殿，古希腊的巴特农神殿，塔高与工作厅高之比为塔高与工作厅高之比为340 5530.615风景照片中风景照片中 地平线的位置地平线的位置美观矩形美观矩形正五角星中的线段比正五角星中的线段比（正五角星很美）（正五角星很美）0.618ABAD0.618ABAC0.618ADD C 舞台报幕者的最佳站位舞台报幕者的最佳站位 在整个舞台宽度的在整个舞台宽度的0.618处较美处较美 小说、戏剧、战争的高潮出现：小

11、说、戏剧、战争的高潮出现：在整个作品的在整个作品的0.618处较好处较好华罗庚先生证明了：华罗庚先生证明了：黄金分割点具有再生性。黄金分割点具有再生性。黄金分割点的黄金分割点的再生性再生性，是，是“黄金分割黄金分割”之所以美的数学依据。之所以美的数学依据。黄金分割为什么美黄金分割为什么美 为什么不是为什么不是0.5的分割点让人感觉愉悦，而是的分割点让人感觉愉悦，而是0.618的分割点让人感觉愉悦呢？的分割点让人感觉愉悦呢？因为因为0.618的分割点反映了的分割点反映了“恰到好处的和谐恰到好处的和谐”。即：即：如果是如果是 的黄金分割点，的黄金分割点，是是 的的黄金分割点，黄金分割点，与与 当然

12、关于中点当然关于中点 对称。对称。特殊的是，特殊的是，又恰是又恰是 的黄金分割点。同样，的黄金分割点。同样，如果如果 是是 的黄金分割点，则的黄金分割点，则 又恰是又恰是 的黄金分割点，等等，一直延续下去的黄金分割点，等等，一直延续下去。（再生）（再生）CABCBACCOCACCCACAC0.6180.618优选法优选法（黄金分割法）（黄金分割法）问题：问题：做做2 2千克大米的干饭，放多少水最好吃？千克大米的干饭，放多少水最好吃？（1 1000g-2000g000g-2000g)“饭好吃饭好吃f(x)”f(x)”是是“放水量放水量x”x”的函数；的函数；但不知其具体表达式，或即使知道但太复杂

13、；但不知其具体表达式，或即使知道但太复杂；函数函数f(x)f(x)有何特点？有何特点？单峰（谷）函数单峰（谷）函数 不能用数学方法寻找单峰函数的最优点，怎么办？不能用数学方法寻找单峰函数的最优点，怎么办？.通过通过作试验的方法来寻找最佳点。作试验的方法来寻找最佳点。优选法优选法是以最少的试验次数迅速找到最佳点的试验方法。是以最少的试验次数迅速找到最佳点的试验方法。这是最优化一种新的思维方法！这是最优化一种新的思维方法！问题：问题：做做2 2千克大米的干饭，放多少水最好吃？千克大米的干饭，放多少水最好吃？（1 1000g-2000g000g-2000g)最最“笨笨”的方法的方法是分别加入是分别加

14、入1001克，克，1002克，克，2000克，做克，做1千次试验，就能发现最佳方案。千次试验，就能发现最佳方案。华罗庚证明了，每次取试验区间的华罗庚证明了，每次取试验区间的0.618处去做试验处去做试验的方法，才是最好的，这种优选法称为的方法，才是最好的，这种优选法称为“黄金分割黄金分割法法”或或“0.618法法”。18黄金分割法步骤：黄金分割法步骤：用一有刻度的纸条表达用一有刻度的纸条表达10001000克克20002000克。克。在这纸条长度的在这纸条长度的0.6180.618的的地方地方C C划一条线，也就是按划一条线，也就是按16181618克克做第一次试验。然后把纸条对折，前一条线落

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

16、 1236克处。克处。按按1236克克C/做第三次试验。把做第三次试验。把1236克处克处C/和和1382克克C/的试验效的试验效果比较，如果果比较，如果1236克克C/的效果较差，就把的效果较差，就把1236克克C/以外的短的以外的短的一段纸条剪去。一段纸条剪去。再对折剩下的纸条，找出第四次试验点再对折剩下的纸条，找出第四次试验点1472克。按克。按1472克做试克做试验后，与验后，与1382克克C/的效果比较，再剪去效果较差点以外的短的的效果比较，再剪去效果较差点以外的短的一段纸条。一段纸条。再对折寻找下一次试验点，一次比一次接近我们的需要，直到再对折寻找下一次试验点，一次比一次接近我们的

17、需要，直到达到我们满意的精确度。达到我们满意的精确度。注意，每次剪掉的都是注意，每次剪掉的都是效果较差点以外的短纸条，效果较差点以外的短纸条，保留下保留下的是效果较好的部分，而每次留下纸条的长度是上次长度的的是效果较好的部分，而每次留下纸条的长度是上次长度的0.6180.618倍。因此，纸条的长度按倍。因此，纸条的长度按0.6180.618的的k k次方倍逐次减小，以次方倍逐次减小，以指指数函数数函数的速度的速度迅速迅速趋于趋于0 0。所以，。所以，“0.6180.618法法”可以较快地找到可以较快地找到满意的点。满意的点。事实上，事实上，当纸条长度已经很小时，纸条上的任一个点都可当纸条长度已

18、经很小时，纸条上的任一个点都可以作为以作为“满意满意”的点了，因为最优点就在纸条上，你取的点与的点了，因为最优点就在纸条上，你取的点与最优点的最优点的误差误差一定小于纸条的长。一定小于纸条的长。1985年年6月月12日华罗庚先生在日本的最后一场演讲（日华罗庚先生在日本的最后一场演讲（75岁）岁）“工作到人生的最后一刻工作到人生的最后一刻”归纳：归纳：0.6180.618优选法优选法（黄金分割法）（黄金分割法）问题：问题：做做2千克大米的干饭，应该放多少水？（千克大米的干饭，应该放多少水？（1000g-2000g)寻找单峰（谷）函数（寻找单峰（谷）函数（不知其具体表达式或太复杂）不知其具体表达式

19、或太复杂）的最优点的最优点.通过通过作试验的方法寻找最佳点作试验的方法寻找最佳点 优选法优选法是以最少的试验次数迅速找到最佳点的试验方法。是以最少的试验次数迅速找到最佳点的试验方法。操作过程：操作过程：第一个试验点第一个试验点x1=a+(b-a)0.618，第二个试验点，第二个试验点x2=a+b-x1；对比对比x1,x2处结果，裁去处结果，裁去“坏点坏点”外边的部分；以此类推；外边的部分；以此类推；在确定第在确定第n个试点个试点xn时，如果存优范围内相应的好点是时，如果存优范围内相应的好点是xm，那么有那么有xn=小小+大大-xm.称称“加两头，减中间加两头，减中间”来确定下来确定下1个试点。

20、个试点。经过经过n n次试验后留下的区间长为原区间长的次试验后留下的区间长为原区间长的0.6180.618n-1n-1（精度）。（精度）。0.618法试点为什么这样选择？法试点为什么这样选择？第一、第二次试点选择的原则：第一、第二次试点选择的原则：1 1、公平原则；、公平原则；使两个试点关于区间使两个试点关于区间 a,ba,b的中点对称的中点对称 2 2、继承原则、继承原则 每次舍去的区间占舍去前的区间的比例数相同。每次舍去的区间占舍去前的区间的比例数相同。据上述原则求出第据上述原则求出第1 1、第、第2 2次试点的位置次试点的位置 线段线段a,ba,b的黄金分割点的黄金分割点 0.6180.

21、618法（黄金分割法）法（黄金分割法）25 0.618这个这个“黄金比黄金比”能产生能产生“优选法优选法”，这告诉，这告诉我们，我们，美的东西美的东西与与有用的东西有用的东西之间，常常是有联系的之间，常常是有联系的。由此再反观由此再反观0.6180.618的分割点为什么在许多场合都反映的分割点为什么在许多场合都反映了了“恰到好处的和谐恰到好处的和谐”。其数学依据就是其数学依据就是“黄金分割点的再生性黄金分割点的再生性”。数学的美，在于数学思想深刻之美。数学的美，在于数学思想深刻之美。分数法分数法 例：在配置某种清洗液时，需要加入某种材料。例：在配置某种清洗液时，需要加入某种材料。经验表明，加入

22、量大于经验表明，加入量大于130130mlml肯定不好。用肯定不好。用150150mlml的锥形量杯计量加入量，该量杯的量程分的锥形量杯计量加入量，该量杯的量程分为为1515格，每格代表格，每格代表1010mlml。用试验法找出这种材料的最优加入量。用试验法找出这种材料的最优加入量。能用能用0.6180.618法吗？法吗？如果用如果用0.6180.618法，算出的试点不是法，算出的试点不是10ml10ml的整数倍，的整数倍，此法不能用。此法不能用。采用采用分数法分数法，借助借助Fibonacci数列数列来处理。来处理。分数法的操作分数法的操作 把实验区间把实验区间00,130,130分成分成1

23、313等分，分点依次设为等分，分点依次设为1,2,3,1,2,3,12,12。选分数选分数8/138/13作为黄金分割数的近似值。作为黄金分割数的近似值。第一个试点为第一个试点为8 8，第二个为，第二个为5 5，若若8 8好，则去掉好，则去掉00,5,5，剩下，剩下55，1313；8 8已试过，在已试过，在1010处做第处做第3 3个试验，若还是个试验，若还是8 8好，去掉好，去掉10,1310,13，剩下，剩下55，1010；在在7 7处做第四个试验，若处做第四个试验，若7 7比比8 8好，去掉好，去掉88，1010，剩，剩下下55，88；在在6 6做第五个试验，如做第五个试验，如6 6比比

24、7 7好，则好，则6 6为最佳点。为最佳点。五次试验后，精度为五次试验后，精度为1/131/13。分数法分数法 现实中，由于受时间、人力等影响，往往现实中，由于受时间、人力等影响，往往使试验次数受到限制，此时采用分数法可使试验次数受到限制，此时采用分数法可以达到较好的效果。以达到较好的效果。分数法与分数法与0.618法的本质是相同的。法的本质是相同的。有两种情况：有两种情况：1.可能的试点总数正好是某一个可能的试点总数正好是某一个(Fn+1-1)；2.可能的试点总数大于某一可能的试点总数大于某一(Fn-1)，而小于，而小于(Fn+1-1)。分数法的最优性分数法的最优性 结论结论1 1：在目标函

25、数为单峰的情形，通过在目标函数为单峰的情形，通过n n次试验，最多能从次试验，最多能从(F Fn+1n+1-1)-1)个试点中保证找个试点中保证找出最佳点。并且这个最佳点就是出最佳点。并且这个最佳点就是n n次试验中次试验中的最优试验点。的最优试验点。结论结论2 2：目标函数为单峰的情形，只有按照目标函数为单峰的情形，只有按照分数法安排试验，才能通过分数法安排试验，才能通过n n次试验，保证次试验，保证从从(F Fn+1n+1-1)-1)个试点中找出最佳点。个试点中找出最佳点。综上所述，综上所述，对于试点个数为某常数对于试点个数为某常数k k时，用时，用分数法找出其最佳点的试验次数最少。分数法找出其最佳点的试验次数最少。分数法的最优性可以用数学方法证明。分数法的最优性可以用数学方法证明。