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

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

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

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

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

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

6、述，而且也依赖于形态和能量形态的认识、把握和描述，而且也依赖于 对系统相关信息不断的采集、积累和加工，这就是用对系统相关信息不断的采集、积累和加工，这就是用 模型研究问题的现实活动模型研究问题的现实活动 . 7 （三）（三） 模型的分类模型的分类 1、原样模型、原样模型 原样模型原样模型是在工程开发末期建立的一种具象实是在工程开发末期建立的一种具象实 体，是具有实物形态的模型体，是具有实物形态的模型 . . 它与目的工程在结构和过程方面基本相同它与目的工程在结构和过程方面基本相同 . . 原样模型经过试验改进和完善后便是所要开发原样模型经过试验改进和完善后便是所要开发 的目的工程的目的工程 .

7、 新产品的样机、新著作的原稿新产品的样机、新著作的原稿 第一章第一章 组合优化模型组合优化模型与计算复杂性与计算复杂性 8 2、相似模型、相似模型 相似模型相似模型是根据不同系统间的相似规律（包括几是根据不同系统间的相似规律（包括几 何相似、逻辑相似和过程相似等）而建立的用于研究何相似、逻辑相似和过程相似等）而建立的用于研究 的模型的模型 . 3、图形模型、图形模型 地球仪、船体放地球仪、船体放 样样 模型、飞机风洞实验模型、飞机风洞实验 模模 拟模型等等拟模型等等 图形模型图形模型可以表达非常丰富的内容，主要有：可以表达非常丰富的内容，主要有： 图画图画 一种可以示形的图形；一种可以示形的图

8、形； 草图草图 一种可以示意的图形；一种可以示意的图形； 框图框图 一种可以表示系统的部分之间或部分一种可以表示系统的部分之间或部分 与整体之间联系的图形；与整体之间联系的图形； 称为不严格图 称为不严格图 （没有严格的规范）（没有严格的规范） 系统分析和设计人员常常借助于这些图形模型来系统分析和设计人员常常借助于这些图形模型来 开发、构建一个新系统的想象力和创造力，逐步引申开发、构建一个新系统的想象力和创造力，逐步引申 出与之有关的问题和需要进一步探索的问题，使所要出与之有关的问题和需要进一步探索的问题，使所要 开发的系统变得越来越清晰、越来越具体开发的系统变得越来越清晰、越来越具体 . .

9、 9 逻辑图逻辑图 一种可以反映因素或对象间逻辑关系一种可以反映因素或对象间逻辑关系 的图形；的图形； 如：程序流程图、 如：程序流程图、 控控 制关系图制关系图 etc. 工程图工程图 一种可以反映物体确定的结构和顺序一种可以反映物体确定的结构和顺序 关系的图形；关系的图形； 如：建筑工程图、 如：建筑工程图、 铁路站场配置图铁路站场配置图 etc. 图论图图论图 包括图论所定义的无向图包括图论所定义的无向图 G(V，E) 、 有向图有向图 G(V，A)、加权有、加权有(无无)向图向图G(V，A(E)，w). 关系关系 称为严格图称为严格图 （有严格确定的结构（有严格确定的结构 形式和规范）

10、形式和规范） 4、数学模型、数学模型 数学模型数学模型是指运用数学符号和公式来表达、研究是指运用数学符号和公式来表达、研究 对象系统的结构或过程的模型对象系统的结构或过程的模型 . . 数学模型数学模型是用数学的语言、方法去近似地刻画实际是用数学的语言、方法去近似地刻画实际 , 是由数字、字母或其他数学符号组成的，描述现实对是由数字、字母或其他数学符号组成的，描述现实对 象数量规律的数学公式、图形或算法象数量规律的数学公式、图形或算法 . 是对现实对象本质属性的抽象而又简洁的刻画，是对现实对象本质属性的抽象而又简洁的刻画， 它或能解释某些客观现象，或能预测未来的发展规它或能解释某些客观现象，或

