第一章组合优化模型

1、1 第一章第一章 组合优化模型组合优化模型 combinatorial optimization theory2第一章第一章 模模 型型1 关于模型关于模型2 数学模型数学模型3 组合优化模型组合优化模型3第一章第一章 组合优化模型组合优化模型 模型（模型（model ）是所研究的系统、过程、事物或）是所研究的系统、过程、事物或概念的一种表达形式概念的一种表达形式 . 一、模型的概念一、模型的概念 模型不是研究对象本身，而是对研究对象的一种模型不是研究对象本身，而是对研究对象的一种抽象，它反映现实中对象系统的主要特征，但它又高抽象，它反映现实中对象系统的主要特征，但它又高于现实，因而具有同类问

2、题的共性于现实，因而具有同类问题的共性 . . 由于研究目的的不同，对于同一个对象系统，由于研究目的的不同，对于同一个对象系统，可以建立完全不同的模型，分别反映该系统的不同可以建立完全不同的模型，分别反映该系统的不同侧面；出于相同的研究目的，对于同一个对象系侧面；出于相同的研究目的，对于同一个对象系统，也可能建立不同的模型，反映不同的研究角统，也可能建立不同的模型，反映不同的研究角度、考察因素和价值取向度、考察因素和价值取向 .4二、模型的本质二、模型的本质 从系统概念上看，模型是系统中各种关系的表达从系统概念上看，模型是系统中各种关系的表达形式形式 . 因此，建立模型要从状态和过程两个方面去

3、寻因此，建立模型要从状态和过程两个方面去寻找、把握和描述各系统要素之间的相互关系找、把握和描述各系统要素之间的相互关系 .状态状态：事物在某个：事物在某个时刻所处的状况或时刻所处的状况或表现形态表现形态 过程过程：事物状态的：事物状态的变化在时间上的持变化在时间上的持续和空间上的延伸续和空间上的延伸 过程和状态两者紧密联系、不可分割，状态决过程和状态两者紧密联系、不可分割，状态决定和影响过程，过程又决定和影响新的状态定和影响过程，过程又决定和影响新的状态 . 状态和过程是相对的状态和过程是相对的 .5 从认识论上看，模型是作为认识与实践活动的中介从认识论上看，模型是作为认识与实践活动的中介 .

4、现实世界现实世界认识（信息）认识（信息） 模模 型型实践活动实践活动概念化概念化用信息载体表达用信息载体表达决策（行动方案）决策（行动方案）产品和服务产品和服务模型化过程示意图模型化过程示意图模型既是认识的表达，又是实践活动的先导模型既是认识的表达，又是实践活动的先导 . . 模型参与认识世界和改造世界的不断的循环往复模型参与认识世界和改造世界的不断的循环往复过程，既是认识不断深化的体现，又是实践活动不断过程，既是认识不断深化的体现，又是实践活动不断拓展的体现拓展的体现 .第一章第一章 组合优化模型组合优化模型6 从信息论上看，模型和认识之间存在密切的反馈从信息论上看，模型和认识之间存在密切的

5、反馈关系关系 . 从已知信息可以通过模型加工产生出新的信从已知信息可以通过模型加工产生出新的信息，相关信息的积累可以从量变产生质变，形成新的息，相关信息的积累可以从量变产生质变，形成新的概念，促使认识深化概念，促使认识深化 . 因此，模型的建立和完善不仅要注重对系统物质因此，模型的建立和完善不仅要注重对系统物质形态和能量形态的认识、把握和描述，而且也依赖于形态和能量形态的认识、把握和描述，而且也依赖于对系统相关信息不断的采集、积累和加工，这就是用对系统相关信息不断的采集、积累和加工，这就是用模型研究问题的现实活动模型研究问题的现实活动 .7三、模型的分类三、模型的分类1、原样模型、原样模型 原

