最优化思想黄金分割和优选法幻灯片.ppt

《最优化思想黄金分割和优选法幻灯片.ppt》由会员分享，可在线阅读，更多相关《最优化思想黄金分割和优选法幻灯片.ppt（30页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、最优化思想黄金分割和优选法第1页，共30页，编辑于2022年，星期六 选修选修3-13-1：数学史选讲：数学史选讲 选修选修3-23-2：信息安全与密码：信息安全与密码 选修选修3-33-3：球面上的几何：球面上的几何 选修选修3-43-4：对称与群：对称与群 选修选修3-53-5：欧拉公式与闭曲面分类：欧拉公式与闭曲面分类 选修选修3-63-6：三等分角与数域扩充：三等分角与数域扩充 选修选修4-14-1：几何证明选讲：几何证明选讲 选修选修4-64-6：初等数论初步：初等数论初步 选修选修4-24-2：矩阵与变换：矩阵与变换 选修选修4-74-7：优选法与试验设计初步：优选法与试验设计初步

2、 选修选修4-34-3：数列与差分：数列与差分 选修选修4-84-8：统筹法与图论初步：统筹法与图论初步 选修选修4-44-4：坐标系与参数方程：坐标系与参数方程 选修选修4-94-9：风险与决策：风险与决策 选修选修4-54-5：不等式选讲：不等式选讲 选修选修4-104-10：开关电路与布尔代数：开关电路与布尔代数 浙江普通高中知识拓展类选修课程实施方案浙江普通高中知识拓展类选修课程实施方案必修拓展课程从国家课程选修模块中选用：必修拓展课程从国家课程选修模块中选用：数学数学1-11-1，数学，数学1-21-2，数学，数学2-12-1、数学、数学2-22-2、数学、数学2-32-3大学初级课

3、程：大学初级课程：微积分、微积分、线性代数、空间解析几何线性代数、空间解析几何 介绍学科最新成果的课程：介绍学科最新成果的课程：现代数学概览、分形几何现代数学概览、分形几何 学科应用性课程：学科应用性课程：数学史选讲、信息安全与密码、数学史选讲、信息安全与密码、球面上的几何、几何证球面上的几何、几何证明选讲、矩阵与变换、数列与差分、明选讲、矩阵与变换、数列与差分、坐标系与参数方程、坐标系与参数方程、不等式选讲、不等式选讲、初初等数论初步、等数论初步、优选法与试验设计初步、优选法与试验设计初步、风险与决策、开关电路与布尔代数、风险与决策、开关电路与布尔代数、生活中的数学、生活中的数学、数学与经济

4、数学与经济 第2页，共30页，编辑于2022年，星期六最优化思想最优化思想黄金分割和优选法黄金分割和优选法第3页，共30页，编辑于2022年，星期六斐波那契数列及其应用斐波那契数列及其应用斐波那契斐波那契计算之书计算之书兔子问题兔子问题（12021202年）年）如果每如果每1 1对成兔每月生对成兔每月生1 1对幼兔，幼兔经过对幼兔，幼兔经过2 2个月后成为成兔，即开始繁殖，个月后成为成兔，即开始繁殖，问年初的问年初的1 1对幼兔经过对幼兔经过1 1年后能繁殖成多少对年后能繁殖成多少对兔子？兔子？假定这一过程兔子不发生任何死亡。假定这一过程兔子不发生任何死亡。第4页，共30页，编辑于2022年，

5、星期六由兔子问题抽象得递推关系由兔子问题抽象得递推关系本月底幼兔总对数本月底幼兔总对数=上上个月底兔子总对数上上个月底兔子总对数所以：本月底兔子总对数所以：本月底兔子总对数=上月底兔子总对数上月底兔子总对数+上上个月底兔子总对数。上上个月底兔子总对数。用用u un n表示第表示第n n个月底兔子的总对数个月底兔子的总对数 ，则有，则有斐波那契数列。斐波那契数列。(A.Girard,1634)为方便，补充定义为方便，补充定义u0=1。第5页，共30页，编辑于2022年，星期六“走楼梯走楼梯”问题问题 某人要走一架某人要走一架n个台阶的楼梯，某人每步个台阶的楼梯，某人每步向上走向上走1个台阶或个台