11、能预测未来的发展规 律，或能为控制某一现象的发展提供某种意义下的最律，或能为控制某一现象的发展提供某种意义下的最 优策略或较好策略优策略或较好策略 . Go back 第一章第一章 组合优化模型组合优化模型与计算复杂性与计算复杂性 10 Example 1七桥问题七桥问题 18世纪的德国有个哥尼斯堡城，在流贯全城的普世纪的德国有个哥尼斯堡城，在流贯全城的普 雷尔河两岸和河中两个岛之间架设了七座桥，把河的雷尔河两岸和河中两个岛之间架设了七座桥，把河的 两岸和两岛连接起来，能否有这样一种走法，它通过两岸和两岛连接起来，能否有这样一种走法，它通过 每座桥一次且仅一次每座桥一次且仅一次 . 该问题由该

12、问题由Euler在在 1736年解决年解决 Solution : 11 A B C D 显然，解决该问题时，显然，解决该问题时， 两岸和岛的大小、形状以及两岸和岛的大小、形状以及 桥的长短曲直都无关，重要桥的长短曲直都无关，重要 的是什么？的是什么？ 每块陆地间有每块陆地间有 几座桥几座桥 对问题进行数学抽象：对问题进行数学抽象： 把两岸和两岛都看做顶点，将连接这些顶点的桥把两岸和两岛都看做顶点，将连接这些顶点的桥 当作边，于是得到一无向图当作边，于是得到一无向图 . 则七桥问题就成为无向图中是否存在通过每一边则七桥问题就成为无向图中是否存在通过每一边 一次且仅一次的路（即一笔画）问题一次且仅

13、一次的路（即一笔画）问题 . . 第一章第一章 组合优化模型组合优化模型与计算复杂性与计算复杂性 12 A B C D Euler 在他的论文中证明在他的论文中证明： 一个图中存在一笔画的一个图中存在一笔画的 充要条件是同时满足：充要条件是同时满足： 1、图是连通的；、图是连通的； 2、与图中每一顶点（可能有两点例外）相连的边与图中每一顶点（可能有两点例外）相连的边 （线度）必须是偶数条（线度）必须是偶数条 . . 这是关于图论这是关于图论 的第一篇论文的第一篇论文 见图可知，与四个顶点相连的边都是奇数条，因见图可知，与四个顶点相连的边都是奇数条，因 而不可能存在通过每条边一次且仅一次的画法，

14、即一而不可能存在通过每条边一次且仅一次的画法，即一 笔画不存在笔画不存在 . . 故七桥问题不可能有解故七桥问题不可能有解 . 问题原型问题原型 七桥问题七桥问题 数学模型数学模型 一笔画问题一笔画问题 无无 解解 ( (一次过七座桥不可能一次过七座桥不可能) ) 无无 解解 ( (一笔画不可能一笔画不可能) ) 数学抽象数学抽象 逻辑推理逻辑推理 翻译回去翻译回去 有无解？有无解？ 这是利用数学模型分析和解决问题的一个成功范例这是利用数学模型分析和解决问题的一个成功范例 13 （一）（一） 数学模型的特点数学模型的特点 1、高度的抽象性高度的抽象性 数学方法不仅要抛开事物的次要属性，突出事物

15、数学方法不仅要抛开事物的次要属性，突出事物 的本质属性，而且要舍弃事物的物质和能量方面的具的本质属性，而且要舍弃事物的物质和能量方面的具 体内容，只考虑其数量关系和空间形式，同时还要把体内容，只考虑其数量关系和空间形式，同时还要把 这些数量关系和空间形式作进一步的抽象，加以形式这些数量关系和空间形式作进一步的抽象，加以形式 化和符号化，以便能够进行逻辑推理和数值运化和符号化，以便能够进行逻辑推理和数值运算算 . 这种高度的抽象性，实质是对事物认识上的高度这种高度的抽象性，实质是对事物认识上的高度 概括和深化，对同类问题包含更多的经验和理解概括和深化，对同类问题包含更多的经验和理解 . 第一章第

16、一章 组合优化模型组合优化模型与计算复杂性与计算复杂性 14 2、高度的精确性高度的精确性 数学方法的高度精确性表现在三个方面：数学方法的高度精确性表现在三个方面： 一是一是表达各种因素、变量和它们之间的关系相当表达各种因素、变量和它们之间的关系相当 明确、清楚；明确、清楚；二是二是逻辑推演和运算规则十分严密；逻辑推演和运算规则十分严密；三三 是是结论非常确定结论非常确定 . 数学方法可以处理多变量、关系复杂的问题，可数学方法可以处理多变量、关系复杂的问题，可 在有意义的范围内获得令人满意的计算精度在有意义的范围内获得令人满意的计算精度 . 特别适合于揭示事物的量的规定性，成为定量研特别适合于

