第一章 组合优化模型与计算复杂性

1、1 第一章第一章 组合优化模型与计算复杂性组合优化模型与计算复杂性 Combinatorial Optimization Theory2第一章第一章 组合优化模型组合优化模型 与计算复杂性与计算复杂性1 组合优化模型与算法组合优化模型与算法2 计算复杂性问题计算复杂性问题3 启发式算法启发式算法3第一章第一章 组合优化模型与计算复杂性组合优化模型与计算复杂性 模型（模型（model ）是所研究的系统、过程、事物或）是所研究的系统、过程、事物或概念的一种表达形式概念的一种表达形式 . （一（一) 模型的概念模型的概念 模型不是研究对象本身，而是对研究对象的一种模型不是研究对象本身，而是对研究对象

2、的一种抽象，它反映现实中对象系统的主要特征，但它又高抽象，它反映现实中对象系统的主要特征，但它又高于现实，因而具有同类问题的共性于现实，因而具有同类问题的共性 . 由于研究目的的不同，对于同一个对象系统，由于研究目的的不同，对于同一个对象系统，可以建立完全不同的模型，分别反映该系统的不同可以建立完全不同的模型，分别反映该系统的不同侧面；出于相同的研究目的，对于同一个对象系侧面；出于相同的研究目的，对于同一个对象系统，也可能建立不同的模型，反映不同的研究角统，也可能建立不同的模型，反映不同的研究角度、考察因素和价值取向度、考察因素和价值取向 .一、关于模型一、关于模型4（二）（二） 模型的本质模

3、型的本质 从系统概念上看，模型是系统中各种关系的表达从系统概念上看，模型是系统中各种关系的表达形式形式 . 因此，建立模型要从状态和过程两个方面去寻因此，建立模型要从状态和过程两个方面去寻找、把握和描述各系统要素之间的相互关系找、把握和描述各系统要素之间的相互关系 .状态状态：事物在某个：事物在某个时刻所处的状况或时刻所处的状况或表现形态表现形态 过程过程：事物状态的：事物状态的变化在时间上的持变化在时间上的持续和空间上的延伸续和空间上的延伸 过程和状态两者紧密联系、不可分割，状态决过程和状态两者紧密联系、不可分割，状态决定和影响过程，过程又决定和影响新的状态定和影响过程，过程又决定和影响新的

4、状态 . 状态和过程是相对的状态和过程是相对的 .5 从认识论上看，模型是作为认识与实践活动的中介从认识论上看，模型是作为认识与实践活动的中介 .现实世界现实世界认识（信息）认识（信息） 模模 型型实践活动实践活动概念化概念化用信息载体表达用信息载体表达决策（行动方案）决策（行动方案）产品和服务产品和服务模型化过程示意图模型化过程示意图模型既是认识的表达，又是实践活动的先导模型既是认识的表达，又是实践活动的先导 . 模型参与认识世界和改造世界的不断的循环往复模型参与认识世界和改造世界的不断的循环往复过程，既是认识不断深化的体现，又是实践活动不断过程，既是认识不断深化的体现，又是实践活动不断拓展

5、的体现拓展的体现 .第一章第一章 组合优化模型组合优化模型与计算复杂性与计算复杂性6 从信息论上看，模型和认识之间存在密切的反馈从信息论上看，模型和认识之间存在密切的反馈关系关系 . 从已知信息可以通过模型加工产生出新的信从已知信息可以通过模型加工产生出新的信息，相关信息的积累可以从量变产生质变，形成新的息，相关信息的积累可以从量变产生质变，形成新的概念，促使认识深化概念，促使认识深化 . 因此，模型的建立和完善不仅要注重对系统物质因此，模型的建立和完善不仅要注重对系统物质形态和能量形态的认识、把握和描述，而且也依赖于形态和能量形态的认识、把握和描述，而且也依赖于对系统相关信息不断的采集、积累

6、和加工，这就是用对系统相关信息不断的采集、积累和加工，这就是用模型研究问题的现实活动模型研究问题的现实活动 .7（三）（三） 模型的分类模型的分类1、原样模型、原样模型 原样模型原样模型是在工程开发末期建立的一种具象实是在工程开发末期建立的一种具象实体，是具有实物形态的模型体，是具有实物形态的模型 .它与目的工程在结构和过程方面基本相同它与目的工程在结构和过程方面基本相同 . 原样模型经过试验改进和完善后便是所要开发原样模型经过试验改进和完善后便是所要开发的目的工程的目的工程 .新产品的样机、新著作的原稿新产品的样机、新著作的原稿 第一章第一章 组合优化模型组合优化模型与计算复杂性与计算复杂性

7、82、相似模型、相似模型 相似模型相似模型是根据不同系统间的相似规律（包括几是根据不同系统间的相似规律（包括几何相似、逻辑相似和过程相似等）而建立的用于研究何相似、逻辑相似和过程相似等）而建立的用于研究的模型的模型 .3、图形模型、图形模型 地球仪、船体放样地球仪、船体放样模型、飞机风洞实验模型、飞机风洞实验模模拟模型等等拟模型等等图形模型图形模型可以表达非常丰富的内容，主要有：可以表达非常丰富的内容，主要有： 图画图画 一种可以示形的图形；一种可以示形的图形； 草图草图 一种可以示意的图形；一种可以示意的图形； 框图框图 一种可以表示系统的部分之间或部分一种可以表示系统的部分之间或部分 与整

