运筹学-最大流- 案例

案例 BMZ公司的最大流问题

背景

BMZ 公司是欧洲一家生产豪华汽车的制造商。它因为提供优质的服务而获得很好的声誉，保持这个声誉一个很重要的秘诀就是它有着充裕的汽车配件供应，从而能够随时供货给公司众多的经销商合授权维修店。

这些供应件主要存放在公司的配送中心里，这样一有需求就可以立即送货。卡尔（ BMZ 公司的供应链的经理）优先考虑的是改进这些配送中心的不足之处。

该公司在美国有几个配送中心。但是，离洛杉机中心最近的一个配送中心却坐落离洛杉机 1000 多英里的西雅图。保证洛杉机中心良好的供应是尤为重要的。因此，现在那里的供应不断减少的现状成为了公司高层管理真正关心的问题。

大部分的汽车配件以及新车是在该公司坐落于德国的斯图加特的总厂和新车一起生产的。也就是这家工厂向洛杉机中心供应汽车配件。每月有超过 300000 立方英尺的配件需要运到。现在，下个月需要多得多的数量以补充正在减少的库存。

问题

卡尔需要尽快制定一个方案，使得下个月从总厂运送到洛杉机配送中心的供应件尽可能多。他认识到了这是个最大流的问题 —— 一个使得从总厂运送到洛杉机配送中心的配件流最大的问题。因为总厂生产的配件量远远要大于能够运送到配送中心的量，所以，可以运送多少配件的限制条件就是公司配送网络的容量。

这个配送网络如下图1 。在图中，标有 ST 和 LA 的节点分别代表斯图加特的工厂和洛杉机的配送中心。由于工厂所在地有一个铁路运转点，所以首先通过铁路把配件运输到欧洲的三个港口：鹿特丹（ RO ）波尔多（ BO ）和里斯本 (LI) ；然后通过船运到美国的港口纽约（ NY ）或新奥尔良（ NO ）；最后用卡车送到洛杉机的配送中心。

图1 网络模型

经营这些铁路、船舶和卡车的组织是独立所有的公司，这些公司为很多的公司运输货物。由于对这些老主顾原有的承诺，这些公司不可以在短时间内为任何一个客户大量增加运输空间配额。因此，BMZ公司只能够保证获得下个月每条运输航线有限的运输空间。图1已经给出可以获得的空间数量，以100立方米为1个单位（由于每100立方米比3500立方英尺大一点，所以，需要运送的这批货物体积是很大的）。 模型描述和求解

这是一个最大流问题，每一条弧下方括号里的数字代表了该弧的容量。通过标号法求得最大流，在各线路上的运输方案如表1所示。最大流量为150单位。

表1 最大流分配方案

进一步改善的方案

在柏林，即斯图加特的工厂的北面，公司有一家较小一点的工厂也生产汽车配件。虽然通常这家工厂用来协助供应给北欧、加拿大和美国北部地区的配送中心（包括在西雅图的一个），但是它也同样可以运输配件到洛杉矶的配送中心去。而且，当洛杉矶配送中心出现库存短缺时，西雅图的配送中心有能力供应配件给洛杉矶配送中心的客户。

受到这一点的启发，卡尔为解决当前洛杉矶存货短缺的问题开发了一个更好的方案。他决定与其仅仅使得从斯图加特的工厂到洛杉矶配送中心的运输量最大，不如使得两个工厂到洛杉矶和西雅图这两个配送中心的运输量最大。

图2显示的网络模型代表扩展后的配送网络。这个经过扩展的网络包括了两个工厂和两个配送中心。除了图1 的节点以外，节点 BE 代表了位于柏林的较小的工厂，节点 HA 和节点 BN 分别代表为这家工厂提供服务的汉堡和波士顿别外两大港口。SE代表了西雅图。和以前一样，弧代表了运输路线，每一条弧下方括号里的数字代表了该弧的容量，即下个

月可以通过这条运输路线的最大运输单位数。

将经过扩展的 BMZ 问题看作是最大流问题的网络模型。重新求解，得到改善的最大流分配方案如表2所示。最大流量为220单位。其中，运送到洛杉矶的单位数由 150 增长到 160 ，另外的新加 60 单位到西雅图作为洛杉矶库存短缺的备份，这个方案不但解决了洛杉矶的危机，而且也使卡尔赢得了高层管理的称赞。

图2 扩展的网络模型 表2 改善的最大流分配方案

问题

（1）标号法求解最大流问题时，如何获得初始可行流？

（2）对于图2所示的扩展的网络模型，是否满足最大流问题对网络图的要求？应如何处理？