17、揭示事物的量的规定性，成为定量研 究的有力工具究的有力工具 . 15 3、应用的普适性应用的普适性 数学方法的高度抽象和精确，使之比任何一种科数学方法的高度抽象和精确，使之比任何一种科 学方法的应用范围都更为广泛学方法的应用范围都更为广泛 . 只存在尚未运用数学方法的领域而不存在不能运只存在尚未运用数学方法的领域而不存在不能运 用数学方法的领域用数学方法的领域 . 许多相同形式的数学模型可用于不同的实际问许多相同形式的数学模型可用于不同的实际问 题，具有重要类比和借鉴意义题，具有重要类比和借鉴意义 .数学方法的形式化和数学方法的形式化和 公理化，使模型本身、计算过程和计算结果都便于交公理化，使

18、模型本身、计算过程和计算结果都便于交 流，数学模型易变动，便于修改和改变计算关系，分流，数学模型易变动，便于修改和改变计算关系，分 析和求解问题速度快，求解成本低析和求解问题速度快，求解成本低 . . 数学模型缺乏直观性、形象性和实时感数学模型缺乏直观性、形象性和实时感 第一章第一章 组合优化模型组合优化模型与计算复杂性与计算复杂性 16 （二）（二） 数学模型分类数学模型分类 数学模型分类的方法很多，如：数学模型分类的方法很多，如： 1、按所研究问题的性质分类按所研究问题的性质分类 静态模型与动态模型静态模型与动态模型 确定型模型与随机型模型确定型模型与随机型模型 连续模型与离散模型连续模型

19、与离散模型 线性模型与非线性模型线性模型与非线性模型 宏观模型与微观模型宏观模型与微观模型 17 2、按模型的解的特征分类按模型的解的特征分类 解析模型与数值模型解析模型与数值模型 3、按模型所用的数学方法分类按模型所用的数学方法分类 初等模型、微分方程模型、差分方程模型、优初等模型、微分方程模型、差分方程模型、优 化模型等化模型等 4、按模型研究的实际范畴分类、按模型研究的实际范畴分类 人口模型、生态系统模型人口模型、生态系统模型 、交通流模型、经济、交通流模型、经济 模型、模型、 基因模型等基因模型等 5、按对实际问题了解的程度分类、按对实际问题了解的程度分类 白箱模型、灰箱模型、黑箱模型

20、白箱模型、灰箱模型、黑箱模型 第一章第一章 组合优化模型组合优化模型与计算复杂性与计算复杂性 18 （三）（三） 数学建模的基本步骤数学建模的基本步骤 数学模型因问题不同而异，对同一问题，从不同数学模型因问题不同而异，对同一问题，从不同 角度、不同要求出发，甚至问题的解表示结构不同，角度、不同要求出发，甚至问题的解表示结构不同， 都可以建立不同的数学模型都可以建立不同的数学模型. 建立数学模型也没有固建立数学模型也没有固 定的方法、标准定的方法、标准 . 不同的实际问题，建模模式千差万不同的实际问题，建模模式千差万 别别. 在此介绍通常的几个步骤：在此介绍通常的几个步骤： 数学建模问题直接来源

21、各领域实际，往往含糊不数学建模问题直接来源各领域实际，往往含糊不 清（目的、条件、类型清（目的、条件、类型 etc.）. 首先，要对该问题进首先，要对该问题进 行全面的、深入细微的调查和研究行全面的、深入细微的调查和研究. 明确所解决问题明确所解决问题 的性质，着手收集数据的性质，着手收集数据 ； 1、明确问题明确问题 合理地、有目的地合理地、有目的地 注意精度注意精度 19 2、合理假设合理假设 现实问题错综复杂，涉及面非常之广现实问题错综复杂，涉及面非常之广. 一个数学一个数学 模型面面俱到、无所不包地反映一个现实是不可能模型面面俱到、无所不包地反映一个现实是不可能 的，即使可能，也因其过

