组合优化模型

关于组合优化模型1第一页，共31页幻灯片2第一章模型§1关于模型§2数学模型§3组合优化模型第二页，共31页幻灯片3第一章组合优化模型

模型（model）是所研究的系统、过程、事物或概念的一种表达形式.

§1关于模型一、模型的概念

模型不是研究对象本身，而是对研究对象的一种抽象，它反映现实中对象系统的主要特征，但它又高于现实，因而具有同类问题的共性.

由于研究目的的不同，对于同一个对象系统，可以建立完全不同的模型，分别反映该系统的不同侧面；出于相同的研究目的，对于同一个对象系统，也可能建立不同的模型，反映不同的研究角度、考察因素和价值取向.第三页，共31页幻灯片4§1关于模型二、模型的本质

从系统概念上看，模型是系统中各种关系的表达形式.因此，建立模型要从状态和过程两个方面去寻找、把握和描述各系统要素之间的相互关系.状态：事物在某个时刻所处的状况或表现形态

过程：事物状态的变化在时间上的持续和空间上的延伸

过程和状态两者紧密联系、不可分割，状态决定和影响过程，过程又决定和影响新的状态.

状态和过程是相对的.第四页，共31页幻灯片5

从认识论上看，模型是作为认识与实践活动的中介.现实世界认识（信息）

模型实践活动概念化用信息载体表达决策（行动方案）产品和服务模型化过程示意图模型既是认识的表达，又是实践活动的先导.

模型参与认识世界和改造世界的不断的循环往复过程，既是认识不断深化的体现，又是实践活动不断拓展的体现.第一章组合优化模型第五页，共31页幻灯片6§1关于模型

从信息论上看，模型和认识之间存在密切的反馈关系.从已知信息可以通过模型加工产生出新的信息，相关信息的积累可以从量变产生质变，形成新的概念，促使认识深化.

因此，模型的建立和完善不仅要注重对系统物质形态和能量形态的认识、把握和描述，而且也依赖于对系统相关信息不断的采集、积累和加工，这就是用模型研究问题的现实活动.第六页，共31页幻灯片7三、模型的分类1、原样模型

原样模型是在工程开发末期建立的一种具象实体，是具有实物形态的模型.它与目的工程在结构和过程方面基本相同.

原样模型经过试验改进和完善后便是所要开发的目的工程.新产品的样机、新著作的原稿…第一章组合优化模型第七页，共31页幻灯片8§1关于模型2、相似模型

相似模型是根据不同系统间的相似规律（包括几何相似、逻辑相似和过程相似等）而建立的用于研究的模型.3、图形模型

地球仪、船体放样模型、飞机风洞实验模拟模型等等图形模型可以表达非常丰富的内容，主要有：①图画

——一种可以示形的图形；②草图

——一种可以示意的图形；③框图

——一种可以表示系统的部分之间或部分与整体之间联系的图形；

称为不严格图（没有严格的规范）

系统分析和设计人员常常借助于这些图形模型来开发、构建一个新系统的想象力和创造力，逐步引申出与之有关的问题和需要进一步探索的问题，使所要开发的系统变得越来越清晰、越来越具体.第八页，共31页幻灯片9④逻辑图

——一种可以反映因素或对象间逻辑关系的图形；

如：程序流程图、控制关系图etc.⑤工程图

——一种可以反映物体确定的结构和顺序关系的图形；

如：建筑工程图、铁路站场配置图etc.⑥图论图

——包括图论所定义的无向图G(V，E)、有向图G(V，A)、加权有(无)向图G(V，A(E)，w).关系

称为严格图（有严格确定的结构形式和规范）4、数学模型

数学模型是指运用数学符号和公式来表达、研究对象系统的结构或过程的模型.数学模型是用数学的语言、方法去近似地刻画实际,是由数字、字母或其他数学符号组成的，描述现实对象数量规律的数学公式、图形或算法.

是对现实对象本质属性的抽象而又简洁的刻画，它或能解释某些客观现象，或能预测未来的发展规律，或能为控制某一现象的发展提供某种意义下的最优策略或较好策略.Goback第一章组合优化模型第九页，共31页幻灯片10§2数学模型Example1七桥问题

18世纪的德国有个哥尼斯堡城，在流贯全城的普雷尔河两岸和河中两个岛之间架设了七座桥，把河的两岸和两岛连接起来，能否有这样一种走法，它通过每座桥一次且仅一次.该问题由Euler在1736年解决Solution:第十页，共31页幻灯片11ABCD

