– Minimum Spanning Tree (最小(生成)树)
– Minimum Arborescence (最小树形图)
– Shortest Path
(最短路)
– Maximum Flow
(最大流)
– Minimum Cost Flow – Matching
(最小费用流) (匹配)
– ……
• Some Modeling Examples
5
B6D
(开始) A
4 4
7
5
C 3E
6
F (结束) 1
项目网络不含圈（其最长路网络问优题化模和型与最算法短路问题都是可解的）12
例：最大流 / 最小费用流
从甲地到乙地的公路网纵横交错，每天每条路上的通 车量有上限. 从甲地到乙地的每天最多能通车多少辆?
5
B6D
(甲) A
4 4
7
5
C 3E
6
F (乙) 1
特殊的最小费
S
T
用流问题
（二部图,
|S|=M, |T|=N）
网络优化模型与算法
14
网络优化问题的例子
网络优化模型
网络优化算法及其复杂性
主要参考书：
• 谢金星 、邢文训，《网络优化》 ，清华大学出版社，2000 年8月；2003年9月。
• Ahuja, R. K., Magnanti T. L., Orlin J. B. Network Flows: Theory, Algorithms, and Applications. Prentice Hall, 1993: Englewood Cliffs, New Jersey.
弧 a1(v1,v2) a2 (v1,v2) a3 (v2,v3)
a4 (v3,v4) a (v ,v) 5 网络优4化模型1与算法 a6 (v3,v3)
7
网络优化问题的例子
例： 公路连接问题
某一地区有若干个主要城市，现准备修建高速公路 把这些城市连接起来， 使得从其中任何一个城市 都可以经高速公路直接或间接到达另一个城市. 假 定已经知道了任意两个城市之间修建高速公路的成 本，那么应如何决定在哪些城市间修建高速公路， 使得总成本最小？
网络优化模型与算法
2
网络优化简介
• 网络：网络社会 ---- 计算机信息网络？
电话通信网络
运输服务网络
能源和物质分派网络 人际关系网络 等等
网络优化就是研究如何有效地计划、管理和控制
网络系统，使之发挥最网络大优化的模型社与算会法 和经济效益
3
网 络 优 化简介
• 优化(Optimization) : 从若干可能的方案中寻求某 种意义下的最优方案
• 网络(Network)：数学模型、数学结构 ---- 图
• 网络优化就是研究与（赋权）图有关的最优化问题
• 与图论有联系，也有区别（侧重点不同）
图论： 图的性质
网络优化： 与（赋权）图有关的优化问题
组合数学
网络优组化模合型与优算化法
4
Optimization Tree
网络优化模型与算法
5
网 络 优 化简介
C13
R3
R1
最
小
C12
C24
树
R2
R4
网络优化模型与算法
9
最小树形图 – 例
例： 信息传播
➢“直接方式”：总经理直接传达； ➢“接力方式”：总经理只给某些部门经理打电话，而让这 些得到信息的部门经理打电话将信息进一步传达给其他某些 部门经理，依此类推，最后将信息传达到所有部门经理. 如何决定传达信息的途径？
✓ 信息传播是有向的，有一个“根”。 ✓ 信息传播途径（忽略方向时）是一棵树。
以上结构称为树形图，上面这样一类问题称为最小树形图问题.
网络优化模型与算法
10
网络优化问题的例子
例 最短路问题（SPP-Shortest Path Problem） 一名货柜车司机奉命在最短的时间内将一车货物从甲地运 往乙地. 从甲地到乙地的公路网纵横交错，因此有多种行车 路线，这名司机应选择哪条线路呢？假设货柜车的运行速 度是恒定的，那么这一问题相当于需要找到一条从甲地到 乙地的最短路.
1 1
2
最小(生成)树
7
6
3
3 8
5
4
也称为
4
5
最小(支撑)树
2
网络优化模型与算法
8
网络优化问题的例子
例： 二维矩阵数据存贮问题
某些蛋白质的氨基酸序列差异不多，如果用二维矩阵 的每一行记录一种蛋白质氨基酸序列，行与行之间的 差异很小. 其中一种方法是只存贮其中一行作为参照行， 再存贮行与行之间的一部分差异信息，使得我们可以 在需要时根据参照行生成所有其它行的元素.
考虑每条路上的通行成本,如何确定某个车队的具体行
Hale Waihona Puke 车路线,使总成本最小?网络优化模型与算法
13
网络优化问题的例子
例： 运输问题(Transportation Problem)
某种原材料有M个产地，现在需要将原材料从产地运往N个 使用这些原材料的工厂. 假定M个产地的产量和N家工厂的 需要量已知，单位产品从任一产地到任一工厂的的运费已 知，那么如何安排运输方案可以使总运输成本最低？
5
B6D
A
4 4
7
5
C 3E
6
F 1
网络优化模型与算法
11
例：计划评审技术, 即PERT(Project Evaluation & Review Technique), 又称网络计划技术或统筹法)
大型复杂工程项目(Project)往往被分成许多子项目,子项目之 间有一定的先后顺序(偏序)要求, 每一子项目需要一定的时间 完成. PERT网络的每条弧表示一个子项目,如果以弧长表示每 一子项目需要的时间,则最早完工时间对应于网络中的最长路 (关键路线). 工程上所谓的关键路线法(CPM: Critical Path Method)基本上也是计划评审技术的一部分.
网络优化 模型与算法
Network Optimization: Models & Algorithms
2004年7月~8月 ---- 江西 庐山
Email:
网络优化模型与算法
1
Outline
• What is Network Optimization?
• Typical Models & Algorithms
《网络优化》或《网络流》（Network Flows)
或《网络规划》（Ne网tw络优o化r模k型P与算ro法gramming)
6
图与网络 – 基本概
念
a5
a2
a3
a4
v1
v2
v3
v4
v5
a1
a6
图G=(V，A)，其中顶点集V= {v1,v2,v3,v4,v5}
弧集A= {a1,a2,a3,a4,a5,a6}