数学模型第七章457数模型第七章457.doc

PAGE  PAGE 21 第七章 图论模型 § 7.4 网 络 最 大 流 7.4.1引例 v1 v6 v2 v3 v4 v5 10 4 8 5 3 5 6 3 11 17 图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) 的一个增量网络. 3, 0 5,1 4, 1 4,3 2, 2 s t 2 4 0 1 1 1 3 3 3 s t 0 图7.4.2 (a) (b) 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. ⑥转② v1 v2 v3 v4 3,0 4,0 5,0 2,0 4,0 (a) 3 4 0 5 0 4 0 v1 v2 v3 v4 0 2 0 图7.4.3 (b) ??? 求图7.4.3(a)的网络的最大流, 初始可行流零流=0, 对应的增量网络N(f)如图7.4.3(b)所示. 得增广路P:. v1→v2→v3→v4,求得δ=4. v1 v2 v3 v4 3,0 4,4 5,4 2,0 4,4 (a) (b) v1 v2 v3 v4 3 0 4 1 4 0 4 0 0 2 图7.4.4 按(7.4.1)式调整流量，得新可行流f’ ,如图7.4.4(a) 所示, 总流量V(f’)=4,对应的增量网络N(f’)如图7.4.4(b)所示. 找得增广路P:. v1→v3→v2→v4,求得δ=2. v1 v2 v3 v4 3,2 4,4 5,2 2,2 4,4 (a) (b) v1 v2 v3 v4 1 0 4 3 2 0 4 2 0 2 图7.4.5 再按（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套房，求房产商使销量最大的推销策略。 Y1 Y2 Y3 Y4 Y5 Y6 Y7 X1 X2 X3 X4 X5 X6 补充发点S和收点T，定义所有弧的容量都是1，得下图，需要求S到T的最大流。 Y1 Y2 Y3 Y4 Y5 Y6 Y7 X1 X2 X3 X4 X5 X6 S T 可用《运筹学》求解网络最大流的软件求解，就得房产商使销量最大的推销策略，下图蓝色粗弧都是饱和弧，其他弧是零弧。 Y1 Y2 Y3 Y4 Y5 Y6 Y7 X1 X2 X3 X4 X5 X6 S T 即得房产商最佳的推销策略是： 即