组合优化模型

1、关于组合优化模型1第一张，PPT共三十一页，创作于2022年6月2第一章 模 型1 关于模型2 数学模型3 组合优化模型第二张，PPT共三十一页，创作于2022年6月3第一章 组合优化模型 模型（model ）是所研究的系统、过程、事物或概念的一种表达形式 . 1 关于模型一、模型的概念 模型不是研究对象本身，而是对研究对象的一种抽象，它反映现实中对象系统的主要特征，但它又高于现实，因而具有同类问题的共性 . 由于研究目的的不同，对于同一个对象系统，可以建立完全不同的模型，分别反映该系统的不同侧面；出于相同的研究目的，对于同一个对象系统，也可能建立不同的模型，反映不同的研究角度、考察因素和价值

2、取向 .第三张，PPT共三十一页，创作于2022年6月41 关于模型二、模型的本质 从系统概念上看，模型是系统中各种关系的表达形式 . 因此，建立模型要从状态和过程两个方面去寻找、把握和描述各系统要素之间的相互关系 .状态：事物在某个时刻所处的状况或表现形态 过程：事物状态的变化在时间上的持续和空间上的延伸 过程和状态两者紧密联系、不可分割，状态决定和影响过程，过程又决定和影响新的状态 . 状态和过程是相对的 .第四张，PPT共三十一页，创作于2022年6月5 从认识论上看，模型是作为认识与实践活动的中介 .现实世界认识（信息） 模 型实践活动概念化用信息载体表达决策（行动方案）产品和服务模型

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

4、年6月7三、模型的分类1、原样模型 原样模型是在工程开发末期建立的一种具象实体，是具有实物形态的模型 .它与目的工程在结构和过程方面基本相同 . 原样模型经过试验改进和完善后便是所要开发的目的工程 .新产品的样机、新著作的原稿 第一章 组合优化模型第七张，PPT共三十一页，创作于2022年6月81 关于模型2、相似模型 相似模型是根据不同系统间的相似规律（包括几何相似、逻辑相似和过程相似等）而建立的用于研究的模型 .3、图形模型 地球仪、船体放样模型、飞机风洞实验模拟模型等等图形模型可以表达非常丰富的内容，主要有： 图画 一种可以示形的图形； 草图 一种可以示意的图形； 框图 一种可以表示系统

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

6、系 称为严格图（有严格确定的结构形式和规范）4、数学模型 数学模型是指运用数学符号和公式来表达、研究对象系统的结构或过程的模型 .数学模型是用数学的语言、方法去近似地刻画实际 ,是由数字、字母或其他数学符号组成的，描述现实对象数量规律的数学公式、图形或算法 . 是对现实对象本质属性的抽象而又简洁的刻画，它或能解释某些客观现象，或能预测未来的发展规律，或能为控制某一现象的发展提供某种意义下的最优策略或较好策略 .Go back第一章 组合优化模型第九张，PPT共三十一页，创作于2022年6月102 数学模型Example 1七桥问题 18世纪的德国有个哥尼斯堡城，在流贯全城的普雷尔河两岸和河中两

7、个岛之间架设了七座桥，把河的两岸和两岛连接起来，能否有这样一种走法，它通过每座桥一次且仅一次 .该问题由Euler在1736年解决Solution :第十张，PPT共三十一页，创作于2022年6月11ABCD 显然，解决该问题时，两岸和岛的大小、形状以及桥的长短曲直都无关，重要的是什么？每块陆地间有几座桥对问题进行数学抽象： 把两岸和两岛都看做顶点，将连接这些顶点的桥当作边，于是得到一无向图 . 则七桥问题就成为无向图中是否存在通过每一边一次且仅一次的路（即一笔画）问题 .第一章 组合优化模型第十一张，PPT共三十一页，创作于2022年6月122 数学模型ABCDEuler 在他的论文中证明：

8、 一个图中存在一笔画的充要条件是同时满足：1、图是连通的；2、与图中每一顶点（可能有两点例外）相连的边 （线度）必须是偶数条 .这是关于图论的第一篇论文 见图可知，与四个顶点相连的边都是奇数条，因而不可能存在通过每条边一次且仅一次的画法，即一笔画不存在 . 故七桥问题不可能有解 .问题原型七桥问题数学模型一笔画问题无 解(一次过七座桥不可能)无 解(一笔画不可能)数学抽象逻辑推理翻译回去有无解？这是利用数学模型分析和解决问题的一个成功范例第十二张，PPT共三十一页，创作于2022年6月13一、数学模型的特点1、高度的抽象性 数学方法不仅要抛开事物的次要属性，突出事物的本质属性，而且要舍弃事物的