22、于复杂而很难求解，也是没的，即使可能，也因其过于复杂而很难求解，也是没 有必要的有必要的 . 所以，要作所以，要作合理合理的假设的假设 . 1、简化问题、简化问题 2、限定适用范围、限定适用范围 但也不能忽略实质但也不能忽略实质 相关的因素相关的因素 作假设的依据通常是出于对问题内在规律的认识作假设的依据通常是出于对问题内在规律的认识, 或来自对数据或现象的分析，也可以是二者的综合或来自对数据或现象的分析，也可以是二者的综合. 善于辨别问题的主次，抓住主要因素，通过合理假设善于辨别问题的主次，抓住主要因素，通过合理假设, 使问题简化以便进行数学描述使问题简化以便进行数学描述 . 假设是在模型的

23、建立、求解和分析过程中完善假设是在模型的建立、求解和分析过程中完善 . 通常开始让问题尽通常开始让问题尽 可能简化可能简化 第一章第一章 组合优化模型组合优化模型与计算复杂性与计算复杂性 20 3、建立模型建立模型 建模时，要分清问题的类型恰当使用数学工具；建模时，要分清问题的类型恰当使用数学工具； 抓住问题的本质简化变量之间的关系抓住问题的本质简化变量之间的关系 . 用什么样的方法建立数学模型，没有绝对的标用什么样的方法建立数学模型，没有绝对的标 准；数学模型的形式可以是多种多样，数学公式、表准；数学模型的形式可以是多种多样，数学公式、表 格、图形、算法格、图形、算法 . 模型的优劣在于是否

24、采用了恰当的方法，合理地模型的优劣在于是否采用了恰当的方法，合理地 描述了实际问题，而不在于是否用到了高深的数学工描述了实际问题，而不在于是否用到了高深的数学工 具具 . 数学建模是一个过程数学建模是一个过程 . 21 4、模型求解模型求解 不同的模型要用到不同的数学工具求解不同的模型要用到不同的数学工具求解 . 这就要这就要 求从事实际工作者对相应的数学分支知识有一定的了求从事实际工作者对相应的数学分支知识有一定的了 解解 . 可借助计算机，特别是利用数学工具软件可借助计算机，特别是利用数学工具软件 . 5、模型分析模型分析 对模型求出的解进行数学上的分析，有助于对实对模型求出的解进行数学上

25、的分析，有助于对实 际问题的解决际问题的解决 . 如如： 结果的误差分析结果的误差分析误差是否在允许的范围内误差是否在允许的范围内 分析误差来源：分析误差来源： 建模假设的误差；建模假设的误差；数据测量的误差；数据测量的误差； 近似求解方法的误差；近似求解方法的误差； 计算工具的舍入误差计算工具的舍入误差 . 结果的统计分析结果的统计分析 结果是否符合特定的统计规律结果是否符合特定的统计规律 模型对数据的灵敏度分析模型对数据的灵敏度分析 模型的结果是否会因数据的微小改变而发生大的变化模型的结果是否会因数据的微小改变而发生大的变化 对假设的鲁棒性分析对假设的鲁棒性分析 模型的结果是否对某一假设非

26、常依赖模型的结果是否对某一假设非常依赖 不同模型间的对比分析不同模型间的对比分析 robustness 第一章第一章 组合优化模型组合优化模型与计算复杂性与计算复杂性 22 6、模型检验模型检验 将求解结果和分析结果翻译回到实际问题之中，将求解结果和分析结果翻译回到实际问题之中， 与实际现象、实际数据进行比较，检验是否与实际吻与实际现象、实际数据进行比较，检验是否与实际吻 合合 . 如果吻合较好，则模型及其结果可以应用于实际如果吻合较好，则模型及其结果可以应用于实际 问题；如果吻合不好，则需要对模型进行修正问题；如果吻合不好，则需要对模型进行修正 . 7、改进模型改进模型 吻合不好，问题常常出

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

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

29、二周三周三周四周四周五周五周六周六周日周日 所需营业员数所需营业员数677278768510698 如果规定每个营业员每周连续工作如果规定每个营业员每周连续工作 5 天，休息天，休息 2 天，求总人数最少的营业员排班方案天，求总人数最少的营业员排班方案 . Solution : 设设 xj 为从周为从周 j 开始连续工作开始连续工作 5 天的营业员天的营业员 人数，人数，j = 1,7 (其中其中 x7 为周日开始连续工作为周日开始连续工作 5 天的天的 营业员数营业员数)，则，则 7 1 min j j zx 14567 . .67stxxxxx 7 1 min j j zx 14567 .

