《IE11OR19 CH6 图与网络分析3 and CH7 网络计划课件》由会员分享，可在线阅读，更多相关《IE11OR19 CH6 图与网络分析3 and CH7 网络计划课件（83页珍藏版）》请在金锄头文库上搜索。
1、第19讲 目录,6.5 最小费用流问题 图与网络分析（小结） CH7 网络计划 7.1 网络图的表示法 7.2 网络时间与关键路线 7.3 网络进度的优化,网络最大流问题(复习),用标号法求最大流考虑费用？,6.5 最小费用流,在网络中实现某一输送任务时,流在网络中的分配不同,所花的代价也不同,如何在完成输送任务的前提下使所花的费用最少,这就是最小费用流问题. 有时除了要求费用少之外,还希望发挥即定网络的最大效能, 即以最低费用流过尽量大的流量, 这就是最小费用最大流问题.,一、基 本 概 念,cij 弧（vi，vj）上的容量 wij 弧（vi，vj）上单位流量的费用（ wij 0）,网络 D
2、=（V，A）,一般说，D中流量为F的网络流不止一个，若 为流量为F的流，且有 则称 为D的流量为F的最小费用流,若F为D的最大流时， 称为D的最小费用最大流,二. 伴随f的费用网络,至多可以再输送 cij - fij= 7-4 = 3 个单位流量 至多可以少输送 fij= 4 个单位流量,（1）点集 Vf = V （2）弧集 ，其中,对D=（V，A），对一可行流f，构造一赋权有向图D（f）,(3) 费率,D（f）：将D中对应流 f有可能增流的弧（正、反向）及其相应的费率构成一个新图，又称为伴随 f 的费用网络。,对（vi，vj） 若 fij = cij，则D（f）中只有反向弧 （ vj ，vi
3、） 若 fij = 0 ，则D（f）只有正向弧（vi，vj）,例：求下图所示网络D的伴随f的费用网络，图中弧旁的数字依次为 cij、fij、wij。,三、最小费用流算法,1. 算法思想 把各条弧上单位流量的费用看成某种长度，用求解最短路问题的方法确定一条自vs到vt的最短路； 再将这条最短路作为可增流链，用求最大流的方法，将其上的流量增至最大可能值； 再重新确定各条弧的单位流量的费用。 如此多次迭代，最终得到最小费用最大流。 注：这里将遇到求解带负权的最短问题。,（1）任意安排一最小费用可行流 （一般取 fij = 0，此时总费用 Z = 0。） （2）构造伴随f的费用网络D（f）； （3）在
4、 D（f）中求 vs 到 vt 的最短路 ，若路长为无 限大，则已求得最小费用最大流，停止。否则，取,2. 算法步骤,（4）调整D上各弧的流量,得到新的最小费用可行流 ，有 f = f + ， Z = Z + ,若要求流量为F的最小费用流，则流量调整量,当 f = F 时，f 即为所求的一个流，终止。,例1：求图中从v1到v5的最小费用最大流，数字为cij，wij,解：给初始可行流为零流，这时f = 0，Z = 0。,D（f（1）， l = 6, =3,f（2）， f=3，Z=18,f（3）, f = 4，Z=24,D（f（2）， l = 6,D（f（3）， l = 7, =1, =1,f（4
5、）， f=5，Z=31,D（f（4），l = 8,D（f（5）) l = 8,f（4）, f=8，Z=55,=1,=3,f（6）， f=9，Z=63,在图D(f（6）)中，不存在从v1到v5的最短路，所以已得到最小费用最大流，如图f（6）所示，最大流为9，最小费用为63。,例P255 例15 求v为10的最小费有流,(容量,单位费用),(单位费用),此时，网络流量为 =510，此流的费用为：,(容量,单位费用),(容量,流量),(容量,流量),(单位费用),此时，网络流量为 =710，此流的费用为：,(容量,单位费用),(容量,流量),(容量,流量),(单位费用),此时，网络流量为 =10，最
6、小费用为：,图与网络分析（小结）,最小生成树(Minimum-Spanning tree problems) 最短路径问题(Shortest path problems) 最大流问题(Maximum flow problems) 最小费用最大流(Minimum-cost network flow problems) (MNCFPS),图与网络分析（小结）,(1)最小生成树(Minimum-Spanning tree problems) 避圈法（Kruskal,1956）、破圈法(管梅谷，1975)。 方法一(破圈法) 任取一个圈，从圈中去掉一条权最大的边。在余下的图中，重复这个步骤，一直到一个
7、不含圈的图为止，这时的图便是最小树。,方法二(避圈法) 开始选一条最小权的边，以后每一步中，总从未被选取的边中选一条权最小的边，并使之与已选取的边不构成圈。,避圈法是一种选边的过程，其步骤如下：,1. 从网络D中任选一点vi，找出与vi相关联的 权最小的边vi，vj，得第二个顶点vj；,2. 把顶点集V分为互补的两部分V1, 1 ，其中,图与网络分析（小结）,(2)最短路径问题(Shortest path problems) 一、Dijkstra算法 （从某一点到其它点的最短路问题） 二、逐次逼近算法 （有负权边的从某一点到其它点的最短路问题） 三、Floyd算法 （任意两点间的最短距离）,三
8、、任意两点间的最短距离,Floyd算法 即矩阵方法 首先建立网络中任意二顶点Vi和Vj间的“条件最短路长”矩阵，即指从Vi到Vj仅考虑可经过某些中间点.由于在达到最后一步之前未考虑经过所有各点的可能性，因而这时求出的最短路长不一定是真正最短路长。 然后设计一种迭代规则，逐步考虑当各个点进入路径时对最短路长的影响，修改条件最短路长矩阵，使其中的元素始终为这时的最短路长。当网络中所有的点均考虑过后，即可得到各点对间真正的最短路长矩阵。,第一步迭代 考虑把顶点V1作为中间点，即将路ViV1Vj 与路 ViVj 的路长进行比较，若前者小于后者，则令新条件最短路长矩阵D1的元素 dij（1）=wi1+w
9、1j，否则，取dij（1）= dij（0）=wij。,第二步迭代在第一步迭代结果的基础上进行，即考虑顶点V2进入线路时最短路长的变化，并以此修改矩阵D1中的元素。 如此继续，当考虑完所有顶点时，最后得到的最短路长矩阵Dp，其中的元素dij（p）即为Vi到Vj的真正最短路长。,设网络中有 p 个顶点。开始时的条件最短路长矩阵 D0=（dij（0）p*p 中的元素dij（0）为Vi到Vj直接距离。,图与网络分析（小结）,(3)最大流问题(Maximum flow problems),图与网络分析（小结）,(4)最小费用最大流(Minimum-cost network flow problems)
10、(MNCFPS) 特例: 运输(transportation)、指派(Assignment)、转运(transhipment)、最大流(maximum flow problems)等问题。,图与网络分析（小结）,例：工厂B1、B2、B3需要从A1、A2、A3供应原料，工厂B2不能缺货，工厂B1和B3缺货要造成损失，单位运价、材料供应量和需求量如下表所示，试确定使总费用最低的原料分配方案。,CH7 网络计划,网络分析方法是五十年代中期发展起来的一种科学计划管理技术，是运筹学的组成部分，也是系统工程中一种重要方法。 网络分析方法在国外称为计划评审技术（PERT）和关键路径法（CPM）国内称为统筹方
11、法。,PERT与CPM的特点： CPM属于肯定型，工作时间采用“一个估计值”（最可能时间），它适用于工程建设项目，它往往兼顾时间和费用两大因素，力求用最低费用去确定工期，在时间和费用两个方面作出决择。 PERT属于非肯定型，工作时间采用“三个估计值”（最乐观时间、最可能时间、最悲观时间）适用于科研项目和一次性计划，它着重考虑时间因素，主要用于控制进度。,一. 传统的工程进度计划图表,1. 甘特图（横道图）,7.1 网络图的表示法,一. 传统的工程进度计划图表,1. 甘特图（横道图）,CPM 关键线路法 Critical Path Method PERT 计划评审技术 Program Evalu
12、ation and Review Technique GERT 图示评审技术 Graphic Evaluation and Review Technique VERT 风险评审技术 Venture Evaluation and Review Technique,华罗庚： 统筹法,网络计划图表是本世纪五十年代末期发展起来的一种工程项目进度计划的新形式和新技术。,二、网络计划图表,三、网络图表示法,工作：至少消耗时间或多数情况下消耗资源的一种活动 事件：工作的开始或结束。 计划项目：工作的集合A和事件的集合E构成的 P=A，E 工作要消耗时间，可看成沿某一方向前进，具有方向性 每一工作需赋时间和各
13、种资源的权， 有向网络。,工作在网络图中有两种表示法： 单代号法 以节点表示工作 双代号法 以弧表示工作,双代号网络图的绘制 （一）绘图的基本规则 1必须正确表达已定的逻辑关系。,双代号网络图中各工作逻辑关系的表示方法 1,D,2网络图中，只能有一个起点节点；在不分期完成任务的网络计划（单目标网络计划）中，应只有一个终点节点；而其他节点均应是中间节点。 3网络图中严禁出现循环回路,4.网络图中不允许出现相同编号的工作,5.不允许出现无开始节点或无完成节点的工作 6.在节点之间，严禁出现带双向箭头或无箭头的连线。,二、双代号网络图的绘制,（二）网络计划的编制（建模）步骤： 1 将任务细化 2 确
14、定工作项目及其关系 3 估计工作的延续时间 4 绘制网络图 5 简化或合并网络图,某机械厂管理信息系统开发活动清单,实例1,1,2,3,4,6,10,9,8,5,7,A 3,B 4,C 6,D 8,E 8,F 5,H 6,G 3,J 5,L 3,K 8,I 3,实例2,某人于早晨7:00起床，按其生活习惯，在其出门工作前，必须完成下列活动: 5分钟时间穿衣服，洗脸4分钟, 10分钟烧开一壶开水, 5分钟取牛奶, 5分钟热牛奶, 5分钟吃饭，试问此人最早何时可以出门上班？假定只有一个炉灶。,7.2 网络时间与关键路线,一、引例,华罗庚 统筹法 某人准备泡茶待客，他需要做: A 取茶具（2分钟）B
15、 洗茶具 （3分钟）C 烧开水 （6分钟),11分钟喝上茶,6分钟喝上茶,C为关键工作，其它工作有一分钟的空闲,3. 烧水的同时用0.5分钟扇火，使水5.5分钟烧开,5.5分钟喝上茶,所有工作皆为关键工作，无空闲时间,6分钟喝上茶,4. 若在烧水的同时用1分钟扇火，使水5分钟烧开,欲缩短工期必须缩短关键工作的延续工作，关键工作和非关键工作是依一定条件而相互转化的。,线路 在网络图中，从起点节点开始，沿箭线方向顺序通过一系列箭线与节点，最后到达终点节点所经过的通路叫线路。, （8天）； （10天）； （9天）； （14天）； （13天）， 共5条线路。,5,第四条线路耗时最长（14天），对整个工程的完工起着决定性的作用，称为关键线路；其余线路均称为非关键线路。处于关键线路上的各项工作称为关键工作。 关键工作完成的快慢将直接影响整个计划工期的实现。关键线路上的箭线常采用粗线、双线或其它颜色的箭线突出表示。 位于非关键线路上的工作除关键工作外，都称为非关键工作，它们都有机动时间(即时差)；非关键工作也不是一成不变的，它可以转化成关键工作；利用非关键工作的机动时间可以科学地、合理地调配资源和对网络计划进行优化。,二、双代号网络计划时间参数的计算,估计活动所需的时间 结点时间的计算 活动时间的计算 时差