8、体之间联系的图形；与整体之间联系的图形； 称为不严格图称为不严格图（没有严格的规范）（没有严格的规范） 系统分析和设计人员常常借助于这些图形模型来系统分析和设计人员常常借助于这些图形模型来开发、构建一个新系统的想象力和创造力，逐步引申开发、构建一个新系统的想象力和创造力，逐步引申出与之有关的问题和需要进一步探索的问题，使所要出与之有关的问题和需要进一步探索的问题，使所要开发的系统变得越来越清晰、越来越具体开发的系统变得越来越清晰、越来越具体 .9 逻辑图逻辑图 一种可以反映因素或对象间逻辑关系一种可以反映因素或对象间逻辑关系 的图形；的图形； 如：程序流程图、如：程序流程图、控控制关系图制关系

9、图 etc. 工程图工程图 一种可以反映物体确定的结构和顺序一种可以反映物体确定的结构和顺序 关系的图形；关系的图形； 如：建筑工程图、如：建筑工程图、铁路站场配置图铁路站场配置图 etc. 图论图图论图 包括图论所定义的无向图包括图论所定义的无向图 G(V，E) 、 有向图有向图 G(V，A)、加权有、加权有(无无)向图向图G(V，A(E)，w).关系关系 称为严格图称为严格图（有严格确定的结构（有严格确定的结构形式和规范）形式和规范）4、数学模型、数学模型 数学模型数学模型是指运用数学符号和公式来表达、研究是指运用数学符号和公式来表达、研究对象系统的结构或过程的模型对象系统的结构或过程的模

10、型 .数学模型数学模型是用数学的语言、方法去近似地刻画实际是用数学的语言、方法去近似地刻画实际 ,是由数字、字母或其他数学符号组成的，描述现实对是由数字、字母或其他数学符号组成的，描述现实对象数量规律的数学公式、图形或算法象数量规律的数学公式、图形或算法 . 是对现实对象本质属性的抽象而又简洁的刻画，是对现实对象本质属性的抽象而又简洁的刻画，它或能解释某些客观现象，或能预测未来的发展规它或能解释某些客观现象，或能预测未来的发展规律，或能为控制某一现象的发展提供某种意义下的最律，或能为控制某一现象的发展提供某种意义下的最优策略或较好策略优策略或较好策略 .Go back第一章第一章 组合优化模型

11、组合优化模型与计算复杂性与计算复杂性10Example 1七桥问题七桥问题 18世纪的德国有个哥尼斯堡城，在流贯全城的普世纪的德国有个哥尼斯堡城，在流贯全城的普雷尔河两岸和河中两个岛之间架设了七座桥，把河的雷尔河两岸和河中两个岛之间架设了七座桥，把河的两岸和两岛连接起来，能否有这样一种走法，它通过两岸和两岛连接起来，能否有这样一种走法，它通过每座桥一次且仅一次每座桥一次且仅一次 .该问题由该问题由Euler在在1736年解决年解决Solution :11ABCD 显然，解决该问题时，显然，解决该问题时，两岸和岛的大小、形状以及两岸和岛的大小、形状以及桥的长短曲直都无关，重要桥的长短曲直都无关，

12、重要的是什么？的是什么？每块陆地间有每块陆地间有几座桥几座桥对问题进行数学抽象：对问题进行数学抽象： 把两岸和两岛都看做顶点，将连接这些顶点的桥把两岸和两岛都看做顶点，将连接这些顶点的桥当作边，于是得到一无向图当作边，于是得到一无向图 . 则七桥问题就成为无向图中是否存在通过每一边则七桥问题就成为无向图中是否存在通过每一边一次且仅一次的路（即一笔画）问题一次且仅一次的路（即一笔画）问题 .第一章第一章 组合优化模型组合优化模型与计算复杂性与计算复杂性12ABCDEuler 在他的论文中证明：在他的论文中证明： 一个图中存在一笔画的一个图中存在一笔画的充要条件是同时满足：充要条件是同时满足：1、

13、图是连通的；、图是连通的；2、与图中每一顶点（可能有两点例外）相连的边、与图中每一顶点（可能有两点例外）相连的边 （线度）必须是偶数条（线度）必须是偶数条 .这是关于图论这是关于图论的第一篇论文的第一篇论文 见图可知，与四个顶点相连的边都是奇数条，因见图可知，与四个顶点相连的边都是奇数条，因而不可能存在通过每条边一次且仅一次的画法，即一而不可能存在通过每条边一次且仅一次的画法，即一笔画不存在笔画不存在 . 故七桥问题不可能有解故七桥问题不可能有解 .问题原型问题原型七桥问题七桥问题数学模型数学模型一笔画问题一笔画问题无无 解解(一次过七座桥不可能一次过七座桥不可能)无无 解解(一笔画不可能一笔

14、画不可能)数学抽象数学抽象逻辑推理逻辑推理翻译回去翻译回去有无解？有无解？这是利用数学模型分析和解决问题的一个成功范例这是利用数学模型分析和解决问题的一个成功范例13（一）（一） 数学模型的特点数学模型的特点1、高度的抽象性、高度的抽象性 数学方法不仅要抛开事物的次要属性，突出事物数学方法不仅要抛开事物的次要属性，突出事物的本质属性，而且要舍弃事物的物质和能量方面的具的本质属性，而且要舍弃事物的物质和能量方面的具体内容，只考虑其数量关系和空间形式，同时还要把体内容，只考虑其数量关系和空间形式，同时还要把这些数量关系和空间形式作进一步的抽象，加以形式这些数量关系和空间形式作进一步的抽象，加以形式

15、化和符号化，以便能够进行逻辑推理和数值运算化和符号化，以便能够进行逻辑推理和数值运算 . 这种高度的抽象性，实质是对事物认识上的高度这种高度的抽象性，实质是对事物认识上的高度概括和深化，对同类问题包含更多的经验和理解概括和深化，对同类问题包含更多的经验和理解 .第一章第一章 组合优化模型组合优化模型与计算复杂性与计算复杂性142、高度的精确性、高度的精确性数学方法的高度精确性表现在三个方面：数学方法的高度精确性表现在三个方面： 一是一是表达各种因素、变量和它们之间的关系相当表达各种因素、变量和它们之间的关系相当明确、清楚；明确、清楚；二是二是逻辑推演和运算规则十分严密；逻辑推演和运算规则十分严

