引言组合优化理论幻灯片.ppt

《引言组合优化理论幻灯片.ppt》由会员分享，可在线阅读，更多相关《引言组合优化理论幻灯片.ppt（22页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、引言组合优化理论第1页，共22页，编辑于2022年，星期六引引 言言 模型是研究和解决现代社会中复杂系统工程问题模型是研究和解决现代社会中复杂系统工程问题的重要工具和方法，模型方法的掌握和运用，不仅需的重要工具和方法，模型方法的掌握和运用，不仅需要自然科学和社会科学方面的广泛知识，而且需要丰要自然科学和社会科学方面的广泛知识，而且需要丰富的实践经验，以及综合运用各种知识、经验、主体富的实践经验，以及综合运用各种知识、经验、主体感悟和创造所形成的整体素质和能力感悟和创造所形成的整体素质和能力 .常识！常识！模型和算法相结合，是运用计算机解决实际问模型和算法相结合，是运用计算机解决实际问题的强有力

2、的现代应用技术的重要组成部分，也是题的强有力的现代应用技术的重要组成部分，也是高级研究和技术人才素质培养的重要一环高级研究和技术人才素质培养的重要一环 .数学建模数学建模竞赛的重竞赛的重要内容要内容第2页，共22页，编辑于2022年，星期六引引 言言 在各种活动，如果要作一决策而备选方案不止在各种活动，如果要作一决策而备选方案不止一个，则自然希望所选方案是最优（最佳）的（某一个，则自然希望所选方案是最优（最佳）的（某种意义下如：最短、最省、最大种意义下如：最短、最省、最大 etcetc.）.最优化方最优化方法就是从众多可能方案中选择以达到最优目标的科法就是从众多可能方案中选择以达到最优目标的科

3、学学.通过数学方法在一个有限的可行解集合通过数学方法在一个有限的可行解集合中寻找最优解的问题中寻找最优解的问题 组合优化问题组合优化问题第3页，共22页，编辑于2022年，星期六引引 言言课程之简介课程之简介课程之要求课程之要求数学之重要数学之重要第4页，共22页，编辑于2022年，星期六引言引言-数学之重要数学之重要数学使人周密数学使人周密 -Francis Bacon 数学处于人类智能的中心领域数学处于人类智能的中心领域数学方数学方法渗透、支配着一切自然科学的理论分支法渗透、支配着一切自然科学的理论分支它已愈来愈成为衡量成就的主要标志。它已愈来愈成为衡量成就的主要标志。-Von Neuma

4、nn第5页，共22页，编辑于2022年，星期六引言引言-数学之重要数学之重要 一门科学只有当它达到能够成功地运用一门科学只有当它达到能够成功地运用 数学时，才算真正发展了数学时，才算真正发展了.-Karl MarxGalileo:展现在我们眼前的宇宙像一本用数学语言展现在我们眼前的宇宙像一本用数学语言写成的大书，如不掌握数学符号语言，就像在黑暗写成的大书，如不掌握数学符号语言，就像在黑暗的迷宫里游荡，什么也认识不清的迷宫里游荡，什么也认识不清.数学是一种语言，是一切科学的共同语言数学是一种语言，是一切科学的共同语言第6页，共22页，编辑于2022年，星期六二十世纪最伟大的数学家二十世纪最伟大的

5、数学家-二十世纪最伟大的物理学家二十世纪最伟大的物理学家-D.HilbertA.EinsteinNobel PrizeFields Medal Go back引言引言-数学之重要数学之重要数学是一种技术，是高技术的本质数学是一种技术，是高技术的本质数学技术数学技术-数学方法与计算技术的结合形数学方法与计算技术的结合形 成的一种关键性的、可实现的技术成的一种关键性的、可实现的技术第7页，共22页，编辑于2022年，星期六引言引言-课程之简介课程之简介Example 1 婚姻问题婚姻问题 (matching problem)DEF女儿女儿ABC追求者追求者EDF327151042628得到分配矩阵

