⑥ 图论图 —— 包括图论所定义的无向图 G(V， 它或能解释某些客观现象，或能预测未来的发展规 铁路站场配置图 etcE . )、 有向图 G(V，A)、加权有(无)向图G(V，A(E)，w). 律，或能为控制某一现象的发展提供某种意义下的最 优策略或较好策略 . 4、数学模型 数学模型是指运用数学符号和公式来表达、研究 对象系统的结构或过程的模型 .
13
§2 数学模型 2、高度的精确性 数学方法的高度精确性表现在三个方面： 一是表达各种因素、变量和它们之间的关系相当 明确、清楚；二是逻辑推演和运算规则十分严密；三
是结论非常确定 .
数学方法可以处理多变量、关系复杂的问题，可 在有意义的范围内获得令人满意的计算精度 . 特别适合于揭示事物的量的规定性，成为定量研 究的有力工具 .
清（目的、条件、类型 etc.）. 的性质，着手收集数据 ；
首先，要对该问题进
行全面的、深入细微的调查和研究. 明确所解决问题
18
第一章
组合优化模型
但也不能忽略实质 1、简化问题
2、合理假设
2、限定适用范围 相关的因素
现实问题错综复杂，涉及面非常之广. 一个数学 模型面面俱到、无所不包地反映一个现实是不可能
流，数学模型易变动，便于修改和改变计算关系，分
析和求解问题速度快，求解成本低 .
15
§2 数学模型 二、数学模型分类 数学模型分类的方法很多，如： 1、按所研究问题的性质分类 ⑴ 静态模型与动态模型 ⑵ 确定型模型与随机型模型 ⑶ 连续模型与离散模型 ⑷ 线性模型与非线性模型 ⑸ 宏观模型与微观模型
概念化 用信息载体表达
认识（信息）
现实世界
产品和服务
模型 实践活动
决策（行动方案）
5
模型化过程示意图
§1 关于模型 从信息论上看，模型和认识之间存在密切的反馈
关系 . 从已知信息可以通过模型加工产生出新的信
息，相关信息的积累可以从量变产生质变，形成新的 概念，促使认识深化 . 因此，模型的建立和完善不仅要注重对系统物质
组合优化理论
Combinatorial Optimization Theory
第一章 组合优化模型
1
第一章
组合优化模型
§1 关于模型 §2 数学模型 §3 组合优化模型
2
第一章
组合优化模型
§1 关于模型
一、模型的概念 模型（ model ）是所研究的系统、过程、事物或 由于研究目的的不同，对于同一个对象系统， 概念的一种表达形式 . 可以建立完全不同的模型，分别反映该系统的不同 侧面；出于相同的研究目的，对于同一个对象系 模型不是研究对象本身，而是对研究对象的一种
x j 0,1,...,106, j 1,...,7
天，求总人数最少的营业员排班方案 .
是有限集
可行解集 Solution : 设 xj 为从周 j 开始连续工作 5 天的营业员
人数，j = 1,…,7 (其中 x7 为周日开始连续工作 5 天的 营业员数)，则
24
第一章
组合优化模型
Example 3
旅行商问题
（Traveling Salesman Problem）
TSP :
进行商品销售，已知：vi v j 的距离为 wij.( i j ,
有一位旅行售货员，欲到城市 v1，v2,…，vn
19
§2 数学模型
3、建立模型
建模时，要分清问题的类型恰当使用数学工具；
抓住问题的本质简化变量之间的关系 . 用什么样的方法建立数学模型，没有绝对的标
准；数学模型的形式可以是多种多样，数学公式、表 格、图形、算法 .
模型的优劣在于是否采用了恰当的方法，合理地
描述了实际问题，而不在于是否用到了高深的数学工 具. 数学建模是一个过程 .
A
C
显然，解决该问题时， 两岸和岛的大小、形状以及 桥的长短曲直都无关，重要 的是什么？ 对问题进行数学抽象：
B D
把两岸和两岛都看做顶点，将连接这些顶点的桥 当作边，于是得到一无向图 . 则七桥问题就成为无向图中是否存在通过每一边
每块陆地间有 几座桥
一次且仅一次的路（即一笔画）问题 .
11
§2 数学模型 Euler 在他的论文中证明 ： 问题原型 数学抽象 一个图中存在一笔画的 充要条件是同时满足： 有无解？ 1、图是连通的； 无 解
§2 数学模型
6、模型检验
将求解结果和分析结果翻译回到实际问题之中， 与实际现象、实际数据进行比较，检验是否与实际吻 合 . 如果吻合较好，则模型及其结果可以应用于实际 问题；如果吻合不好，则需要对模型进行修正 . 7、改进模型
吻合不好，问题常常出现在模型假设上 . 可能由 于假设了过于苛刻的条件，或者忽略了一些不该忽略 的因素. 所以, 要对实际问题中的主次因素再次分析, 对模型进行修改、补充、完善 . 需要多次反复才能达 到比较满意的程度 。 22
形态和能量形态的认识、把握和描述，而且也依赖于
对系统相关信息不断的采集、积累和加工，这就是用
模型研究问题的现实活动 .
6
第一章
组合优化模型
三、模型的分类
1、原样模型
原样模型是在工程开发末期建立的一种具象实 体，是具有实物形态的模型 . 它与目的工程在结构和过程方面基本相同 . 原样模型经过试验改进和完善后便是所要开发 的目的工程 . 新产品的样机、新著作的原稿 …
组合优化模型
关系 数学模型是用数学的语言、方法去近似地刻画实际 ④ 逻辑图 —— 一种可以反映因素或对象间逻辑关系 ,
是由数字、字母或其他数学符号组成的，描述现实对 的图形； 如：程序流程图、 称为严格图 ⑤ 工程图 —— 一种可以反映物体确定的结构和顺序 象数量规律的数学公式、图形或算法 .
控 （有严格确定的结构 关系的图形； 形式和规范） 是对现实对象本质属性的抽象而又简洁的刻画， 制关系图 etc. 如：建筑工程图、
这是关于图论
笔画不存在 .
故七桥问题不可能有解 .
12
第一章
组合优化模型
一、数学模型的特点 1、高度的抽象性 数学方法不仅要抛开事物的次要属性，突出事物
的本质属性，而且要舍弃事物的物质和能量方面的具
体内容，只考虑其数量关系和空间形式，同时还要把 这些数量关系和空间形式作进一步的抽象，加以形式 化和符号化，以便能够进行逻辑推理和数值运算 . 这种高度的抽象性，实质是对事物认识上的高度 概括和深化，对同类问题包含更多的经验和理解 .
23
§3 组合优化模型 min z xj
Example 2 营业员配置问题 s.t. x1 x4 x5 x6 x7 67 x1 x2 x5 x6 x7 72 某商场根据客流量统计得出一周中每天所需要的
j 1
7
营业员数如表：
时间 所需营业员数 周一 67 周二 72
7
§1 关于模型 2、相似模型 系统分析和设计人员常常借助于这些图形模型来 开发、构建一个新系统的想象力和创造力，逐步引申 相似模型是根据不同系统间的相似规律（包括几
出与之有关的问题和需要进一步探索的问题，使所要 何相似、逻辑相似和过程相似等）而建立的用于研究
开发的系统变得越来越清晰、越来越具体 . 的模型 .
时刻所处的状况或 表现形态 状态和过程是相对的 . 变化在时间上的持 续和空间上的延伸
4
第一章
组合优化模型
从认识论上看，模型是作为认识与实践活动的中介 . 模型既是认识的表达，又是实践活动的先导 . 模型参与认识世界和改造世界的不断的循环往复 过程，既是认识不断深化的体现，又是实践活动不断 拓展的体现 .
称为不严格图 地球仪、船体放 3、图形模型 样 （没有严格的规范） 模型、飞机风洞实验 图形模型可以表达非常丰富的内容，主要有： 模
拟模型等等 ① 图画 —— 一种可以示形的图形； ② 草图 —— 一种可以示意的图形； ③ 框图 —— 一种可以表示系统的部分之间或部分
与整体之间联系的图形；
8
第一章
16
第一章
组合优化模型
2、按模型的解的特征分类 解析模型与数值模型 3、按模型所用的数学方法分类 初等模型、微分方程模型、差分方程模型、优
化模型等
4、按模型研究的实际范畴分类
人口模型、生态系统模型 、交通流模型、经济
模型、 基因模型等 5、按对实际问题了解的程度分类 白箱模型、灰箱模型、黑箱模型
17
翻译回去
七桥问题 A
C
数学模型 一笔画问题 D
逻辑推理
B 无 解
(与图中每一顶点（可能有两点例外）相连的边 一次过七座桥不可能) (一笔画不可能) 2、
（线度）必须是偶数条 . 见图可知，与四个顶点相连的边都是奇数条，因 这是利用数学模型分析和解决问题的一个成功范例 的第一篇论文 而不可能存在通过每条边一次且仅一次的画法，即一
Go back 9
§2 数学模型
Example 1 七桥问题
该问题由Euler在 1736年解决
18世纪的德国有个哥尼斯堡城，在流贯全城的普
雷尔河两岸和河中两个岛之间架设了七座桥，把河的
两岸和两岛连接起来，能否有这样一种走法，它通过 每座桥一次且仅一次 . Solution :
10
第一章
组合优化模型
§2 数学模型
三、数学建模的基本步骤
合理地、有目的地
注意精度 数学模型因问题不同而异，对同一问题，从不同 角度、不同要求出发，甚至问题的解表示结构不同， 都可以建立不同的数学模型. 建立数学模型也没有固 定的方法、标准 . 不同的实际问题，建模模式千差万 别. 在此介绍通常的几个步骤：
1、明确问题 数学建模问题直接来源各领域实际，往往含糊不
第一章