16、密；三三是是结论非常确定结论非常确定 . 数学方法可以处理多变量、关系复杂的问题，可数学方法可以处理多变量、关系复杂的问题，可在有意义的范围内获得令人满意的计算精度在有意义的范围内获得令人满意的计算精度 . 特别适合于揭示事物的量的规定性，成为定量研特别适合于揭示事物的量的规定性，成为定量研究的有力工具究的有力工具 .153、应用的普适性、应用的普适性 数学方法的高度抽象和精确，使之比任何一种科数学方法的高度抽象和精确，使之比任何一种科学方法的应用范围都更为广泛学方法的应用范围都更为广泛 . 只存在尚未运用数学方法的领域而不存在不能运只存在尚未运用数学方法的领域而不存在不能运用数学方法的领域用

17、数学方法的领域 . 许多相同形式的数学模型可用于不同的实际问许多相同形式的数学模型可用于不同的实际问题，具有重要类比和借鉴意义题，具有重要类比和借鉴意义 .数学方法的形式化和数学方法的形式化和公理化，使模型本身、计算过程和计算结果都便于交公理化，使模型本身、计算过程和计算结果都便于交流，数学模型易变动，便于修改和改变计算关系，分流，数学模型易变动，便于修改和改变计算关系，分析和求解问题速度快，求解成本低析和求解问题速度快，求解成本低 .数学模型缺乏直观性、形象性和实时感数学模型缺乏直观性、形象性和实时感第一章第一章 组合优化模型组合优化模型与计算复杂性与计算复杂性16（二）（二） 数学模型分类

18、数学模型分类数学模型分类的方法很多，如：数学模型分类的方法很多，如：1、按所研究问题的性质分类、按所研究问题的性质分类 静态模型与动态模型静态模型与动态模型 确定型模型与随机型模型确定型模型与随机型模型 连续模型与离散模型连续模型与离散模型 线性模型与非线性模型线性模型与非线性模型 宏观模型与微观模型宏观模型与微观模型172、按模型的解的特征分类、按模型的解的特征分类解析模型与数值模型解析模型与数值模型3、按模型所用的数学方法分类、按模型所用的数学方法分类初等模型、微分方程模型、差分方程模型、优初等模型、微分方程模型、差分方程模型、优化模型等化模型等4、按模型研究的实际范畴分类、按模型研究的实

19、际范畴分类人口模型、生态系统模型人口模型、生态系统模型 、交通流模型、经济、交通流模型、经济模型、模型、 基因模型等基因模型等5、按对实际问题了解的程度分类、按对实际问题了解的程度分类 白箱模型、灰箱模型、黑箱模型白箱模型、灰箱模型、黑箱模型第一章第一章 组合优化模型组合优化模型与计算复杂性与计算复杂性18（三）（三） 数学建模的基本步骤数学建模的基本步骤 数学模型因问题不同而异，对同一问题，从不同数学模型因问题不同而异，对同一问题，从不同角度、不同要求出发，甚至问题的解表示结构不同，角度、不同要求出发，甚至问题的解表示结构不同，都可以建立不同的数学模型都可以建立不同的数学模型. 建立数学模型

20、也没有固建立数学模型也没有固定的方法、标准定的方法、标准 . 不同的实际问题，建模模式千差万不同的实际问题，建模模式千差万别别. 在此介绍通常的几个步骤：在此介绍通常的几个步骤： 数学建模问题直接来源各领域实际，往往含糊不数学建模问题直接来源各领域实际，往往含糊不清（目的、条件、类型清（目的、条件、类型 etc.）. 首先，要对该问题进首先，要对该问题进行全面的、深入细微的调查和研究行全面的、深入细微的调查和研究. 明确所解决问题明确所解决问题的性质，着手收集数据的性质，着手收集数据 ；1、明确问题、明确问题合理地、有目的地合理地、有目的地注意精度注意精度192、合理假设、合理假设 现实问题错

21、综复杂，涉及面非常之广现实问题错综复杂，涉及面非常之广. 一个数学一个数学模型面面俱到、无所不包地反映一个现实是不可能模型面面俱到、无所不包地反映一个现实是不可能的，即使可能，也因其过于复杂而很难求解，也是没的，即使可能，也因其过于复杂而很难求解，也是没有必要的有必要的 . 所以，要作所以，要作合理合理的假设的假设 .1、简化问题、简化问题2、限定适用范围、限定适用范围但也不能忽略实质但也不能忽略实质相关的因素相关的因素 作假设的依据通常是出于对问题内在规律的认识作假设的依据通常是出于对问题内在规律的认识,或来自对数据或现象的分析，也可以是二者的综合或来自对数据或现象的分析，也可以是二者的综合

22、. 善于辨别问题的主次，抓住主要因素，通过合理假设善于辨别问题的主次，抓住主要因素，通过合理假设,使问题简化以便进行数学描述使问题简化以便进行数学描述 . 假设是在模型的建立、求解和分析过程中完善假设是在模型的建立、求解和分析过程中完善 .通常开始让问题尽通常开始让问题尽可能简化可能简化第一章第一章 组合优化模型组合优化模型与计算复杂性与计算复杂性203、建立模型、建立模型 建模时，要分清问题的类型恰当使用数学工具；建模时，要分清问题的类型恰当使用数学工具；抓住问题的本质简化变量之间的关系抓住问题的本质简化变量之间的关系 . 用什么样的方法建立数学模型，没有绝对的标用什么样的方法建立数学模型，

