数学建模引言组合优化理论

组合优化理论

CombinatorialOptimizationTheory数学科学系引言

模型是研究和解决现代社会中复杂系统工程问题的重要工具和方法，模型方法的掌握和运用，不仅需要自然科学和社会科学方面的广泛知识，而且需要丰富的实践经验，以及综合运用各种知识、经验、主体感悟和创造所形成的整体素质和能力.常识！

模型和算法相结合，是运用计算机解决实际问题的强有力的现代应用技术的重要组成部分，也是高级研究和技术人才素质培养的重要一环.数学建模竞赛的重要内容引言

在各种活动，如果要作一决策而备选方案不止一个，则自然希望所选方案是最优（最佳）的（某种意义下如：最短、最省、最大etc.）.最优化方法就是从众多可能方案中选择以达到最优目标的科学.

通过数学方法在一个有限的可行解集合中寻找最优解的问题——

组合优化问题引言课程之简介课程之要求数学之重要引言---数学之重要……数学使人周密……----FrancisBacon

数学处于人类智能的中心领域……数学方法渗透、支配着一切自然科学的理论分支……它已愈来愈成为衡量成就的主要标志。

----VonNeumann引言---数学之重要

一门科学只有当它达到能够成功地运用数学时，才算真正发展了.----KarlMarxGalileo:

展现在我们眼前的宇宙像一本用数学语言写成的大书，如不掌握数学符号语言，就像在黑暗的迷宫里游荡，什么也认识不清.数学是一种语言，是一切科学的共同语言二十世纪最伟大的数学家----二十世纪最伟大的物理学家----D.HilbertA.EinsteinNobelPrizeFieldsMedal

Goback引言---数学之重要数学是一种技术，是高技术的本质数学技术----数学方法与计算技术的结合形成的一种关键性的、可实现的技术引言---课程之简介Example1婚姻问题

(matchingproblem)DEF女儿ABC追求者EDF327151042628得到分配矩阵：如何嫁娶，使获得的礼品最多？7共有3!种可能引言---课程之简介DEF贪婪（Greedy)解一般不会产生最差解；在某些模型中,贪婪算法能得到最优解；3.可以使用穷举法，但是以时间为代价贪婪解的结果：28+5+1=34最优解的结果：

27+4+26=57Note：最差解的结果：3+10+7=20引言---课程之简介Example2

旅行商问题（Traveling

Salesman

Problem）TSP

:

有一位旅行售货员，欲到城市v1，v2,…，vn

进行商品销售，已知：的距离为

wij.(,).他从其中某个城市出发，需访问每一个城市一次且仅一次（在欧氏距离下）而回到出发的城市.问应如何计划他的旅行路线，使他所走路线的总长度最短？共有（n-1)!种可能最优Hamilton回路引言---课程之简介

组合优化问题又称离散优化问题，是一类重要的优化问题.

在信息的采集、传递、加工过程中这类问题与日俱增，越来越受到运筹学、应用数学、计算机科学及管理科学等诸多学科的高度重视.

组合优化是近几十年发展起来的一门新兴的交叉学科分支.

在计算机科学、计算生物学、物流和供应链管理等新兴领域有大量的应用。

引言---课程之简介

组合优化就其研究的问题和所形成的学科连贯性不能与数学、力学、电工学等学科相比.

后者是从研究自然科学的基本问题而逐渐深入的、前后连贯的完整学科，有严密的理论体系和系统的研究方法.

组合优化问题多为专题研究系统最优问题，以不同模型为对象，具有趣味性、应用性.

大多数模型以独立的理论基础和解题方法出现，技巧性较强.引言---课程之简介

组合优化问题最优解的存在和有正确的算法（穷举法etc.）是没问题的.

问题解决了吗？没有！时间

设有n个城市（有向图）的TSP,则有（n-1）！种可能方案.以计算机1秒可以完成24个城市所有路径枚举为单位，则城市数2425262728293031计算时间1s24s10min4.3h4.9d

136.5d10.8y

325y

因此，对不同的问题（甚至同一问题解的不同表示）必须研究是否有有效算法、如何设计算法、分析算法的有效性等等.

问题的模型与应用算法的设计与分析

引言---课程之简介内容：

课程内容包括线性规划、对偶线性规划、运输问题、整数规划、指派问题、背包问题、装箱问题、排序问题、网络规划等.参考书目：1、《数学规划与组合优化》姚恩瑜等2、《运筹学及其应用》胡觉亮等Goback引言---课程之要求会做人会做事怎样做为什么这样做不这样做可以吗

How?Why?Otherways?4、提高数学素养1、增强优化意识2、掌握常用的优化模型3、掌握求解这些模型的思想和方法(算法)比方法更重要

未来的文盲不再是目不识丁的人，而是那些没有学会怎样学习的人

AlvinToffler引言---课程之要求英国商船配置高射炮的评价步行时间狗的位置重力加速度问题Ramsey数homeRailwaystation提前30分钟下班提前10分钟到家问：步行了几分钟单程提前5分钟结论：步行25分钟Goback步行时间速度：女主人3km/h男主人5km/h狗7km/h

一对夫妇及一只小狗同时从家里出发，沿相同道路步行，小狗不停地往返在男女主人之间，已知他们的速度，问：1小时后狗在男女主人之间什么位置？结论：狗可以在男女主人之间的任何位置。分析：运用极限理论中的两边夹定理。狗的位置Goback引言---课程之要求重力加速度问题AristotleHeavyLight快慢GalileoHeavyLight快？慢？Goback引言---课程之要求Ramsey数鸽洞（抽屉）原理：把100只鸽子关进99个洞里面，则其中必有一个洞内至少关有2只鸽子。●●●●●●认识：不认识：

在