30、 .67stxxxxx 12567 72xxxxx 12367 78xxxxx 12347 76xxxxx 12345 85xxxxx 23456 106xxxxx 34567 98xxxxx 0,1,.,106 ,1,.,7 j xj 可行解集可行解集 是有限集是有限集 25 Example 3 旅行商问题旅行商问题 （Traveling Salesman Problem） TSP : 有一位旅行售货员，欲到城市有一位旅行售货员，欲到城市 v1，v2,，vn 进行商品销售，已知：进行商品销售，已知： 的距离为的距离为 wij.( ,.( , ). ).他从其中某个城市出发，需访问每一个他从其

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

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

33、. 2 5 2 3 Theorem 1 如果赋权图满足三角不等式如果赋权图满足三角不等式 （欧氏距离），则它的最优旅行商回路（欧氏距离），则它的最优旅行商回路 与最优与最优 Hamilton 回路相同回路相同 （Hamilton 回路存在时）回路存在时）. 第一章第一章 组合优化模型组合优化模型与计算复杂性与计算复杂性 28 min ijij ij d x TSP 问题的数学模型（问题的数学模型（非对称的非对称的） 1 . .11(1) n ij j stxin 1 11(2) n ij i xjn , 1221,2,(3) ij i j s xssnsn ,11 0 ij i jnij x

34、ij 表示回路通过第 个城市到第 个城市的边 否则 1 ij i Sj S x 或 v6 v4 v5 v3v2 v1 Note：条件条件(1)，(2)表表示每个城市经过一示每个城市经过一 次，但不能保证它可行次，但不能保证它可行. . 要求局部不构成圈，条件要求局部不构成圈，条件(3)就是为就是为 了约束这一点了约束这一点 . 29 共同特点：可行方案是有限的共同特点：可行方案是有限的 组合优化问题组合优化问题 Definition 1 组合优化问题组合优化问题是一个极小化（或极大是一个极小化（或极大 化）的问题，它是由以下三部分组成：化）的问题，它是由以下三部分组成： （1）实例集合）实例集

35、合 ； （2）对每个实例）对每个实例 I，有一个有穷的可行解集合，有一个有穷的可行解集合 S(I)； （3）目标函数目标函数 f ，它对于每个实例，它对于每个实例 I 和每个可行解和每个可行解 S(I)，赋以一个实数，赋以一个实数 f (I, ). 则实例则实例I的最优解为的最优解为 这样一个可行解这样一个可行解 * S(I) ,它使得对于所有它使得对于所有S(I)， 都有都有 (I, *) f (I, ) （f (I, *) f( I, )）. 问题：问题：一类实际问题的数学模型的总称，如一类实际问题的数学模型的总称，如TSP、 LP etc ； 实例实例：（一个问题中总包含了若干个参数）对

36、问题一个问题中总包含了若干个参数）对问题 给定一组参数所得到的例子给定一组参数所得到的例子. 第一章第一章 组合优化模型组合优化模型与计算复杂性与计算复杂性 30 组合优化的数学模型：组合优化的数学模型： Min f(x) s.t. g(x) 0 xD 其中其中x为决策变量为决策变量 f(x)为目标函数为目标函数 g(x)为约束函数为约束函数 D为决策变量的定义域为决策变量的定义域 F=x|x D, g(x) 0可行可行域域(有限集有限集) 很多组合优化问题都可以给出整数线性规划描很多组合优化问题都可以给出整数线性规划描 述，甚至在一些时候还不得不利用整数线性规划的技述，甚至在一些时候还不得不

37、利用整数线性规划的技 巧来解巧来解 . 当然也可以用文字、网络等来叙述当然也可以用文字、网络等来叙述 . 线性规划是连续模型，但由于它的解的特殊结线性规划是连续模型，但由于它的解的特殊结 构，也可以作为组合优化问题考虑构，也可以作为组合优化问题考虑 . 31 有两种思想，像珠宝商放在天鹅绒上的宝石一样有两种思想，像珠宝商放在天鹅绒上的宝石一样 熠熠生辉，一个是微积分，另一个就是算法，微积分熠熠生辉，一个是微积分，另一个就是算法，微积分 以及在微积分基础上建立起来的数学分析体系造就了以及在微积分基础上建立起来的数学分析体系造就了 现代科学，而算法则造就了现代世界现代科学，而算法则造就了现代世界