23、没有绝对的标准；数学模型的形式可以是多种多样，数学公式、表准；数学模型的形式可以是多种多样，数学公式、表格、图形、算法格、图形、算法 . 模型的优劣在于是否采用了恰当的方法，合理地模型的优劣在于是否采用了恰当的方法，合理地描述了实际问题，而不在于是否用到了高深的数学工描述了实际问题，而不在于是否用到了高深的数学工具具 .数学建模是一个过程数学建模是一个过程 .214、模型求解、模型求解 不同的模型要用到不同的数学工具求解不同的模型要用到不同的数学工具求解 . 这就要这就要求从事实际工作者对相应的数学分支知识有一定的了求从事实际工作者对相应的数学分支知识有一定的了解解 .可借助计算机，特别是利用

24、数学工具软件可借助计算机，特别是利用数学工具软件 .5、模型分析、模型分析 对模型求出的解进行数学上的分析，有助于对实对模型求出的解进行数学上的分析，有助于对实际问题的解决际问题的解决 .如：如： 结果的误差分析结果的误差分析误差是否在允许的范围内误差是否在允许的范围内分析误差来源：分析误差来源： 建模假设的误差；建模假设的误差；数据测量的误差；数据测量的误差；近似求解方法的误差；近似求解方法的误差； 计算工具的舍入误差计算工具的舍入误差 . 结果的统计分析结果的统计分析结果是否符合特定的统计规律结果是否符合特定的统计规律 模型对数据的灵敏度分析模型对数据的灵敏度分析模型的结果是否会因数据的微

25、小改变而发生大的变化模型的结果是否会因数据的微小改变而发生大的变化 对假设的鲁棒性分析对假设的鲁棒性分析模型的结果是否对某一假设非常依赖模型的结果是否对某一假设非常依赖 不同模型间的对比分析不同模型间的对比分析robustness第一章第一章 组合优化模型组合优化模型与计算复杂性与计算复杂性226、模型检验、模型检验 将求解结果和分析结果翻译回到实际问题之中，将求解结果和分析结果翻译回到实际问题之中，与实际现象、实际数据进行比较，检验是否与实际吻与实际现象、实际数据进行比较，检验是否与实际吻合合 . 如果吻合较好，则模型及其结果可以应用于实际如果吻合较好，则模型及其结果可以应用于实际问题；如果

26、吻合不好，则需要对模型进行修正问题；如果吻合不好，则需要对模型进行修正 .7、改进模型、改进模型 吻合不好，问题常常出现在模型假设上吻合不好，问题常常出现在模型假设上 . 可能由可能由于假设了过于苛刻的条件，或者忽略了一些不该忽略于假设了过于苛刻的条件，或者忽略了一些不该忽略的因素的因素. 所以所以, 要对实际问题中的主次因素再次分析要对实际问题中的主次因素再次分析,对模型进行修改、补充、完善对模型进行修改、补充、完善 . 需要多次反复才能达需要多次反复才能达到比较满意的程度到比较满意的程度 。238、模型应用、模型应用 数学建模最终的目的是为了解决问题数学建模最终的目的是为了解决问题 . 一

27、方面可一方面可以解释以前的实践成果；另一方面可以为现在的实际以解释以前的实践成果；另一方面可以为现在的实际问题提供解决方案，甚至可以对一些不确定的现象或问题提供解决方案，甚至可以对一些不确定的现象或规律作出预测规律作出预测 .现实问题现实问题简化、假设简化、假设建立模型建立模型求解模型求解模型检验分析模型检验分析模型模型应用模型应用观察、分析观察、分析收集数据收集数据确定主要因素确定主要因素及相互关系及相互关系Go back第一章第一章 组合优化模型组合优化模型与计算复杂性与计算复杂性24Example 2 某商场根据客流量统计得出一周中每天所需要的某商场根据客流量统计得出一周中每天所需要的营

28、业员数如表：营业员数如表：营业员配置问题营业员配置问题时间时间周一周一周二周二周三周三周四周四周五周五周六周六周日周日所需营业员数所需营业员数677278768510698 如果规定每个营业员每周连续工作如果规定每个营业员每周连续工作 5 天，休息天，休息 2 天，求总人数最少的营业员排班方案天，求总人数最少的营业员排班方案 .Solution : 设设 xj 为从周为从周 j 开始连续工作开始连续工作 5 天的营业员天的营业员人数，人数，j = 1,7 (其中其中 x7 为周日开始连续工作为周日开始连续工作 5 天的天的营业员数营业员数)，则，则71minjjzx14567. .67stxx

29、xxx71minjjzx14567. .67stxxxxx1256772xxxxx1236778xxxxx1234776xxxxx1234585xxxxx23456106xxxxx3456798xxxxx0,1,.,106 ,1,.,7jxj可行解集可行解集是有限集是有限集25Example 3 旅行商问题旅行商问题（Traveling Salesman Problem）TSP : 有一位旅行售货员，欲到城市有一位旅行售货员，欲到城市 v1，v2,，vn 进行商品销售，已知：进行商品销售，已知： 的距离为的距离为 wij.( , ).他从其中某个城市出发，需访问每一个他从其中某个城市出发，需访

30、问每一个城市一次而回到出发的城市城市一次而回到出发的城市.问应如何计划他的旅行问应如何计划他的旅行路线，使他所走路线的总长度最短？路线，使他所走路线的总长度最短？ijvvij,1i jnTSP可分为：对称（可分为：对称（dij = dji)和非对称（和非对称（dij dji）距离两种）距离两种第一章第一章 组合优化模型组合优化模型与计算复杂性与计算复杂性26Hamilton 回路：回路：不含平行不含平行边及自环边及自环 这是这是1856年，年，Hamilton 首先提出的所谓环球首先提出的所谓环球航行问题而得名。它的存在性远比航行问题而得名。它的存在性远比 Eular 回路的存回路的存在性复杂

