数学模型第七章57.doc

第七章 图论模型 § 7.4 网 络 最 大 流 7.4.1引例 如图有一连接某产品的产地v1与销地v6的交通网.每条弧表示运输线路.弧旁的数字表示该运输线的最大通过能力.要求制定一个运输计划使从v1到v6的产品输送量最大.这就是一个网络最大流问题. 7.4.2基本概念 设有一有向图D=(V,A), 发点是指定的起始点 vs∈V; 收点是指定的终止点 vt∈V. 对每一弧(vi,vj)∈A , 规定一个非负数Cij表示流量的上限称为容量; 指定了发点、收点和各弧容量的有向图D称为网络; 所谓网络上的一个流是指定义在弧集A上的一个实函f = {f(vi,vj)}. fij =f(vi,vj) 称为从vi到vj的流量. 若f满足以下2个条件者，则称f为可行流. (1) 容量限制 对每一条弧(vi,vj)∈A, 0≤fij≤Cij (2) 平衡条件 (i)对每个中间点vi∈A，流入量等于流出量. （流出vi） (流入vi) (ii) 发点净流出量等于收点净流入量 (称为总流量) 最大流问题就是求一个可行流f，使达到最大. 对可行流f，若fij=Cij，则称(vi,vj)为饱和弧;对可行流f，若fij=0，则称(vi,vj)为零弧; 根据原网络的每条弧变作一条顺向弧和一条逆向弧，且把顺向弧的容量定义为，逆向弧的容量定义为，这样得到的网络称为原网络D=(V,A,C)关于流f的增量网络，记为. 例7.4.1 图7.4.2(b) 就是图7.4.2(a) 的一个增量网络. 7.4.3求网络最大流的方法 增量网络与原网络的关系 N(f)的顺向弧的数表示原网络对应弧上最大可增加的流量.N(f)的逆向弧的数表示原网络对应弧上最大可减少的流量.若在N(f)中能找到从s到t的一条路P，且每条弧容量为正数，则称P为f的增广路.令：，则，称为增广量. 对原网络的流f作如下调整： , (7.4.1) 则是新的可行流且，若N(f)中不存在增广路，则对应的流f已是最大流. 步骤 ①以零流f=0作初始可行流 ②作增量网络N(f) ③寻找增广路P.若无，则结束. ④令 ⑤按（7.4.1）式调整流量，得新流f. ⑥转② 例 求图7.4.3(a)的网络的最大流, 初始可行流零流=0, 对应的增量网络N(f)如图7.4.3(b)所示. 得增广路P:. v1→v2→v3→v4,求得δ=4. 按(7.4.1)式调整流量，得新可行流f’ ,如图7.4.4(a) 所示, 总流量V(f’)=4,对应的增量网络N(f’)如图7.4.4(b)所示. 找得增广路P:. v1→v3→v2→v4,求得δ=2. 再按（7.4.1）式调整流量，得新可行流f” ,如图7.4.5(a) 所示, 对应的增量网络N(f”如图7.4.5(b)所示.没有增广路, f”已经是最大流, V(f”)=6. 7.4.4应用实例----房产商的推销策略 某房产商现有6套房（用Xi表示）要出售，现来了7个买主（用Yj表示），分别看中了其中若干套房（如图），假设每个买主至多只买1套房，求房产商使销量最大的推销策略。 补充发点S和收点T，定义所有弧的容量都是1，得下图，需要求S到T的最大流。 可用《运筹学》求解网络最大流的软件求解，就得房产商使销量最大的推销策略，下图蓝色粗弧都是饱和弧，其他弧是零弧。 即得房产商最佳的推销策略是： 即极力说服买主Y1去买X1, Y2去买X3, Y3去买X4, Y4去买X2, Y5去买X6. 这样能卖出5套房。（当然，此题最优解是不唯一的） 注：此题也可以转化为指派问题，方法是先虚拟一套房X7，然后定义Cij，若Yi看中了Xj，则Cij=1，否则Cij=0，当然Ci7=0，目标最大化。 应用案例------BMZ公司的最大流问题 1.背景 ???BMZ 公司是欧洲一家生产豪华汽车的制造商。它因为提供优质的服务而获得很好的声誉，保持这个声誉一个很重要的秘诀就是它有着充裕的汽车配件供应，从而能够随时供货给公司众多的经销商和授权维修店。 ??这些供应件主要存放在公司的配送中心里，这样一有需求就可以立即送货。卡尔(BMZ公司的供应链的经理)优先考虑的是改进这些配送中心的不足之处。 ???该公司在美国有几个配送中心。但是，离洛杉机中心最近的一个配送中心却坐落离洛杉机 1000 多英里的西雅图。保证洛杉机中心良好的供应是尤为重要的。因此，现在那里的供应不断减少的现状成为了公司高层管理真正关心的问题。 ??大部分的汽车配件