显然，解决该问题时，两岸和岛的大小、形状以及桥的长短曲直都无关，重要的是什么？每块陆地间有几座桥对问题进行数学抽象：

把两岸和两岛都看做顶点，将连接这些顶点的桥当作边，于是得到一无向图.

则七桥问题就成为无向图中是否存在通过每一边一次且仅一次的路（即一笔画）问题.第一章组合优化模型第十一页，共31页幻灯片12§2数学模型ABCDEuler

在他的论文中证明：

一个图中存在一笔画的充要条件是同时满足：1、图是连通的；2、与图中每一顶点（可能有两点例外）相连的边（线度）必须是偶数条.这是关于图论的第一篇论文

见图可知，与四个顶点相连的边都是奇数条，因而不可能存在通过每条边一次且仅一次的画法，即一笔画不存在.故七桥问题不可能有解

.问题原型七桥问题数学模型一笔画问题无解(一次过七座桥不可能)无解(一笔画不可能)数学抽象逻辑推理翻译回去有无解？这是利用数学模型分析和解决问题的一个成功范例第十二页，共31页幻灯片13一、数学模型的特点1、高度的抽象性

数学方法不仅要抛开事物的次要属性，突出事物的本质属性，而且要舍弃事物的物质和能量方面的具体内容，只考虑其数量关系和空间形式，同时还要把这些数量关系和空间形式作进一步的抽象，加以形式化和符号化，以便能够进行逻辑推理和数值运算.

这种高度的抽象性，实质是对事物认识上的高度概括和深化，对同类问题包含更多的经验和理解.第一章组合优化模型第十三页，共31页幻灯片14§2数学模型2、高度的精确性数学方法的高度精确性表现在三个方面：

一是表达各种因素、变量和它们之间的关系相当明确、清楚；二是逻辑推演和运算规则十分严密；三是结论非常确定.

数学方法可以处理多变量、关系复杂的问题，可在有意义的范围内获得令人满意的计算精度.

特别适合于揭示事物的量的规定性，成为定量研究的有力工具.第十四页，共31页幻灯片153、应用的普适性

数学方法的高度抽象和精确，使之比任何一种科学方法的应用范围都更为广泛.

只存在尚未运用数学方法的领域而不存在不能运用数学方法的领域.

许多相同形式的数学模型可用于不同的实际问题，具有重要类比和借鉴意义.数学方法的形式化和公理化，使模型本身、计算过程和计算结果都便于交流，数学模型易变动，便于修改和改变计算关系，分析和求解问题速度快，求解成本低.数学模型缺乏直观性、形象性和实时感第一章组合优化模型第十五页，共31页幻灯片16§2数学模型二、数学模型分类数学模型分类的方法很多，如：1、按所研究问题的性质分类⑴静态模型与动态模型⑵确定型模型与随机型模型⑶连续模型与离散模型⑷线性模型与非线性模型⑸宏观模型与微观模型第十六页，共31页幻灯片172、按模型的解的特征分类解析模型与数值模型3、按模型所用的数学方法分类初等模型、微分方程模型、差分方程模型、优化模型等4、按模型研究的实际范畴分类人口模型、生态系统模型、交通流模型、经济模型、基因模型等5、按对实际问题了解的程度分类

白箱模型、灰箱模型、黑箱模型第一章组合优化模型第十七页，共31页幻灯片18§2数学模型三、数学建模的基本步骤

数学模型因问题不同而异，对同一问题，从不同角度、不同要求出发，甚至问题的解表示结构不同，都可以建立不同的数学模型.建立数学模型也没有固定的方法、标准.不同的实际问题，建模模式千差万别.在此介绍通常的几个步骤：

数学建模问题直接来源各领域实际，往往含糊不清（目的、条件、类型etc.）.首先，要对该问题进行全面的、深入细微的调查和研究.明确所解决问题的性质，着手收集数据；1、明确问题合理地、有目的地注意精度第十八页，共31页幻灯片192、合理假设

现实问题错综复杂，涉及面非常之广.一个数学模型面面俱到、无所不包地反映一个现实是不可能的，即使可能，也因其过于复杂而很难求解，也是没有必要的.

所以，要作合理的假设.1、简化问题2、限定适用范围但也不能忽略实质相关的因素

作假设的依据通常是出于对问题内在规律的认识,或来自对数据或现象的分析，也可以是二者的综合.善于辨别问题的主次，抓住主要因素，通过合理假设,使问题简化以便进行数学描述.