31、得多。在性复杂得多。最优最优 Hamilton 回路：回路：在赋权图中，权和最小的在赋权图中，权和最小的 Hamilton 回路回路 .过简单图过简单图 G 的每一个顶点一次且仅一次的回路的每一个顶点一次且仅一次的回路 .27最优旅行商问题与最优最优旅行商问题与最优 Hamilton 回路一样吗？回路一样吗？ 如果不满足三角不等式，则可通如果不满足三角不等式，则可通过求最短路方法，构造新图，使之满过求最短路方法，构造新图，使之满足三角不等式足三角不等式 . 所以以下仅讨论最优所以以下仅讨论最优的的 Hamilton 回路回路 . 2 5 2 3Theorem 1 如果赋权图满足三角不等式如果赋

32、权图满足三角不等式（欧氏距离），则它的最优旅行商回路（欧氏距离），则它的最优旅行商回路与最优与最优 Hamilton 回路相同回路相同 （Hamilton 回路存在时）回路存在时）.第一章第一章 组合优化模型组合优化模型与计算复杂性与计算复杂性28minijijijd xTSP 问题的数学模型（问题的数学模型（非对称的非对称的）1. .11(1)nijjstxin111(2)nijixjn,1221,2,(3)iji j sxssnsn,110iji jnijxij表示回路通过第 个城市到第 个城市的边否则 1iji Sj Sx或v6v4v5v3v2v1Note：条件条件(1)，(2)表示每个

33、城市经过一表示每个城市经过一次，但不能保证它可行次，但不能保证它可行. 要求局部不构成圈，条件要求局部不构成圈，条件(3)就是为就是为了约束这一点了约束这一点 .29共同特点：可行方案是有限的共同特点：可行方案是有限的 组合优化问题组合优化问题 Definition 1 组合优化问题组合优化问题是一个极小化（或极大是一个极小化（或极大化）的问题，它是由以下三部分组成：化）的问题，它是由以下三部分组成：（1）实例集合）实例集合 ；（2）对每个实例）对每个实例 I，有一个有穷的可行解集合，有一个有穷的可行解集合 S(I)；（3）目标函数）目标函数 f ，它对于每个实例，它对于每个实例 I 和每个可

34、行解和每个可行解 S(I)，赋以一个实数，赋以一个实数 f (I, ). 则实例则实例I的最优解为的最优解为这样一个可行解这样一个可行解 * S(I) ,它使得对于所有它使得对于所有S(I)，都有都有 (I, *) f (I, ) （f (I, *) f( I, )）.问题：问题：一类实际问题的数学模型的总称，如一类实际问题的数学模型的总称，如TSP、 LP etc ；实例实例：（一个问题中总包含了若干个参数）对问题一个问题中总包含了若干个参数）对问题 给定一组参数所得到的例子给定一组参数所得到的例子.第一章第一章 组合优化模型组合优化模型与计算复杂性与计算复杂性30组合优化的数学模型：组合优

35、化的数学模型： Min f(x)s.t. g(x) 0 xD其中其中x为决策变量为决策变量 f(x)为目标函数为目标函数g(x)为约束函数为约束函数D为决策变量的定义域为决策变量的定义域F=x|x D, g(x) 0可行域可行域(有限集有限集) 很多组合优化问题都可以给出整数线性规划描很多组合优化问题都可以给出整数线性规划描述，甚至在一些时候还不得不利用整数线性规划的技述，甚至在一些时候还不得不利用整数线性规划的技巧来解巧来解 . 当然也可以用文字、网络等来叙述当然也可以用文字、网络等来叙述 . 线性规划是连续模型，但由于它的解的特殊结线性规划是连续模型，但由于它的解的特殊结构，也可以作为组合

36、优化问题考虑构，也可以作为组合优化问题考虑 .31 有两种思想，像珠宝商放在天鹅绒上的宝石一样有两种思想，像珠宝商放在天鹅绒上的宝石一样熠熠生辉，一个是微积分，另一个就是算法，微积分熠熠生辉，一个是微积分，另一个就是算法，微积分以及在微积分基础上建立起来的数学分析体系造就了以及在微积分基础上建立起来的数学分析体系造就了现代科学，而算法则造就了现代世界现代科学，而算法则造就了现代世界 .伯林斯基（伯林斯基（D. Berlinski ）算法思想：算法思想：指通过把数学问题的求解分解为简单的、指通过把数学问题的求解分解为简单的、刻板的、重复的机械动作，达到以数目较多的、简单刻板的、重复的机械动作，达

37、到以数目较多的、简单的量的工作去实现较复杂的质的目的的量的工作去实现较复杂的质的目的 .算法思想是数学发展的一个重要源泉算法思想是数学发展的一个重要源泉 20 世纪中叶计算机的问世是人类智力最伟大的成世纪中叶计算机的问世是人类智力最伟大的成就之一就之一 . 算法是计算机的灵魂，随着计算机融入现代算法是计算机的灵魂，随着计算机融入现代科学实践和社会生活的各个方面，算法思想的意义与科学实践和社会生活的各个方面，算法思想的意义与作用日益为数学家所认识作用日益为数学家所认识 . 是数学发展的机械化之路是数学发展的机械化之路.第一章第一章 组合优化模型组合优化模型与计算复杂性与计算复杂性32 一个科学的