38、. 伯林斯基伯林斯基（D. Berlinski ） 算法思想：算法思想：指通过把数学问题的求解分解为简单的、指通过把数学问题的求解分解为简单的、 刻板的、重复的机械动作，达到以数目较多的、简单刻板的、重复的机械动作，达到以数目较多的、简单 的量的工作去实现较复杂的质的目的的量的工作去实现较复杂的质的目的 .算法思想是数学发展的一个重要源泉算法思想是数学发展的一个重要源泉 20 世纪中叶计算机的问世是人类智力最伟大的成世纪中叶计算机的问世是人类智力最伟大的成 就之一就之一 . 算法是计算机的灵魂，随着计算机融入现代算法是计算机的灵魂，随着计算机融入现代 科学实践和社会生活的各个方面，算法思想的意

39、义与科学实践和社会生活的各个方面，算法思想的意义与 作用日益为数学家所认识作用日益为数学家所认识 . 是数学发展的机械化之路是数学发展的机械化之路. 第一章第一章 组合优化模型组合优化模型与计算复杂性与计算复杂性 32 一个科学的计算过程，指一步步求解问题的通一个科学的计算过程，指一步步求解问题的通 用程序，它是解决问题的程序步骤的一个清晰用程序，它是解决问题的程序步骤的一个清晰 描述描述 . 算法是相对问题而言的，不单单是针对问题的算法是相对问题而言的，不单单是针对问题的 某个实例某个实例 . 算法：算法： Note： 假设你想把某个解决问题的方法传授给一台没有假设你想把某个解决问题的方法传

40、授给一台没有 任何智能的机器，以便由它来帮你完成解决这类问题任何智能的机器，以便由它来帮你完成解决这类问题, , 机器会要求你怎么做？机器会要求你怎么做？( ( 算法的能行性算法的能行性 ) ) 你当然不能只告诉它一个大概或者模棱两可、含你当然不能只告诉它一个大概或者模棱两可、含 糊其辞，而应该明确无误地告诉它所有解决问题的细糊其辞，而应该明确无误地告诉它所有解决问题的细 节，而且这些细节应详细到机器可以执行的程度节，而且这些细节应详细到机器可以执行的程度（机（机 械性）械性）；你当然也不可能无休止地进行传授，而只能；你当然也不可能无休止地进行传授，而只能 用到一些有限的符号，告诉它一些有限的

41、规则用到一些有限的符号，告诉它一些有限的规则（有限（有限 性）性） . . 33 如果算法从前一步到后一步的运行是由如果算法从前一步到后一步的运行是由 当时状态唯一确定的当时状态唯一确定的. . 如：单纯形如：单纯形 法，表上作业法法，表上作业法 . . 遗传算法是随机性算法遗传算法是随机性算法 . 确定性算法：确定性算法： 数学上常常将算法分为数学上常常将算法分为数值算法数值算法和和非数值算法非数值算法 . 一般来说，一般来说，数值算法用于科学计算数值算法用于科学计算，主要进行代数运，主要进行代数运 算；而算；而非数值算法则用于数据处理非数值算法则用于数据处理，主要进行比较和，主要进行比较和

42、 逻辑运算（也含代数运算）逻辑运算（也含代数运算） . 第一章第一章 组合优化模型组合优化模型与计算复杂性与计算复杂性 34 对于一个极小化（极大化）优化问题对于一个极小化（极大化）优化问题， 如果给定任意一个实例如果给定任意一个实例I，算法，算法A总能找到一个可总能找到一个可 行解行解* S（I）。）。 使得使得 f(I, *) f(I, )（f(I, *) f(I, )） 启发式算法启发式算法（近似算法，在（近似算法，在4 中介绍中介绍） 组合优化总存在最优算法，仅讨论可计算问题组合优化总存在最优算法，仅讨论可计算问题 最优算法最优算法： 是否任何数学问题都有算法求解吗？是否任何数学问题都