9、物质和能量方面的具体内容，只考虑其数量关系和空间形式，同时还要把这些数量关系和空间形式作进一步的抽象，加以形式化和符号化，以便能够进行逻辑推理和数值运算 . 这种高度的抽象性，实质是对事物认识上的高度概括和深化，对同类问题包含更多的经验和理解 .第一章 组合优化模型第十三张，PPT共三十一页，创作于2022年6月142 数学模型2、高度的精确性数学方法的高度精确性表现在三个方面： 一是表达各种因素、变量和它们之间的关系相当明确、清楚；二是逻辑推演和运算规则十分严密；三是结论非常确定 . 数学方法可以处理多变量、关系复杂的问题，可在有意义的范围内获得令人满意的计算精度 . 特别适合于揭示事物的量

10、的规定性，成为定量研究的有力工具 .第十四张，PPT共三十一页，创作于2022年6月153、应用的普适性 数学方法的高度抽象和精确，使之比任何一种科学方法的应用范围都更为广泛 . 只存在尚未运用数学方法的领域而不存在不能运用数学方法的领域 . 许多相同形式的数学模型可用于不同的实际问题，具有重要类比和借鉴意义 .数学方法的形式化和公理化，使模型本身、计算过程和计算结果都便于交流，数学模型易变动，便于修改和改变计算关系，分析和求解问题速度快，求解成本低 .数学模型缺乏直观性、形象性和实时感第一章 组合优化模型第十五张，PPT共三十一页，创作于2022年6月162 数学模型二、数学模型分类数学模型

11、分类的方法很多，如：1、按所研究问题的性质分类 静态模型与动态模型 确定型模型与随机型模型 连续模型与离散模型 线性模型与非线性模型 宏观模型与微观模型第十六张，PPT共三十一页，创作于2022年6月172、按模型的解的特征分类解析模型与数值模型3、按模型所用的数学方法分类初等模型、微分方程模型、差分方程模型、优化模型等4、按模型研究的实际范畴分类人口模型、生态系统模型 、交通流模型、经济模型、 基因模型等5、按对实际问题了解的程度分类 白箱模型、灰箱模型、黑箱模型第一章 组合优化模型第十七张，PPT共三十一页，创作于2022年6月182 数学模型三、数学建模的基本步骤 数学模型因问题不同而异

12、，对同一问题，从不同角度、不同要求出发，甚至问题的解表示结构不同，都可以建立不同的数学模型. 建立数学模型也没有固定的方法、标准 . 不同的实际问题，建模模式千差万别. 在此介绍通常的几个步骤： 数学建模问题直接来源各领域实际，往往含糊不清（目的、条件、类型 etc.）. 首先，要对该问题进行全面的、深入细微的调查和研究. 明确所解决问题的性质，着手收集数据 ；1、明确问题合理地、有目的地注意精度第十八张，PPT共三十一页，创作于2022年6月192、合理假设 现实问题错综复杂，涉及面非常之广. 一个数学模型面面俱到、无所不包地反映一个现实是不可能的，即使可能，也因其过于复杂而很难求解，也是没

13、有必要的 . 所以，要作合理的假设 .1、简化问题2、限定适用范围但也不能忽略实质相关的因素 作假设的依据通常是出于对问题内在规律的认识,或来自对数据或现象的分析，也可以是二者的综合. 善于辨别问题的主次，抓住主要因素，通过合理假设,使问题简化以便进行数学描述 . 假设是在模型的建立、求解和分析过程中完善 .通常开始让问题尽可能简化第一章 组合优化模型第十九张，PPT共三十一页，创作于2022年6月202 数学模型3、建立模型 建模时，要分清问题的类型恰当使用数学工具；抓住问题的本质简化变量之间的关系 . 用什么样的方法建立数学模型，没有绝对的标准；数学模型的形式可以是多种多样，数学公式、表格