38、计算过程，指一步步求解问题的通一个科学的计算过程，指一步步求解问题的通用程序，它是解决问题的程序步骤的一个清晰用程序，它是解决问题的程序步骤的一个清晰描述描述 .算法是相对问题而言的，不单单是针对问题的算法是相对问题而言的，不单单是针对问题的某个实例某个实例 .算法：算法：Note： 假设你想把某个解决问题的方法传授给一台没有假设你想把某个解决问题的方法传授给一台没有任何智能的机器，以便由它来帮你完成解决这类问题任何智能的机器，以便由它来帮你完成解决这类问题,机器会要求你怎么做？机器会要求你怎么做？( 算法的能行性算法的能行性 ) 你当然不能只告诉它一个大概或者模棱两可、含你当然不能只告诉它一

39、个大概或者模棱两可、含糊其辞，而应该明确无误地告诉它所有解决问题的细糊其辞，而应该明确无误地告诉它所有解决问题的细节，而且这些细节应详细到机器可以执行的程度节，而且这些细节应详细到机器可以执行的程度（机（机械性）械性）；你当然也不可能无休止地进行传授，而只能；你当然也不可能无休止地进行传授，而只能用到一些有限的符号，告诉它一些有限的规则用到一些有限的符号，告诉它一些有限的规则（有限（有限性）性） .33如果算法从前一步到后一步的运行是由如果算法从前一步到后一步的运行是由当时状态唯一确定的当时状态唯一确定的. 如：单纯形如：单纯形法，表上作业法法，表上作业法 . 遗传算法是随机性算法遗传算法是随

40、机性算法 .确定性算法：确定性算法： 数学上常常将算法分为数学上常常将算法分为数值算法数值算法和和非数值算法非数值算法 . 一般来说，一般来说，数值算法用于科学计算数值算法用于科学计算，主要进行代数运，主要进行代数运算；而算；而非数值算法则用于数据处理非数值算法则用于数据处理，主要进行比较和，主要进行比较和逻辑运算（也含代数运算）逻辑运算（也含代数运算） .第一章第一章 组合优化模型组合优化模型与计算复杂性与计算复杂性34 对于一个极小化（极大化）优化问题对于一个极小化（极大化）优化问题，如果给定任意一个实例如果给定任意一个实例I，算法，算法A总能找到一个可总能找到一个可行解行解* S（I）。

41、）。 使得使得 f(I, *) f(I, )（f(I, *) f(I, )）启发式算法启发式算法（近似算法，在（近似算法，在4 中介绍）中介绍） 组合优化总存在最优算法，仅讨论可计算问题组合优化总存在最优算法，仅讨论可计算问题最优算法最优算法：是否任何数学问题都有算法求解吗？是否任何数学问题都有算法求解吗？答案是否定的答案是否定的 （不可计算）（不可计算）停机问题：停机问题：给定一个带输入的计算机程序，它会停机给定一个带输入的计算机程序，它会停机 吗？吗？ 英国数学家图灵英国数学家图灵 (Turing) 证明了不存在一证明了不存在一个算法，它能对该问题的一切实例给出正确答案个算法，它能对该问题

42、的一切实例给出正确答案 . D.Hilbert 23个问题之个问题之10 Diophantus 方程的方程的可解性可解性 . （求出一个整系数方程的整数根）（求出一个整系数方程的整数根）算法的正确性不蕴含算法的有效性算法的正确性不蕴含算法的有效性35算法设计的基本方法算法设计的基本方法 本节介绍算法设计的一些基本方法本节介绍算法设计的一些基本方法 . 在进行复杂在进行复杂的算法设计时，常常利用这些基本方法（的算法设计时，常常利用这些基本方法（思想思想），有），有必要熟练掌握必要熟练掌握 .（一）（一） 穷举法穷举法穷举法：穷举法：穷举所有可能的解并进行比较和选优的方法穷举所有可能的解并进行比较

43、和选优的方法 .优点：优点：获得最优解是确切无疑的（算法的正确性）获得最优解是确切无疑的（算法的正确性） 对于运算规模较小的、运算时间允许的优化问对于运算规模较小的、运算时间允许的优化问题，如无适合该问题的优化算法时，可采用穷举法题，如无适合该问题的优化算法时，可采用穷举法 .缺点：缺点：需要大量的机时和内存空间（算法的有效性）需要大量的机时和内存空间（算法的有效性）引言中对引言中对TSP问题已有说问题已有说明，复杂性为明，复杂性为O(n-1)!) 采用穷举法的关键在于：采用穷举法的关键在于：1、能否在理论上确定所求解问题的全部可行解集；、能否在理论上确定所求解问题的全部可行解集；2、对所求解

44、问题的全部可行解集进行比选是否可能、对所求解问题的全部可行解集进行比选是否可能. （计算时间复杂性）（计算时间复杂性）第一章第一章 组合优化模型组合优化模型与计算复杂性与计算复杂性36（二）（二） 登山法登山法 （也称贪心法）（也称贪心法）登山法：登山法：从对问题的某一从对问题的某一初始推测初始推测或或初始解初始解出发，逐出发，逐步逼近给定的目标，并步逼近给定的目标，并尽可能快尽可能快地逼近更好的解；当地逼近更好的解；当进行到某一步，不能再继续逼近时，算法便终止进行到某一步，不能再继续逼近时，算法便终止 .得到的是近似解得到的是近似解或局部最优解或局部最优解 方法简单、方法简单、适用面广适用面

45、广 登山法是一个多步决策过程，每一步的选择都是登山法是一个多步决策过程，每一步的选择都是为了能构成问题的一个可行解，同时使目标函数的值为了能构成问题的一个可行解，同时使目标函数的值增加最大或最小增加最大或最小 .选择过程选择过程是以某些最优化量度为依据是以某些最优化量度为依据 . 最优化量度可以是目标函数，也可以是别的量最优化量度可以是目标函数，也可以是别的量度，它的选择是登山法的度，它的选择是登山法的关键关键 .371275144324127413532312345vvvvv12345vvvvvTSP 的距离矩阵的距离矩阵Example 2 用登山法求用登山法求 TSP .v5v4v3v2v

