a4 (v3 , v4 )
a5 (v4 , v1 )
2
1
2
a6 (v3 , v3 )
3
2
3
7
网络优化问题的例子
例： 公路连接问题 某一地区有若干个主要城市，现准备修建高速公路 把这些城市连接起来， 使得从其中任何一个城市 都可以经高速公路直接或间接到达另一个城市. 假 定已经知道了任意两个城市之间修建高速公路的成 本，那么应如何决定在哪些城市间修建高速公路， 使得总成本最小？
S
T
特殊的最小费 用流问题
（二部图,
|S|=M, |T|=N）
14
网络优化问题的例子
例： 指派问题(Assignment Problem) 一家公司经理准备安排N名员工去完成N项任务，每人一项. 由于各员工的特点不同，不同的员工去完成同一项任务时 所获得的回报是不同的. 如何分配工作方案可以使总回报最 大？
22
匹配算法
二部基数匹配
增广路算法：O(mn) 简单网络上的最大流算法：O(mn1/2)
一般基数匹配
“花”算法: O(n3)
二部赋权匹配（指派问题）
最小费用流算法（如匈牙利算法）: O(n3)
一般赋权匹配
原始-对偶算法: O(n3)
23
网络优化的评注
• 许多实际问题可以直接用网络优化建模
•单向？ •双向？ •风向？
28
网络优化问题的例子
例：旅行商问题(TSP-Traveling Salesman Problem) 一名推销员准备前往若干城市推销产品. 如何为他(她)设计 一条最短的旅行路线(从驻地出发，经过每个城市恰好一次， 最后返回驻地)？这一问题的研究历史十分悠久，通常称之 为旅行商问题.
预流推进算法
最高标号预流推进算法： O(n2m1/2)
实际计算 效率高
21
最小费用流算法
消圈算法 最小费用路算法 原始-对偶算法
Ford和Forkerson(1957,1962)
瑕疵算法(Out-Of-Kilter Algorithm) 松弛(Relaxation)算法 实际计算效率高 网络单纯形算法
Bellman - Ford算法 (1956)： O(mn)
一般网络，所有点对
Floyd-Warshall算法(1962)： O(n3)
负圈检测
20
最大流算法
增广路算法
Ford-Fulkerson标号算法 (1956) 最大容量增广路算法 容量变尺度算法 最短增广路算法： O(n2m)
凸 规 划
狭义模型
广义模型
16
网络优化问题的例子
例：匹配问题(Matching Problem)
在一次有m个大学毕业生和n家公司参加的供需见面会上， 每个毕业生愿意加入到若干家公司中的一家工作，而每个 公司愿意接收若干毕业生中的一人到公司工作. 那么，最后 最多有多少人可以在这次供需见面会上找到工作（即最多 有多少家公司可以在这次供需见面会上招聘到员工）？如 果每个毕业生到每一家公司工作将会产生的效益不同，那 么，为了使得最后产生的总效益最大，最多有多少人可以 在这次供需见面会上找到工作？
网 络 优 化 模型与算法
Network Optimization: Models & Algorithms
2004年7月~8月 ---- 江西 庐山 清华大学数学科学系 谢金星
Email:jxie@ /~jxie
5
B
6 4
D
6 F (结束)
(开始) A
7
4
C
5 3 E
1
项目网络不含圈（其最长路问题和最短路问题都是可解的） 12
例：最大流 / 最小费用流
从甲地到乙地的公路网纵横交错，每天每条路上的通 车量有上限. 从甲地到乙地的每天最多能通车多少辆? B 6 4 D 6
5 (甲) A 7
4
C
F
5 3 E 1
《网络优化》或《网络流》（Network Flows) 或《网络规划》（Network Programming)
6
图与网络 – 基本概念
a5
a2
v1
a1
a3
v2
a4
v3 a6
v4
v5
图G=(V，A)，其中顶点集V= {v1 , v2 , v3 , v4 , v5 } 弧集A= {a1 , a2 , a3 , a4 , a5 , a6 } 弧 a1 (v1 , v 2 ) a ( v , v ) a (v , v )
D C
A B H I
F E
G
29
• 铁路/公路混合运输最短路问题
铁路/公路混合运输网络 最短路 ==〉铁路/公路混合运输最小运费矩阵
27
网络优化问题的其他例子
例：中国邮递员问题(CPP-Chinese Postman Problem) 一名邮递员负责投递某个街区的邮件 . 如何设计一条最短 的投递路线(从邮局出发，经过投递区内每条街道至少一次， 最后返回邮局)？由于这一问题是我国学者管梅谷教授1960 年首先提出的，所以国际上称之为中国邮递员问题.
• 许多实际问题可能用到网络优化建模
• 许多实际问题是网络优化的变种 • 网络优化问题通常可以用整数规划建模
24
西气东送（钢管运输）问题 （CUMCM-2000B)
290
30
S7 20
S3
S2 690 1200 720 202 1100 20 12 195 3060 1150 600 5 10 10 31 201 A8 680 S1 42
S4
690
170 520 88
160 70
320
160 70 30 S6 62 110 420 A13 210 A12 A14 20
A15
500
462 70 10
S5 220 A11
10
480
A9
A10
300
450
194
A6 606 A5
80
205
A7
铁路运价表
≤300 20 301～ 351～ 401～ 350 400 450 23 26 29 451～ 500 32 … …
1
Outline
• What is Network Optimization? • Typical Models & Algorithms
– – – – – – – Minimum Spanning Tree (最小(生成)树) Minimum Arborescence (最小树形图) Shortest Path (最短路) Maximum Flow (最大流) Minimum Cost Flow (最小费用流) Matching (匹配) ……
两种运输方式（铁路／公路）混合最短路问题 是普通最短路问题的变种，需要自己设计算法
26
铁路／公路混合运输最短路问题
最小运费矩阵算法（四川大学/清华大学等队） Dijkstra算法 或 Floyd-Warshall算法 • 铁路最短路问题
最短路 ==〉铁路最小运费矩阵
• 公路最短路问题
最短路 ==〉公路最小运费矩阵
25
2
3 104 A1 A2 301
750 A3
A4
里程 运价
西气东送（钢管运输）问题 （CUMCM-2000B)
• 二次规划（常用解法） • 最小费用流问题？ （清华大学队，获网易杯）
线性模型（网络规模较大，有现成算法） 非线性模型（网络规模较小，需要自己设计算法）
• 基本问题 ---- 最小运费矩阵的计算
( 乙)
考虑每条路上的通行成本,如何确定某个车队的具体行 车路线,使总成本最小?
13
网络优化问题的例子
例： 运输问题(Transportation Problem) 某种原材料有M个产地，现在需要将原材料从产地运往N个 使用这些原材料的工厂 . 假定M个产地的产量和N家工厂的 需要量已知，单位产品从任一产地到任一工厂的的运费已 知，那么如何安排运输方案可以使总运输成本最低？
信息传播途径（忽略方向时）是一棵树。 以上结构称为树形图，上面这样一类问题称为最小树形图问题.
10
网络优化问题的例子
例 最短路问题（SPP-Shortest Path Problem） 一名货柜车司机奉命在最短的时间内将一车货物从甲地运 往乙地. 从甲地到乙地的公路网纵横交错，因此有多种行车 路线，这名司机应选择哪条线路呢？假设货柜车的运行速 度是恒定的，那么这一问题相当于需要找到一条从甲地到 乙地的最短路.
R1
C13 C12
R3
R2
C24
最 小 树
R4
9
最小树形图 – 例
例： 信息传播
“直接方式”：总经理直接传达；
“接力方式”：总经理只给某些部门经理打电话，而让这 些得到信息的部门经理打电话将信息进一步传达给其他某些 部门经理，依此类推，最后将信息传达到所有部门经理. 如何决定传达信息的途径？
信息传播是有向的，有一个“根”。
1
3 4 8 1 7 6 3 2 5 5
2
4
最小(生成)树
也称为
最小(支撑)树
8
网络优化问题的例子
例： 二维矩阵数据存贮问题 某些蛋白质的氨基酸序列差异不多，如果用二维矩阵 的每一行记录一种蛋白质氨基酸序列，行与行之间的 差异很小 . 其中一种方法是只存贮其中一行作为参照 行，再存贮行与行之间的一部分差异信息，使得我们 可以在需要时根据参照行生成所有其它行的元素.
• Some Modeling Examples
2
网 络 优 化 简 介