6、样模型原样模型是在工程开发末期建立的一种具象实是在工程开发末期建立的一种具象实体，是具有实物形态的模型体，是具有实物形态的模型 . .它与目的工程在结构和过程方面基本相同它与目的工程在结构和过程方面基本相同 . . 原样模型经过试验改进和完善后便是所要开发原样模型经过试验改进和完善后便是所要开发的目的工程的目的工程 .新产品的样机、新著作的原稿新产品的样机、新著作的原稿 第一章第一章 组合优化模型组合优化模型82、相似模型、相似模型 相似模型相似模型是根据不同系统间的相似规律（包括几是根据不同系统间的相似规律（包括几何相似、逻辑相似和过程相似等）而建立的用于研究何相似、逻辑相似和过程相似等）而

7、建立的用于研究的模型的模型 .3、图形模型、图形模型 地球仪、船体放地球仪、船体放样样模型、飞机风洞实验模型、飞机风洞实验模模拟模型等等拟模型等等图形模型图形模型可以表达非常丰富的内容，主要有：可以表达非常丰富的内容，主要有： 图画图画 一种可以示形的图形；一种可以示形的图形； 草图草图 一种可以示意的图形；一种可以示意的图形； 框图框图 一种可以表示系统的部分之间或部分一种可以表示系统的部分之间或部分 与整体之间联系的图形；与整体之间联系的图形； 称为不严格图称为不严格图（没有严格的规范）（没有严格的规范） 系统分析和设计人员常常借助于这些图形模型来系统分析和设计人员常常借助于这些图形模型来

8、开发、构建一个新系统的想象力和创造力，逐步引申开发、构建一个新系统的想象力和创造力，逐步引申出与之有关的问题和需要进一步探索的问题，使所要出与之有关的问题和需要进一步探索的问题，使所要开发的系统变得越来越清晰、越来越具体开发的系统变得越来越清晰、越来越具体 . .9 逻辑图逻辑图 一种可以反映因素或对象间逻辑关系一种可以反映因素或对象间逻辑关系 的图形；的图形； 如：程序流程图、如：程序流程图、控控制关系图制关系图 etc. 工程图工程图 一种可以反映物体确定的结构和顺序一种可以反映物体确定的结构和顺序 关系的图形；关系的图形； 如：建筑工程图、如：建筑工程图、铁路站场配置图铁路站场配置图 e

9、tc. 图论图图论图 包括图论所定义的无向图包括图论所定义的无向图 g(v，e) 、 有向图有向图 g(v，a)、加权有、加权有(无无)向图向图g(v，a(e)，w).关系关系 称为严格图称为严格图（有严格确定的结构（有严格确定的结构形式和规范）形式和规范）4、数学模型、数学模型 数学模型数学模型是指运用数学符号和公式来表达、研究是指运用数学符号和公式来表达、研究对象系统的结构或过程的模型对象系统的结构或过程的模型 . .数学模型数学模型是用数学的语言、方法去近似地刻画实际是用数学的语言、方法去近似地刻画实际 ,是由数字、字母或其他数学符号组成的，描述现实对是由数字、字母或其他数学符号组成的，

10、描述现实对象数量规律的数学公式、图形或算法象数量规律的数学公式、图形或算法 . 是对现实对象本质属性的抽象而又简洁的刻画，是对现实对象本质属性的抽象而又简洁的刻画，它或能解释某些客观现象，或能预测未来的发展规它或能解释某些客观现象，或能预测未来的发展规律，或能为控制某一现象的发展提供某种意义下的最律，或能为控制某一现象的发展提供某种意义下的最优策略或较好策略优策略或较好策略 .go back第一章第一章 组合优化模型组合优化模型10example 1七桥问题七桥问题 18世纪的德国有个哥尼斯堡城，在流贯全城的普世纪的德国有个哥尼斯堡城，在流贯全城的普雷尔河两岸和河中两个岛之间架设了七座桥，把河