6、阶或2个台阶。个台阶。un表示该人从地面向上走到第表示该人从地面向上走到第n个台阶时个台阶时所有不同的走法种数，求所有不同的走法种数，求un。第6页，共30页，编辑于2022年，星期六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),(11111),(2

7、111),(1211),(1121),(1112),(221),(212),(122)(221),(212),(122)8 86 6n n第7页，共30页，编辑于2022年，星期六按第一步的走按第一步的走法分类法分类un=un-1+un-2(n3)；u1=1,u2=2。斐波那契数列斐波那契数列解法解法1：第8页，共30页，编辑于2022年，星期六n n阶阶楼梯的所有走法楼梯的所有走法u un n1 1(1)(1)1 12 2(11)(11)；(2)(2)2 23 3(111)(111)；(21),(12)(21),(12)3 34 4(1111)(1111)；(211),(121),(112)

8、(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 8n n贾宪三角形表达式贾宪三角形表达式E.Piccioli，1916 1916 第9页，共30页，编辑于2022年，星期六De Moivre提出，提出，J.P.M.Binet 1843年证明，世称年证明，世称Binet公式公式黄金分割率，它是美的标准之一，也是黄金分割率，它是美的标准之一，也是优选法的理论基础。优选法的理

9、论基础。该数列极限为该数列极限为该数列相邻两项之比构成的该数列相邻两项之比构成的“比值比值”数列数列通项公式通项公式第10页，共30页，编辑于2022年，星期六黄金分割的美黄金分割的美（黄金比（黄金比0.618）人体各部分的比人体各部分的比 肚肚 脐脐：（头（头脚）脚）印堂穴：印堂穴：（口（口头顶）头顶）肘关节：肘关节：（肩（肩中指尖）中指尖）膝膝 盖：盖：（髋关节（髋关节足尖）足尖）第11页，共30页，编辑于2022年，星期六著名建筑物中各部分的比著名建筑物中各部分的比 埃及的金字塔，高（埃及的金字塔，高（137米）与底米）与底边长（边长（227米）之比为米）之比为0.629.古希古希腊的巴

10、特农神殿，塔高与工作厅腊的巴特农神殿，塔高与工作厅高之比为高之比为340 5530.615风景照片中风景照片中 地平线的位置地平线的位置美观矩形美观矩形第12页，共30页，编辑于2022年，星期六正五角星中的线段比正五角星中的线段比（正五角星很美）（正五角星很美）第13页，共30页，编辑于2022年，星期六 舞台报幕者的最佳站位舞台报幕者的最佳站位 在整个舞台宽度的在整个舞台宽度的0.618处较美处较美 小说、戏剧、战争的高潮出现：小说、戏剧、战争的高潮出现：在整在整个作品的个作品的0.618处较好处较好第14页，共30页，编辑于2022年，星期六华罗庚先生证明了：华罗庚先生证明了：黄金分割点

11、具有再生性。黄金分割点具有再生性。黄金分割点的黄金分割点的再生性再生性，是，是“黄金分割黄金分割”之所以之所以美的数学依据。美的数学依据。黄金分割为什么美黄金分割为什么美为什么不是为什么不是0.5的分割点让人感觉愉悦，而是的分割点让人感觉愉悦，而是0.618的分割点让人感觉愉悦呢？的分割点让人感觉愉悦呢？因为因为0.618的分割点反映了的分割点反映了“恰到好处的和谐恰到好处的和谐”。第15页，共30页，编辑于2022年，星期六 即：即：如果是如果是 的黄金分割点，的黄金分割点，是是 的的黄金分割点，黄金分割点，与与 当然关于中点当然关于中点 对称。对称。特殊的是，特殊的是，又恰是又恰是 的黄金

12、分割点。同样，的黄金分割点。同样，如果如果 是是 的黄金分割点，则的黄金分割点，则 又恰是又恰是 的黄金分割点，等等，一直延续下去的黄金分割点，等等，一直延续下去。（再生）（再生）第16页，共30页，编辑于2022年，星期六0.6180.618优选法优选法（黄金分割法）（黄金分割法）问题：问题：做做2 2千克大米的干饭，放多少水最好吃？千克大米的干饭，放多少水最好吃？（1000g-2000g)1000g-2000g)“饭好吃饭好吃f(x)”f(x)”是是“放水量放水量x”x”的函数；的函数；但不知其具体表达式，或即使知道但太复杂；但不知其具体表达式，或即使知道但太复杂；函数函数f(x)f(x)

