第七章——图论模型

1第七章 图论模型§ 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) 容量限制 对每一条弧(v i,vj) A, 0 fij Cij(2) 平衡条件 (i)对每个中间点 vi A，流入量等于流出量 .（流出 vi） (流入 vi)Av, Av,kiijji ikff）（ ）（(ii) 发点净流出量等于收点净流入量v1 v6v2v3v4v51048535631117图 7.4.12(称为总流量)fVffff Av,tiAv,jtAv,ksAv,sj ittjskjs ）（）（）（）（最大流问题就是求一个可行流 f，使 达到最大.)(fV对可行流 f，若 fij=Cij，则称( vi,vj)为饱和弧 ;对可行流 f，若 fij=0，则称(vi,vj)为零弧; 根据原网络的每条弧变作一条顺向弧和一条逆向弧，且把顺向弧的容量定义为 ，逆向弧的容量定义为 ，这样得到ijijijf ijijfC的网络称为原网络 D=(V,A,C)关于流 f 的增量网络，记为 .),()CAVN例 7.4.1 图 7.4.2(b) 就是图 7.4.2(a) 的一个增量网络.7.4.3 求网络最大流的方法（1） 增量网络与原网络的关系3,05,1 4,14,32,2st1V2Vijcijf24011 1333st1V2V0图 7.4.2(a) (b)网络最大流问题的线性规划模型： , , , , ,max () () .0 (), sj ksjt tiij kisjksjttivAvAvAvAijkivvijijijVffffVftfff（ ） （ ） （ ） （ ）（ ） （ ）3N(f)的顺向弧的数表示原网络对应弧上最大可增加的流量.N(f) 的逆向弧的数表示原网络对应弧上最大可减少的流量.若在 N(f)中能找到从s 到 t 的一条路 P，且每条弧容量为正数，则称 P 为 f 的增广链.令：，则 ，称为增广量.0ijjiij C,)v,(|Cmn 0对原网络的流 f 作如下调整：, (7.4.1)其 它（ ,),(ij ijij jiijijf Pvff则 是新的可行流且 ，若 N(f)中不存在增广f )()()( fVfVf链，则对应的流 f 已是最大流.（2） 步骤以零流 f=0 作初始可行流作增量网络 N(f)寻找增广链 P.若无，则结束 .令 0ijjiij C,P)v,(|Cmn按（7.4.1）式调整流量，得新流 f.转例 7.4.2 求图 7.4.3(a)的网络的最大流, 初始可行流零流 =0, 对应的f增量网络 N(f)如图 7.4.3(b)所示. 寻找得增广链 P:. v1 v2 v3 v4,求得=4.v1v2v3v43,04,05,02,04,0(a)34 0504 0v1v2v3v4020图 7.4.3(b)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.v1v2v3v43,04,45,42,04,4(a) (b)v1v2v3v430 41 40 4002图 7.4.4v1v2v3v43,24,45,22,24,4(a)(b)v1v2v3v410 43 20 4202图 7.4.55§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 道工序构成:AB4 6图 7.5.1BA4 65图 7.5.26A:拆旧厂房;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.1234 5 6ABCDE F图 7.5.3图 7.5.47请注意, 图 7.5.5 的作法是错的.这样画的话,工序 D 也变为工序 G 的紧前工序了,与原题意不符.7.5.2 工序流线图的时间参数设工序流线图中始点编号为 1，终点编号为 n.以下引进几个记号.TE总工期，等于图中终点的最早完工时间，也等于终点的最迟完工时间;工序（i,j）的耗用工时;ijWtE(k)事项 k 的最早时间，即以事项 k 为开工事项的工序的最早可以开工时间，也即它前面全部工序都已完工的时间.递推公式为 (7.5.1)(max)(01ikEiEwtkt图 7.5.5提醒:使用虚工序时尽量避免多个同向相连8如图 7.5.6 所示.若已算得 tE(2)=3, tE(3)=2 又知 w24=2,w34=4 从而按(7.5.1)式算得 tE(4)=max3+2,2+4=6.tL(k)事项 k 的最迟时间，即以事项 k 为完工事项的工序的最迟必须完工时间（以不耽误总工期而言）,递推公式为 (7.5.2)(min)( kjLjL Ewjtkt nT如图 7.5.7 所示.若已算得 tL(8)=5, tL(9)=6 又知 w78=3,w79=2 从而按(7.5.2)式算得 tL(7)=min5-3,6-2=2.tE(1)=0tE(2)=3tE(3)=2tE(4)=6图 7.5.67tL(7)=2tL(8)=5tL(9)=6图 7.5.79R(i,j)-工序（i,j）的总时差（指不误总工期条件下的最大机动时间）.定义 , (7.5.3)(,)()()LEijRijtjtiw如果 ， ，w 45=3, 则 R(i,j)=8-2-3=38)5(Lt24Et若图不太复杂,则时间参数 tE 与 tL 可直接在图上计算, 称为图算法. 把每个事项分为 3 部分，分别表示编号、最早时间和最迟时间,如图 7.5.8.先按编号从小到大计算 tE(k)， 再按编号从大到小算 tL(k); 如图 7.5.9 所示.7.5.3 关键路工序流线图中按箭头方向从始点到终点的一条顺向通道称为路;图7.5.9 中有四条路.路上各工序时间之和称为路长;图中最长的路称为ktE tL图 7.5.8图 7.5.910关键路; 关键路上的工序称为关键工序.注意,每个工序流线图都一定有关键路，关键路的长就是全工程的完工 的总工时; 关键路可能不是唯一的;要想工程提前完工，只有缩短关键工序的工时.故寻找工序流线图的关键路,在工程项目的管理中,有十分重要的作用.我们可以用以下方法确定关键路.由于关键路上的各工序都是不停留地一道紧接一道进行.才能保证不误总工期.从而关键路上各事项必满足 tL(k)=tE(k).故只须把图中全部满足此关系的事项连接起来就得关键路.在图 7.5.9 中, 关键路为，总工期为 41 天.注：一道工序是关键工序的充要条件是总时差为 0.