43、有算法求解吗？ 答案是否定的答案是否定的 （不可计算）（不可计算） 停机问题：停机问题：给定一个带输入的计算机程序，它会停机给定一个带输入的计算机程序，它会停机 吗？吗？ 英国数学家图灵英国数学家图灵 (Turing) 证明了不存在一证明了不存在一 个算法，它能对该问题的一切实例给出正确答案个算法，它能对该问题的一切实例给出正确答案 . D.Hilbert 23个问题之个问题之10 Diophantus 方程的方程的 可解性可解性 . （求出一个整系数方程的整数根）（求出一个整系数方程的整数根） 算法的正确性不蕴含算法的有效性算法的正确性不蕴含算法的有效性 35 算法设计的基本方法算法设计的基

44、本方法 本节介绍算法设计的一些基本方法本节介绍算法设计的一些基本方法 . 在进行复杂在进行复杂 的算法设计时，常常利用这些基本方法（的算法设计时，常常利用这些基本方法（思想思想），有），有 必要熟练掌握必要熟练掌握 . （一）（一） 穷举法穷举法 穷举法：穷举法：穷举所有可能的解并进行比较和选优的方法穷举所有可能的解并进行比较和选优的方法 . 优点：优点：获得最优解是确切无疑的（算法的正确性）获得最优解是确切无疑的（算法的正确性） 对于运算规模较小的、运算时间允许的优化问对于运算规模较小的、运算时间允许的优化问 题，如无适合该问题的优化算法时，可采用穷举法题，如无适合该问题的优化算法时，可采用

45、穷举法 . 缺点：缺点：需要大量的机时和内存空间（算法的有效性）需要大量的机时和内存空间（算法的有效性） 引言中对引言中对TSP问题已有说问题已有说 明，复杂性为明，复杂性为O(n-1)!) 采用穷举法的关键在于：采用穷举法的关键在于： 1、能否在理论上确定所求解问题的全部可行解集；、能否在理论上确定所求解问题的全部可行解集； 2、对所求解问题的全部可行解集进行比选是否可能、对所求解问题的全部可行解集进行比选是否可能. （计算时间复杂性）（计算时间复杂性） 第一章第一章 组合优化模型组合优化模型与计算复杂性与计算复杂性 36 （二）（二） 登山法登山法 （也称贪心法）（也称贪心法） 登山法：登

46、山法：从对问题的某一从对问题的某一初始推测初始推测或或初始解初始解出发，逐出发，逐 步逼近给定的目标，并步逼近给定的目标，并尽可能快尽可能快地逼近更好的解；当地逼近更好的解；当 进行到某一步，不能再继续逼近时，算法便终止进行到某一步，不能再继续逼近时，算法便终止 . 得到的是近似解得到的是近似解 或局部最优解或局部最优解 方法简单、方法简单、 适用面广适用面广 登山法是一个多步决策过程，每一步的选择都是登山法是一个多步决策过程，每一步的选择都是 为了能构成问题的一个可行解，同时使目标函数的值为了能构成问题的一个可行解，同时使目标函数的值 增加最大或最小增加最大或最小 . 选择过程选择过程是以某

47、些最优化量度为依据是以某些最优化量度为依据 . 最优化量度可以是目标函数，也可以是别的量最优化量度可以是目标函数，也可以是别的量 度，它的选择是登山法的度，它的选择是登山法的关键关键 . 37 1275 1443 2412 7413 5323 12345 vvvvv 1 2 3 4 5 v v v v v TSP 的距离矩阵的距离矩阵 Example 2 用登山法求用登山法求 TSP . v5 v4v3 v2 v1 4 1 4 3 2 3 5 72 1 Solution : 优化准则：最短距离优化准则：最短距离. 从从 v1 出发，有出发，有4 个选择，个选择， 按优化准则：选按优化准则：选

48、v2 ; 得：得： v1 v2 v5 v3 v4 v1 总距离为总距离为：14 复杂性为复杂性为 O(n2) . 记住：没有免费的午餐！记住：没有免费的午餐！ 从选择从选择 p 个不同的个不同的 城市出发，分别用登山法得到城市出发，分别用登山法得到 p 个结果个结果 . 比较得距离和最短比较得距离和最短 的路线的路线 . n 复杂性为复杂性为 O(pn2) . 但求得的解更接近于最优解，如从但求得的解更接近于最优解，如从 v2 出发，得：出发，得： v2 v1 v3 v4 v5 v2 总距离为总距离为：10 这是最优解（运气好）这是最优解（运气好）. 也可以从一个可行解出也可以从一个可行解出