13、有何特点？有何特点？单峰（谷）函数单峰（谷）函数不能用数学方法寻找单峰函数的最优点，怎么办？不能用数学方法寻找单峰函数的最优点，怎么办？.通过通过作试验的方法来寻找最佳点。作试验的方法来寻找最佳点。优选法优选法是以最少的试验次数迅速找到最佳点的试验方法。是以最少的试验次数迅速找到最佳点的试验方法。这是最优化一种新的思维方法！这是最优化一种新的思维方法！第17页，共30页，编辑于2022年，星期六问题：问题：做做2 2千克大米的干饭，放多少水最好吃？千克大米的干饭，放多少水最好吃？（1000g-2000g)1000g-2000g)最最“笨笨”的方法的方法是分别加入是分别加入1001克，克，100

14、2克，克，2000克，克，做做1千次试验，就能发现最佳方案。千次试验，就能发现最佳方案。华罗庚证明了，每次取试验区间的华罗庚证明了，每次取试验区间的0.618处去做试验的处去做试验的方法，才是最好的，这种优选法称为方法，才是最好的，这种优选法称为“黄金分割法黄金分割法”或或“0.618法法”。18第18页，共30页，编辑于2022年，星期六黄金分割法步骤：黄金分割法步骤：用一有刻度的纸条表达用一有刻度的纸条表达10001000克克20002000克。克。在这纸条长度的在这纸条长度的0.6180.618的的地方地方C C划一条线，也就是按划一条线，也就是按16181618克做第一克做第一次试验。

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

16、），这条线在这条线在 1236克处。克处。第19页，共30页，编辑于2022年，星期六按按1236克克C/做第三次试验。把做第三次试验。把1236克处克处C/和和1382克克C/的试验效的试验效果比较，如果果比较，如果1236克克C/的效果较差，就把的效果较差，就把1236克克C/以外的短的以外的短的一段纸条剪去。一段纸条剪去。再对折剩下的纸条，找出第四次试验点再对折剩下的纸条，找出第四次试验点1472克。按克。按1472克做试克做试验后，与验后，与1382克克C/的效果比较，再剪去效果较差点以外的短的的效果比较，再剪去效果较差点以外的短的一段纸条。一段纸条。再对折寻找下一次试验点，一次比一次

17、接近我们的需要，直到再对折寻找下一次试验点，一次比一次接近我们的需要，直到达到我们满意的精确度。达到我们满意的精确度。第20页，共30页，编辑于2022年，星期六 注意，每次剪掉的都是注意，每次剪掉的都是效果较差点以外的短纸条，效果较差点以外的短纸条，保留下的是效果保留下的是效果较好的部分，而每次留下纸条的长度是上次长度的较好的部分，而每次留下纸条的长度是上次长度的0.6180.618倍。因此，纸条的倍。因此，纸条的长度按长度按0.6180.618的的k k次方倍逐次减小，以次方倍逐次减小，以指数函数指数函数的速度的速度迅速迅速趋于趋于0 0。所以，。所以，“0.618“0.618法法”可以较

18、快地找到满意的点。可以较快地找到满意的点。事实上，事实上，当纸条长度已经很小时，纸条上的任一个点都可以作为当纸条长度已经很小时，纸条上的任一个点都可以作为“满意满意”的点了，因为最优点就在纸条上，你取的点与最优点的的点了，因为最优点就在纸条上，你取的点与最优点的误差误差一定一定小于纸条的长。小于纸条的长。第21页，共30页，编辑于2022年，星期六1985年年6月月12日华罗庚先生在日本的最后一场演讲（日华罗庚先生在日本的最后一场演讲（75岁）岁）“工作到人生的最后一刻工作到人生的最后一刻”第22页，共30页，编辑于2022年，星期六归纳：归纳：0.6180.618优选法优选法（黄金分割法）（

19、黄金分割法）问题：问题：做做2千克大米的干饭，应该放多少水？（千克大米的干饭，应该放多少水？（1000g-2000g)寻找单峰（谷）函数（寻找单峰（谷）函数（不知其具体表达式或太复杂）不知其具体表达式或太复杂）的最优点的最优点.通过通过作试验的方法寻找最佳点作试验的方法寻找最佳点优选法优选法是以最少的试验次数迅速找到最佳点的试验方法。是以最少的试验次数迅速找到最佳点的试验方法。操作过程：操作过程：第一个试验点第一个试验点x1=a+(b-a)0.618，第二个试验点，第二个试验点x2=a+b-x1；对比对比x1,x2处结果，裁去处结果，裁去“坏点坏点”外边的部分；以此类推；外边的部分；以此类推；