14、、图形、算法 . 模型的优劣在于是否采用了恰当的方法，合理地描述了实际问题，而不在于是否用到了高深的数学工具 .数学建模是一个过程 .第二十张，PPT共三十一页，创作于2022年6月214、模型求解 不同的模型要用到不同的数学工具求解 . 这就要求从事实际工作者对相应的数学分支知识有一定的了解 .可借助计算机，特别是利用数学工具软件 .5、模型分析 对模型求出的解进行数学上的分析，有助于对实际问题的解决 .如： 结果的误差分析误差是否在允许的范围内分析误差来源：建模假设的误差；数据测量的误差；近似求解方法的误差；计算工具的舍入误差 . 结果的统计分析结果是否符合特定的统计规律 模型对数据的灵敏

15、度分析模型的结果是否会因数据的微小改变而发生大的变化 对假设的鲁棒性分析模型的结果是否对某一假设非常依赖 不同模型间的对比分析robustness第一章 组合优化模型第二十一张，PPT共三十一页，创作于2022年6月222 数学模型6、模型检验 将求解结果和分析结果翻译回到实际问题之中，与实际现象、实际数据进行比较，检验是否与实际吻合 . 如果吻合较好，则模型及其结果可以应用于实际问题；如果吻合不好，则需要对模型进行修正 .7、改进模型 吻合不好，问题常常出现在模型假设上 . 可能由于假设了过于苛刻的条件，或者忽略了一些不该忽略的因素. 所以, 要对实际问题中的主次因素再次分析,对模型进行修改

16、、补充、完善 . 需要多次反复才能达到比较满意的程度 。第二十二张，PPT共三十一页，创作于2022年6月238、模型应用 数学建模最终的目的是为了解决问题 . 一方面可以解释以前的实践成果；另一方面可以为现在的实际问题提供解决方案，甚至可以对一些不确定的现象或规律作出预测 .现实问题简化、假设建立模型求解模型检验分析模型模型应用观察、分析收集数据确定主要因素及相互关系Go back第一章 组合优化模型第二十三张，PPT共三十一页，创作于2022年6月243 组合优化模型Example 2 某商场根据客流量统计得出一周中每天所需要的营业员数如表：营业员配置问题时间周一周二周三周四周五周六周日所

17、需营业员数677278768510698 如果规定每个营业员每周连续工作 5 天，休息 2 天，求总人数最少的营业员排班方案 .Solution : 设 xj 为从周 j 开始连续工作 5 天的营业员人数，j = 1,7 (其中 x7 为周日开始连续工作 5 天的营业员数)，则可行解集是有限集第二十四张，PPT共三十一页，创作于2022年6月25Example 3 旅行商问题（Traveling Salesman Problem）TSP : 有一位旅行售货员，欲到城市 v1，v2,，vn 进行商品销售，已知： 的距离为 wij.( , ).他从其中某个城市出发，需访问每一个城市一次而回到出发的

18、城市.问应如何计划他的旅行路线，使他所走路线的总长度最短？TSP可分为：对称（dij = dji)和非对称（dij dji）距离两种第一章 组合优化模型第二十五张，PPT共三十一页，创作于2022年6月263 组合优化模型Hamilton 回路：不含平行边及自环 这是1856年，Hamilton 首先提出的所谓环球航行问题而得名。它的存在性远比 Eular 回路的存在性复杂得多。最优 Hamilton 回路：在赋权图中，权和最小的 Hamilton 回路 .过简单图 G 的每一个顶点一次且仅一次的回路 .第二十六张，PPT共三十一页，创作于2022年6月27最优旅行商问题与最优 Hamilton 回路一样吗？ 如果不满足三角不等式，则可通过求最短路方法，构造新图，使之满足三角不等式 . 所以以下仅讨论最优的 Hamilton 回路 . 2 5 2 3Theorem 如果赋权图满足三角不等式（欧氏距离），则它的最优旅行商回路与最优 Hamilton 回路相同 （Hamilton 回路存在时）.第一章 组合优化模型第二十七张，PPT共三十一页，创作于2022年6月283 组合优化模型TSP 问题的数学模型（非对称的）：v6v4v5v3v2v1Note：条件(1)，(2)表示每个城市经过一次，但不能保证它可行. 要求局部不构成圈，条件(3)就是为了约束这一点