46olution :优化准则：最短距离优化准则：最短距离. 从从 v1 出发，有出发，有4 个选择，个选择，按优化准则：选按优化准则：选 v2 ;得：得： v1 v2 v5 v3 v4 v1总距离为：总距离为：14 复杂性为复杂性为 O(n2) .记住：没有免费的午餐！记住：没有免费的午餐！ 从选择从选择 p 个不同的个不同的城市出发，分别用登山法得到城市出发，分别用登山法得到 p 个结果个结果 . 比较得距离和最短比较得距离和最短的路线的路线 . n复杂性为复杂性为 O(pn2) .但求得的解更接近于最优解，如从但求得的解更接近于最优解，如从 v2 出发，得：出发，得：

47、 v2 v1 v3 v4 v5 v2总距离为：总距离为：10 这是最优解（运气好）这是最优解（运气好）. 也可以从一个可行解出也可以从一个可行解出发，交换相邻两个城市位置发，交换相邻两个城市位置,优化准则：总距离下降优化准则：总距离下降. v1 v2 v5 v3 v4 v1第一章第一章 组合优化模型组合优化模型与计算复杂性与计算复杂性38（三）（三） 分枝与定界法分枝与定界法分枝与定界分枝与定界法的基本思想是对有约束条件的最优化问法的基本思想是对有约束条件的最优化问题的所有可行解（其数目为有限集）空间适当地进行题的所有可行解（其数目为有限集）空间适当地进行搜索搜索 . 具体执行时，把可行解空间

48、不断分割为越来越小具体执行时，把可行解空间不断分割为越来越小的子集（称为分枝），并确定每个分枝内的解值的下的子集（称为分枝），并确定每个分枝内的解值的下界或上界（称为定界）界或上界（称为定界）. 在每次分枝后，对凡是界超在每次分枝后，对凡是界超出已知可行解值的子集被剪去，从而不断缩小搜索范出已知可行解值的子集被剪去，从而不断缩小搜索范围围. 这个过程一直进行到找出最优解为止，该可行解这个过程一直进行到找出最优解为止，该可行解的值不大于或不小于任何子集的界的值不大于或不小于任何子集的界 .优点：优点：1、适用面广、适用面广 2、可检查较少的解（运、可检查较少的解（运气好）气好）3、可获得最优解、

49、可获得最优解缺点：本质是穷缺点：本质是穷举，复杂性大于穷举法举，复杂性大于穷举法给出一个重要思想给出一个重要思想:设门槛设门槛 (称为隐枚举称为隐枚举)39设设min( )(1)x Af xmin( )(2)x Bf xAB如果如果 则称问题（则称问题（2）是问题（）是问题（1）的松弛问题）的松弛问题.Note : 1、松弛问题未必比原问题难解；、松弛问题未必比原问题难解；如：整数规划与线性规划；如：整数规划与线性规划；TSP 与指派问题与指派问题 etc. 如：如： A：寻找全国：寻找全国18 岁百米最快的运动员岁百米最快的运动员.B：寻找全国所有百米最快的运动员：寻找全国所有百米最快的运动

50、员.显然，显然，B 问题是问题是 A 问题的松弛问题，且问题的松弛问题，且B 问题更易解问题更易解 .2、如果松弛问题易解，则先解松弛问题是有益的、如果松弛问题易解，则先解松弛问题是有益的 .1）设）设 x0 是松弛问题的最优解，且是松弛问题的最优解，且 则原问题已解则原问题已解0 xA0 xA2）即使）即使 给出了原问题最优值的界给出了原问题最优值的界 f(x0) .x0BABAx0第一章第一章 组合优化模型组合优化模型与计算复杂性与计算复杂性40分枝与定界法为什么能少检查一些解？分枝与定界法为什么能少检查一些解？B10sB1B210.2s*10sB3B410.3s*几点注意：几点注意：确定

51、问题（子问题）的最优值的确定问题（子问题）的最优值的界界 通常是通过求解松弛问题，通常是通过求解松弛问题，用松弛问题的解作为界，也可用松弛问题的解作为界，也可以用启发式算法得到以用启发式算法得到 .Note 松弛问题选择的松弛问题选择的原则原则、松弛问题要与原问题的、松弛问题要与原问题的 最优值尽量接近；最优值尽量接近；松弛问题要尽量容易解松弛问题要尽量容易解 .这两个原则不易统一，所以可选择不同的松弛问题这两个原则不易统一，所以可选择不同的松弛问题41划分方法的选择划分方法的选择原则是希望分出来的子问题容易被查清，可加快计算原则是希望分出来的子问题容易被查清，可加快计算.选哪个活问题先检查选

52、哪个活问题先检查先检查最大上界（极大化问题）的活问题先检查最大上界（极大化问题）的活问题优点：优点：检查子问题较其他规则为少；检查子问题较其他规则为少；缺点：缺点：计算机储存量较大计算机储存量较大先检查最新产生的最大上界的活问题先检查最新产生的最大上界的活问题优点：优点：计算机储存量较少计算机储存量较少 ；缺点：缺点：需要更多的分支运算需要更多的分支运算选择的不同，提供了发挥的余地选择的不同，提供了发挥的余地 分枝与定界法的重要在于它提出了一类新的思分枝与定界法的重要在于它提出了一类新的思路（隐枚举法），使得许多原来不好解决的问题有路（隐枚举法），使得许多原来不好解决的问题有了解决的可能性了解

