网络优化模型PPT学习课件.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,管 理 运 筹 学,1,运筹与优化模型,大连海事大学,刘巍,2,第七章 网络优化模型,绪：图论的起源：,从哥尼斯堡七桥问题,及,哈密顿周游世界游戏,谈起,3,哥尼斯,堡,七桥问題,(,Bridges of Koenigsberg,),能不能走过每一个桥,刚,好一次并且回到原來的地方？,4,解决七桥问题的欧拉,欧拉（,Leonard Euler;1707,1783,），瑞士人，出身于牧师家庭，,13,岁考入大学，,16,岁已经获得硕士学位。,1727,年到俄国圣彼得科学院工作。,1741,年转到德国，任柏林科学院物理数学所所长。,1766,年回到俄国，直至去世。他在,1735,年，由于过度工作的关系，引至右眼失明。,1771,年又因眼疾引致左眼失明。,1783,年逝世于俄国的圣彼得堡。,著作有无穷微量分析入门，无穷小分析引论（,1748,），微分学原理（,1755,），关于曲面上曲线的研究（,1766,），积分学原理（,1768-1770,），方程的积分法研究,等。,欧拉是数学史上最多产的数学家，我们现在习以为常的数学符号很多都是欧拉所发明介绍的，例如：函数符号,f(x),、圆周率,、自然对数的底,e,、求和符号,、,log x,、,sinx,、,cosx,以及虚数单位,i,等，论著涉及的范围非常之广泛，他的成就对后世数学发展有深远的影响。,5,解,决,七,桥问题,的方法,欧拉解决问题问题的第一步把问题抽象化。他想到：岛的形状、大小及桥的长短并不影响结果，位置才是重点。他把四大块陆地缩成四个点，而把七座桥变成七条线，于是，就画出了如此之图形。,6,欧拉路径,解決哥尼斯,堡,七桥问題,原來是一,笔画问题,啊！,数学,家,欧拉,(Euler,1707-1783),于,1736,年,严格的证明了上述,哥尼斯堡,七桥问题无解,，,并且,由此,开创,了,图论,的典型,思维,方式及,论证,方式,7,一,笔画,定理,终于,，,1736,年，,欧,拉,证实,了自己的猜想,七,桥问题,的走法根本不存在。,并发表,了他的一,笔画,定理：一,个图,形要能一,笔画,完成,必须,符合,两个状况,：,图,形是封,闭连,通的。,图,形中的奇,点个数为,0,或,2,。,七,桥问题,中的四,个点,全部都是奇,点,，所以,无,法一次走完七座,桥,。,8,哈密頓（,Hamilton,）周遊世界问題,正十二面,体,有二十个顶点,表示世界上,20,个城市,各经每个城市一次,最后,返回原地,投影至平面,9,实际生活中的图论,Graph Model,10,电路模拟,例：,Pspice,、,Cadence,、,ADS.,Pspice,Cadence,11,交通网络,航空网络,!,捷運路線图！,12,有向道路图,有,单,行道的街道！,行程表！,13,某学校网络架构图,计算机网络,14,走迷宫与,深度优先搜索,(Depth-First Search),老鼠走迷宮,深度优先搜索,一直往前走,碰壁就回,头,換条路找,沿途要,记录,下走过的,路线,15,第,1,节,图论,的基本概念和术语,16,什么是图？,一堆顶点和边的组合！,Set of vertices connected pairwise by edges.,例一,例二,17,图论的,术语,顶点,(Vertex),边,(Edge),一个图,G=(V,E),V:,顶点的集合,E:,边的集合,例：如右图,V=a,b,c,d,e,E=(a,b),(a,c),(a,d),(b,e),(c,d),(c,e),(d,e),18,图的表示法,v,1,v,2,v,3,v,4,v,5,9,7,6,5,4,8,3,2,4,A=,a,ij,=,w,ij,(v,j,v,j,)E,0,其它,0 9 2 4 7,9 0 3 4 0,2 3 0 8 5,4 4 8 0 6,7 0 5 6 0,权矩阵,令所有权为,1,A=,0 1 1 1 1,1 0 1 1 0,1 1 0 1 1,1 1 1 0 1,1 0 1 1 0,邻接矩阵,19,图的表示,A=,0 1 1 0 0 0,0 0 1 0 0 0,0 1 0 0 1 0,0 1 0 0 0 1,0 1 0 1 0 1,0 0 0 0 1 0,v,1,v,2,v,3,v,4,v,5,v,6,其邻接矩阵为：,20,再來一些,术语,连通图,(connected graph),子图,(subgraph),树,(,tree),沒有,回路,的,连通图,森林,(forest),一堆,树的集合,21,树,Trees,树,(tree):,连通无简单回路无向图,若有,n,个顶点,，則有,n-1,条边,任,两点之间仅有一条路径,生成,树,(spanning tree):,包括图中所有的,顶点,，,并且是一棵树,A connected graph G,Spanning trees of G,tree,22,树,实例：,行政,组织,图,23,生成树,(Spanning Tree),生成树,包括图中所有的顶点，并且是一棵树,24,有向图,(Digraph),有向图,(Digraph),有向且无简单回路的图,(,directed acyclic graph,),25,加权图,(Weighted Graph),图片來源：雷欽隆老師“資料結構”課投影片,26,一些特殊的图,27,完,全图,Complete graphs,任意,两点之间,都有一,条边与其,相,连,的,图称为,完,全图,，以,K,n,來表示，,n,为顶点数,28,二分,图,（偶图）,Bipartite graphs,A graph that can be decomposed into two partite sets but not fewer is,bipartite,It is a,complete bipartite,if its vertices can be divided into two non-empty groups,A and B.Each vertex in A is connected to B,and vice-versa,Complete bipartite graph K,2,3,The graph is bipartite,29,平面图,P,lanar graphs,A planar graph is a graph that can be embedded in a plane so that no edges intersect,Planar:,=,NOT Planar:,30,更多,平面,图实例,31,第,2,节,最短路径问題,(Shortest Path Problem),最快航線,最快的,routing,32,最短路问题算法,标号法,最短路问题：对一个赋权的有向图,D,中的指定的两个点,V,s,和,V,t,找到一条从,V,s,到,V,t,的路，使得这条路上所有弧的权数的总和最小，这条路被称之为从,V,s,到,V,t,的最短路。这条路上所有弧的权数的总和被称为从,V,s,到,V,t,的距离。,一、求解最短路的,Dijkstra,算法,(,双标号法）,步骤：,1.,给出点,V,1,以标号,(0,s),2.,找出已标号的点的集合,I,，没标号的点的集合,J,以及弧的集合,3.,如果上述弧的集合是空集，则计算结束。如果,v,t,已标号（,l,t,k,t,），则,v,s,到,v,t,的距离为,l,t,，而从,v,s,到,v,t,的最短路径，则可以从,k,t,反向追踪到起点,v,s,而得到。如果,v,t,未标号，则可以断言不存在从,v,s,到,v,t,的有向路。如果上述的弧的集合不是空集，则转下一步。,4.,对上述弧的集合中的每一条弧，计算,s,ij,=l,i,+c,ij,。在所有的,s,ij,中，找到其值为最小的弧。不妨设此弧为（,V,c,V,d,），则给此弧的终点以双标号（,s,cd,c,）,返回步骤,2,。,33,最短路,算法,DijKstra,算法,例：从油田铺设管道，把原油从,A,地,运到,G,地，要求管道必须按照图中,给定的道路铺设，问如何铺设,煤气管道，使的需要铺设管道,的长度最短,A,G,B,C,D,E,F,5,2,2,4,1,3,8,2,6,5,5,3,2,5,2,5,4,4,6,5,5,10,5,10,1,4,2,7,5,1,3,2,6,A,B,D,F,E,C,1,4,2,7,5,1,3,2,6,0,1,4,1,4,2,7,5,1,3,2,6,0,1,8,6,3,1,4,2,7,5,1,3,2,6,0,1,8,4,3,1,4,2,7,5,1,3,2,6,0,1,7,10,4,3,1,4,2,7,5,1,3,2,6,0,1,7,9,4,3,34,最短路问题,例,1,电信公司准备在甲、乙两地沿路架设一条光缆线，问如何架设使其光缆线路最短？下图给出了甲乙两地间的交通图。权数表示两地间公路的长度（单位：公里）。,解：用标号法求解,V,1,（甲地）,15,17,6,2,4,4,4,3,10,6,5,v,2,V,7,（乙地）,v,3,v,4,v,5,v,6,35,最短路问题,例,1,最终解得：,最短路径,v,1,v,3,v,5,v,6,v,7,，每点的标号见下图,（,0,s,）,V,1,（甲地）,15,17,6,2,4,4,3,10,6,5,(13,3),v,2,(22,6),V,7,（乙地）,V,5,(14,3),V,6,(16,5),V,3,(10,1),V,4,(18,5),36,最短路问题的一个应用模型,例,32,设备更新问题。某公司使用一台设备，在每年年初，公司就要决定是购买新的设备还是继续使用旧设备。如果购置新设备，就要支付一定的购置费，当然新设备的维修费用就低。如果继续使用旧设备，可以省去购置费，但维修费用就高了。请设计一个五年之内的更新设备的计划，使得五年内购置费用和维修费用总的支付费用最小。,已知：设备每年年初的价格表,设备维修费如下表,年份,1,2,3,4,5,年初价格,11,11,12,12,13,使用年数,0-1,1-2,2-3,3-4,4-5,每年维修费用,5,6,8,11,18,37,最短路问题,例,3,的解：,将问题转化为最短路问题，如下图：,用,v,i,表示“第,i,年年初购进一台新设备”,弧（,v,i,v,j,）表示第,i,年年初购进的,设备一直使用到第,j,年年初。,把所有弧的权数计算如下表：,v,1,v,2,v,3,v,4,v,5,v,6,1,2,3,4,5,6,1,16,22,30,41,59,2,16,22,30,41,3,17,23,31,4,17,23,5,18,6,38,最短路问题,(,继上页,),把权数赋到图中，再用,Dijkstra,算法求最短路。,最终得到下图，可知，,v,1,到,v,6,的距离是,53,，最短路径有两条：,v,1,v,3,v,6,和,v,1,v,4,v,6,v,1,v,2,v,3,v,4,v,5,v,6,16,22,30,41,59,16,22,30,41,31,23,17,18,17,23,V,1,（,0,s,）,v,3,v,4,(41,1),v,5,v,6,22,30,41,59,16,(22,1),30,41,31,23,17,18,17,23,V,2,（,16,1,）,16,(30,1),(53,3),(53,4),39,第,3,节最小生成树问题,树是图论中的重要概念，所谓树就是一个无圈的连通图。,图,11-11,中，,(a),就是一个树，而,(b),因为图中有圈所以就不是树，,(c),因为不连通所以也不是树。,图,11-11,v,1,v,2,v,3,v,4,v,5,v,6,v,7,v,8,v,9,v,1,v,2,v,3,v,5,v,8,v,7,v,6,v,4,v,1,v,2,v,3,v,4,v,5,v,7,v,6,v,8,v,9,(a),(b),(c),40,最小生成树问题,给了一个无向图,G=(V,E),，我们保留,G,的所有点，而删掉部分,G,的边或者说保留一部分,G,的边，所获得的图,G,，称之为,G,的生成子图。在图,11-12,中，,(b),和,(c),都是,(a),的生成子图。,如果图,G,的一个生成子图还是一个树，则称这个生成子图为生成树，在图,11-12,中，,(c),就是,(a),的生成树。,最小生成树问题就是指在一个赋权的连通的无向图,G,中找出一个生成树，并使得这个生成树的所有边的权数之和为最小。,图,11-12,(a),(b),(c),41,最小生成树问题,一、求解最小生成树的破圈算法,算法的步骤：,1,、在给定的赋权的连通图上任找一个圈。,2,、在所找的圈中去掉一个权数最大的边（如果有两条或两条以上的边都是权数最大的边，则任意去掉其中一条）。,3,、如果所余下的图已不包含圈，则计算结束，所余下的图即为最小生成树，否则返回第,1,步。,42,最小生成树,算法,避圈法（,Kruskal,）,6,4,4,5,8,4,3,5,5,7,2,5,6,v,s,6,4,4,5,8,4,3,5,5,7,2,5,6,破圈法（,Kruskal,）,A,B,F,G,E,C,D,例：从某供气站要向,A,、,B,、,C,、,D,E,、,F,、,G,小区供气，问如何铺设,煤气管道，使的需要铺设管道,的总长度最短,43,最小生成树问题,例,4,用破圈算法求图（,a,）中的一个最小生成树,v,1,3,3,1,7,2,8,5,4,10,3,4,v,7,v,6,v,5,v,4,v,2,v,1,3,3,1,7,2,8,5,4,3,4,v,7,v,6,v,5,v,4,v,2,v,1,3,3,7,2,5,4,3,4,v,7,v,6,v,5,v,4,v,2,v,3,v,3,v,3,1,v,1,3,3,7,2,4,3,4,v,7,v,6,v,5,v,4,v,2,v,3,1,v,1,3,3,7,2,3,4,v,7,v,6,v,5,v,4,v,2,v,3,1,v,1,3,3,7,2,3,v,7,v,6,v,5,v,4,v,2,v,3,1,(a),(b),(c),(d),(e),(f),图,11-13,44,最小生成树问题,例,5,、某大学准备对其所属的,7,个学院办公室计算机联网，这个网络的可能联通的途径如下图，图中,v,1,v,7,表示,7,个学院办公室，请设计一个网络能联通,7,个学院办公室，并使总的线路长度为最短。,解：此问题实际上是求图,11-14,的最小生成树，这在例,4,中已经求得，也即按照图,11-13,的,(f),设计，可使此网络的总的线路长度为最短，为,19,百米。,v,1,3,3,1,7,2,8,5,4,10,3,4,v,7,v,6,v,5,v,4,v,2,v,3,图,11-14,45,第,4,节最大流问题,最大流问题：给一个带收发点的网络，其每条弧的赋权称之为容量，在不超过每条弧的容量的前提下，求出从发点到收点的最大流量。,一、最大流的数学模型,例,6,某石油公司拥有一个管道网络，使用这个网络可以把石油从采地运送到一些销售点，这个网络的一部分如下图所示。由于管道的直径的变化，它的各段管道（,v,i,v,j,）的流量,c,ij,（容量）也是不一样的。,c,ij,的单位为万加仑,/,小时。如果使用这个网络系统从采地,v,1,向销地,v,7,运送石油，问每小时能运送多少加仑石油？,v,5,6,3,5,2,2,2,4,1,2,6,3,v,1,v,2,v,7,v,4,v,3,v,6,图,11-26,46,4,最大流问题,我们可以为此例题建立线性规划数学模型：,设弧,(v,i,v,j,),上流量为,f,ij,，网络上的总的流量为,F,，则有：,47,4,最大流问题,在这个线性规划模型中，其约束条件中的前,6,个方程表示了网络中的流量必须满足守恒条件，发点的流出量必须等于收点的总流入量；其余的点称之为中间点，它的总流入量必须等于总流出量。其后面几个约束条件表示对每一条弧,(v,i,v,j,),的流量,f,ij,要满足流量的可行条件，应小于等于弧,(v,i,v,j,),的容量,c,ij,，并大于等于零，即,0,f,ij,c,ij,。我们把满足守恒条件及流量可行条件的一组网络流,f,ij,称之为可行流，（即线性规划的可行解），可行流中一组流量最大（也即发出点总流出量最大）的称之为最大流（即线性规划的最优解）。,我们把例,6,的数据代入以上线性规划模型，用,“,管理运筹学软件,”,，马上得到以下的结果：,f,12,=5,，,f,14,=5,，,f,23,=2,，,f,25,=3,，,f,43,=2,，,f,46,=1,，,f,47,=2,，,f,35,=2,，,f,36,=2,，,f,57,=5,，,f,67,=3,。最优值（最大流量）,=10,。,48,4,最大流问题,二、最大流问题网络图论的解法 对网络上弧的容量的表示作改进。为省去弧的方向，如下图,:(a),和,(b),、,(c),和,(d),的意义相同。,用以上方法对例,6,的图的容量标号作改进，得下图,v,i,v,j,v,i,v,j,c,ij,0,（,a,）,（,b,）,c,ij,c,ij,v,i,v,j,（,c,ji,）,（,c,）,v,i,v,j,c,ij,c,ji,（,d,）,6,3,5,2,2,2,4,1,2,6,3,v,1,v,2,v,5,v,7,v,4,v,3,v,6,0,0,0,0,0,0,0,0,0,0,0,49,4,最大流问题,求最大流的基本算法,（,1,）找出一条从发点到收点的路，在这条路上的每一条弧顺流方向的容量都大于零。如果不存在这样的路，则已经求得最大流。,（,2,）找出这条路上各条弧的最小的顺流的容量,p,f,，通过这条路增加网络的流量,p,f,。,（,3,）在这条路上，减少每一条弧的顺流容量,p,f,，同时增加这些弧的逆流容量,p,f,，返回步骤（,1,）。,用此方法对例,6,求解：,第一次迭代：选择路为,v,1,v,4,v,7,。弧（,v,4,v,7,）的顺流容量为,2,，,决定了,p,f,=2,，改进的网络流量图如下图：,6,3,5,2,2,2,4,1,2,6,3,v,1,v,2,v,5,v,7,v,4,v,3,v,6,0,0,0,0,0,0,0,0,0,0,0,4,2,0,2,50,4,最大流问题,第二次迭代：选择路为,v,1,v,2,v,5,v,7,。弧（,v,2,v,5,）的顺流容量为,3,，决定了,p,f,=3,，改进的网络流量图如下图：,第三次迭代：选择路为,v,1,v,4,v,6,v,7,。弧（,v,4,v,6,）的顺流容量为,1,，决定了,p,f,=1,，改进的网络流量图如下图：,6,3,5,2,2,2,4,1,3,v,1,v,2,v,5,v,7,v,4,v,3,v,6,0,0,0,0,0,0,0,0,4,2,0,2,2,0,3,3,3,0,3,2,2,2,4,1,3,v,1,v,2,v,5,v,7,v,4,v,3,v,6,0,0,0,0,0,0,4,2,0,2,2,0,3,3,3,3,3,0,1,3,51,第四次迭代：选择路为,v,1,v,4,v,3,v,6,v,7,。弧（,v,3,v,6,）的顺流容,量为,2,，决定了,p,f,=2,，改进的网络流量图如下图：,第五次迭代：选择路为,v,1,v,2,v,3,v,5,v,7,。弧（,v,2,v,3,）的顺流容,量为,2,，决定了,p,f,=2,，改进的网络流量图如下图：,2,2,2,4,3,v,1,v,2,v,5,v,7,v,4,v,3,v,6,1,0,0,0,0,1,2,0,3,2,0,3,3,3,5,0,3,1,2,0,0,2,3,1,3,2,2,v,1,v,2,v,5,v,7,v,4,v,3,v,6,1,0,1,2,0,2,0,3,3,3,5,0,1,2,0,2,3,1,3,1,5,0,0,2,0,2,0,5,4,最大流问题,52,经过第五次迭代后在图中已经找不到从发点到收点的一条路，路上的每一条弧顺流容量都大于零，运算停止。得到最大流量为,10,。,最大流量图如下图：,2,2,v,1,v,2,v,5,v,7,v,4,v,3,v,6,1,2,3,5,2,2,3,5,5,4,最大流问题,“,管理运筹学软件”中还有专门的子程序用于解决最大流问题。,53,第,5,节最小费用最大流问题,最小费用最大流问题：给了一个带收发点的网络，对每一条弧,（,v,i,v,j,），除了给出容量,c,ij,外，还给出了这条弧的单位流量的费用,b,ij,，要,求一个最大流,F,，并使得总运送费用最小。,一、最小费用最大流的数学模型,例,7,由于输油管道的长短不一，所以在例,6,中每段管道（,v,i,v,j,）除,了有不同的流量限制,c,ij,外，还有不同的单位流量的费用,b,ij,，,c,ij,的单位为万,加仑,/,小时，,b,ij,的单位为百元,/,万加仑。如图。从采地,v,1,向销地,v,7,运送石,油，怎样运送才能运送最多的石油并使得总的运送费用最小？求出最大流,量和最小费用。,(6,6),(3,4),(5,7),(2,5),(2,4),（,2,3,）,(4,4),(1,3),(2,8),（,3,2,）,v,1,v,2,v,5,v,7,v,4,v,3,v,6,(6,3),54,5,最小费用最大流问题,这个最小费用最大流问题也是一个线性规划的问题。,解：我们用线性规划来求解此题，可以分两步走。,第一步，先求出此网络图中的最大流量,F,，这已在例,6,中建立了线性规划的模型，通过管理运筹学软件已经获得结果。,第二步，在最大流量,F,的所有解中，找出一个最小费用的解，我们来建立第二步中的线性规划模型如下：,仍然设弧（,v,i,v,j,）上的流量为,f,ij,，这时已知网络中最大流量为,F,，只要在例,6,的约束条件上，再加上总流量必须等于,F,的约束条件：,f,12,=f,14,=F,即得此线性规划的约束条件，此线性规划的目标函数显然是求其流量的最小费用 。,由此得到线性规划模型如下：,55,5,最小费用最大流问题,56,5,最小费用最大流问题,用管理运筹学软件，可求得如下结果：,f,12,=4,f,14,=6,f,25,=3,f,23,=1,f,43,=3,F,57,=5,f,36,=2,f,46,=1,f,47,=2,f,67,=3,f,35,=2,。其最优值,(,最小费用,)=145,。对照前面例,6,的结果，可对最小费用最大流的概念有一个深刻的理解。,如果我们把例,7,的问题改为：每小时运送,6,万加仑的石油从采地,v,1,到销地,v,7,最小费用是多少？应怎样运送？这就变成了一个最小费用流的问题。一般来说，所谓最小费用流的问题就是：在给定了收点和发点并对每条弧,(v,i,v,j,),赋权以容量,c,ij,及单位费用,b,ij,的网络中，求一个给定值,f,的流量的最小费用，这个给定值,f,的流量应小于等于最大流量,F,，否则无解。求最小费用流的问题的线性规划的模型只要把最小费用最大流模型中的约束条件中的发点流量,F,改为,f,即可。在例,6,中只要把,f,12,+f,14,=F,改为,f,12,+f,14,=f=6,得到了最小费用流的线性规划的模型了。,57,5,最小费用最大流问题,二、最小费用最大流的网络图论解法,对网络上弧（,v,i,v,j,）的（,c,ij,b,ij,）的表示作如下改动，用,(b),来表示,(a),。,用上述方法对例,7,中的图形进行改进，得图如下页：,v,i,v,j,v,i,v,j,（,c,ij,b,ij,）,（,0,-b,ij,）,（,a,）,（,b,）,（,c,ij,b,ij,）,（,c,ij,b,ij,）,v,i,v,j,（,c,ji,b,ji,）,（,c,ij,b,ij,）,v,i,v,j,（,c,ji,b,ji,）,（,0,-b,ji,),（,0,-b,ji,),（,c,）,（,d,）,58,5,最小费用最大流问题,求最小费用最大流的基本算法,在对弧的标号作了改进的网络图上求最小费用最大流的基本算法与求,最大流的基本算法完全一样，不同的只是在步骤（,1,）中要选择一条总的,单位费用最小的路，而不是包含边数最小的路。,(6,6),(3,4),(5,7),(2,5),(0,-4),（,2,3,）,(4,4),(1,3),(2,8),（,3,2,）,v,1,v,2,v,5,v,7,v,4,v,3,v,6,(6,3),(0,-3),(0,-8),(0,-3),（,0,-2,）,(0,-6),(0,-4),(0,-5),（,2,4,）,(0,-7),(0,-4),（,0,-3,）,图,11-28,59,5,最小费用最大流问题,用上述方法对例,7,求解：,第一次迭代：找到最短路,v,1,v,4,v,6,v,7,。,第一次迭代后总流量为,1,，总,费用,10,。,v,5,(6,6),(3,4),(5,7),(2,5),(0,-4),（,2,3,）,(3,4),(0,3),(2,8),（,3,2,）,v,1,v,2,v,7,v,4,v,3,v,6,(5,3),(1,-3),(0,-8),(1,-3),（,0,-2,）,(0,-6),(0,-4),(0,-5),（,2,4,）,(0,-7),(1,-4),（,0,-3,）,图,11-29,60,5,最小费用最大流问题,第二次迭代：找到最短路,v,1,v,4,v,7,。,第二次迭代后总流量为,3,，总费用,32,。,(6,6),(3,4),(5,7),(2,5),(0,-4),（,2,3,）,(3,4),(0,3),(0,8),（,3,2,）,v,1,v,2,v,5,v,7,v,4,v,3,v,6,(3,3),(3,-3),(2,-8),(1,-3),（,0,-2,）,(0,-6),(0,-4),(0,-5),（,2,4,）,(0,-7),(1,-4),（,0,-3,）,图,11-30,61,5,最小费用最大流问题,第三次迭代：找到最短路,v,1,v,4,v,3,v,6,v,7,。,第三次迭代后总流量为,5,，总费用,56,。,(6,6),(3,4),(5,7),(2,5),(0,-4),（,0,3,）,(1,4),(0,3),(0,8),（,1,2,）,v,1,v,2,v,5,v,7,v,4,v,3,v,6,(1,3),(5,-3),(2,-8),(1,-3),（,2,-2,）,(0,-6),(0,-4),(0,-5),（,2,4,）,(0,-7),(3,-4),（,2,-3,）,图,11-31,62,5,最小费用最大流问题,第四次迭代：找到最短路,v,1,v,4,v,3,v,5,v,7,。,第四次迭代后总流量为,6,，总费用,72,。,(6,6),(3,4),(4,7),(2,5),(1,-4),（,0,3,）,(1,4),(0,3),(0,8),（,0,2,）,v,1,v,2,v,5,v,7,v,4,v,3,v,6,(1,3),(6,-3),(2,-8),(1,-3),（,3,-2,）,(0,-6),(0,-4),(0,-5),（,1,4,）,(1,-7),(3,-4),（,2,-3,）,图,11-32,63,5,最小费用最大流问题,第五次迭代：找到最短路,v,1,v,2,v,5,v,7,。,第五次迭代后总流量为,9,，总,费用,123,。,(3,6),(0,4),(1,7),(2,5),(1,-4),（,0,3,）,(1,4),(0,3),(0,8),（,0,2,）,v,1,v,2,v,5,v,7,v,4,v,3,v,6,(0,3),(6,-3),(2,-8),(1,-3),（,3,-2,）,(3,-6),(3,-4),(0,-5),（,1,4,）,(4,-7),(3,-4),（,2,-3,）,图,11-33,64,5,最小费用最大流问题,第六次迭代：找到最短路,v,1,v,2,v,3,v,5,v,7,。,第六次迭代后总流量为,10,，总费用,145,。已经找不到从,v,1,到,v,7,的每条弧容量都大于零的路了，故,已求得最小费用最大流了。,(3,6),(0,4),(1,7),(2,5),(1,-4),（,0,3,）,(1,4),(0,3),(0,8),（,0,2,）,v,1,v,2,v,5,v,7,v,4,v,3,v,6,(0,3),(6,-3),(2,-8),(1,-3),（,3,-2,）,(3,-6),(3,-4),(0,-5),（,1,4,）,(4,-7),(3,-4),（,2,-3,）,图,11-34,65,5,最小费用最大流问题,如果对例,7,求一个最小费用流的问题：每小时运送,6,万加仑石油从,v,1,到,v,7,的最小费用是多少，或者每小时运送,7,万加仑呢？我们可以从第四次迭代及图,11-32,即可得到运送,6,万加仑最小费用,72,百元，其运送方式通过比较图,11-28,及图,11-32,即得图,11-36,所示。,至于每小时运送,7,万加仑，我们可以在图,11-36,的基础上，再按第五次迭代所选的最短路运送,1,万加仑即得最小费用：,72+1*17=89,百元，其运送方式如图,11-37,所示。,3,5,1,2,3,1,2,6,v,1,v,2,v,5,v,4,v,3,v,6,10,3,4,2,v,7,10,第六次迭代后总流量,图,11-35,66,5,最小费用最大流问题,1,2,3,1,2,6,v,1,v,2,v,5,v,4,v,3,v,6,6,3,1,v,7,图,11-36,1,2,1,2,3,1,2,6,v,1,v,2,v,5,v,4,v,3,v,6,3,1,1,v,7,图,11-37,注：,“,管理运筹学软件,”,有专门的子程序用于解决这类问题。,67,第,6,节网络计划技术（关键路径法）,关键路径法包括绘制计划网络图、进度安排、网络优化等环节，下面进行分别讨论：,一、计划网络图,统筹方法的第一步工作就是绘制计划网络图，也就是将工序（或称为,活动）进度表转换为统筹方法的网络图。,例,3,、某公司研制新产品的部分工序与所需时间以及它们之间的相互,关系都显示在其工序进度表如表,12-8,所示，请画出其统筹方法网络图。,表,12-8,工序代号,工序内容,所需时间（天,),紧前工序,a,b,c,d,e,产品设计与工艺设计,外购配套零件,外购生产原料,自制主件,主配可靠性试验,60,15,13,38,8,-,a,a,c,b,d,68,关键路径法,解,:,用网络图表示上述的工序进度表,网络图中的点表示一个事件,是一个或若干个工序的开始或结束,是相,邻工序在时间上的分界点,点用圆圈表示,圆圈里的数字表示点的编号。弧,表示一个工序（或活动），弧的方向是从工序开始指向工序的结束，弧上,是各工序的代号，下面标以完成此工序所需的时间（或资源）等数据，即,为对此弧所赋的权数,a,b,c,d,e,60,13,8,38,15,图,12-4,69,关键路径法,例、把例的工序进度表做一些扩充，如表,12-9,，请画出其统筹方法的网络图。,表,12-9,工序代号,所需时间（天）,紧前工序,工序代号,所需时间（天）,紧前工序,a,b,c,d,60,15,13,38,a,a,c,e,f,g,h,8,10,16,5,b,，,d,d,e,，,70,关键路径法,解：我们把工序扩充到图,12-4,发生了问题，由于是的紧前工序，故的结束应该是的开始，所以代表的弧的起点应该是，由于工序的结束也是，所以工序也成了工序的紧前工序，与题意不符。,为此我们设立虚工序。虚工序是实际上并不存在而虚设的工序，用来表示相邻工序的衔接关系，不需要人力、物力等资源与时间。,1,5,2,6,4,3,a,60,b,15,8,e,10,13,d,c,38,f,图,12-5,71,关键路径法,在网络图上添加、工序得网络图,12-6,。,在统筹方法的网络图中不允许两个点之间多于一条弧，因此增加了一个点和虚工序如图,12-7,。,1,2,5,6,7,3,4,a,60,15,b,e,c,13,d,38,8,h,5,10,f,g,16,图,12-6,72,关键路径法,在绘制统筹方法的网络图时，要注意图中不能有缺口和回路,。,1,2,5,7,8,3,4,a,60,15,b,e,c,13,d,38,8,h,5,10,f,6,16,g,图,12-7,73,关键路径法,二、网络时间与关键路线,在绘制出网络图之后，我们可以由网络图求出：,1,、完成此工程项目所需的最少时间。,2,、每个工序的开始时间与结束时间。,3,、关键路线及其应用的关键工序。,4,、非关键工序在不影响工程的完成时间的前提下，其开始时间与结束时,间可以推迟多久。,例,5,、某公司装配一条新的生产线，具体过程如表,12-10,求：完成此,工程的最少时间，关键路线及相应的关键工序，各工序的最早开始时间和,非关键工序在不影响工程完成时间的前提下，其开始时间与结束时间可以,推迟多久。,74,关键路径法,表,12-10,工序代号,工序内容,所需时间（天）,紧前工序,a,b,c,d,e,f,g,h,i,j,生产线设计,外购零配件,下料、锻件,工装制造,1,木模、铸件,机械加工,1,工装制造,2,机械加工,2,机械加工,3,装配调试,60,45,10,20,40,18,30,15,25,35,/,a,a,a,a,c,d,d,e,g,b,i,f,h,75,关键路径法,解：据表,12-10,绘制网络图如图,12-8,。,图,12-8,如图,12-8,-,就是一条关键路线，我们要干完所有的工序,就必须走完所有这样的路线，由于很多工序可以同时进行，所以网络中最,长的路线就决定了完成整个工程所需的最少时间，这条路线称为关键路,线。,1,2,3,4,6,7,8,5,a,60,b,45,e,c,h,j,35,i,g,10,30,d,20,40,25,f,18,15,76,关键路径法,下面我们给出找关键路线的办法,首先，从网络的发点开始，按顺序计算出每个工序的最早开始时间,（,ES),和最早结束时间（,EF),，设一个工序所需的时间为,t,，这对于同一,个工序来说，有,EF=ES+t,。,工序,a,的最早,开始时间,工序,a,的最早,完成时间,1,1,a0,，,60,60,图,12-9,77,关键路径法,图,12-10,其次,从网络的收点开始计算出在不影响整个工程最早结束时间的情,况下各个工序的最晚开始时间,(,缩写为,LS),和最晚结束时间（缩写为,LF),显然对同一工序有,LS=LF-t,1,2,3,6,7,8,5,a0,60,60,b60,105,45,e60.100,c60,70,h100,115,j135,170,35,i110.135,g80,110,30,d60.80,20,40,25,f70,88,18,4,10,15,78,关键路径法,运用此法则，可以从首点开始计算出每个工序的,LF,与,LS,，如图,12-11,所示。,接着，可以计算出每一个工序的时差，把在不影响工程最早结束时间,的条件下，工序最早开始（或结束）的时间可以推迟的时间，成为该工序,的时差，对每个工序来说其时差记为,T,s,有,T,s,=LS-ES=LF-EF,1,2,3,6,7,8,5,a0,60,600,60,b60,105,4590,135,e60.100,c60,70,h100,115,j135,170,35135,170,i110.135,g80,110,3080,110,d60.80,2060,80,4080,120,25110,135,f70,88,18117,135,4,10107,117,15120,135,79,关键路径法,最后将各工序的时差，以及其他信息构成工序时间表如表,12-11,所,示。,这样就找到了一条由关键工序,a,d,g,i,和,j,依次连接成的从发点到收点的,关键路线。,80,关键路径法,三、网络优化,得到初始的计划方案，但通常要对初始方案进行调整与完善。根据计,划目标，综合考虑