第一章 组合优化模型.ppt

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

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

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

4、的模型 .,它与目的工程在结构和过程方面基本相同 .,原样模型经过试验改进和完善后便是所要开发 的目的工程 .,新产品的样机、新著作的原稿 ,第一章 组合优化模型,8,1 关于模型,2、相似模型,相似模型是根据不同系统间的相似规律（包括几 何相似、逻辑相似和过程相似等）而建立的用于研究 的模型 .,3、图形模型,地球仪、船体放样 模型、飞机风洞实验模 拟模型等等,图形模型可以表达非常丰富的内容，主要有：, 图画 一种可以示形的图形；, 草图 一种可以示意的图形；, 框图 一种可以表示系统的部分之间或部分 与整体之间联系的图形；,称为不严格图 （没有严格的规范）,系统分析和设计人员常常借助于这些

5、图形模型来 开发、构建一个新系统的想象力和创造力，逐步引申 出与之有关的问题和需要进一步探索的问题，使所要 开发的系统变得越来越清晰、越来越具体 .,9, 逻辑图 一种可以反映因素或对象间逻辑关系 的图形；,如：程序流程图、控 制关系图 etc., 工程图 一种可以反映物体确定的结构和顺序 关系的图形；,如：建筑工程图、铁路站场配置图 etc., 图论图 包括图论所定义的无向图 G(V，E) 、 有向图 G(V，A)、加权有(无)向图G(V，A(E)，w).,关系,称为严格图 （有严格确定的结构形式和规范）,4、数学模型,数学模型是指运用数学符号和公式来表达、研究 对象系统的结构或过程的模型

6、.,数学模型是用数学的语言、方法去近似地刻画实际 , 是由数字、字母或其他数学符号组成的，描述现实对 象数量规律的数学公式、图形或算法 .,是对现实对象本质属性的抽象而又简洁的刻画， 它或能解释某些客观现象，或能预测未来的发展规 律，或能为控制某一现象的发展提供某种意义下的最 优策略或较好策略 .,Go back,第一章 组合优化模型,10,2 数学模型,Example 1,七桥问题,18世纪的德国有个哥尼斯堡城，在流贯全城的普 雷尔河两岸和河中两个岛之间架设了七座桥，把河的 两岸和两岛连接起来，能否有这样一种走法，它通过 每座桥一次且仅一次 .,该问题由Euler在1736年解决,Solut

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

8、是奇数条，因 而不可能存在通过每条边一次且仅一次的画法，即一 笔画不存在 . 故七桥问题不可能有解 .,问题原型 七桥问题,数学模型 一笔画问题,无 解 (一次过七座桥不可能),无 解 (一笔画不可能),数学抽象,逻辑推理,翻译回去,有无解？,这是利用数学模型分析和解决问题的一个成功范例,13,一、数学模型的特点,1、高度的抽象性,数学方法不仅要抛开事物的次要属性，突出事物 的本质属性，而且要舍弃事物的物质和能量方面的具 体内容，只考虑其数量关系和空间形式，同时还要把 这些数量关系和空间形式作进一步的抽象，加以形式 化和符号化，以便能够进行逻辑推理和数值运算 .,这种高度的抽象性，实质是对事物

9、认识上的高度 概括和深化，对同类问题包含更多的经验和理解 .,第一章 组合优化模型,14,2 数学模型,2、高度的精确性,数学方法的高度精确性表现在三个方面：,一是表达各种因素、变量和它们之间的关系相当 明确、清楚；二是逻辑推演和运算规则十分严密；三 是结论非常确定 .,数学方法可以处理多变量、关系复杂的问题，可 在有意义的范围内获得令人满意的计算精度 .,特别适合于揭示事物的量的规定性，成为定量研 究的有力工具 .,15,3、应用的普适性,数学方法的高度抽象和精确，使之比任何一种科 学方法的应用范围都更为广泛 .,只存在尚未运用数学方法的领域而不存在不能运 用数学方法的领域 .,许多相同形式

10、的数学模型可用于不同的实际问 题，具有重要类比和借鉴意义 .数学方法的形式化和 公理化，使模型本身、计算过程和计算结果都便于交 流，数学模型易变动，便于修改和改变计算关系，分 析和求解问题速度快，求解成本低 .,数学模型缺乏直观性、形象性和实时感,第一章 组合优化模型,16,2 数学模型,二、数学模型分类,数学模型分类的方法很多，如：,1、按所研究问题的性质分类, 静态模型与动态模型, 确定型模型与随机型模型, 连续模型与离散模型, 线性模型与非线性模型, 宏观模型与微观模型,17,2、按模型的解的特征分类,解析模型与数值模型,3、按模型所用的数学方法分类,初等模型、微分方程模型、差分方程模型

11、、优 化模型等,4、按模型研究的实际范畴分类,人口模型、生态系统模型 、交通流模型、经济 模型、 基因模型等,5、按对实际问题了解的程度分类,白箱模型、灰箱模型、黑箱模型,第一章 组合优化模型,18,2 数学模型,三、数学建模的基本步骤,数学模型因问题不同而异，对同一问题，从不同 角度、不同要求出发，甚至问题的解表示结构不同， 都可以建立不同的数学模型. 建立数学模型也没有固 定的方法、标准 . 不同的实际问题，建模模式千差万 别.,在此介绍通常的几个步骤：,数学建模问题直接来源各领域实际，往往含糊不 清（目的、条件、类型 etc.）. 首先，要对该问题进 行全面的、深入细微的调查和研究. 明