49、发，交换相邻两个城市位置发，交换相邻两个城市位置, 优化准则：总距离下降优化准则：总距离下降. v1 v2 v5 v3 v4 v1 第一章第一章 组合优化模型组合优化模型与计算复杂性与计算复杂性 38 （三）（三） 分枝与定界法分枝与定界法 分枝与定界分枝与定界法的基本思想是对有约束条件的最优化问法的基本思想是对有约束条件的最优化问 题的所有可行解（其数目为有限集）空间适当地进行题的所有可行解（其数目为有限集）空间适当地进行 搜索搜索 . 具体执行时，把可行解空间不断分割为越来越小具体执行时，把可行解空间不断分割为越来越小 的子集（称为分枝），并确定每个分枝内的解值的下的子集（称为分枝），并确

50、定每个分枝内的解值的下 界或上界（称为定界）界或上界（称为定界）. . 在每次分枝后，对凡是界超在每次分枝后，对凡是界超 出已知可行解值的子集被剪去，从而不断缩小搜索范出已知可行解值的子集被剪去，从而不断缩小搜索范 围围. . 这个过程一直进行到找出最优解为止，该可行解这个过程一直进行到找出最优解为止，该可行解 的值不大于或不小于任何子集的界的值不大于或不小于任何子集的界 . 优点：优点：1、适用面广、适用面广 2、可检查较少的解（运、可检查较少的解（运 气好）气好）3、可获得最优解、可获得最优解 缺点：本质是穷缺点：本质是穷 举，复杂性大于穷举法举，复杂性大于穷举法 给出一个重要思想给出一个

51、重要思想: 设门槛设门槛 (称为隐枚举称为隐枚举) 39 设设 min( )(1) x A f x min( )(2) x B f x AB 如果如果 则称问题（则称问题（2）是问题（）是问题（1）的松弛问题）的松弛问题. . Note : 1、松弛问题未必比原问题难解；、松弛问题未必比原问题难解； 如：如：整数规划与线性规划；整数规划与线性规划；TSP 与指派问题与指派问题 etc. 如：如： A：寻找全国：寻找全国18 岁百米最快的运动员岁百米最快的运动员. B：寻找：寻找全国所有百米最快的运动员全国所有百米最快的运动员. . 显然，显然，B 问题是问题是 A 问题的松弛问题，且问题的松弛

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

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

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

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

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

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

58、可以合并为该问利用该问题分解出的子问题的解可以合并为该问 题的解；题的解； 4、该问题所分解出的各个子问题是相互独立的，即该问题所分解出的各个子问题是相互独立的，即 子问题之间不包含公共的子子问题子问题之间不包含公共的子子问题 . . 如何使用，因问题而异如何使用，因问题而异. . 分治法的应用很广，如铁路运输技术计划中的分治法的应用很广，如铁路运输技术计划中的 空车调度计划等空车调度计划等. 45 （五）（五） 递归方法递归方法 递归递归就是自己调用自己的过程就是自己调用自己的过程 . . 这里的这里的“自己自己”可可 以以 是函数、过程、语言结构和解题方法等是函数、过程、语言结构和解题方法

59、等 . 递归方法思路递归方法思路: : 第一步骤（递归步骤）：将规模较大的原问题分第一步骤（递归步骤）：将规模较大的原问题分 解为一个或多个规模更小、但具有类似于原问题特性解为一个或多个规模更小、但具有类似于原问题特性 的子问题。即较大的问题递归地用较小的子问题来描的子问题。即较大的问题递归地用较小的子问题来描 述，解原问题的方法同样可用来解这些子问题述，解原问题的方法同样可用来解这些子问题. . 第二步骤：确定一个或多个无须分解、可直接求第二步骤：确定一个或多个无须分解、可直接求 解的最小子问题（称为递归的终止条件）解的最小子问题（称为递归的终止条件）. . 第一章第一章 组合优化模型组合优

60、化模型与计算复杂性与计算复杂性 46 Example 4斐波那契数定义为下列无穷整数的序列：斐波那契数定义为下列无穷整数的序列： 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