Copyright 2011 © 北京工商大学商学院 18
转运问题
Newark港和Jacksonville港接受到进口到美国 的汽车分别为200辆和300辆。 B城，G城，Y城，R城和M城的经销商分别需 要100辆，60辆，170辆、80辆和70辆汽车。 根据各个城市间的运输费用确定成本最小的 运送汽车的方式。
Copyright 2011 © 北京工商大学商学院 17
净流量=流入量-流出量
对每一个节点有一个约束，必须遵循“流量 守恒规则”
最小成本网络流中 将流量守恒规则应用于每个节点
总供给>总需求
总供给<总需求 总供给=总需求
流入量-流出量>=供给或需求
流入量-流出量<=供给或需求 流入量-流出量=供给或需求
Copyright 2011 © 北京工商大学商学院 12
最小费用流问题的假设
5. 网络中有足够的弧提供足够的容
量，使得所有在供应点中产生的 流都能够达到需求点 6. 在流的单位成本已知的前提下， 通过每一条弧的流的成本和流量 成正比
7. 最小费用流问题的目标是在满足给定
需求的条件下，使得通过网络供应的 总成本最小[或通过这样做使得总利润 最大化]
Copyright 2011 © 北京工商大学商学院 27
纸浆生产问题提取纸浆数据
再生过程1 原料 每吨成本 产出结果 再生过程2 每吨成本 产出结果
报纸
混合纸
13
11
90%
80%
12
13
85%
85%
白色办 公纸 纸板
9
13
95%
75%
10
14
90%
85%
Copyright 2011 © 北京工商大学商学院 28
Copyright 2011 © 北京工商大学商学院 13
最小费用流问题的特征 具有可行解的特征：在以上假设下，当且 仅当供应点所提供的流量总和等于需求点 所需要的流量总和时，最小费用流问题有 可行解
具有整数解的特征：只要其所有的供应、 需求和弧的容量都是整数值，那么任何 最小费用流问题的可行解就一定有所有 流量都是整数的最优解
3. 如果节点产生的净流量[流出减去流入]
是一个确定的正数的话，这个节点就 是供应点 4. 如果节点产生的净流量是一个确定的 负数的话，那么这个节点就称为需求 点
Copyright 2011 © 北京工商大学商学院 10
最小费用流问题的术语
5. 如果节点产生的净流量恒为零，那么这个
节点就称为转运点，我们把流出节点的量 等于流入节点的量称为流量守恒
最终纸浆产出结果
新闻用纸 过程1 过程2 5 6 95% 90% 包装用纸 6 8 90% 95% 打印纸 8 7 90% 95% 纸浆来源 每吨成本 产出 每吨成本 产出 每吨成本 产出
如果有70吨报纸，50吨混合纸，30吨白色办公纸 和40吨纸板。 如何转化成60吨新闻用纸纸浆，40吨包装用纸纸 浆，50吨打印纸纸浆，成本最低。 使用供给为负，需求为正的方法
Copyright 2011 © 北京工商大学商学院 14
电子表格描述
Copyright 2011 © 北京工商大学商学院 15
SUMIF 函数
SUMIF公式可以简化节点流约束 SUMIF(Range A, x, Range B) 区域A中的每一个量满足条件x时，SUMIF函 数就会计算区域B中相应内容之和 节点x的净流出[流出-流入]就等于 SUMIF(“From labels”, x, “Flow”) – SUMIF(“To labels”, x, “Flow”)
Copyright 2011 © 北京工商大学商学院 22
供给为正、需求为负时的电子表格模型
Copyright 2011 © 北京工商大学商学院 23
供给为负、需求为正的电子表格模型
Copyright 2011 © 北京工商大学商学院 24
分析最优解
Copyright 2011 © 北京工商大学商学院 25
卡车司机至多可以从工厂运输50 个单位到配送中心，然后可以从 配送中心运输50个单位到仓库
Copyright 2011 © 北京工商大学商学院 4
配送网络
Copyright 2011 © 北京工商大学商学院 5
配送网络的数据
Copyright 2011 © 北京工商大学商学院 6
最小费用流问题的网络模型
最大流问题的应用
1. 通过配送网络的流量最大，如BMZ问题 2. 通过从供应商到处理设施的公司供应网络的流 量最大 3. 通过管道运输系统运送的油量最大 4. 最大化通过输水系统的水量 5. 通过交通网络的车流量最大
Copyright 2011 © 北京工商大学商学院 48
网络流与整数解
使用单纯形法求解具有约束的右侧值是整数 的任何最小成本的网络流模型，最优解自动 取整。 但是如果加入了副约束，这样不服从流量守 恒规则，就不能保证问题的线性规划模型的 解是整数。
广义网络流问题
目前所考虑的网络流问题，从一条弧线出 来的流量与进入的流量一定是相等的。 事实上是这种情况吗？
Copyright 2011 © 北京工商大学商学院 26
Coal Bank Hollow 再生公司
该公司使用两种不同的再生过程来将报纸、 混合纸、白色办公纸和纸板转化为纸浆。 从再生原料提出再生纸浆的数量和纸浆的 提取成本由于使用不同的再生过程而不同。 通过两种不同的再生过程产生的纸浆通过 其他处理转化为新闻用纸、包装用纸或高 质量打印纸。 两种处理过程的具体数据如下
Copyright 2011 © 北京工商大学商学院 43
BMZ 公司具有多个供应点和需求点的案例 BMZ公司在柏林还有一家更小的工厂 一旦洛杉矶配送中心出现缺货，位于西雅 图的配送中心就可以给有关的客户供应配 件
Copyright 2011 © 北京工商大学商学院 44
扩展的BMZ问题的网络模型
Copyright 2011 © 北京工商大学商学院 41
最大流问题的假设
4. 最大流问题的目标是使得从源到收点 的总流量最大。这个流量的大小可以 用两种等价的方法来衡量，分别叫作 从源点出发的流量和进入收点的流量
Copyright 2011 © 北京工商大学商学院 42
最大流问题和最小费用流问题区别 最小费用流问题：供应点、需 求点 最大流问题：源、收点 最小费用流问题的供应量和需 求量都是固定的，而最大流问 题的源和收点却不是 最小费用流问题的供应点和需 求点可能有多个，但最大流问 题的源和收点只有一个
6. 网络中的箭头称为弧
7. 允许通过某一条弧的最大流量称为该
弧的容量
Copyright 2011 © 北京工商大学商学院 11
最小费用流问题的假设
1. 至少有一个节点是供应点 2. 至少有一个节点是需求点 3. 所有剩下的节点都是转运点
4. 通过弧的流只允许沿着箭头的方向
流动，通过弧的最大流量取决于该 弧的容量[如果流是双向的话，则需 要用一对箭头指向相反的弧来表示]
必须加入虚节点或虚弧线
Copyright 2011 © 北京工商大学商学院 51
特殊建模的考虑
0 100 1 30
$0
L.B.= -50 $0 L.B.=
3
5
-75
100
2
40 0
4
6
-50
-60
如果要求进入节点3的流量至少为50，进入节点4 的流量至少为60，如何建模？
Copyright 2011 © 北京工商大学商学院 45
扩展的BMZ问题
通过每一条运送路线 应该运送多少配件， 才能使从斯图加特和 柏林到洛杉矶和西雅 图的总流量最大？
Copyright 2011 © 北京工商大学商学院 46
电子表格描述
Copyright 2011 © 北京工商大学商学院 47
Copyright 2011 © 北京工商大学商学院 19
净流量=流出量-流入量
Copyright 2011 © 北京工商大学商学院 20
净流量等于流入量-流出量
Copyright 2011 © 北京工商大学商学院 21
请在电子表格里分别按照供给为正和供给 为负的情况，建立两种情况下的模型，并 求解比较
当不确定总供给和总需求的关系时，假设 供给大于需求 如果没有可行解，再更改为需求大于供给
Copyright 2011 © 北京工商大学商学院 33
最小费用流问题的应用
1. 通过配送网络的费用最小 2. 现金流管理 3. 工厂协调产品组合
Copyright 2011 © 北京工商大学商学院 34
BMZ公司的最大流问题 BMZ公司是欧洲一家生产豪华汽车的制 造商，其产品出口到美国尤为重要 BMZ公司的汽车尤其在加利福尼亚大受 欢迎，因此保持洛杉矶中心零部件的充 足供给，以便及时维修这些汽车就显得 特别重要了
Copyright 2011 © 北京工商大学商学院 7
无限配送公司的问题
每条路线应该运送多少 单位的产品？
Copyright 2011 © 北京工商大学商学院 8
最优解
Copyright 2011 © 北京工商大学商学院 9
最小费用流问题的术语
1. 所有最小费用流问题都是用带有通
过其中的流的网络表示的 2. 网络中的圆圈被称为节点
Copyright 2011 © 北京工商大学商学院 35
BMZ公司的最大流问题 BMZ公司需要迅速执行一项计划，下个月要 从位于斯图加特和德国的主要工厂运送尽可 能多的配件到洛杉矶的配送中心 配件运送数量的限制因素就是公司配送网络 的容量
Copyright 2011 © 北京工商大学商学院 36
Copyright 2011 © 北京工商大学商学院 49