12、确所解决问题 的性质，着手收集数据 ；,1、明确问题,合理地、有目的地,注意精度,19,2、合理假设,现实问题错综复杂，涉及面非常之广. 一个数学 模型面面俱到、无所不包地反映一个现实是不可能 的，即使可能，也因其过于复杂而很难求解，也是没 有必要的 . 所以，要作合理的假设 .,1、简化问题 2、限定适用范围,但也不能忽略实质相关的因素,作假设的依据通常是出于对问题内在规律的认识, 或来自对数据或现象的分析，也可以是二者的综合. 善于辨别问题的主次，抓住主要因素，通过合理假设, 使问题简化以便进行数学描述 .,假设是在模型的建立、求解和分析过程中完善 .,通常开始让问题尽可能简化,第一章 组

13、合优化模型,20,2 数学模型,3、建立模型,建模时，要分清问题的类型恰当使用数学工具； 抓住问题的本质简化变量之间的关系 .,用什么样的方法建立数学模型，没有绝对的标 准；数学模型的形式可以是多种多样，数学公式、表 格、图形、算法 .,模型的优劣在于是否采用了恰当的方法，合理地 描述了实际问题，而不在于是否用到了高深的数学工 具 .,数学建模是一个过程 .,21,4、模型求解,不同的模型要用到不同的数学工具求解 . 这就要 求从事实际工作者对相应的数学分支知识有一定的了 解 .,可借助计算机，特别是利用数学工具软件 .,5、模型分析,对模型求出的解进行数学上的分析，有助于对实 际问题的解决

14、.,如：, 结果的误差分析,误差是否在允许的范围内,分析误差来源：,建模假设的误差；,数据测量的误差；,近似求解方法的误差；,计算工具的舍入误差 ., 结果的统计分析,结果是否符合特定的统计规律, 模型对数据的灵敏度分析,模型的结果是否会因数据的微小改变而发生大的变化, 对假设的鲁棒性分析,模型的结果是否对某一假设非常依赖, 不同模型间的对比分析,robustness,第一章 组合优化模型,22,2 数学模型,6、模型检验,将求解结果和分析结果翻译回到实际问题之中， 与实际现象、实际数据进行比较，检验是否与实际吻 合 . 如果吻合较好，则模型及其结果可以应用于实际 问题；如果吻合不好，则需要对

15、模型进行修正 .,7、改进模型,吻合不好，问题常常出现在模型假设上 . 可能由 于假设了过于苛刻的条件，或者忽略了一些不该忽略 的因素. 所以, 要对实际问题中的主次因素再次分析, 对模型进行修改、补充、完善 . 需要多次反复才能达 到比较满意的程度 。,23,8、模型应用,数学建模最终的目的是为了解决问题 . 一方面可 以解释以前的实践成果；另一方面可以为现在的实际 问题提供解决方案，甚至可以对一些不确定的现象或 规律作出预测 .,现实问题,简化、假设,建立模型,求解模型,检验分析模型,模型应用,观察、分析,收集数据,确定主要因素,及相互关系,Go back,第一章 组合优化模型,24,3

16、组合优化模型,Example 2,某商场根据客流量统计得出一周中每天所需要的 营业员数如表：,营业员配置问题,如果规定每个营业员每周连续工作 5 天，休息 2 天，求总人数最少的营业员排班方案 .,Solution :,设 xj 为从周 j 开始连续工作 5 天的营业员 人数，j = 1,7 (其中 x7 为周日开始连续工作 5 天的 营业员数)，则,可行解集是有限集,25,Example 3 旅行商问题,（Traveling Salesman Problem）,TSP :,有一位旅行售货员，欲到城市 v1，v2,，vn 进行商品销售，已知： 的距离为 wij.( , ).他从其中某个城市出发

17、，需访问每一个 城市一次而回到出发的城市.问应如何计划他的旅行 路线，使他所走路线的总长度最短？,TSP可分为：对称（dij = dji) 和非对称（dij dji）距离两种,第一章 组合优化模型,26,3 组合优化模型,Hamilton 回路：,不含平行边及自环,这是1856年，Hamilton 首先提出的所谓环球 航行问题而得名。它的存在性远比 Eular 回路的存 在性复杂得多。,最优 Hamilton 回路：,在赋权图中，权和最小的 Hamilton 回路 .,过简单图 G 的每一个顶点一次且仅一次的回路 .,27,最优旅行商问题与最优 Hamilton 回路一样吗？,如果不满足三角不

18、等式，则可通 过求最短路方法，构造新图，使之满 足三角不等式 . 所以以下仅讨论最优 的 Hamilton 回路 .,2 5,2 3,Theorem 如果赋权图满足三角不等式 （欧氏距离），则它的最优旅行商回路 与最优 Hamilton 回路相同 （Hamilton 回路存在时）.,第一章 组合优化模型,28,3 组合优化模型,TSP 问题的数学模型（非对称的）：,v6,v4,v5,v3,v2,v1,Note：条件(1)，(2)表示每个城市经过一 次，但不能保证它可行.,要求局部不构成圈，条件(3)就是为 了约束这一点 .,29,共同特点：可行方案是有限的 组合优化问题,Definition 1 组合优化问题是一个极小化（或极大 化）的问题，它是由以下三部分组成：,（1）实例集合 ；,（2）对每个实例 I，有一个有穷的可行解集合 S(I)；,（3）目标函数 f ，它对于每个实例 I 和每个可行解 S(I)，赋以一个实数 f (I, ). 则实例I的最优解为 这样一个可行解 * S(I) ,它使得对于所有S(I)， 都有 (I, *) f (I, ) （f (I, *) f( I, )）.,问题：一类实际问题的数学模型的总称，如TS