11、的雷尔河两岸和河中两个岛之间架设了七座桥，把河的两岸和两岛连接起来，能否有这样一种走法，它通过两岸和两岛连接起来，能否有这样一种走法，它通过每座桥一次且仅一次每座桥一次且仅一次 .该问题由该问题由euler在在1736年解决年解决solution :11abcd 显然，解决该问题时，显然，解决该问题时，两岸和岛的大小、形状以及两岸和岛的大小、形状以及桥的长短曲直都无关，重要桥的长短曲直都无关，重要的是什么？的是什么？每块陆地间有每块陆地间有几座桥几座桥对问题进行数学抽象：对问题进行数学抽象： 把两岸和两岛都看做顶点，将连接这些顶点的桥把两岸和两岛都看做顶点，将连接这些顶点的桥当作边，于是得到一

12、无向图当作边，于是得到一无向图 . 则七桥问题就成为无向图中是否存在通过每一边则七桥问题就成为无向图中是否存在通过每一边一次且仅一次的路（即一笔画）问题一次且仅一次的路（即一笔画）问题 . .第一章第一章 组合优化模型组合优化模型12abcdeuler 在他的论文中证明在他的论文中证明： 一个图中存在一笔画的一个图中存在一笔画的充要条件是同时满足：充要条件是同时满足：1、图是连通的；、图是连通的；2、与图中每一顶点（可能有两点例外）相连的边与图中每一顶点（可能有两点例外）相连的边 （线度）必须是偶数条（线度）必须是偶数条 . .这是关于图论这是关于图论的第一篇论文的第一篇论文 见图可知，与四个

13、顶点相连的边都是奇数条，因见图可知，与四个顶点相连的边都是奇数条，因而不可能存在通过每条边一次且仅一次的画法，即一而不可能存在通过每条边一次且仅一次的画法，即一笔画不存在笔画不存在 . . 故七桥问题不可能有解故七桥问题不可能有解 .问题原型问题原型七桥问题七桥问题数学模型数学模型一笔画问题一笔画问题无无 解解( (一次过七座桥不可能一次过七座桥不可能) )无无 解解( (一笔画不可能一笔画不可能) )数学抽象数学抽象逻辑推理逻辑推理翻译回去翻译回去有无解？有无解？这是利用数学模型分析和解决问题的一个成功范例这是利用数学模型分析和解决问题的一个成功范例13一、数学模型的特点一、数学模型的特点1

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

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

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

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

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

19、优化模型18三、数学建模的基本步骤三、数学建模的基本步骤 数学模型因问题不同而异，对同一问题，从不同数学模型因问题不同而异，对同一问题，从不同角度、不同要求出发，甚至问题的解表示结构不同，角度、不同要求出发，甚至问题的解表示结构不同，都可以建立不同的数学模型都可以建立不同的数学模型. 建立数学模型也没有固建立数学模型也没有固定的方法、标准定的方法、标准 . 不同的实际问题，建模模式千差万不同的实际问题，建模模式千差万别别. 在此介绍通常的几个步骤：在此介绍通常的几个步骤： 数学建模问题直接来源各领域实际，往往含糊不数学建模问题直接来源各领域实际，往往含糊不清（目的、条件、类型清（目的、条件、类

20、型 etc.）. 首先，要对该问题进首先，要对该问题进行全面的、深入细微的调查和研究行全面的、深入细微的调查和研究. 明确所解决问题明确所解决问题的性质，着手收集数据的性质，着手收集数据 ；1、明确问题明确问题合理地、有目的地合理地、有目的地注意精度注意精度192、合理假设合理假设 现实问题错综复杂，涉及面非常之广现实问题错综复杂，涉及面非常之广. 一个数学一个数学模型面面俱到、无所不包地反映一个现实是不可能模型面面俱到、无所不包地反映一个现实是不可能的，即使可能，也因其过于复杂而很难求解，也是没的，即使可能，也因其过于复杂而很难求解，也是没有必要的有必要的 . 所以，要作所以，要作合理合理的