6、：得到分配矩阵：如何嫁娶，使获如何嫁娶，使获得的礼品最多？得的礼品最多？7共有共有3!种可能种可能第8页，共22页，编辑于2022年，星期六引言引言-课程之简介课程之简介DEF1.贪婪（贪婪（Greedy)解解 一般不会产生最差一般不会产生最差 解；解；2.在某些模型中在某些模型中,贪贪 婪算法能得到最优婪算法能得到最优 解；解；3.可以使用穷举法，可以使用穷举法，但是以时间为代价但是以时间为代价贪婪解的结果：贪婪解的结果：28+5+1=34最优解的结果：最优解的结果：27+4+26=57Note：最差解的结果：最差解的结果：3+10+7=20第9页，共22页，编辑于2022年，星期六引言引言

7、-课程之简介课程之简介Example 2 旅行商问题旅行商问题（Traveling Salesman Problem）TSP:有一位旅行售货员，欲到城市有一位旅行售货员，欲到城市 v1，v2,，vn 进行商品销售，已知：进行商品销售，已知：的距离为的距离为 wij.(,.(,).).他从其中某个城市出发，需访问每一个他从其中某个城市出发，需访问每一个城市一次且仅一次（在欧氏距离下）而回到出发的城城市一次且仅一次（在欧氏距离下）而回到出发的城市市.问应如何计划他的旅行路线，使他所走路线的总问应如何计划他的旅行路线，使他所走路线的总长度最短？长度最短？共有（共有（n-1)!种可能种可能最优最优Ha

8、milton 回路回路第10页，共22页，编辑于2022年，星期六引言引言-课程之简介课程之简介 组合优化问题又称离散优化问题，是一类重要的组合优化问题又称离散优化问题，是一类重要的优化问题优化问题.在信息的采集、传递、加工过程中这类问题与日在信息的采集、传递、加工过程中这类问题与日俱增，越来越受到运筹学、应用数学、计算机科学及俱增，越来越受到运筹学、应用数学、计算机科学及管理科学等诸多学科的高度重管理科学等诸多学科的高度重视视.组合优化是组合优化是近几十年发展起来的一门新兴的交叉近几十年发展起来的一门新兴的交叉学科分支学科分支.在计算机科学、计算生物学、物流和供应在计算机科学、计算生物学、物

9、流和供应链管理等新兴领域有大量的应用。链管理等新兴领域有大量的应用。第11页，共22页，编辑于2022年，星期六引言引言-课程之简介课程之简介 组合优化就其研究的问题和所形成的学科连贯性组合优化就其研究的问题和所形成的学科连贯性不能与数学、力学、电工学等学科相比不能与数学、力学、电工学等学科相比.后者是从研究自然科学的基本问题而逐渐深入的、后者是从研究自然科学的基本问题而逐渐深入的、前后连贯的完整学科，有严密的理论体系和系统的研前后连贯的完整学科，有严密的理论体系和系统的研究方法究方法.组合优化问题多为专题研究系统最优问题，以不组合优化问题多为专题研究系统最优问题，以不同模型为对象，具有趣味性

10、、应用性同模型为对象，具有趣味性、应用性.大多数模型以大多数模型以独立的理论基础和解题方法出现，技巧性较独立的理论基础和解题方法出现，技巧性较强强.第12页，共22页，编辑于2022年，星期六引言引言-课程之简介课程之简介 组合优化问题最优解的存在和有正确的算法（穷组合优化问题最优解的存在和有正确的算法（穷举法举法 etc.）是没问题的）是没问题的.问题解决了吗？问题解决了吗？没有！没有！时间时间 设有设有 n 个城市（有向图）的个城市（有向图）的 TSP,则有（则有（n-1）！）！种可能方案种可能方案.以计算机以计算机 1 秒可以完成秒可以完成 24 个城市所有路个城市所有路径枚举为单位，则

11、径枚举为单位，则城市数城市数2425 262728 29 30 31计算时间计算时间1 1s s2424s s1010min4.34.3h h4.94.9d d 136.5136.5d d10.810.8y y 325325y y 因此，对不同的问题（甚至同一问题解的不因此，对不同的问题（甚至同一问题解的不 同表示）必须研究是否有有效算法、如何设计算同表示）必须研究是否有有效算法、如何设计算 法、分析算法的有效性等等法、分析算法的有效性等等.问题的模型与应用问题的模型与应用 算法的设计与分析算法的设计与分析 第13页，共22页，编辑于2022年，星期六引言引言-课程之简介课程之简介内容：内容：