假设是在模型的建立、求解和分析过程中完善.通常开始让问题尽可能简化第一章组合优化模型第十九页，共31页幻灯片20§2数学模型3、建立模型

建模时，要分清问题的类型恰当使用数学工具；抓住问题的本质简化变量之间的关系.

用什么样的方法建立数学模型，没有绝对的标准；数学模型的形式可以是多种多样，数学公式、表格、图形、算法.

模型的优劣在于是否采用了恰当的方法，合理地描述了实际问题，而不在于是否用到了高深的数学工具.数学建模是一个过程.第二十页，共31页幻灯片214、模型求解

不同的模型要用到不同的数学工具求解.这就要求从事实际工作者对相应的数学分支知识有一定的了解.可借助计算机，特别是利用数学工具软件.5、模型分析

对模型求出的解进行数学上的分析，有助于对实际问题的解决.如：①结果的误差分析误差是否在允许的范围内分析误差来源：建模假设的误差；数据测量的误差；近似求解方法的误差；计算工具的舍入误差.②

结果的统计分析结果是否符合特定的统计规律③模型对数据的灵敏度分析模型的结果是否会因数据的微小改变而发生大的变化④对假设的鲁棒性分析模型的结果是否对某一假设非常依赖⑤不同模型间的对比分析robustness第一章组合优化模型第二十一页，共31页幻灯片22§2数学模型6、模型检验

将求解结果和分析结果翻译回到实际问题之中，与实际现象、实际数据进行比较，检验是否与实际吻合.如果吻合较好，则模型及其结果可以应用于实际问题；如果吻合不好，则需要对模型进行修正.7、改进模型

吻合不好，问题常常出现在模型假设上.可能由于假设了过于苛刻的条件，或者忽略了一些不该忽略的因素.所以,要对实际问题中的主次因素再次分析,对模型进行修改、补充、完善.需要多次反复才能达到比较满意的程度。第二十二页，共31页幻灯片238、模型应用

数学建模最终的目的是为了解决问题.一方面可以解释以前的实践成果；另一方面可以为现在的实际问题提供解决方案，甚至可以对一些不确定的现象或规律作出预测.现实问题简化、假设建立模型求解模型检验分析模型模型应用观察、分析收集数据确定主要因素及相互关系Goback第一章组合优化模型第二十三页，共31页幻灯片24§3组合优化模型Example2

某商场根据客流量统计得出一周中每天所需要的营业员数如表：营业员配置问题时间周一周二周三周四周五周六周日所需营业员数677278768510698

如果规定每个营业员每周连续工作5天，休息2天，求总人数最少的营业员排班方案.Solution:

设xj

为从周j开始连续工作5天的营业员人数，j=1,…,7(其中

x7

为周日开始连续工作5天的营业员数)，则可行解集是有限集第二十四页，共31页幻灯片25Example3

旅行商问题（Traveling

Salesman

Problem）TSP

:

有一位旅行售货员，欲到城市v1，v2,…，vn

进行商品销售，已知：的距离为

wij.(,).他从其中某个城市出发，需访问每一个城市一次而回到出发的城市.问应如何计划他的旅行路线，使他所走路线的总长度最短？TSP可分为：对称（dij=dji)和非对称（dij≠dji）距离两种第一章组合优化模型第二十五页，共31页幻灯片26§3组合优化模型Hamilton

回路：不含平行边及自环

这是1856年，Hamilton

首先提出的所谓环球航行问题而得名。它的存在性远比Eular回路的存在性复杂得多。最优

Hamilton

回路：在赋权图中，权和最小的

Hamilton

回路.过简单图G

的每一个顶点一次且仅一次的回路.第二十六页，共31页幻灯片27最优旅行商问题与最优Hamilton回路一样吗？

如果不满足三角不等式，则可通过求最短路方法，构造新图，使之满足三角不等式.所以以下仅讨论最优的

Hamilton

回路.2523Theorem

如果赋权图满足三角不等式（欧氏距离），则它的最优旅行商回路与最优Hamilton

回路相同（Hamilton回路存在时）.第一章组合优化模型第二十七页，共31页幻灯片28§3组合优化模型TSP

问题的数学模型（非对称的）：v6v4v5v3v2v1Note：条件(1)，(2)表示每个城市经过一次，但不能保证它可行.

要求局部不构成圈，条件(3)就是为了约束这一点.第二十八页，共31页幻灯片29共同特点：可行方案是有限的

——组合优化问题

Definition1

组合优化问题