20、在确定第在确定第n个试点个试点xn时，如果存优范围内相应的好点是时，如果存优范围内相应的好点是xm，那么有那么有xn=小小+大大-xm.称称“加两头，减中间加两头，减中间”来确定下来确定下1个试点。个试点。经过经过n n次试验后留下的区间长为原区间长的次试验后留下的区间长为原区间长的0.6180.618n-1n-1（精度）。（精度）。第23页，共30页，编辑于2022年，星期六0.618法试点为什么这样选择？法试点为什么这样选择？第一、第二次试点选择的原则：第一、第二次试点选择的原则：1 1、公平原则；、公平原则；使两个试点关于区间使两个试点关于区间a,ba,b的中点对称的中点对称2 2、继承

21、原则、继承原则每次舍去的区间占舍去前的区间的比例数相同。每次舍去的区间占舍去前的区间的比例数相同。据上述原则求出第据上述原则求出第1 1、第、第2 2次试点的位置次试点的位置线段线段a,ba,b的黄金分割点的黄金分割点0.6180.618法（黄金分割法）法（黄金分割法）第24页，共30页，编辑于2022年，星期六25 0.618这个这个“黄金比黄金比”能产生能产生“优选法优选法”，这告诉我们，这告诉我们，美美的东西的东西与与有用的东西有用的东西之间，常常是有联系的之间，常常是有联系的。由此再反观由此再反观0.6180.618的分割点为什么在许多场合都反映了的分割点为什么在许多场合都反映了“恰到

22、好处的和谐恰到好处的和谐”。其数学依据就是其数学依据就是“黄金分割点的再生性黄金分割点的再生性”。数学的美，在于数学思想深刻之美。数学的美，在于数学思想深刻之美。第25页，共30页，编辑于2022年，星期六分数法分数法例：在配置某种清洗液时，需要加入某种材料。例：在配置某种清洗液时，需要加入某种材料。经验表明，加入量大于经验表明，加入量大于130ml130ml肯定不好。用肯定不好。用150ml150ml的锥形量杯计量加入量，该量杯的量程分的锥形量杯计量加入量，该量杯的量程分为为1515格，每格代表格，每格代表10ml10ml。用试验法找出这种材料的最优加入量。用试验法找出这种材料的最优加入量。

23、能用能用0.6180.618法吗？法吗？如果用如果用0.6180.618法，算出的试点不是法，算出的试点不是10ml10ml的整数倍，的整数倍，此法不能用。此法不能用。采用采用分数法分数法，借助借助Fibonacci数列数列来处理。来处理。第26页，共30页，编辑于2022年，星期六分数法的操作分数法的操作 把实验区间把实验区间0,1300,130分成分成1313等分，分点依次设为等分，分点依次设为1,2,3,121,2,3,12。选分数选分数8/138/13作为黄金分割数的近似值。作为黄金分割数的近似值。第一个试点为第一个试点为8 8，第二个为，第二个为5 5，若若8 8好，则去掉好，则去掉

24、0,50,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比比7 7好，则好，则6 6为最佳点。为最佳点。五次试验后，精度为五次试验后，精度为1/131/13。第27页，共30页，编辑于2022年，星期六分数法分数法现实中，由于受时间、人力等影响，往往现实中，由于受时间、人力等影响，往往使试验次数受到限

25、制，此时采用分数法可使试验次数受到限制，此时采用分数法可以达到较好的效果。以达到较好的效果。分数法与分数法与0.618法的本质是相同的。法的本质是相同的。有两种情况：有两种情况：1.可能的试点总数正好是某一个可能的试点总数正好是某一个(Fn+1-1)；2.可能的试点总数大于某一可能的试点总数大于某一(Fn-1)，而小于，而小于(Fn+1-1)。第28页，共30页，编辑于2022年，星期六分数法的最优性分数法的最优性结论结论1 1：在目标函数为单峰的情形，通过在目标函数为单峰的情形，通过n n次试验，最多能从次试验，最多能从(F(Fn+1n+1-1)-1)个试点中保证找个试点中保证找出最佳点。并

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