21、假设的假设 .1、简化问题、简化问题2、限定适用范围、限定适用范围但也不能忽略实质但也不能忽略实质相关的因素相关的因素 作假设的依据通常是出于对问题内在规律的认识作假设的依据通常是出于对问题内在规律的认识,或来自对数据或现象的分析，也可以是二者的综合或来自对数据或现象的分析，也可以是二者的综合. 善于辨别问题的主次，抓住主要因素，通过合理假设善于辨别问题的主次，抓住主要因素，通过合理假设,使问题简化以便进行数学描述使问题简化以便进行数学描述 . 假设是在模型的建立、求解和分析过程中完善假设是在模型的建立、求解和分析过程中完善 .通常开始让问题尽通常开始让问题尽可能简化可能简化第一章第一章 组合

22、优化模型组合优化模型203、建立模型建立模型 建模时，要分清问题的类型恰当使用数学工具；建模时，要分清问题的类型恰当使用数学工具；抓住问题的本质简化变量之间的关系抓住问题的本质简化变量之间的关系 . 用什么样的方法建立数学模型，没有绝对的标用什么样的方法建立数学模型，没有绝对的标准；数学模型的形式可以是多种多样，数学公式、表准；数学模型的形式可以是多种多样，数学公式、表格、图形、算法格、图形、算法 . 模型的优劣在于是否采用了恰当的方法，合理地模型的优劣在于是否采用了恰当的方法，合理地描述了实际问题，而不在于是否用到了高深的数学工描述了实际问题，而不在于是否用到了高深的数学工具具 .数学建模是

23、一个过程数学建模是一个过程 .214、模型求解模型求解 不同的模型要用到不同的数学工具求解不同的模型要用到不同的数学工具求解 . 这就要这就要求从事实际工作者对相应的数学分支知识有一定的了求从事实际工作者对相应的数学分支知识有一定的了解解 .可借助计算机，特别是利用数学工具软件可借助计算机，特别是利用数学工具软件 .5、模型分析模型分析 对模型求出的解进行数学上的分析，有助于对实对模型求出的解进行数学上的分析，有助于对实际问题的解决际问题的解决 .如如： 结果的误差分析结果的误差分析误差是否在允许的范围内误差是否在允许的范围内分析误差来源：分析误差来源： 建模假设的误差；建模假设的误差；数据测

24、量的误差；数据测量的误差；近似求解方法的误差；近似求解方法的误差； 计算工具的舍入误差计算工具的舍入误差 . 结果的统计分析结果的统计分析结果是否符合特定的统计规律结果是否符合特定的统计规律 模型对数据的灵敏度分析模型对数据的灵敏度分析模型的结果是否会因数据的微小改变而发生大的变化模型的结果是否会因数据的微小改变而发生大的变化 对假设的鲁棒性分析对假设的鲁棒性分析模型的结果是否对某一假设非常依赖模型的结果是否对某一假设非常依赖 不同模型间的对比分析不同模型间的对比分析robustness第一章第一章 组合优化模型组合优化模型226、模型检验模型检验 将求解结果和分析结果翻译回到实际问题之中，将

25、求解结果和分析结果翻译回到实际问题之中，与实际现象、实际数据进行比较，检验是否与实际吻与实际现象、实际数据进行比较，检验是否与实际吻合合 . 如果吻合较好，则模型及其结果可以应用于实际如果吻合较好，则模型及其结果可以应用于实际问题；如果吻合不好，则需要对模型进行修正问题；如果吻合不好，则需要对模型进行修正 .7、改进模型改进模型 吻合不好，问题常常出现在模型假设上吻合不好，问题常常出现在模型假设上 . 可能由可能由于假设了过于苛刻的条件，或者忽略了一些不该忽略于假设了过于苛刻的条件，或者忽略了一些不该忽略的因素的因素. 所以所以, 要对实际问题中的主次因素再次分析要对实际问题中的主次因素再次分