12、课程内容包括线性规划、对偶线性规划、课程内容包括线性规划、对偶线性规划、运输问题、整数规划、指派问题、背包问题、装箱运输问题、整数规划、指派问题、背包问题、装箱问题、排序问题、网络规划等问题、排序问题、网络规划等.参考书目参考书目：1、数学规划与组合优化数学规划与组合优化 姚恩瑜姚恩瑜 等等2、运筹学及其应用运筹学及其应用 胡觉亮胡觉亮 等等Go back第14页，共22页，编辑于2022年，星期六引言引言-课程之要求课程之要求会做人会做人 会做事会做事怎样做怎样做 为什么这样做为什么这样做 不这样做可以吗不这样做可以吗 How?Why?Other ways?4 4、提高数学素养、提高数学素养

13、1 1、增强优化意识、增强优化意识 2 2、掌握常用的优化模型、掌握常用的优化模型 3 3、掌握求解这些模型的思想和方法、掌握求解这些模型的思想和方法(算法算法)比方法更重要比方法更重要 未来的文盲不再是目不识丁的人，而是那些没未来的文盲不再是目不识丁的人，而是那些没有学会怎样学习的人有学会怎样学习的人 Alvin Toffler第15页，共22页，编辑于2022年，星期六引言引言-课程之要求课程之要求英国商船配置高射炮的评价英国商船配置高射炮的评价步行时间步行时间狗的位置狗的位置重力加速度问题重力加速度问题Ramsey 数数第16页，共22页，编辑于2022年，星期六homeRailway

14、station提前提前30分钟下班分钟下班提前提前1010分钟到家分钟到家问：步行了几分钟问：步行了几分钟单程提前单程提前5分钟分钟结论：步行结论：步行25分钟分钟Go back步行时间步行时间第17页，共22页，编辑于2022年，星期六速度速度：女主人女主人 3 km/h 男主人男主人 5 km/h 狗狗 7 km/h 一对夫妇及一只小狗同时从家里出发，沿相同道一对夫妇及一只小狗同时从家里出发，沿相同道路步行，小狗不停地往返在男女主人之间，已知他们路步行，小狗不停地往返在男女主人之间，已知他们的速度，问：的速度，问：1 1 小时后狗在男女主人之间什么位置？小时后狗在男女主人之间什么位置？结论

15、：结论：狗可以在男女狗可以在男女主主 人之间的任何位置人之间的任何位置。分析：分析：运用极限理论运用极限理论中的两边夹定理。中的两边夹定理。狗的位置狗的位置Go back第18页，共22页，编辑于2022年，星期六引言引言-课程之要求课程之要求重力加速度问题重力加速度问题Aristotle HeavyLight快快慢慢GalileoHeavyLight快？快？慢？慢？Go back第19页，共22页，编辑于2022年，星期六引言引言-课程之要求课程之要求Ramsey 数数鸽洞（抽屉）原理：鸽洞（抽屉）原理：把把100100只鸽子关进只鸽子关进9999个个洞里面，则其中必有一个洞里面，则其中必有

16、一个洞内至少关有洞内至少关有2 2只鸽子。只鸽子。认识：认识：不认识不认识：在世界任何地方找六在世界任何地方找六个人，则其中必有三个人个人，则其中必有三个人相互认识或相互不认识相互认识或相互不认识。第20页，共22页，编辑于2022年，星期六引引 言言完完第21页，共22页，编辑于2022年，星期六1、热爱教学、热爱教学 热爱学生热爱学生辛苦，并快乐着辛苦，并快乐着交交 流流 了解学生，让学生了解你了解学生，让学生了解你2、教书育人、教书育人激发学生积极向上激发学生积极向上3、教学上的几点体会、教学上的几点体会a、对所授课程要非常熟悉、对所授课程要非常熟悉b、设问题，引导学生思考、提出正确途径、设问题，引导学生思考、提出正确途径c、内容之间要设法自然连接、内容之间要设法自然连接d、复杂问题简单说、复杂问题简单说第22页，共22页，编辑于2022年，星期六