- 📚 相关推荐文章
- 最大流问题 推荐
- 最小费用最大流 推荐
最大流问题
奥鹏教育学习平台-福建省住房和城乡
2023年3月17日发(作者：委托书范本图片)一、某工厂生产甲乙两种产品，需A、B二种原料，其有关数据如表所示：
页脚内容1
案例BMZ公司的最大流问题
背景
BMZ公司是欧洲一家生产豪华汽车的制造商。它因为提供优质的服
务而获得很好的声誉，保持这个声誉一个很重要的秘诀就是它有着充裕的
汽车配件供应，从而能够随时供货给公司众多的经销商合授权维修店。
这些供应件主要存放在公司的配送中心里，这样一有需求就可以立即
送货。卡尔（BMZ公司的供应链的经理）优先考虑的是改进这些配送
中心的不足之处。
该公司在美国有几个配送中心。但是，离洛杉机中心最近的一个配送
中心却坐落离洛杉机1000多英里的西雅图。保证洛杉机中心良好的供
应是尤为重要的。因此，现在那里的供应不断减少的现状成为了公司高层
管理真正关心的问题。
大部分的汽车配件以及新车是在该公司坐落于德国的斯图加特的总
厂和新车一起生产的。也就是这家工厂向洛杉机中心供应汽车配件。每月
有超过300000立方英尺的配件需要运到。现在，下个月需要多得多的
数量以补充正在减少的库存。
问题
卡尔需要尽快制定一个方案，使得下个月从总厂运送到洛杉机配送中
心的供应件尽可能多。他认识到了这是个最大流的问题——一个使得
从总厂运送到洛杉机配送中心的配件流最大的问题。因为总厂生产的配件
量远远要大于能够运送到配送中心的量，所以，可以运送多少配件的限制
条件就是公司配送网络的容量。
这个配送网络如下图1。在图中，标有ST和LA的节点分别代表
斯图加特的工厂和洛杉机的配送中心。由于工厂所在地有一个铁路运转
点，所以首先通过铁路把配件运输到欧洲的三个港口：鹿特丹（RO）
波尔多（BO）和里斯本(LI)；然后通过船运到美国的港口纽约（NY）
或新奥尔良（NO）；最后用卡车送到洛杉机的配送中心。
S
R
B
L
N
N
L
5
7
4
6
0
4
5
3
8
0
7
图1网络模型
一、某工厂生产甲乙两种产品，需A、B二种原料，其有关数据如表所示：
页脚内容2
经营这些铁路、船舶和卡车的组织是独立所有的公司，这些公司为很
多的公司运输货物。由于对这些老主顾原有的承诺，这些公司不可以在短
时间内为任何一个客户大量增加运输空间配额。因此，BMZ公司只能够
保证获得下个月每条运输航线有限的运输空间。图1已经给出可以获得的
空间数量，以100立方米为1个单位（由于每100立方米比3500立方英
尺大一点，所以，需要运送的这批货物体积是很大的）。
模型描述和求解
这是一个最大流问题，每一条弧下方括号里的数字代表了该弧的
容量。通过标号法求得最大流，在各线路上的运输方案如表1所
示。最大流量为150单位。
表1最大流分配方案
出发点目的地运输量
斯图加特鹿特丹
50
斯图加特波尔图
70
斯图加特里斯本
30
鹿特丹纽约
50
波尔图纽约
30
波尔图新奥尔良
40
里斯本新奥尔良
30
纽约洛杉矶
80
新奥尔良洛杉矶
70
进一步改善的方案
在柏林，即斯图加特的工厂的北面，公司有一家较小一点的工厂也生
产汽车配件。虽然通常这家工厂用来协助供应给北欧、加拿大和美国北部
地区的配送中心（包括在西雅图的一个），但是它也同样可以运输配件到
洛杉矶的配送中心去。而且，当洛杉矶配送中心出现库存短缺时，西雅图
的配送中心有能力供应配件给洛杉矶配送中心的客户。
受到这一点的启发，卡尔为解决当前洛杉矶存货短缺的问题开发了一
个更好的方案。他决定与其仅仅使得从斯图加特的工厂到洛杉矶配送中心
的运输量最大，不如使得两个工厂到洛杉矶和西雅图这两个配送中心的运
输量最大。
图2显示的网络模型代表扩展后的配送网络。这个经过扩展的网络包
括了两个工厂和两个配送中心。除了图1的节点以外，节点BE代表了
位于柏林的较小的工厂，节点HA和节点BN分别代表为这家工厂提供
服务的汉堡和波士顿别外两大港口。SE代表了西雅图。和以前一样，弧
代表了运输路线，每一条弧下方括号里的数字代表了该弧的容量，即下个
一、某工厂生产甲乙两种产品，需A、B二种原料，其有关数据如表所示：
页脚内容3
月可以通过这条运输路线的最大运输单位数。
将经过扩展的BMZ问题看作是最大流问题的网络模型。重新求解，
得到改善的最大流分配方案如表2所示。最大流量为220单位。其中，运
送到洛杉矶的单位数由150增长到160，另外的新加60单位到西雅
图作为洛杉矶库存短缺的备份，这个方案不但解决了洛杉矶的危机，而且
也使卡尔赢得了高层管理的称赞。
表2改善的最大流分配方案
出发点目的地运输量
斯图加特鹿特丹
60
斯图加特波尔图
10
斯图加特里斯本
50
鹿特丹纽约
70
波尔图纽约
30
波尔图新奥尔良
30
里斯本新奥尔良
30
纽约洛杉矶
60
新奥尔良洛杉矶
30
问题
（1）标号法求解最大流问题时，如何获得初始可行流？
（2）对于图2所示的扩展的网络模型，是否满足最大流问题对网络图的要求？
应如何处理？
S
R
B
L
N
N
L
5
7
4
6
0
4
5
3
8
0
7
图2扩展的网络模型
B
H
B
S
2
6
3
4
2
4
10