26、析,对模型进行修改、补充、完善对模型进行修改、补充、完善 . 需要多次反复才能达需要多次反复才能达到比较满意的程度到比较满意的程度 。238、模型应用模型应用 数学建模最终的目的是为了解决问题数学建模最终的目的是为了解决问题 . 一方面可一方面可以解释以前的实践成果；另一方面可以为现在的实际以解释以前的实践成果；另一方面可以为现在的实际问题提供解决方案，甚至可以对一些不确定的现象或问题提供解决方案，甚至可以对一些不确定的现象或规律作出预测规律作出预测 .现实问题现实问题简化、假设简化、假设建立模型建立模型求解模型求解模型检验分析模型检验分析模型模型应用模型应用观察、分析观察、分析收集数据收集数

27、据确定主要因素确定主要因素及相互关系及相互关系go back第一章第一章 组合优化模型组合优化模型24example 2 某商场根据客流量统计得出一周中每天所需要的某商场根据客流量统计得出一周中每天所需要的营业员数如表：营业员数如表：营业员配置问题营业员配置问题时间时间周一周一周二周二周三周三周四周四周五周五周六周六周日周日所需营业员数所需营业员数677278768510698 如果规定每个营业员每周连续工作如果规定每个营业员每周连续工作 5 天，休息天，休息 2 天，求总人数最少的营业员排班方案天，求总人数最少的营业员排班方案 .solution : 设设 xj 为从周为从周 j 开始连续工

28、作开始连续工作 5 天的营业员天的营业员人数，人数，j = 1,7 (其中其中 x7 为周日开始连续工作为周日开始连续工作 5 天的天的营业员数营业员数)，则，则71minjjzx14567. .67stxxxxx71minjjzx14567. .67stxxxxx1256772xxxxx1236778xxxxx1234776xxxxx1234585xxxxx23456106xxxxx3456798xxxxx0,1,.,106 ,1,.,7jxj可行解集可行解集是有限集是有限集25example 3 旅行商问题旅行商问题（traveling salesman problem）tsp : 有一位

29、旅行售货员，欲到城市有一位旅行售货员，欲到城市 v1，v2,，vn 进行商品销售，已知：进行商品销售，已知： 的距离为的距离为 wij.( ,.( , ). ).他从其中某个城市出发，需访问每一个他从其中某个城市出发，需访问每一个城市一次而回到出发的城市城市一次而回到出发的城市. .问应如何计划他的旅行问应如何计划他的旅行路线，使他所走路线的总长度最短？路线，使他所走路线的总长度最短？ijvvij,1i jntsp可分为：对称（可分为：对称（dij = dji)和非对称（和非对称（dij dji）距离两种）距离两种第一章第一章 组合优化模型组合优化模型26hamilton 回路：回路：不含平行

30、不含平行边及自环边及自环 这是这是1856年，年，hamilton 首先提出的所谓环球首先提出的所谓环球航行问题而得名。它的存在性远比航行问题而得名。它的存在性远比 eular 回路的存回路的存在性复杂得多。在性复杂得多。最优最优 hamilton 回路：回路：在赋权图中，权和最小的在赋权图中，权和最小的 hamilton 回路回路 .过简单图过简单图 g 的每一个顶点一次且仅一次的回路的每一个顶点一次且仅一次的回路 .27最优旅行商问题与最优最优旅行商问题与最优 hamilton 回路一样吗？回路一样吗？ 如果不满足三角不等式，则可通如果不满足三角不等式，则可通过求最短路方法，构造新图，使之满过求最短路方法，构造新图，使之满足三角不等式足三角不等式 . 所以以下仅讨论最优所以以下仅讨论最优的的 hamilton 回路回路 .1 2 51 2 3theorem 如果赋权图满足三角不等式如果赋权图满足三角不等式（欧氏距离），则它的最优旅行商回路（欧氏距离），则它的最优旅行商回路与最优与最优 hamilton 回路相同回路相同 （hamilton 回路存在时）回路存在时）.第一章第一章 组合优化模型组合优化模型28minijijijd xtsp 问题的数学模型（问题的数学模型（非对称的非对称的）1. .11(1)nijjstxin111(2)nijixjn,1221