53、决的可能性. （具有普适性）（具有普适性）第一章第一章 组合优化模型组合优化模型与计算复杂性与计算复杂性42（四）（四） 分治法分治法分治法分治法就是把原问题分成若干个规模较小的子问题，就是把原问题分成若干个规模较小的子问题，这些子问题互相独立且与原问题形式相同，对每个子这些子问题互相独立且与原问题形式相同，对每个子问题分别求解，然后将各子问题的解合并得到原问题问题分别求解，然后将各子问题的解合并得到原问题的解的解 . 如果子问题仍较复杂，可递归使用上述方法如果子问题仍较复杂，可递归使用上述方法 .Note：问题的类别在细分过程中不允许改变，改变的问题的类别在细分过程中不允许改变，改变的只是问

54、题的尺度只是问题的尺度 .分治法的基本步骤：分治法的基本步骤：分治法在每一层递归上都有三个步骤：分治法在每一层递归上都有三个步骤：分解：分解：将原问题分解为若干个规模较小，相互独立，将原问题分解为若干个规模较小，相互独立，与原问题形式相同的子问题；与原问题形式相同的子问题；解决：解决：若子问题规模较小而容易被解决则直接解，否若子问题规模较小而容易被解决则直接解，否则递归地解各个子问题；则递归地解各个子问题；合并：合并：将各个子问题的解合并为原问题的解将各个子问题的解合并为原问题的解.43 整序问题的快速算法是典型的分治策略运用整序问题的快速算法是典型的分治策略运用.8 1 9 6 7 5 3

55、281967532合并合并合并合并合并合并合并合并1 86 95 72 31 6 8 92 3 5 71 2 3 5 6 7 8 9合并合并合并合并合并合并第一章第一章 组合优化模型组合优化模型与计算复杂性与计算复杂性44分治法所能解决的问题一般具有以下几个特征：分治法所能解决的问题一般具有以下几个特征：1、该问题的规模缩小到一定的程度就可以容易地解决、该问题的规模缩小到一定的程度就可以容易地解决;2、该问题可以分解为若干个规模较小的相同问题；、该问题可以分解为若干个规模较小的相同问题；3、利用该问题分解出的子问题的解可以合并为该问、利用该问题分解出的子问题的解可以合并为该问 题的解；题的解；

56、 4、该问题所分解出的各个子问题是相互独立的，即、该问题所分解出的各个子问题是相互独立的，即 子问题之间不包含公共的子子问题子问题之间不包含公共的子子问题 . 如何使用，因问题而异如何使用，因问题而异. 分治法的应用很广，如铁路运输技术计划中的分治法的应用很广，如铁路运输技术计划中的空车调度计划等空车调度计划等.45（五）（五） 递归方法递归方法递归递归就是自己调用自己的过程就是自己调用自己的过程 . 这里的这里的“自己自己”可以可以是函数、过程、语言结构和解题方法等是函数、过程、语言结构和解题方法等 .递归方法思路递归方法思路: 第一步骤（递归步骤）：将规模较大的原问题分第一步骤（递归步骤）

57、：将规模较大的原问题分解为一个或多个规模更小、但具有类似于原问题特性解为一个或多个规模更小、但具有类似于原问题特性的子问题。即较大的问题递归地用较小的子问题来描的子问题。即较大的问题递归地用较小的子问题来描述，解原问题的方法同样可用来解这些子问题述，解原问题的方法同样可用来解这些子问题. 第二步骤：确定一个或多个无须分解、可直接求第二步骤：确定一个或多个无须分解、可直接求解的最小子问题（称为递归的终止条件）解的最小子问题（称为递归的终止条件）.第一章第一章 组合优化模型组合优化模型与计算复杂性与计算复杂性46Example 4斐波那契数定义为下列无穷整数的序列：斐波那契数定义为下列无穷整数的序

58、列： 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89， 第第 n 个元素是紧接在它之前的两个元素之和，用个元素是紧接在它之前的两个元素之和，用FIB(n) 表示第表示第 n 个斐波那契数，则可用如下递归关系个斐波那契数，则可用如下递归关系式定义：式定义：FIB(n) = FIB(n-1) + FIB(n-2) FIB(1) = 1 FIB(2) = 1 为了计算为了计算 FIB(n) ，要递归调用，要递归调用 FIB(n-1) 、FIB(n-2) ,而为了计算而为了计算 FIB(n-1) ，除了利用已调用的，除了利用已调用的 FIB(n-2) 外，还要调用外，还要调用

59、FIB(n-3)，因此，为了计算，因此，为了计算FIB(n)需作需作 n-1 次递归调用次递归调用 . 递归调用次数递归调用次数递归深度递归深度 分治与递归像一对孪生兄弟，经常同时应分治与递归像一对孪生兄弟，经常同时应用在算法设计之中，并由此产生许多高效算法用在算法设计之中，并由此产生许多高效算法.47（六）（六） 动态规划法动态规划法Example 5 100多年前，有位美国推销员乘驿站马车多年前，有位美国推销员乘驿站马车向西旅行向西旅行 ，从州，从州A (state ,状态状态) 到州到州E 如图，需要如图，需要4个个驿程（驿程（stage，阶段）。问题为求从，阶段）。问题为求从 Stat

60、e A到到 State E 走哪条途径使他最安全？走哪条途径使他最安全？ 原问题为求从原问题为求从 A 到到 E 走哪条途径使保险单走哪条途径使保险单（policy，策略）的总费用达到最小？，策略）的总费用达到最小？26AB2B1B3C1C2C3D1D2E243743241543333464第一章第一章 组合优化模型组合优化模型与计算复杂性与计算复杂性4826AB2B1B3C1C2C3D1D2E243743241543333464Note : 作出各相继驿程上最佳决策。不一定产生总作出各相继驿程上最佳决策。不一定产生总的最佳决策（即的最佳决策（即Greedy 算法未必取得最佳策略）算法未必取得