第七章45数学模型.docVIP

第七章 图论模型 § 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.2 求图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.5统筹方法 统筹方法是一种研究如何对工程计划进行合理组织、统筹安排使其发挥最大效益的方法.通常借助工序流线图对各工序的关系进行描述. 7.5.1. 工序流线图 工序流线图是用于描述各工序的逻辑关系与工程进度的一种有向网路图.绘图规则如下： （1）用箭号→表示工序，箭号旁可用数字表示该工序所需时间; （2）用小圆○表示事项（工序开工或完工的时刻）, 箭尾处为开工事项, 箭头处为完工事项; （3）全部事项从小到大进行编号，不得重复; （4）任一工序的开工事项编号小于完工事项编号，如 ⑤→⑧; （5）不同的工序不得使用两个相同的相关事项，如图7.5.1是不允许的; 从而可用（i,j）表示开工事项编号为i, 完工事项编号为j的工序; （6）必要时可使用虚工序（无须实际执行的工序，工时为0）， 用虚箭号 表示，如图7.5.2所示; （7）一个工程只有一个始点与一个终点. 例7.5.1 某工厂改建工程由下列6道工序构成: A:拆旧厂房; B:工程设计; C:采购设备,紧前工序(紧接本工序之前的工序)是B; D:厂房土建, 紧前工序是A与B; E:设备安装, 紧前工序是C与D; F:设备调试, 紧前工序是E. 本工程可用图7.5.3的工序流线图来描述 作工序流线图时我们要小心虚箭号的合理使用,否则容易出错. 例7.5.2 现有一工程： 代号 A B C D E F G H 紧前工序 — A B B B C，D C，E F，G 工序时间 1 3 1 6 2 4 2 4 作出图7.5.4. 请注意, 图7.5.5的作法是错的. 这样画的话,工序D也变为工序G的紧前工序了,与原题意不符. 7.5.2工序流线图的