Chapter 7
Network Optimization Problems
网络最优化问题
RUC Information School,Ye Xiang,2007
Data,Model and Decisions
数据、模型与决策第七章
Network Optimization Problems
网络最优化问题
Chapter 7
Network Optimization Problems
网络最优化问题
RUC Information School,Ye Xiang,2007
本章内容 Topics P241
Applications of Network Optimization
网络最优化模型的应用
Types of Network Optimization Problem
网络最优化问题类型
7.1 Minimum-Cost Flow Problem 最小费用流问题
7.2/7.3 Maximum Flow Problem 最大流问题
7.4 Shortest Path Problem 最短路问题补充：最短路问题的另一个实际应用－货郎担问题补充：最短路问题的另一个实际应用－中国邮路问题
7.5 Minimum Spanning Tree Problem 最小支撑树问题案例 7.2资金的运作 （ 最小费用流问题 ）
与第 6章相比：
1,有 转运点,一般不是全连通图，所以要画网络图
2,在 Excel中用弧 表示稀疏矩阵
3,约束条件中用净流量
Chapter 7
Network Optimization Problems
网络最优化问题
RUC Information School,Ye Xiang,2007
Applications of Network Optimization
网络最优化模型的应用 P241
网络在各种实际背景问题中以各种各样的形式存在。交通、电子和通讯网络遍及我们日常生活的各个方面，网络规划也广泛用于解决不同领域中的各种问题，如生产
、分配、项目计划、厂址选择、资源管理和财务策划等等。
网络规划为描述系统各组成部分之间的关系提供了非常有效的直观和概念上的帮助，广泛应用于科学、社会和经济活动的每个领域中。
近些年来，管理科学中一个振奋人心的发展是它的网络最优化问题的方法论和应用方面都取得了不同寻常的飞速发展。
Chapter 7
Network Optimization Problems
网络最优化问题
RUC Information School,Ye Xiang,2007
Types of Network Optimization Problem
网络最优化问题类型 P242
Minimum-Cost Flow Problem
最小费用流问题
Maximum Flow Problem
最大流问题
Shortest Path Problem
最短路问题
Minimum Spanning Tree Problem
最小支撑树问题 － 唯一不是线性规划问题
Chapter 7
Network Optimization Problems
网络最优化问题
RUC Information School,Ye Xiang,2007
F1
DC
F2 W2
W1
8 0 u n i t s
p r o d u ce d
7 0 u n i t s
p r o d u ce d
6 0 u n i t s
needed
9 0 u n i t s
needed
7,1 Minimum-Cost Flow Problem
最小费用流问题 P242
例子：无限配送公司的问题（网络配送问题是网络最小费用流问题的另外一个名称）
无限配送公司有 两个工厂生产产品，这些产品需要运送到两个仓库里。
配送网络图 （网络模型）
目标是通过配送网络的运输成本最小。
Chapter 7
Network Optimization Problems
网络最优化问题
RUC Information School,Ye Xiang,2007
7,1 Minimum-Cost Flow Problem
最小费用流问题－术语 P244
最小费用流问题的构成（网络表示）：
1.节点 (nodes)（ 供应点 -净流量为正,需求点 -净流量为负
,转运点 -净流量为零 ）
2.弧（ arcs）：可行的运输线路（节点 i->节点 j），
经常有最大流量（容量）的限制
3.决策变量,xij－通过弧（节点 i->节点 j）的流量
Chapter 7
Network Optimization Problems
网络最优化问题
RUC Information School,Ye Xiang,2007
Assumptions of Minimum Cost Flow Problem
最小费用流问题的假设 P244
1,至少一个 供应点
2,至少一个 需求点
3,剩下都是 转运点
4,通过 弧 的流只允许沿着箭头方向流动，通过弧的最大流量取决于该弧的容量
5,网络中有足够的弧提供足够 容量,使得所有在供应点中产生的流都能够到达需求点
6,在流的单位成本已知前提下，通过每一条弧的流的成本和流量成正比（ 目标函数是线性的 ）
7,最小费用流问题的目标在满足给定需求条件下，使得通过网络配送的总成本最小（或总利润最大化）
Chapter 7
Network Optimization Problems
网络最优化问题
RUC Information School,Ye Xiang,2007
Characteristic of Solution
解的特征 P244
具有 可行解 的特征：在以上的假设下，当且仅当供应点所提供的流量总和等于需求点所需要的流量总和时，最小费用流问题有可行解（ 平衡条件 ） 。
具有 整数解 的特征：只要其所有的 供应量、需求量和弧的容量都是整数值,那么任何最小费用流问题的可行解就一定有所有流量都是整数的最优解 。
Chapter 7
Network Optimization Problems
网络最优化问题
RUC Information School,Ye Xiang,2007
无限配送公司的最小费用流问题的 线性规划数学模型（补充）
决策变量 xij：通过弧 (节点 i到节点 j)的流量总运输成本 最小化 Min Cost = $700xF1-W1 + $300xF1-DC +
$200xDC-W1 + $400xDC-W2 + $400xF2-DC + $900xF2-W2
约束条件 (节点净流量,弧的容量限制，非负）
（由于 80＋ 70＝ 60＋ 90，即总供应＝总需求，平衡）
供应点 F1,xF1-W1 + xF1-DC = 80
供应点 F2,xF2-DC + xF2-W2 = 70
转运点 DC,xDC-W1 + xDC-W2 - (xF1-DC + xF2-DC ) = 0
需求点 W1,xF1-W1 + xDC-W1 = 60
需求点 W2,xDC-W2 + xF2-W2 = 90
弧的容量限制,xF1-DC,xDC-W1,xDC-W2,xF2-DC?50
且 xij? 0
Chapter 7
Network Optimization Problems
网络最优化问题
RUC Information School,Ye Xiang,2007
无限配送公司的最小费用流问题的电子表格模型 P245
列出了网络中的 弧 和各弧所对应的 容量,单位流量成本
决策变量（可变单元格）为通过弧的流量 xij
目标单元格：计算流量的总成本
每个节点的 净流量（总流出－总流入） 为约束条件。供应点的净流量为正，需求点的净流量为负，而转运点的净流量为 0
窍门：用两个 SUMIF函数的差来计算每个节点的净流量（快捷且不容易犯错）
Chapter 7
Network Optimization Problems
网络最优化问题
RUC Information School,Ye Xiang,2007
更加有效地解决大规模的最小费用流问题 P246
网络单纯法 （ Network Simplex Method）：
可以用于解决大型的运输问题
现在，许多公司都使用网络单纯法来解决他们的最小费用流问题。有些问题是非常庞大的，有着数万个节点和弧。有时，弧的数量甚至可能会多得多，达到几百万条。
但 Excel ―规划求解”软件中没有网络单纯法
，但其他的线性规划的商业软件包通常都有这种方法。
Chapter 7
Network Optimization Problems
网络最优化问题
RUC Information School,Ye Xiang,2007
Some Applications
一些实际应用 P247
应用类型 供应点 转运点 需求点配送网络的运作 货源 中间存储设施 客户固体废弃物管理 固体废弃物源 处理设施 固体废弃物掩埋地供应网络的运作 供应商 中间仓库 加工设备工厂协调产品组合 工厂 某一特定产品的生产某一特定产品的市场现金流管理 某一特定时间的现金来源短期投资期权 在特定时间对现金的需求表 7.1 几类典型的最小费用流问题的应用
Chapter 7
Network Optimization Problems
网络最优化问题
RUC Information School,Ye Xiang,2007
Some Applications
一些实际应用 P247
国际纸业公司（ International Paper Company）
配送网络（ Interfaces 1988年 3~4）
世界上最大的纸浆、纸和纸类产品的制造商以及木材和夹板的主要生产者。拥有 2000万英亩的林区或其权益。分布在不同地方的林区是它配送网络的供应点。
但是，在公司的产品最终到达需求点（客户）以前，
供应流必须经过一系列很长的转运点。它通过配送网络的一条典型的路径就是：
林区 → 木材堆积场 → 锯木厂 → 造纸厂
→ 纸制品加工厂 → 仓库 → 客户
Chapter 7
Network Optimization Problems
网络最优化问题
RUC Information School,Ye Xiang,2007
Some Applications
一些实际应用 P248
马歇尔公司（ Marshalls,Inc.）
配送网络（ Interfaces 1987年 7～ 8）
一家折扣连锁零售店，现在和以前是如何使用微型计算机去处理一个最小费用流问题。
应用中公司力图使得从供应商到加工中心，
再从加工中心到零售店的商流最优。其中的一些网络有超过 20,000条弧。
Chapter 7
Network Optimization Problems
网络最优化问题
RUC Information School,Ye Xiang,2007
Some Applications
一些实际应用 P248
现金流管理 （动态规划问题）
不同的节点可以代表发生在不同时间的事件。在这个应用中，每一个供应点代表了一个特定的时间（或一个时期），在这个时间的供应量就是那时所能得到的现金量。同理，每个需求点代表了某个特定的时间（
或时期）公司所需的现金储备。每个需求点的需求量就是到时所需要的现金量。
目标：使得公司在每个从有现金闲置到有现金需求期间的现金投资所得收入最大。
因此，每个转运点代表在特定的时间间隔里对一种特定的短期投资期权（如从银行购买存款单）的选择。
得到的网络将有一个连续流，代表了从有现金闲置、
投资现金到在投资到期后利用现金的计划。
Chapter 7
Network Optimization Problems
网络最优化问题
RUC Information School,Ye Xiang,2007
最小费用流问题的特殊类型 P248
（五种重要的类型）
1,运输问题,有出发地 (供应点 -供应量 )和目的地 (需求点 -需求量 )，
没有转运点和弧的容量限制，目标：总运输成本最小（或总利润最大）
2,指派类型,出发地 (供应点 -供应量为 1)是人,目的地 (需求点 -需求量为 1)是任务,没有转运点和弧的容量限制，目标：总指派成本最小（或总利润最大）
3,转运问题,有出发地 (供应点 -供应量 )和目的地 (需求点 -需求量 )，
有转运点，但没有弧的容量限制 (或有容量限制 )，目标：总流量费用最小（或总利润最大）
4,最大流问题,有 供应点、需求点,转运点、弧的容量限制，但没有 供应量和需求量的限制,目标：通过网络到目的地的总流量最大
5,最短路问题,有 供应点 (供应量为 1),需求点 (需求量为 1),转运点、没有弧的容量限制,目标：通过网络到目的地的总距离最短
Chapter 7
Network Optimization Problems
网络最优化问题
RUC Information School,Ye Xiang,2007
7,2 BMZ Case Study
案例研究,BMZ 公司的最大流问题 P249
BMZ公司从德国斯图加特的工厂到洛杉矶的配送中心的配送网络图
ST
LI
BO
RO
NO
NY
LA
N e w Y or k
R ott e r d am
S t u ttg ar t
Li s b on
N e w O r l e an s
{ 40 u n i t s m a x,]
Bo r d e au x
[7 0 u ni t s m a x,]
Lo s A n ge l e s
[8 0 u ni t s m a x,]
[6 0 u ni t s m a x,]
[5 0 u ni t s m a x,]
[3 0 u ni t s m a x,]
[5 0 u ni t s m a x,]
[4 0 u ni t s m a x,]
[7 0 u ni t s m a x]
Chapter 7
Network Optimization Problems
网络最优化问题
RUC Information School,Ye Xiang,2007
作为最大流问题的 BMZ
问题的网络模型 P252
ST
LI
BO
RO
NO
NY
LA
[7 0]
[8 0]
[7 0]
[6 0]
[4 0]
[5 0]
[3 0]
[5 0]
[4 0]
Chapter 7
Network Optimization Problems
网络最优化问题
RUC Information School,Ye Xiang,2007
BMZ公司的 线性规划数学模型（补充）
决策变量,xij为通过弧 (节点 i到节点 j)的流量总流量最大化 Max Flow = xST-RO+xST-BO+xST-LI （目标：从 ST流出的总流量最大）
约束条件 (转运点的净流量为 0、弧的容量限制，非负）
转运点 鹿特丹 (RO),xRO-NY - xST-RO = 0
转运点 波尔多 (BO),(xBO-NY + xBO-NO ) - xST-BO = 0
转运点 里斯本 (LI),xLI-NO - xST-LI = 0
转运点 纽约 (NY),xNY-LA – (xRO-NY + xBO-NY ) = 0
转运点 新奥尔良 (NO),xN0-LA – (xBO-NO + xLI-NO ) = 0
弧的容量限制,xij? Capacity（容量）
且 xij? 0
参看
P252
BMZ问题的网络模型和电子表格模型
Chapter 7
Network Optimization Problems
网络最优化问题
RUC Information School,Ye Xiang,2007
BMZ公司的电子表格模型 P252
B M Z C o,M a x i m u m F l o w P r o b l e m
P252 BMZ公 司的最大流问题从 到 流量X i j 容量 节点 净流量 供应/ 需求斯图加特( S T ) 鹿特丹( R O ) 50 <= 50 斯图加特( S T ) 150 源斯图加特( S T ) 波尔多( B O ) 70 <= 70 鹿特丹( R O ) 0 = 0
斯图加特( S T ) 里斯本( L I ) 30 <= 40 波尔多( B O ) 0 = 0
鹿特丹( R O ) 纽约( N Y ) 50 <= 60 里斯本( L I ) 0 = 0
波尔多( B O ) 纽约( N Y ) 30 <= 40 纽约( N Y ) 0 = 0
波尔多( B O ) 新奥尔良( N O ) 40 <= 50 新奥尔良( N O ) 0 = 0
里斯本( L I ) 新奥尔良( N O ) 30 <= 30 洛杉矶( L A ) -150 汇纽约( N Y ) 洛杉矶( L A ) 80 <= 80
新奥尔良( N O ) 洛杉矶( L A ) 70 <= 70
最大流 150
决策变量,xij为节点 i->节点 j的流量目标：从 ST流出的总流量最大
= xST-RO+xST-BO+xST-LI
Chapter 7
Network Optimization Problems
网络最优化问题
RUC Information School,Ye Xiang,2007
7,3 Maximum Flow Problems
最大流问题 P253
最大流问题也与网络中的流有关，
但目标不是使得流的成本最小化，
而是寻找一个流的方案，使得通过网络的流量最大
Chapter 7
Network Optimization Problems
网络最优化问题
RUC Information School,Ye Xiang,2007
Assumptions of Maximum Flow Problems
最大流问题的假设 P253
1,网络中所有流起源于一个叫做 源 Source的节点,所有的流终止于另一个叫做 收点 （汇） Sink的节点
2,其余所有的节点叫做 转运点
3,通过每一个 弧 的流只允许沿着弧的箭头方向流动
4,目标是使得从源到收点（汇）的 总流量最大
Chapter 7
Network Optimization Problems
网络最优化问题
RUC Information School,Ye Xiang,2007
最大流问题的变形 P254
（多个供应点和多个需求点 )
1,扩展的 BMZ公司的最大流问题（ 2个供应点和 2个需求点）
2,多了：一个源 (柏林 )，一个收点 (西雅图 )，两个港口（汉堡、
波士顿）,7条弧
3,目标：从斯图加特 ST和柏林 BE两个工厂运出的总流量最大
B M Z C o,E x p a n d e d M a x i m u m F l o w P r o b l e m
P 255 扩展的 B M Z 公司的最大流问题（两个工厂 ST 和 BE,两个配送中心 LA 和 SE ）
From( 从 ) TO( 到 ) 流量 X i j 容量 节点 净流量 供应/ 需求斯图加特( S T ) 鹿特丹 ( R O ) 40 <= 50 斯图加特 ( S T ) 140 源斯图加特 ( S T ) 波尔多 ( B O ) 70 <= 70 柏林 ( B E ) 80 源斯图加特 ( S T ) 里斯本 ( L I ) 30 <= 40 汉堡 ( H A ) 0 = 0
柏林 ( B E ) 鹿特丹 ( R O ) 20 <= 20 鹿特丹 ( R O ) 0 = 0
柏林 ( B E ) 汉堡 ( H A ) 60 <= 60 波尔多 ( B O ) 0 = 0
鹿特丹 ( R O ) 纽约 ( N Y ) 60 <= 60 里斯本 ( L I ) 0 = 0
波尔多 ( B O ) 纽约 ( N Y ) 30 <= 40 波士顿 ( B N ) 0 = 0
波尔多 ( B O ) 新奥尔良 ( N O ) 40 <= 50 纽约 ( N Y ) 0 = 0
里斯本 ( L I ) 新奥尔良 ( N O ) 30 <= 30 新奥尔良 ( N O ) 0 = 0
汉堡 ( H A ) 纽约 ( N Y ) 30 <= 30 洛杉矶 ( L A ) - 1 6 0 汇汉堡 ( H A ) 波士顿 ( B N ) 30 <= 40 西雅图 ( SE) - 6 0 汇新奥尔良 ( N O ) 洛杉矶 ( L A ) 70 <= 70
纽约 ( N Y ) 洛杉矶 ( L A ) 80 <= 80
纽约 ( N Y ) 西雅图 ( SE) 40 <= 40
波士顿 ( B N ) 洛杉矶 ( L A ) 10 <= 10
波士顿 ( B N ) 西雅图 ( SE) 20 <= 20
最大流 220
决策变量,xij为节点 i->节点 j的流量目标：从 ST和 BE流出的总流量最大
=xST-RO+xST-BO+xST-LI＋ xBE-RO+xBE-HA
Chapter 7
Network Optimization Problems
网络最优化问题
RUC Information School,Ye Xiang,2007
Some Applications
一些实际应用 P255
1,通过配送网络的流量最大，如 BMZ问题
2,通过从供应商到处理设施的公司供应网络的流量最大
3,通过管道运输系统的油的流量最大
4,通过输水系统的水的流量最大
5,通过交通网络的车辆的流量最大
P256 解决非常大型的问题：网络单纯形法
（但 Excel 规划求解软件中没有）
Chapter 7
Network Optimization Problems
网络最优化问题
RUC Information School,Ye Xiang,2007
7,4 Shortest Path Problem
最短路问题 P256
最短路问题的最普遍的应用在两个点之间寻找最短路
是最小费用流问题的一种特殊类型，源的供应量为 1,目的地（需求点）的 需求量为 1,转运点的净流量为 0、没有弧的容量限制,目标：通过网络到目的地的总距离最短
与指派问题是运输问题的一种特殊类型相似（没有转运点）
Chapter 7
Network Optimization Problems
网络最优化问题
RUC Information School,Ye Xiang,2007
Example,Littletown Fire Station
例子：里特城消防站 P256
里特城 (Littletown)的消防站和某一农场社区间的道路系统 P257
F i re
S t a t i on
H
G
F
E
D
C
B
A
3
6
4
2
1
7
5
4
6
8
6
4
3
4
6
7
5
2
3
F a r m i ng
Co m m un i t y
Chapter 7
Network Optimization Problems
网络最优化问题
RUC Information School,Ye Xiang,2007
里特城 (Littletown)的消防站道路系统的网络模型 P257
里特城 (Littletown)的消防站道路系统的网络模型 P257（注意
：这里连接节点的连线是 边 （边的两端都没有箭头），边允许双向流动
岔路口 用网络中的 节点 表示，消防站和农场社区是另外两个节点，分别标为 O（源）和 T（目的地）
目标：找到从消防站到农场社区的最短路线（总距离最短）。
T
H
G
F
E
D
B
C
A
O (D e s t i n a t i o n )(O r i g i n )
3
6
1
2
6
4
3
4
7
8
6
5
4
2
3
4
6
7
5
Chapter 7
Network Optimization Problems
网络最优化问题
RUC Information School,Ye Xiang,2007
里特城消防的最短路问题的电子表格模型 P259
L i t t l e t o w n F i r e D e p a r t m e n t S h o r t e s t P a t h P r o b l e m
P 259 里特城消防站的最短路问题从 到 是否走 X i j 距离 节点 净流量 供应 / 需求消防站 A 1 3 消防站 1 = 1
消防站 B 0 6 A 0 = 0
消防站 C 0 4 B 0 = 0
A B 1 1 C 0 = 0
A D 0 6 D 0 = 0
B A 0 1 E 0 = 0
B C 0 2 F 0 = 0
B D 0 4 G 0 = 0
B E 1 5 H 0 = 0
C B 0 2 农场社区 -1 = -1
C E 0 7
D E 0 3
D F 0 8
E D 0 3
E F 1 6
E G 0 5
E H 0 4
F G 0 3
F 农场社区 1 4
G F 0 3
G H 0 2
G 农场社区 0 6
H G 0 2
H 农场社区 0 7
总距离 19
一条 边 用 方向相反 的 2条弧表示
，但这里根据实际问题，只将垂直的当作边（ AB/BC/DE/FG/GH
），其余的直接当作弧
消防站：供应量为 1的供应点，
代表此次行程的开始
农场社区：需求量为 1的需求点
，代表此次行程的结束
其余的节点：转运点
Chapter 7
Network Optimization Problems
网络最优化问题
RUC Information School,Ye Xiang,2007
里特城消防站的 线性规划数学模型（补充）
决策变量,xij为弧 (节点 i->节点 j) 是否走（ 1－走,0－不走）
总距离最小化 Min D=3xO-A+6xO-B+4xO-C +……+4 xF-T+6xG-T+7xH-T
约束条件 (节点净流量、非负）
供应点 O,xO-A + xO-B +xO-C = 1
转运点 A,(xA-D + xA-B)-(xO-A+ xB-A)= 0
转运点 B,(xB-A+xB-D+ xB-E+ xB-C)-(xO-B+xA-B +xC-B)= 0
……
转运点 G,(xG-F + xG-T+ xG-H)- (xF-G + xE-G + xH-G) = 0
转运点 H,(xH-T + xH-G)- (xE-H + xG-H ) = 0
需求点 T,xF-T + xG-T + xH-T = 1
且 xij? 0
参看
P257
网络模型和
P259的电子表格模型与电子表格对应，只将垂直的当作边（
AB/BC/DE/FG/GH），其余的直接当作弧
Chapter 7
Network Optimization Problems
网络最优化问题
RUC Information School,Ye Xiang,2007
Assumptions of shortest Path Problem
最短路问题的假设 P258
1,在网络中选择一条路，始于某源点终于目标地
2,连接两个节点的连线叫做 边 （允许任一个方向行进）,弧 （只允许沿着一个方向行进）
3,和每条边相关的一个 非负数,叫做该边的长度
4,目标是为了寻找从源到目标地的最短路（总长度最小的路）
Chapter 7
Network Optimization Problems
网络最优化问题
RUC Information School,Ye Xiang,2007
Applications of shortest Path Problem
最短路问题的一些实际应用 P258
1,行进的总距离最短：里特城消防站 (前面的例子 )
2,总费用最小：二手车的买卖决策
3,总时间最短：新产品开发时间
Chapter 7
Network Optimization Problems
网络最优化问题
RUC Information School,Ye Xiang,2007
最短路问题的应用
--使总费用最小的例子 P259
买卖二手车问题决策：
已知购买价格、保养费用、卖车价格 P260表 7,2
注意数据的状态转换（节点间的关系）
数据的转换公式（在第一个节点这个时间买车，然后在第二个节点的那个时间把车折价卖出）：
弧长＝买车的价格＋使用和保养多年的总费用－使用多年后折价卖出的价格
Chapter 7
Network Optimization Problems
网络最优化问题
RUC Information School,Ye Xiang,2007
总费用最小 (莎拉买卖二手车）
的电子表格模型 P262
Sarah's Car Purchasing Problem
P 2 6 2 总费用最小( 莎拉买卖二手车）
开车和保养 最后一年卖出 购买的费用 的价值 价格第1 年 $2,000 $8,500 $12,000
第2 年 $3,000 $6,500
第3 年 $4,500 $4,500
第4 年 $6,500 $3,000
从 到 是否买卖 Xij 费用 节点 净流量 供应/ 需求现在 第1 年末 0 $5,500 现在 1 = 1
现在 第2 年末 1 $10,500 第1 年末 0 = 0
现在 第3 年末 0 $17,000 第2 年末 0 = 0
现在 第4 年末 0 $25,000 第3 年末 0 = 0
第1 年末 第2 年末 0 $5,500 第4 年末 -1 = -1
第1 年末 第3 年末 0 $10,500
第1 年末 第4 年末 0 $17,000
第2 年末 第3 年末 0 $5,500
第2 年末 第4 年末 1 $10,500
第3 年末 第4 年末 0 $5,500
总费用 $21,000
结果（买卖两次）：
现在买，第 2年末卖，
第 2年末买，第 4年末卖。
Chapter 7
Network Optimization Problems
网络最优化问题
RUC Information School,Ye Xiang,2007
最短路问题的应用
--使总时间最短的例子 P261
新产品投放市场决策：
已知新产品计划 20个月后投放市场，但还有四个没有时间重叠的阶段没有完成，而每个阶段的实施水平可以从正常水平提高为优先水平或应急水平，使之能够加速完成；而且最后三个阶段中都可以考虑提高实施水平。各阶段各水平所需时间见 P261表 7,3
管理层现在已经给这四个阶段拨款 $3000万，每个阶段的费用见 P263
表 7,4
管理层希望确定这四个阶段各自应该采取哪一种水平，从而在 $3000
万预算限制内，使得这种产品可以尽早地推向市场。
注意数据的状态转换（节点间的关系）：
每个节点由两个数字表示（已经完成的阶段数目，剩余资金）：
弧长 -所需时间
引入一个虚拟目的地 T
(2,12)和 (3,3)由于资金问题，不能采用应急水平思考题：是否可以将费用作为弧长，而节点为（已经完成的阶段数目，剩余时间），求总费用最少
Chapter 7
Network Optimization Problems
网络最优化问题
RUC Information School,Ye Xiang,2007
使总时间最短（奎克公司）
的电子表格模型 P265
P 2 6 5 奎克公司 Q u i c k C o,P r o d u c t D e v e l o p m e n t S c h e d u l i n g P r o b l e m
从 到 是否采用 X i j 所需时间 节点 净流量 供应 / 需求
( 0,3 0 ) ( 1,2 7 ) 0 5 ( 0,3 0 ) 1 = 1
( 0,3 0 ) ( 1,2 4 ) 0 4 ( 1,2 7 ) 0 = 0
( 0,3 0 ) ( 1,2 1 ) 1 2 ( 1,2 4 ) 0 = 0
( 1,2 7 ) ( 2,2 1 ) 0 3 ( 1,2 1 ) 0 = 0
( 1,2 7 ) ( 2,1 8 ) 0 2 ( 2,2 1 ) 0 = 0
( 1,2 4 ) ( 2,1 8 ) 0 3 ( 2,1 8 ) 0 = 0
( 1,2 4 ) ( 2,1 5 ) 0 2 ( 2,1 5 ) 0 = 0
( 1,2 1 ) ( 2,1 5 ) 1 3 ( 2,1 2 ) 0 = 0
( 1,2 1 ) ( 2,1 2 ) 0 2 ( 3,1 2 ) 0 = 0
( 2,2 1 ) ( 3,1 2 ) 0 5 ( 3,9 ) 0 = 0
( 2,2 1 ) ( 3,9 ) 0 3 ( 3,6 ) 0 = 0
( 2,1 8 ) ( 3,9 ) 0 5 ( 3,3 ) 0 = 0
( 2,1 8 ) ( 3,6 ) 0 3 ( 4,9 ) 0 = 0
( 2,1 5 ) ( 3,6 ) 0 5 ( 4,6 ) 0 = 0
( 2,1 5 ) ( 3,3 ) 1 3 ( 4,3 ) 0 = 0
( 2,1 2 ) ( 3,3 ) 0 5 ( 4,0 ) 0 = 0
( 3,1 2 ) ( 4,9 ) 0 2 ( T ) -1 = -1
( 3,1 2 ) ( 4,6 ) 0 1
( 3,9 ) ( 4,6 ) 0 2
( 3,9 ) ( 4,3 ) 0 1
( 3,6 ) ( 4,3 ) 0 2
( 3,6 ) ( 4,0 ) 0 1
( 3,3 ) ( 4,0 ) 1 2
( 4,9 ) ( T ) 0 0
( 4,6 ) ( T ) 0 0
( 4,3 ) ( T ) 0 0
( 4,0 ) ( T ) 1 0
总时间 10
结果：
阶段 1：应急，需 2个月，成本 9
阶段 2：优先，需 3个月，成本 6
阶段 3：应急，需 3个月，成本 12
阶段 4：优先，需 2个月，成本 3
合计：总时间 =10个月，资金 =30(百万 $)
注意：
(2,12)和
(3,3)由于资金问题
，不能采用应急水平
Chapter 7
Network Optimization Problems
网络最优化问题
RUC Information School,Ye Xiang,2007
使总时间最短（奎克公司）
思考题 1：是否可以将费用作为弧长，而节点为
（已经完成的阶段数目，剩余时间），求总费用最少?
回答：可以，结果为：
总费用＝ 3＋ 6＋ 9＋ 3＝ 21，
总时间＝ 20－ 5＝ 15个月，
实际上每次采用时间最长，费用最小的那种情况。
思考题 2：是否可以采用第 9章的 BIP（ 0－ 1整数规划），求总时间最短?
回答：可以，因为每个阶段必须完成（＝ 1），
且受到总拨款 3000万美元的限制。
Chapter 7
Network Optimization Problems
网络最优化问题
RUC Information School,Ye Xiang,2007
补充材料：最短路问题的另一个实际应用－货郎担问题
1,货郎担问题属于传统运筹学的动态规划问题（本章问题基本上都是动态规划问题，即可试着用本章的网络最优化问题的 Excel思路解决传统运筹学的动态规划问题）
2,货郎担问题（带权的哈密尔顿图）：一个货郎要去若干个城镇售货，已知各城镇之间的距离，那么货郎应如何选择行走路线，使每个城镇恰好经过一次，并回到原出发点，并使总行程最短
3,我（叶向）自己认为的解题方法,由于原来的最短路问题，有些节点可以不经过，但货郎担问题要求每个节点都要恰好经过一次，所以约束条件改为将每个节点的总流出和总流入分开（每个节点两个约束，而非最短路问题的一个净流量约束），且供应 /需求 =1
4,上面 3的方法（称为改进的最短路法），有时可以得到解（具体请见补充的
4城市货郎担问题的 Excel文件），但有时会得到有几个回路的解，此时就应该再增加去掉回路的约束，具体请见补充的 5城市货郎担问题的 Excel文件）
Chapter 7
Network Optimization Problems
网络最优化问题
RUC Information School,Ye Xiang,2007
补充材料：货郎担问题的线性规划模型
11
1
1
Mi n D c
1 1,2,...,( ) j
1 1,2,...,( )
1
ij
nn
ij ij
ij
n
ij
i
n
ij
j
ij ji
x i j
x i j
x j n i j
x i n i j
x x i j
决 策 变 量,－ 城 市 到 城 市 是 否 走 （ 结 果 为 0,1 ）
目 标 总 距 离 最 小 化约 束 条 件,
节 点 的 总 流 入节 点 i 的 总 流 出
2
,..
1 ( m <= n/2)
0,1,2,...,
ij jk k i
ij jk k l pi
ij
x x x i j k
x x x x m i j p
x i j n
任 何 2 个 节 点 i,j 间 不 能 有 回 路任 何 3 个 节 点 i,j,k 间 不 能 有 回 路任 何 m 个 节 点 间 不 能 有 回 路LL
由于回路的约束很多，用 Excel
实现时，采用各个击破的方法，
即,有回路，再增加约束条件去掉回路,的办法。
Chapter 7
Network Optimization Problems
网络最优化问题
RUC Information School,Ye Xiang,2007
补充材料：中国邮路问题
1,一个邮递员从邮局出发，将邮件投递到他管辖的所有街道，最后回到邮局，如何安排他的行驶路线，使总路长最短。这个问题由中国数学家 管梅谷 教授 1962
年提出，因此称为 中国邮路问题。
2,货郎担问题与中国邮路问题不同之处是：前者遍历图的所有节点，后者遍历图的所有边。
3,如果存在一条回路，不重复包含图中的每一条边，这条回路称为欧拉（ Euler
）回路。具有欧拉回路的图称为欧拉图，全为偶点的图是欧拉图。
4,如果有奇点，不存在欧拉回路，无论邮局在哪一个点，邮递员要经过每一条边
，至少有一条边重复经过。
5,解法：
（ 1） 虚拟边将所有奇点变为偶点，虚拟边就是邮递员重复经过的街道。
（ 2）调整虚拟边。初始欧拉回路不一定是最短回路。判断最短回路的准则：（
a）每条边最多重复一次；（ b）所有回路中虚拟边长之和不超过回路边长之和的一半。
思考题,Excel解法，具体例子请见补充的 7城市中国邮路问题的 Excel文件
Chapter 7
Network Optimization Problems
网络最优化问题
RUC Information School,Ye Xiang,2007
7,5 Minimum Spanning Tree Problem
最小支撑树问题 P264
给你网络中的节点,但没有给你边 。 或者,
给你可供选择的边和如果把它插入到网络中后的每条边的正的成本 （ 或者相似的度量 ）
在 设计网络 时你希望通过插入足够的边,以满足每两个节点之间都存在一条路的需要
目标是寻找一种方法,使得在满足要求的同时总成本最小
Chapter 7
Network Optimization Problems
网络最优化问题
RUC Information School,Ye Xiang,2007
例子：默登 Modern公司的问题 P267
默登（ Modern）公司的管理层已经决定铺设最先进的光导纤维网络，为它的主要中心之间提供高速通信（数据
、声音和图像）。
P266图 7.18中的节点显示了该公司主要中心（包括公司的总部、巨型计算机、研究区、生产和配送中心等）的分布图。虚线是铺设纤维光缆可能的位置。每条虚线旁边的数字表示了如果选择在这个位置铺设光缆需要花费的成本。
为了充分利用光纤技术在中心之间高速通信的优势,不需要 在每两个中心之间都要用一条光缆把它们直接连接起来。
现在的问题就是要确定需要铺设哪些光缆使得提供给每两个中心之间的高速通信的总成本最低。实际上，这就是一个 最小支撑树问题
Chapter 7
Network Optimization Problems
网络最优化问题
RUC Information School,Ye Xiang,2007
The Simple Algorithm
简单的算法 —贪婪算法 P267
1,选择第一条边：选择成本最低的备选边
2,选择下一条边：在一个已经有一条边连接的节点和另一个还没有边连接的节点之间选择成本最低的备选边
3,重复第二个步骤,直到所有的节点都有一条边 （ 可能会有多于一条边 ） 与其相连 。
4,此时就得到了最优解 （ 最小支撑树 ）
Chapter 7
Network Optimization Problems
网络最优化问题
RUC Information School,Ye Xiang,2007
贪婪算法的另一种形式（ Kruska算法
,1959年提出）,我（叶向）认为此种方法更适合用 Excel帮助求解 ）
1,选择第一条边：选择成本最低的备选边
2,选择下一条边：从剩下的边中取一条边满足：
最小边,?不构成圈
3,重复第二个步骤,直到选取的边数为节点数 -1
4,此时就得到了最优解 （ 最小支撑树 ）
加边法：取图的 n个孤立点作为一个支撑图,从最短边开始往支撑图中添加,见圈回避,直到连通 （ 有 n-1条边 ）
具体 Excel解法请看补充的 P266 默登公司问题 (最小支撑树
Excel解法 )
还有破圈法：
任取一圈，去掉圈中最长边
，直到无圈。
Chapter 7
Network Optimization Problems
网络最优化问题
RUC Information School,Ye Xiang,2007
P271 Some Applications
最小支撑树的一些实际应用
电信网络（计算机网络、电话专用线网络、有线电视网络等等）的设计
低负荷运输网络的设计，使得网络中提供链接的部分
（如铁路、公路等 等）的总成本最小
高压输电线路网络的设计
电器设备线路网络（如数字计算机系统）的设计，使得线路总长度最短
连接多个场所的管道网络设计
Chapter 7
Network Optimization Problems
网络最优化问题
RUC Information School,Ye Xiang,2007
7,6 Summary 小结 P271
网络表示在描绘网络系统中各部分之间关联上非常有用
最小费用流问题的特殊类型包括运输问题和指派问题
最大流问题的目标是使得从一个特定的起点 （ 源 ） 到一个特定的终点 （ 汇 ） 的总流量最大
最短路问题也有始点 （ 源 ） 和终点 （ 目标地 ）,但是,
它的目标是从源点到目标地寻找一条总长度最短的路
最小支撑树问题的目标是使得为任意两个节点之间提供路时总成本最小
Chapter 7
Network Optimization Problems
网络最优化问题
RUC Information School,Ye Xiang,2007
案例 7.2 资金的运作 P281
背景：在亚洲金融危机时期,为了保证资金安全,
所以格兰特 ·希尔协会希望把包括日元,卢比和林吉特在内的三种亚洲货币转换成美元 。
由于存在各国政府对个人或公司把本国货币兑换成某一特定外国货币和把资金从本国抽走的行为都有严格的管制,所以格兰特 ·希尔协会需要借助其它国家的市场,从而最终使以上三种亚洲货币转换成美元 。
协会同时注意到一种货币兑换成另一种货币要支付一定的交易费用,也就是协会要承担一定的交易成本 。 在这种情况下,协会有关此次资金运作就可以理解为：在保证货币的顺利转移的前提下,使交易成本最小化 。
Chapter 7
Network Optimization Problems
网络最优化问题
RUC Information School,Ye Xiang,2007
案例 7.2 资金的运作（续）
按照货币汇率（表 1）的提示，可以看出在此次货币资金的转移过程中不存在套利机会，
所以我们可以把协会所有持有的亚洲货币直接按照汇率兑换成美元，无需考虑在资金运动过程中的各种汇率转换。即协会持有的在亚洲市场的相当美元头寸为：
日本市场,1500万 × 80× 0.008＝ 9600K$
印尼市场,105亿 × 0.00016＝ 1680K$
马来西亚市场,2800万 × 0.2＝ 5600K$
Chapter 7
Network Optimization Problems
网络最优化问题
RUC Information School,Ye Xiang,2007
案例 7.2 资金的运作（续）
对于交易成本（表 2），为了简化题设要求，在本题中对交易成本只做最后结算，不考虑在交易过程中由于交易成本的出现所导致的所持头寸的变化。
对于交易限额（表 3,单位为千美元 ），我们假设只有在亚洲市场才会出现交易限额的情况，对于其它市场却不做讨论。
本题是最小费用流的一个应用：
供应点：日元 (9600K$)、卢比 (1680K$)、林吉特
(5600K$)
转运点：加拿大元、欧元、英镑、比索
需求点：美元（ 9600+1680+5600=16880K$）
Chapter 7
Network Optimization Problems
网络最优化问题
RUC Information School,Ye Xiang,2007
案例 7.2 资金的运作（ Excel实现 ）
a.供应点：日元、卢比、林吉特，需求点：美元
b.最小费用流问题 (总交易成本最低 )：
供应点：日元 (9600K$)、卢比 (1680K$),林吉特 (5600K$)
转运点：加拿大元、欧元、英镑、比索
需求点：美元（ 9600+1680+5600=16880K$）
弧,3*7(源 ->其他 )+4*3(转运点 ->其他转运点 )+4*1(转运点 ->美元 )
=37条
Min C=83.38K$
c.在 b中去掉交易限制，得 Min C=67.48K$
d.只对,卢比 ->其他 7种货币,,即在 c基础上，改 7处成本，得 Min
C=92.68K$
e.汇率不断变化，应该投资比较安全的欧共体，而非风险大的亚洲市场（中国除外）
Chapter 7
Network Optimization Problems
网络最优化问题
RUC Information School,Ye Xiang,2007
Exercise
作业（上机）
P273 习题：
7,2（最小费用流问题）
7,8,7,9 （ 最大流问题）
7,11（ 最短路问题－分两种情况：最短路问题和考虑 5个城市都要经过）
7,12（ 最短路问题的应用）
7,17（ 最小支撑树问题－可用 Excel帮助求解）
Chapter 7
Network Optimization Problems
网络最优化问题
RUC Information School,Ye Xiang,2007
补充：最短路应用举例
（设备更新问题） （选作题）
企业在使用某设备时，每年年初可购置新设备，也可以使用一年或几年后卖掉重新购置新设备。
已知 4年年初购置新设备的价格分别为 2.5,2.6,2.8和 3.1
万元。
设备使用了 1－ 4年后的残值分别为 2,1.6,1.3和 1.1万元。
使用时间在 1－ 4年内的维修保养费用分别为 0.3,0.8,1.5
和 2.0万元。
试确定一个设备更新策略，在下列两种情形下使用使 4年的设备购置和维护总费用最小。
（ 1）第 4年年末设备一定要处理掉。
（ 2）第 4年年末设备不处理。
Chapter 7
Network Optimization Problems
网络最优化问题
RUC Information School,Ye Xiang,2007
补充,最短路应用举例－设备更新问题
(残值与设备原值有关 )（选作题）
Anly大学毕业后刚取得汽车驾驶执照，对 SKY05型小汽车情有独钟，准备第 1年年初买一辆使用 3年的 SKY05型的二手车，价格
7.12万元。一年后可以继续使用该车，也可以卖掉购买同一品牌的新车，不再购买二手车。通过市场调查和预测，得到有关资料如下：
（ 1）该车第一年年初的价格为 10万元，以后逐年降价，第 2年到第 5年的降价幅度分别 4％,5％,7％,5％。第 t年的价格记为 Pt，
t=1,2,… 。
（ 2）购新车必须支付 10％的各项税费。购置费用记为 Ct,Ct＝ 1.1Pt。
（ 3）该车第 t年的维护费用 Mt是使用年限 t的函数,Mt＝ 0.4t1.3
（ 4）汽车年折旧率为 15％，汽车残值为 Bt＝ 0.85tPt。
无论第 5年年末更新或不更新，将汽车残值从总成本中减去，等价于将车卖掉。 Anly如何制定一个 5年的购车方案，使 5年的总成本最低（不计其他成本）。
Network Optimization Problems
网络最优化问题
RUC Information School,Ye Xiang,2007
Data,Model and Decisions
数据、模型与决策第七章
Network Optimization Problems
网络最优化问题
Chapter 7
Network Optimization Problems
网络最优化问题
RUC Information School,Ye Xiang,2007
本章内容 Topics P241
Applications of Network Optimization
网络最优化模型的应用
Types of Network Optimization Problem
网络最优化问题类型
7.1 Minimum-Cost Flow Problem 最小费用流问题
7.2/7.3 Maximum Flow Problem 最大流问题
7.4 Shortest Path Problem 最短路问题补充：最短路问题的另一个实际应用－货郎担问题补充：最短路问题的另一个实际应用－中国邮路问题
7.5 Minimum Spanning Tree Problem 最小支撑树问题案例 7.2资金的运作 （ 最小费用流问题 ）
与第 6章相比：
1,有 转运点,一般不是全连通图，所以要画网络图
2,在 Excel中用弧 表示稀疏矩阵
3,约束条件中用净流量
Chapter 7
Network Optimization Problems
网络最优化问题
RUC Information School,Ye Xiang,2007
Applications of Network Optimization
网络最优化模型的应用 P241
网络在各种实际背景问题中以各种各样的形式存在。交通、电子和通讯网络遍及我们日常生活的各个方面，网络规划也广泛用于解决不同领域中的各种问题，如生产
、分配、项目计划、厂址选择、资源管理和财务策划等等。
网络规划为描述系统各组成部分之间的关系提供了非常有效的直观和概念上的帮助，广泛应用于科学、社会和经济活动的每个领域中。
近些年来，管理科学中一个振奋人心的发展是它的网络最优化问题的方法论和应用方面都取得了不同寻常的飞速发展。
Chapter 7
Network Optimization Problems
网络最优化问题
RUC Information School,Ye Xiang,2007
Types of Network Optimization Problem
网络最优化问题类型 P242
Minimum-Cost Flow Problem
最小费用流问题
Maximum Flow Problem
最大流问题
Shortest Path Problem
最短路问题
Minimum Spanning Tree Problem
最小支撑树问题 － 唯一不是线性规划问题
Chapter 7
Network Optimization Problems
网络最优化问题
RUC Information School,Ye Xiang,2007
F1
DC
F2 W2
W1
8 0 u n i t s
p r o d u ce d
7 0 u n i t s
p r o d u ce d
6 0 u n i t s
needed
9 0 u n i t s
needed
7,1 Minimum-Cost Flow Problem
最小费用流问题 P242
例子：无限配送公司的问题（网络配送问题是网络最小费用流问题的另外一个名称）
无限配送公司有 两个工厂生产产品，这些产品需要运送到两个仓库里。
配送网络图 （网络模型）
目标是通过配送网络的运输成本最小。
Chapter 7
Network Optimization Problems
网络最优化问题
RUC Information School,Ye Xiang,2007
7,1 Minimum-Cost Flow Problem
最小费用流问题－术语 P244
最小费用流问题的构成（网络表示）：
1.节点 (nodes)（ 供应点 -净流量为正,需求点 -净流量为负
,转运点 -净流量为零 ）
2.弧（ arcs）：可行的运输线路（节点 i->节点 j），
经常有最大流量（容量）的限制
3.决策变量,xij－通过弧（节点 i->节点 j）的流量
Chapter 7
Network Optimization Problems
网络最优化问题
RUC Information School,Ye Xiang,2007
Assumptions of Minimum Cost Flow Problem
最小费用流问题的假设 P244
1,至少一个 供应点
2,至少一个 需求点
3,剩下都是 转运点
4,通过 弧 的流只允许沿着箭头方向流动，通过弧的最大流量取决于该弧的容量
5,网络中有足够的弧提供足够 容量,使得所有在供应点中产生的流都能够到达需求点
6,在流的单位成本已知前提下，通过每一条弧的流的成本和流量成正比（ 目标函数是线性的 ）
7,最小费用流问题的目标在满足给定需求条件下，使得通过网络配送的总成本最小（或总利润最大化）
Chapter 7
Network Optimization Problems
网络最优化问题
RUC Information School,Ye Xiang,2007
Characteristic of Solution
解的特征 P244
具有 可行解 的特征：在以上的假设下，当且仅当供应点所提供的流量总和等于需求点所需要的流量总和时，最小费用流问题有可行解（ 平衡条件 ） 。
具有 整数解 的特征：只要其所有的 供应量、需求量和弧的容量都是整数值,那么任何最小费用流问题的可行解就一定有所有流量都是整数的最优解 。
Chapter 7
Network Optimization Problems
网络最优化问题
RUC Information School,Ye Xiang,2007
无限配送公司的最小费用流问题的 线性规划数学模型（补充）
决策变量 xij：通过弧 (节点 i到节点 j)的流量总运输成本 最小化 Min Cost = $700xF1-W1 + $300xF1-DC +
$200xDC-W1 + $400xDC-W2 + $400xF2-DC + $900xF2-W2
约束条件 (节点净流量,弧的容量限制，非负）
（由于 80＋ 70＝ 60＋ 90，即总供应＝总需求，平衡）
供应点 F1,xF1-W1 + xF1-DC = 80
供应点 F2,xF2-DC + xF2-W2 = 70
转运点 DC,xDC-W1 + xDC-W2 - (xF1-DC + xF2-DC ) = 0
需求点 W1,xF1-W1 + xDC-W1 = 60
需求点 W2,xDC-W2 + xF2-W2 = 90
弧的容量限制,xF1-DC,xDC-W1,xDC-W2,xF2-DC?50
且 xij? 0
Chapter 7
Network Optimization Problems
网络最优化问题
RUC Information School,Ye Xiang,2007
无限配送公司的最小费用流问题的电子表格模型 P245
列出了网络中的 弧 和各弧所对应的 容量,单位流量成本
决策变量（可变单元格）为通过弧的流量 xij
目标单元格：计算流量的总成本
每个节点的 净流量（总流出－总流入） 为约束条件。供应点的净流量为正，需求点的净流量为负，而转运点的净流量为 0
窍门：用两个 SUMIF函数的差来计算每个节点的净流量（快捷且不容易犯错）
Chapter 7
Network Optimization Problems
网络最优化问题
RUC Information School,Ye Xiang,2007
更加有效地解决大规模的最小费用流问题 P246
网络单纯法 （ Network Simplex Method）：
可以用于解决大型的运输问题
现在，许多公司都使用网络单纯法来解决他们的最小费用流问题。有些问题是非常庞大的，有着数万个节点和弧。有时，弧的数量甚至可能会多得多，达到几百万条。
但 Excel ―规划求解”软件中没有网络单纯法
，但其他的线性规划的商业软件包通常都有这种方法。
Chapter 7
Network Optimization Problems
网络最优化问题
RUC Information School,Ye Xiang,2007
Some Applications
一些实际应用 P247
应用类型 供应点 转运点 需求点配送网络的运作 货源 中间存储设施 客户固体废弃物管理 固体废弃物源 处理设施 固体废弃物掩埋地供应网络的运作 供应商 中间仓库 加工设备工厂协调产品组合 工厂 某一特定产品的生产某一特定产品的市场现金流管理 某一特定时间的现金来源短期投资期权 在特定时间对现金的需求表 7.1 几类典型的最小费用流问题的应用
Chapter 7
Network Optimization Problems
网络最优化问题
RUC Information School,Ye Xiang,2007
Some Applications
一些实际应用 P247
国际纸业公司（ International Paper Company）
配送网络（ Interfaces 1988年 3~4）
世界上最大的纸浆、纸和纸类产品的制造商以及木材和夹板的主要生产者。拥有 2000万英亩的林区或其权益。分布在不同地方的林区是它配送网络的供应点。
但是，在公司的产品最终到达需求点（客户）以前，
供应流必须经过一系列很长的转运点。它通过配送网络的一条典型的路径就是：
林区 → 木材堆积场 → 锯木厂 → 造纸厂
→ 纸制品加工厂 → 仓库 → 客户
Chapter 7
Network Optimization Problems
网络最优化问题
RUC Information School,Ye Xiang,2007
Some Applications
一些实际应用 P248
马歇尔公司（ Marshalls,Inc.）
配送网络（ Interfaces 1987年 7～ 8）
一家折扣连锁零售店，现在和以前是如何使用微型计算机去处理一个最小费用流问题。
应用中公司力图使得从供应商到加工中心，
再从加工中心到零售店的商流最优。其中的一些网络有超过 20,000条弧。
Chapter 7
Network Optimization Problems
网络最优化问题
RUC Information School,Ye Xiang,2007
Some Applications
一些实际应用 P248
现金流管理 （动态规划问题）
不同的节点可以代表发生在不同时间的事件。在这个应用中，每一个供应点代表了一个特定的时间（或一个时期），在这个时间的供应量就是那时所能得到的现金量。同理，每个需求点代表了某个特定的时间（
或时期）公司所需的现金储备。每个需求点的需求量就是到时所需要的现金量。
目标：使得公司在每个从有现金闲置到有现金需求期间的现金投资所得收入最大。
因此，每个转运点代表在特定的时间间隔里对一种特定的短期投资期权（如从银行购买存款单）的选择。
得到的网络将有一个连续流，代表了从有现金闲置、
投资现金到在投资到期后利用现金的计划。
Chapter 7
Network Optimization Problems
网络最优化问题
RUC Information School,Ye Xiang,2007
最小费用流问题的特殊类型 P248
（五种重要的类型）
1,运输问题,有出发地 (供应点 -供应量 )和目的地 (需求点 -需求量 )，
没有转运点和弧的容量限制，目标：总运输成本最小（或总利润最大）
2,指派类型,出发地 (供应点 -供应量为 1)是人,目的地 (需求点 -需求量为 1)是任务,没有转运点和弧的容量限制，目标：总指派成本最小（或总利润最大）
3,转运问题,有出发地 (供应点 -供应量 )和目的地 (需求点 -需求量 )，
有转运点，但没有弧的容量限制 (或有容量限制 )，目标：总流量费用最小（或总利润最大）
4,最大流问题,有 供应点、需求点,转运点、弧的容量限制，但没有 供应量和需求量的限制,目标：通过网络到目的地的总流量最大
5,最短路问题,有 供应点 (供应量为 1),需求点 (需求量为 1),转运点、没有弧的容量限制,目标：通过网络到目的地的总距离最短
Chapter 7
Network Optimization Problems
网络最优化问题
RUC Information School,Ye Xiang,2007
7,2 BMZ Case Study
案例研究,BMZ 公司的最大流问题 P249
BMZ公司从德国斯图加特的工厂到洛杉矶的配送中心的配送网络图
ST
LI
BO
RO
NO
NY
LA
N e w Y or k
R ott e r d am
S t u ttg ar t
Li s b on
N e w O r l e an s
{ 40 u n i t s m a x,]
Bo r d e au x
[7 0 u ni t s m a x,]
Lo s A n ge l e s
[8 0 u ni t s m a x,]
[6 0 u ni t s m a x,]
[5 0 u ni t s m a x,]
[3 0 u ni t s m a x,]
[5 0 u ni t s m a x,]
[4 0 u ni t s m a x,]
[7 0 u ni t s m a x]
Chapter 7
Network Optimization Problems
网络最优化问题
RUC Information School,Ye Xiang,2007
作为最大流问题的 BMZ
问题的网络模型 P252
ST
LI
BO
RO
NO
NY
LA
[7 0]
[8 0]
[7 0]
[6 0]
[4 0]
[5 0]
[3 0]
[5 0]
[4 0]
Chapter 7
Network Optimization Problems
网络最优化问题
RUC Information School,Ye Xiang,2007
BMZ公司的 线性规划数学模型（补充）
决策变量,xij为通过弧 (节点 i到节点 j)的流量总流量最大化 Max Flow = xST-RO+xST-BO+xST-LI （目标：从 ST流出的总流量最大）
约束条件 (转运点的净流量为 0、弧的容量限制，非负）
转运点 鹿特丹 (RO),xRO-NY - xST-RO = 0
转运点 波尔多 (BO),(xBO-NY + xBO-NO ) - xST-BO = 0
转运点 里斯本 (LI),xLI-NO - xST-LI = 0
转运点 纽约 (NY),xNY-LA – (xRO-NY + xBO-NY ) = 0
转运点 新奥尔良 (NO),xN0-LA – (xBO-NO + xLI-NO ) = 0
弧的容量限制,xij? Capacity（容量）
且 xij? 0
参看
P252
BMZ问题的网络模型和电子表格模型
Chapter 7
Network Optimization Problems
网络最优化问题
RUC Information School,Ye Xiang,2007
BMZ公司的电子表格模型 P252
B M Z C o,M a x i m u m F l o w P r o b l e m
P252 BMZ公 司的最大流问题从 到 流量X i j 容量 节点 净流量 供应/ 需求斯图加特( S T ) 鹿特丹( R O ) 50 <= 50 斯图加特( S T ) 150 源斯图加特( S T ) 波尔多( B O ) 70 <= 70 鹿特丹( R O ) 0 = 0
斯图加特( S T ) 里斯本( L I ) 30 <= 40 波尔多( B O ) 0 = 0
鹿特丹( R O ) 纽约( N Y ) 50 <= 60 里斯本( L I ) 0 = 0
波尔多( B O ) 纽约( N Y ) 30 <= 40 纽约( N Y ) 0 = 0
波尔多( B O ) 新奥尔良( N O ) 40 <= 50 新奥尔良( N O ) 0 = 0
里斯本( L I ) 新奥尔良( N O ) 30 <= 30 洛杉矶( L A ) -150 汇纽约( N Y ) 洛杉矶( L A ) 80 <= 80
新奥尔良( N O ) 洛杉矶( L A ) 70 <= 70
最大流 150
决策变量,xij为节点 i->节点 j的流量目标：从 ST流出的总流量最大
= xST-RO+xST-BO+xST-LI
Chapter 7
Network Optimization Problems
网络最优化问题
RUC Information School,Ye Xiang,2007
7,3 Maximum Flow Problems
最大流问题 P253
最大流问题也与网络中的流有关，
但目标不是使得流的成本最小化，
而是寻找一个流的方案，使得通过网络的流量最大
Chapter 7
Network Optimization Problems
网络最优化问题
RUC Information School,Ye Xiang,2007
Assumptions of Maximum Flow Problems
最大流问题的假设 P253
1,网络中所有流起源于一个叫做 源 Source的节点,所有的流终止于另一个叫做 收点 （汇） Sink的节点
2,其余所有的节点叫做 转运点
3,通过每一个 弧 的流只允许沿着弧的箭头方向流动
4,目标是使得从源到收点（汇）的 总流量最大
Chapter 7
Network Optimization Problems
网络最优化问题
RUC Information School,Ye Xiang,2007
最大流问题的变形 P254
（多个供应点和多个需求点 )
1,扩展的 BMZ公司的最大流问题（ 2个供应点和 2个需求点）
2,多了：一个源 (柏林 )，一个收点 (西雅图 )，两个港口（汉堡、
波士顿）,7条弧
3,目标：从斯图加特 ST和柏林 BE两个工厂运出的总流量最大
B M Z C o,E x p a n d e d M a x i m u m F l o w P r o b l e m
P 255 扩展的 B M Z 公司的最大流问题（两个工厂 ST 和 BE,两个配送中心 LA 和 SE ）
From( 从 ) TO( 到 ) 流量 X i j 容量 节点 净流量 供应/ 需求斯图加特( S T ) 鹿特丹 ( R O ) 40 <= 50 斯图加特 ( S T ) 140 源斯图加特 ( S T ) 波尔多 ( B O ) 70 <= 70 柏林 ( B E ) 80 源斯图加特 ( S T ) 里斯本 ( L I ) 30 <= 40 汉堡 ( H A ) 0 = 0
柏林 ( B E ) 鹿特丹 ( R O ) 20 <= 20 鹿特丹 ( R O ) 0 = 0
柏林 ( B E ) 汉堡 ( H A ) 60 <= 60 波尔多 ( B O ) 0 = 0
鹿特丹 ( R O ) 纽约 ( N Y ) 60 <= 60 里斯本 ( L I ) 0 = 0
波尔多 ( B O ) 纽约 ( N Y ) 30 <= 40 波士顿 ( B N ) 0 = 0
波尔多 ( B O ) 新奥尔良 ( N O ) 40 <= 50 纽约 ( N Y ) 0 = 0
里斯本 ( L I ) 新奥尔良 ( N O ) 30 <= 30 新奥尔良 ( N O ) 0 = 0
汉堡 ( H A ) 纽约 ( N Y ) 30 <= 30 洛杉矶 ( L A ) - 1 6 0 汇汉堡 ( H A ) 波士顿 ( B N ) 30 <= 40 西雅图 ( SE) - 6 0 汇新奥尔良 ( N O ) 洛杉矶 ( L A ) 70 <= 70
纽约 ( N Y ) 洛杉矶 ( L A ) 80 <= 80
纽约 ( N Y ) 西雅图 ( SE) 40 <= 40
波士顿 ( B N ) 洛杉矶 ( L A ) 10 <= 10
波士顿 ( B N ) 西雅图 ( SE) 20 <= 20
最大流 220
决策变量,xij为节点 i->节点 j的流量目标：从 ST和 BE流出的总流量最大
=xST-RO+xST-BO+xST-LI＋ xBE-RO+xBE-HA
Chapter 7
Network Optimization Problems
网络最优化问题
RUC Information School,Ye Xiang,2007
Some Applications
一些实际应用 P255
1,通过配送网络的流量最大，如 BMZ问题
2,通过从供应商到处理设施的公司供应网络的流量最大
3,通过管道运输系统的油的流量最大
4,通过输水系统的水的流量最大
5,通过交通网络的车辆的流量最大
P256 解决非常大型的问题：网络单纯形法
（但 Excel 规划求解软件中没有）
Chapter 7
Network Optimization Problems
网络最优化问题
RUC Information School,Ye Xiang,2007
7,4 Shortest Path Problem
最短路问题 P256
最短路问题的最普遍的应用在两个点之间寻找最短路
是最小费用流问题的一种特殊类型，源的供应量为 1,目的地（需求点）的 需求量为 1,转运点的净流量为 0、没有弧的容量限制,目标：通过网络到目的地的总距离最短
与指派问题是运输问题的一种特殊类型相似（没有转运点）
Chapter 7
Network Optimization Problems
网络最优化问题
RUC Information School,Ye Xiang,2007
Example,Littletown Fire Station
例子：里特城消防站 P256
里特城 (Littletown)的消防站和某一农场社区间的道路系统 P257
F i re
S t a t i on
H
G
F
E
D
C
B
A
3
6
4
2
1
7
5
4
6
8
6
4
3
4
6
7
5
2
3
F a r m i ng
Co m m un i t y
Chapter 7
Network Optimization Problems
网络最优化问题
RUC Information School,Ye Xiang,2007
里特城 (Littletown)的消防站道路系统的网络模型 P257
里特城 (Littletown)的消防站道路系统的网络模型 P257（注意
：这里连接节点的连线是 边 （边的两端都没有箭头），边允许双向流动
岔路口 用网络中的 节点 表示，消防站和农场社区是另外两个节点，分别标为 O（源）和 T（目的地）
目标：找到从消防站到农场社区的最短路线（总距离最短）。
T
H
G
F
E
D
B
C
A
O (D e s t i n a t i o n )(O r i g i n )
3
6
1
2
6
4
3
4
7
8
6
5
4
2
3
4
6
7
5
Chapter 7
Network Optimization Problems
网络最优化问题
RUC Information School,Ye Xiang,2007
里特城消防的最短路问题的电子表格模型 P259
L i t t l e t o w n F i r e D e p a r t m e n t S h o r t e s t P a t h P r o b l e m
P 259 里特城消防站的最短路问题从 到 是否走 X i j 距离 节点 净流量 供应 / 需求消防站 A 1 3 消防站 1 = 1
消防站 B 0 6 A 0 = 0
消防站 C 0 4 B 0 = 0
A B 1 1 C 0 = 0
A D 0 6 D 0 = 0
B A 0 1 E 0 = 0
B C 0 2 F 0 = 0
B D 0 4 G 0 = 0
B E 1 5 H 0 = 0
C B 0 2 农场社区 -1 = -1
C E 0 7
D E 0 3
D F 0 8
E D 0 3
E F 1 6
E G 0 5
E H 0 4
F G 0 3
F 农场社区 1 4
G F 0 3
G H 0 2
G 农场社区 0 6
H G 0 2
H 农场社区 0 7
总距离 19
一条 边 用 方向相反 的 2条弧表示
，但这里根据实际问题，只将垂直的当作边（ AB/BC/DE/FG/GH
），其余的直接当作弧
消防站：供应量为 1的供应点，
代表此次行程的开始
农场社区：需求量为 1的需求点
，代表此次行程的结束
其余的节点：转运点
Chapter 7
Network Optimization Problems
网络最优化问题
RUC Information School,Ye Xiang,2007
里特城消防站的 线性规划数学模型（补充）
决策变量,xij为弧 (节点 i->节点 j) 是否走（ 1－走,0－不走）
总距离最小化 Min D=3xO-A+6xO-B+4xO-C +……+4 xF-T+6xG-T+7xH-T
约束条件 (节点净流量、非负）
供应点 O,xO-A + xO-B +xO-C = 1
转运点 A,(xA-D + xA-B)-(xO-A+ xB-A)= 0
转运点 B,(xB-A+xB-D+ xB-E+ xB-C)-(xO-B+xA-B +xC-B)= 0
……
转运点 G,(xG-F + xG-T+ xG-H)- (xF-G + xE-G + xH-G) = 0
转运点 H,(xH-T + xH-G)- (xE-H + xG-H ) = 0
需求点 T,xF-T + xG-T + xH-T = 1
且 xij? 0
参看
P257
网络模型和
P259的电子表格模型与电子表格对应，只将垂直的当作边（
AB/BC/DE/FG/GH），其余的直接当作弧
Chapter 7
Network Optimization Problems
网络最优化问题
RUC Information School,Ye Xiang,2007
Assumptions of shortest Path Problem
最短路问题的假设 P258
1,在网络中选择一条路，始于某源点终于目标地
2,连接两个节点的连线叫做 边 （允许任一个方向行进）,弧 （只允许沿着一个方向行进）
3,和每条边相关的一个 非负数,叫做该边的长度
4,目标是为了寻找从源到目标地的最短路（总长度最小的路）
Chapter 7
Network Optimization Problems
网络最优化问题
RUC Information School,Ye Xiang,2007
Applications of shortest Path Problem
最短路问题的一些实际应用 P258
1,行进的总距离最短：里特城消防站 (前面的例子 )
2,总费用最小：二手车的买卖决策
3,总时间最短：新产品开发时间
Chapter 7
Network Optimization Problems
网络最优化问题
RUC Information School,Ye Xiang,2007
最短路问题的应用
--使总费用最小的例子 P259
买卖二手车问题决策：
已知购买价格、保养费用、卖车价格 P260表 7,2
注意数据的状态转换（节点间的关系）
数据的转换公式（在第一个节点这个时间买车，然后在第二个节点的那个时间把车折价卖出）：
弧长＝买车的价格＋使用和保养多年的总费用－使用多年后折价卖出的价格
Chapter 7
Network Optimization Problems
网络最优化问题
RUC Information School,Ye Xiang,2007
总费用最小 (莎拉买卖二手车）
的电子表格模型 P262
Sarah's Car Purchasing Problem
P 2 6 2 总费用最小( 莎拉买卖二手车）
开车和保养 最后一年卖出 购买的费用 的价值 价格第1 年 $2,000 $8,500 $12,000
第2 年 $3,000 $6,500
第3 年 $4,500 $4,500
第4 年 $6,500 $3,000
从 到 是否买卖 Xij 费用 节点 净流量 供应/ 需求现在 第1 年末 0 $5,500 现在 1 = 1
现在 第2 年末 1 $10,500 第1 年末 0 = 0
现在 第3 年末 0 $17,000 第2 年末 0 = 0
现在 第4 年末 0 $25,000 第3 年末 0 = 0
第1 年末 第2 年末 0 $5,500 第4 年末 -1 = -1
第1 年末 第3 年末 0 $10,500
第1 年末 第4 年末 0 $17,000
第2 年末 第3 年末 0 $5,500
第2 年末 第4 年末 1 $10,500
第3 年末 第4 年末 0 $5,500
总费用 $21,000
结果（买卖两次）：
现在买，第 2年末卖，
第 2年末买，第 4年末卖。
Chapter 7
Network Optimization Problems
网络最优化问题
RUC Information School,Ye Xiang,2007
最短路问题的应用
--使总时间最短的例子 P261
新产品投放市场决策：
已知新产品计划 20个月后投放市场，但还有四个没有时间重叠的阶段没有完成，而每个阶段的实施水平可以从正常水平提高为优先水平或应急水平，使之能够加速完成；而且最后三个阶段中都可以考虑提高实施水平。各阶段各水平所需时间见 P261表 7,3
管理层现在已经给这四个阶段拨款 $3000万，每个阶段的费用见 P263
表 7,4
管理层希望确定这四个阶段各自应该采取哪一种水平，从而在 $3000
万预算限制内，使得这种产品可以尽早地推向市场。
注意数据的状态转换（节点间的关系）：
每个节点由两个数字表示（已经完成的阶段数目，剩余资金）：
弧长 -所需时间
引入一个虚拟目的地 T
(2,12)和 (3,3)由于资金问题，不能采用应急水平思考题：是否可以将费用作为弧长，而节点为（已经完成的阶段数目，剩余时间），求总费用最少
Chapter 7
Network Optimization Problems
网络最优化问题
RUC Information School,Ye Xiang,2007
使总时间最短（奎克公司）
的电子表格模型 P265
P 2 6 5 奎克公司 Q u i c k C o,P r o d u c t D e v e l o p m e n t S c h e d u l i n g P r o b l e m
从 到 是否采用 X i j 所需时间 节点 净流量 供应 / 需求
( 0,3 0 ) ( 1,2 7 ) 0 5 ( 0,3 0 ) 1 = 1
( 0,3 0 ) ( 1,2 4 ) 0 4 ( 1,2 7 ) 0 = 0
( 0,3 0 ) ( 1,2 1 ) 1 2 ( 1,2 4 ) 0 = 0
( 1,2 7 ) ( 2,2 1 ) 0 3 ( 1,2 1 ) 0 = 0
( 1,2 7 ) ( 2,1 8 ) 0 2 ( 2,2 1 ) 0 = 0
( 1,2 4 ) ( 2,1 8 ) 0 3 ( 2,1 8 ) 0 = 0
( 1,2 4 ) ( 2,1 5 ) 0 2 ( 2,1 5 ) 0 = 0
( 1,2 1 ) ( 2,1 5 ) 1 3 ( 2,1 2 ) 0 = 0
( 1,2 1 ) ( 2,1 2 ) 0 2 ( 3,1 2 ) 0 = 0
( 2,2 1 ) ( 3,1 2 ) 0 5 ( 3,9 ) 0 = 0
( 2,2 1 ) ( 3,9 ) 0 3 ( 3,6 ) 0 = 0
( 2,1 8 ) ( 3,9 ) 0 5 ( 3,3 ) 0 = 0
( 2,1 8 ) ( 3,6 ) 0 3 ( 4,9 ) 0 = 0
( 2,1 5 ) ( 3,6 ) 0 5 ( 4,6 ) 0 = 0
( 2,1 5 ) ( 3,3 ) 1 3 ( 4,3 ) 0 = 0
( 2,1 2 ) ( 3,3 ) 0 5 ( 4,0 ) 0 = 0
( 3,1 2 ) ( 4,9 ) 0 2 ( T ) -1 = -1
( 3,1 2 ) ( 4,6 ) 0 1
( 3,9 ) ( 4,6 ) 0 2
( 3,9 ) ( 4,3 ) 0 1
( 3,6 ) ( 4,3 ) 0 2
( 3,6 ) ( 4,0 ) 0 1
( 3,3 ) ( 4,0 ) 1 2
( 4,9 ) ( T ) 0 0
( 4,6 ) ( T ) 0 0
( 4,3 ) ( T ) 0 0
( 4,0 ) ( T ) 1 0
总时间 10
结果：
阶段 1：应急，需 2个月，成本 9
阶段 2：优先，需 3个月，成本 6
阶段 3：应急，需 3个月，成本 12
阶段 4：优先，需 2个月，成本 3
合计：总时间 =10个月，资金 =30(百万 $)
注意：
(2,12)和
(3,3)由于资金问题
，不能采用应急水平
Chapter 7
Network Optimization Problems
网络最优化问题
RUC Information School,Ye Xiang,2007
使总时间最短（奎克公司）
思考题 1：是否可以将费用作为弧长，而节点为
（已经完成的阶段数目，剩余时间），求总费用最少?
回答：可以，结果为：
总费用＝ 3＋ 6＋ 9＋ 3＝ 21，
总时间＝ 20－ 5＝ 15个月，
实际上每次采用时间最长，费用最小的那种情况。
思考题 2：是否可以采用第 9章的 BIP（ 0－ 1整数规划），求总时间最短?
回答：可以，因为每个阶段必须完成（＝ 1），
且受到总拨款 3000万美元的限制。
Chapter 7
Network Optimization Problems
网络最优化问题
RUC Information School,Ye Xiang,2007
补充材料：最短路问题的另一个实际应用－货郎担问题
1,货郎担问题属于传统运筹学的动态规划问题（本章问题基本上都是动态规划问题，即可试着用本章的网络最优化问题的 Excel思路解决传统运筹学的动态规划问题）
2,货郎担问题（带权的哈密尔顿图）：一个货郎要去若干个城镇售货，已知各城镇之间的距离，那么货郎应如何选择行走路线，使每个城镇恰好经过一次，并回到原出发点，并使总行程最短
3,我（叶向）自己认为的解题方法,由于原来的最短路问题，有些节点可以不经过，但货郎担问题要求每个节点都要恰好经过一次，所以约束条件改为将每个节点的总流出和总流入分开（每个节点两个约束，而非最短路问题的一个净流量约束），且供应 /需求 =1
4,上面 3的方法（称为改进的最短路法），有时可以得到解（具体请见补充的
4城市货郎担问题的 Excel文件），但有时会得到有几个回路的解，此时就应该再增加去掉回路的约束，具体请见补充的 5城市货郎担问题的 Excel文件）
Chapter 7
Network Optimization Problems
网络最优化问题
RUC Information School,Ye Xiang,2007
补充材料：货郎担问题的线性规划模型
11
1
1
Mi n D c
1 1,2,...,( ) j
1 1,2,...,( )
1
ij
nn
ij ij
ij
n
ij
i
n
ij
j
ij ji
x i j
x i j
x j n i j
x i n i j
x x i j
决 策 变 量,－ 城 市 到 城 市 是 否 走 （ 结 果 为 0,1 ）
目 标 总 距 离 最 小 化约 束 条 件,
节 点 的 总 流 入节 点 i 的 总 流 出
2
,..
1 ( m <= n/2)
0,1,2,...,
ij jk k i
ij jk k l pi
ij
x x x i j k
x x x x m i j p
x i j n
任 何 2 个 节 点 i,j 间 不 能 有 回 路任 何 3 个 节 点 i,j,k 间 不 能 有 回 路任 何 m 个 节 点 间 不 能 有 回 路LL
由于回路的约束很多，用 Excel
实现时，采用各个击破的方法，
即,有回路，再增加约束条件去掉回路,的办法。
Chapter 7
Network Optimization Problems
网络最优化问题
RUC Information School,Ye Xiang,2007
补充材料：中国邮路问题
1,一个邮递员从邮局出发，将邮件投递到他管辖的所有街道，最后回到邮局，如何安排他的行驶路线，使总路长最短。这个问题由中国数学家 管梅谷 教授 1962
年提出，因此称为 中国邮路问题。
2,货郎担问题与中国邮路问题不同之处是：前者遍历图的所有节点，后者遍历图的所有边。
3,如果存在一条回路，不重复包含图中的每一条边，这条回路称为欧拉（ Euler
）回路。具有欧拉回路的图称为欧拉图，全为偶点的图是欧拉图。
4,如果有奇点，不存在欧拉回路，无论邮局在哪一个点，邮递员要经过每一条边
，至少有一条边重复经过。
5,解法：
（ 1） 虚拟边将所有奇点变为偶点，虚拟边就是邮递员重复经过的街道。
（ 2）调整虚拟边。初始欧拉回路不一定是最短回路。判断最短回路的准则：（
a）每条边最多重复一次；（ b）所有回路中虚拟边长之和不超过回路边长之和的一半。
思考题,Excel解法，具体例子请见补充的 7城市中国邮路问题的 Excel文件
Chapter 7
Network Optimization Problems
网络最优化问题
RUC Information School,Ye Xiang,2007
7,5 Minimum Spanning Tree Problem
最小支撑树问题 P264
给你网络中的节点,但没有给你边 。 或者,
给你可供选择的边和如果把它插入到网络中后的每条边的正的成本 （ 或者相似的度量 ）
在 设计网络 时你希望通过插入足够的边,以满足每两个节点之间都存在一条路的需要
目标是寻找一种方法,使得在满足要求的同时总成本最小
Chapter 7
Network Optimization Problems
网络最优化问题
RUC Information School,Ye Xiang,2007
例子：默登 Modern公司的问题 P267
默登（ Modern）公司的管理层已经决定铺设最先进的光导纤维网络，为它的主要中心之间提供高速通信（数据
、声音和图像）。
P266图 7.18中的节点显示了该公司主要中心（包括公司的总部、巨型计算机、研究区、生产和配送中心等）的分布图。虚线是铺设纤维光缆可能的位置。每条虚线旁边的数字表示了如果选择在这个位置铺设光缆需要花费的成本。
为了充分利用光纤技术在中心之间高速通信的优势,不需要 在每两个中心之间都要用一条光缆把它们直接连接起来。
现在的问题就是要确定需要铺设哪些光缆使得提供给每两个中心之间的高速通信的总成本最低。实际上，这就是一个 最小支撑树问题
Chapter 7
Network Optimization Problems
网络最优化问题
RUC Information School,Ye Xiang,2007
The Simple Algorithm
简单的算法 —贪婪算法 P267
1,选择第一条边：选择成本最低的备选边
2,选择下一条边：在一个已经有一条边连接的节点和另一个还没有边连接的节点之间选择成本最低的备选边
3,重复第二个步骤,直到所有的节点都有一条边 （ 可能会有多于一条边 ） 与其相连 。
4,此时就得到了最优解 （ 最小支撑树 ）
Chapter 7
Network Optimization Problems
网络最优化问题
RUC Information School,Ye Xiang,2007
贪婪算法的另一种形式（ Kruska算法
,1959年提出）,我（叶向）认为此种方法更适合用 Excel帮助求解 ）
1,选择第一条边：选择成本最低的备选边
2,选择下一条边：从剩下的边中取一条边满足：
最小边,?不构成圈
3,重复第二个步骤,直到选取的边数为节点数 -1
4,此时就得到了最优解 （ 最小支撑树 ）
加边法：取图的 n个孤立点作为一个支撑图,从最短边开始往支撑图中添加,见圈回避,直到连通 （ 有 n-1条边 ）
具体 Excel解法请看补充的 P266 默登公司问题 (最小支撑树
Excel解法 )
还有破圈法：
任取一圈，去掉圈中最长边
，直到无圈。
Chapter 7
Network Optimization Problems
网络最优化问题
RUC Information School,Ye Xiang,2007
P271 Some Applications
最小支撑树的一些实际应用
电信网络（计算机网络、电话专用线网络、有线电视网络等等）的设计
低负荷运输网络的设计，使得网络中提供链接的部分
（如铁路、公路等 等）的总成本最小
高压输电线路网络的设计
电器设备线路网络（如数字计算机系统）的设计，使得线路总长度最短
连接多个场所的管道网络设计
Chapter 7
Network Optimization Problems
网络最优化问题
RUC Information School,Ye Xiang,2007
7,6 Summary 小结 P271
网络表示在描绘网络系统中各部分之间关联上非常有用
最小费用流问题的特殊类型包括运输问题和指派问题
最大流问题的目标是使得从一个特定的起点 （ 源 ） 到一个特定的终点 （ 汇 ） 的总流量最大
最短路问题也有始点 （ 源 ） 和终点 （ 目标地 ）,但是,
它的目标是从源点到目标地寻找一条总长度最短的路
最小支撑树问题的目标是使得为任意两个节点之间提供路时总成本最小
Chapter 7
Network Optimization Problems
网络最优化问题
RUC Information School,Ye Xiang,2007
案例 7.2 资金的运作 P281
背景：在亚洲金融危机时期,为了保证资金安全,
所以格兰特 ·希尔协会希望把包括日元,卢比和林吉特在内的三种亚洲货币转换成美元 。
由于存在各国政府对个人或公司把本国货币兑换成某一特定外国货币和把资金从本国抽走的行为都有严格的管制,所以格兰特 ·希尔协会需要借助其它国家的市场,从而最终使以上三种亚洲货币转换成美元 。
协会同时注意到一种货币兑换成另一种货币要支付一定的交易费用,也就是协会要承担一定的交易成本 。 在这种情况下,协会有关此次资金运作就可以理解为：在保证货币的顺利转移的前提下,使交易成本最小化 。
Chapter 7
Network Optimization Problems
网络最优化问题
RUC Information School,Ye Xiang,2007
案例 7.2 资金的运作（续）
按照货币汇率（表 1）的提示，可以看出在此次货币资金的转移过程中不存在套利机会，
所以我们可以把协会所有持有的亚洲货币直接按照汇率兑换成美元，无需考虑在资金运动过程中的各种汇率转换。即协会持有的在亚洲市场的相当美元头寸为：
日本市场,1500万 × 80× 0.008＝ 9600K$
印尼市场,105亿 × 0.00016＝ 1680K$
马来西亚市场,2800万 × 0.2＝ 5600K$
Chapter 7
Network Optimization Problems
网络最优化问题
RUC Information School,Ye Xiang,2007
案例 7.2 资金的运作（续）
对于交易成本（表 2），为了简化题设要求，在本题中对交易成本只做最后结算，不考虑在交易过程中由于交易成本的出现所导致的所持头寸的变化。
对于交易限额（表 3,单位为千美元 ），我们假设只有在亚洲市场才会出现交易限额的情况，对于其它市场却不做讨论。
本题是最小费用流的一个应用：
供应点：日元 (9600K$)、卢比 (1680K$)、林吉特
(5600K$)
转运点：加拿大元、欧元、英镑、比索
需求点：美元（ 9600+1680+5600=16880K$）
Chapter 7
Network Optimization Problems
网络最优化问题
RUC Information School,Ye Xiang,2007
案例 7.2 资金的运作（ Excel实现 ）
a.供应点：日元、卢比、林吉特，需求点：美元
b.最小费用流问题 (总交易成本最低 )：
供应点：日元 (9600K$)、卢比 (1680K$),林吉特 (5600K$)
转运点：加拿大元、欧元、英镑、比索
需求点：美元（ 9600+1680+5600=16880K$）
弧,3*7(源 ->其他 )+4*3(转运点 ->其他转运点 )+4*1(转运点 ->美元 )
=37条
Min C=83.38K$
c.在 b中去掉交易限制，得 Min C=67.48K$
d.只对,卢比 ->其他 7种货币,,即在 c基础上，改 7处成本，得 Min
C=92.68K$
e.汇率不断变化，应该投资比较安全的欧共体，而非风险大的亚洲市场（中国除外）
Chapter 7
Network Optimization Problems
网络最优化问题
RUC Information School,Ye Xiang,2007
Exercise
作业（上机）
P273 习题：
7,2（最小费用流问题）
7,8,7,9 （ 最大流问题）
7,11（ 最短路问题－分两种情况：最短路问题和考虑 5个城市都要经过）
7,12（ 最短路问题的应用）
7,17（ 最小支撑树问题－可用 Excel帮助求解）
Chapter 7
Network Optimization Problems
网络最优化问题
RUC Information School,Ye Xiang,2007
补充：最短路应用举例
（设备更新问题） （选作题）
企业在使用某设备时，每年年初可购置新设备，也可以使用一年或几年后卖掉重新购置新设备。
已知 4年年初购置新设备的价格分别为 2.5,2.6,2.8和 3.1
万元。
设备使用了 1－ 4年后的残值分别为 2,1.6,1.3和 1.1万元。
使用时间在 1－ 4年内的维修保养费用分别为 0.3,0.8,1.5
和 2.0万元。
试确定一个设备更新策略，在下列两种情形下使用使 4年的设备购置和维护总费用最小。
（ 1）第 4年年末设备一定要处理掉。
（ 2）第 4年年末设备不处理。
Chapter 7
Network Optimization Problems
网络最优化问题
RUC Information School,Ye Xiang,2007
补充,最短路应用举例－设备更新问题
(残值与设备原值有关 )（选作题）
Anly大学毕业后刚取得汽车驾驶执照，对 SKY05型小汽车情有独钟，准备第 1年年初买一辆使用 3年的 SKY05型的二手车，价格
7.12万元。一年后可以继续使用该车，也可以卖掉购买同一品牌的新车，不再购买二手车。通过市场调查和预测，得到有关资料如下：
（ 1）该车第一年年初的价格为 10万元，以后逐年降价，第 2年到第 5年的降价幅度分别 4％,5％,7％,5％。第 t年的价格记为 Pt，
t=1,2,… 。
（ 2）购新车必须支付 10％的各项税费。购置费用记为 Ct,Ct＝ 1.1Pt。
（ 3）该车第 t年的维护费用 Mt是使用年限 t的函数,Mt＝ 0.4t1.3
（ 4）汽车年折旧率为 15％，汽车残值为 Bt＝ 0.85tPt。
无论第 5年年末更新或不更新，将汽车残值从总成本中减去，等价于将车卖掉。 Anly如何制定一个 5年的购车方案，使 5年的总成本最低（不计其他成本）。
