数学建模 - 第一章 组合优化模型与计算复杂性.ppt

《数学建模 - 第一章 组合优化模型与计算复杂性.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第一章组合优化模型与计算复杂性组合优化理论CombinatorialOptimizationTheory1第一章组合优化模型与计算复杂性§1组合优化模型与算法§2计算复杂性问题§3启发式算法2第一章组合优化模型与计算复杂性模型（model）是所研究的系统、过程、事物或概念的一种表达形式.§1组合优化模型与算法（一)模型的概念模型不是研究对象本身，而是对研究对象的一种抽象，它反映现实中对象系统的主要特征，但它又高于现实，因而具有同类问题的共性.由于研究目的的不同，对于同一个对象系统，可以建立完全不同的模型，分别反映该系统的不同侧面；出于相同的研究目的，对于

2、同一个对象系统，也可能建立不同的模型，反映不同的研究角度、考察因素和价值取向.一、关于模型3§1组合优化模型与算法（二）模型的本质从系统概念上看，模型是系统中各种关系的表达形式.因此，建立模型要从状态和过程两个方面去寻找、把握和描述各系统要素之间的相互关系.状态：事物在某个时刻所处的状况或表现形态过程：事物状态的变化在时间上的持续和空间上的延伸过程和状态两者紧密联系、不可分割，状态决定和影响过程，过程又决定和影响新的状态.状态和过程是相对的.4从认识论上看，模型是作为认识与实践活动的中介.现实世界认识（信息）模型实践活动概念化用信息载体表达决策（行动方案

3、）产品和服务模型化过程示意图模型既是认识的表达，又是实践活动的先导.模型参与认识世界和改造世界的不断的循环往复过程，既是认识不断深化的体现，又是实践活动不断拓展的体现.第一章组合优化模型与计算复杂性5§1组合优化模型与算法从信息论上看，模型和认识之间存在密切的反馈关系.从已知信息可以通过模型加工产生出新的信息，相关信息的积累可以从量变产生质变，形成新的概念，促使认识深化.因此，模型的建立和完善不仅要注重对系统物质形态和能量形态的认识、把握和描述，而且也依赖于对系统相关信息不断的采集、积累和加工，这就是用模型研究问题的现实活动.6（三）模型的分类1、原样模

4、型原样模型是在工程开发末期建立的一种具象实体，是具有实物形态的模型.它与目的工程在结构和过程方面基本相同.原样模型经过试验改进和完善后便是所要开发的目的工程.新产品的样机、新著作的原稿…第一章组合优化模型与计算复杂性7§1组合优化模型与算法2、相似模型相似模型是根据不同系统间的相似规律（包括几何相似、逻辑相似和过程相似等）而建立的用于研究的模型.3、图形模型地球仪、船体放样模型、飞机风洞实验模拟模型等等图形模型可以表达非常丰富的内容，主要有：①图画——一种可以示形的图形；②草图——一种可以示意的图形；③框图——一种可以表示系统的部分之间或部分与整体之间联

5、系的图形；称为不严格图（没有严格的规范）系统分析和设计人员常常借助于这些图形模型来开发、构建一个新系统的想象力和创造力，逐步引申出与之有关的问题和需要进一步探索的问题，使所要开发的系统变得越来越清晰、越来越具体.8④逻辑图——一种可以反映因素或对象间逻辑关系的图形；如：程序流程图、控制关系图etc.⑤工程图——一种可以反映物体确定的结构和顺序关系的图形；如：建筑工程图、铁路站场配置图etc.⑥图论图——包括图论所定义的无向图G(V，E)、有向图G(V，A)、加权有(无)向图G(V，A(E)，w).关系称为严格图（有严格确定的结构形式和规范）4、数学模型数

6、学模型是指运用数学符号和公式来表达、研究对象系统的结构或过程的模型.数学模型是用数学的语言、方法去近似地刻画实际,是由数字、字母或其他数学符号组成的，描述现实对象数量规律的数学公式、图形或算法.是对现实对象本质属性的抽象而又简洁的刻画，它或能解释某些客观现象，或能预测未来的发展规律，或能为控制某一现象的发展提供某种意义下的最优策略或较好策略.Goback第一章组合优化模型与计算复杂性9二、数学模型Example1七桥问题18世纪的德国有个哥尼斯堡城，在流贯全城的普雷尔河两岸和河中两个岛之间架设了七座桥，把河的两岸和两岛连接起来，能否有这样一种走法，它通过

7、每座桥一次且仅一次.该问题由Euler在1736年解决Solution:§1组合优化模型与算法10ABCD显然，解决该问题时，两岸和岛的大小、形状以及桥的长短曲直都无关，重要的是什么？每块陆地间有几座桥对问题进行数学抽象：把两岸和两岛都看做顶点，将连接这些顶点的桥当作边，于是得到一无向图.则七桥问题就成为无向图中是否存在通过每一边一次且仅一次的路（即一笔画）问题.第一章组合优化模型与计算复杂性11§1组合优化模型与算法ABCDEuler在他的论文中证明：一个图中存在一笔画的充要条件是同时满足：1、图是连通的；2、与图中每一顶点（可能有两点例外）相连的边（

8、线度）必须是偶数条.这是关于图论的第一篇论文见图可知，与四个顶点相连的边都是奇数