网络计划.pptx

Click to edit Master title style,Click to edit Master text styles,Second level,Third level,Fourth level,Fifth level,11/7/2009,#,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,第四章网络(wnglu)计划,第一页，共76页。,最小生成(shn chn)树(The Minimum Spanning Tree),树(无圈的连通图)是图论中结构(jigu)最简单但十分重要的图.有着广泛的应用.如铁路专用线,管理组织机构,学科分类和一般决策过程往往都可以用树来表示.,树的基本概念:如果无向图是连通的，且不包含圈，则该图为树（Tree）.,第二页，共76页。,最小生成(shn chn)树(The Minimum Spanning Tree),定义 若连通图G的生成子图是一棵树,则称该树为G的生成树(Spanning tree),最小生成树:连通图G的每条边上(bin shn)有非负权W(e)一棵生成树所有树枝上权的总和，称为这可棵生成树的权具有最小权的生成树称为最小生成树,第三页，共76页。,最小生成(shn chn)树的应用,许多网络问题都可归结为最小生成树问题如设计(shj)长度最小的公路网把若干城市相联；设计(shj)用料最省的 线网把有关单位联系起来等,例4-2-1 电信网络的设计(shj),某高科技公司准备铺设先进的光纤网络.为其核心部门提供高速通信.部门位置分布,线路分布及每条线路的铺设成本如下图.请设计(shj)一个网络方案,各部门互通且网络总成本最低.,第四页，共76页。,最小生成(shn chn)树,B,A,E,C,D,F,G,2,2,7,5,4,5,4,1,4,3,1,7,实际上是要确定需要铺设哪些光缆使得(sh de)提供给每两个部门之间的高速通信的总成本最低.这是一个最小生成树问题.,第五页，共76页。,Kruskal算法(sun f),每步从未选的边中选取边e，使它与已选边不构成(guchng)圈，且e是未选边中的最小权边，直到选够n-1条边止这个算法称为避圈法.,B,A,E,C,D,F,G,2,2,7,5,4,5,4,1,4,3,1,7,最低成本(chngbn),=1+1+2+2+3+5,=14,第六页，共76页。,最小生成树问题(wnt)的典型应用,电信网络的设计,低负荷运输网络的设计,使得网络中提供链接的部分(如公路(gngl),铁路等)的总成本最小.,高压输电线路的设计,电器设备线路网络(如数字计算机系统)的设计,使得线路总长度最短.,连接多个场所的管道网络设计.,第七页，共76页。,最短路(dunl)问题(The Shortest Path Problem),最短路问题是网络理论中应用最广泛的问题之一。许多优化问题可以使用这个(zh ge)模型，如设备更新、管道铺设、线路安排等等。,最短路问题的一般描述：设G=(V,E)为连通图，且任意一边(vi,vj)的权为lij,求一条通路，使该通路的权L()=最小。,第八页，共76页。,Dijkstra算法(sun f),目前被认为(rnwi)是求无负权网络最短路问题的最好方法。算法的基本思路：若序列vs,v1,vn-1,vn是从 vs到vn的最短路，则序列vs,v1,vn-1必为从vs到vn-1的最短路。,第九页，共76页。,整数规划(guhu)模型,假设图有n个顶点，现需要从顶点1到顶点n的最短路。设决策变量为xij,当xij=1时，说明边（i,j）在最短路径(ljng)上，否则xij=0.其数学表达式为：,第十页，共76页。,例4-2-2 设备更新问题,某工厂使用一台设备,每年年初工厂都要作出决定,是继续(jx)使用旧的,要付维修费;若购买一台新设备,要付购买费.试制定一个5年的更新计划,使总的支出最少.该设备各年的购买费及不同机器役龄时的残值与维修费见下表.,最短路问题(wnt)的应用,第十一页，共76页。,项目,第,1,年,第,2,年,第,3,年,第,4,年,第,5,年,购买费,11,12,13,14,14,机器役龄,0-1,1-2,2-3,3-4,4-5,维修费,5,6,8,11,18,残值,4,3,2,1,0,最短路(dunl)问题的应用,第十二页，共76页。,11+(5+6+8)-2=28,第一年初购买费11，三年的维修费用5，6，8，减去3年役龄(ylng)机器的残值2。,v1,v2,v3,v4,v5,v6,用点vi表示第i年年初购进一台设备,边(vi,vj)上的数字表示第i年初购进设备用到第j年初.边上的权为使用(shyng)期间的总费用.5年的更新计划最终转化为最短路问题.,第十三页，共76页。,最短路问题(wnt)的求解,v1,v2,v3,v4,v5,v6,1.决策变量xij,若经过经过边vi-vj,则xij=1,否则(fuz)为0.即定义xij为一个0-1变量.,2.目标函数min Z=.cij边vi-vj的权值.,第十四页，共76页。,最短路(dunl)问题的求解,v1,v2,v3,v4,v5,v6,3.约束条件,起点(qdin):有出度无入度,始于该点必有出-入=1.,中间点:有入有出,若过该点必有出-入=0.,终点:有入无出,终于该点必有出-入=-1.,1,0,-1,第十五页，共76页。,最短路(dunl)问题的LINGO 求解,Model:,Sets:,Nodes/v1,v2,v3,v4,v5,v6/;,OnRoute(Nodes,Nodes)/v1,v2 v1,v3 v1,v4 v1,v5 v1,v6 v2,v3 v2,v4 v2,v5 v2,v6 v3,v4 v3,v5 v3,v6 v4,v5 v4,v6 v5,v6/:Cost,x;,Endsets,Data:,Cost=12 19 28 40 59 13 20 29 41 14 21 30 15 22 15;,EndData,N=size(Nodes);,Min=sum(OnRoute:Cost*x);,for(Nodes(i)|i#ne#1#and#i#ne#N:sum(OnRoute(i,j):x(i,j)=sum(OnRoute(j,i):x(j,i);,sum(OnRoute(i,j)|i#eq#1:x(i,j)=1;,sum(OnRoute(i,j)|j#eq#N:x(i,j)=1;,for(OnRoute(i,j):bin(x(i,j);,End,第十六页，共76页。,最短路问题(wnt)的LINGO 求解,第十七页，共76页。,最大流问题(wnt)(Maximal Flow Problem),Vt,Vs,V1,V2,V3,V4,2,1,4,3,4,2,4,2,2,3,3,将左图看作输油管道，Vs,Vt 为起始点和终止点，中间各点为中转站，每条边的权代表该条管道的最大输油能力，问如何安排(npi)各条管道的输油量，才能使从Vs 到Vt的总输油量最大？,第十八页，共76页。,最大流问题(wnt)(Maximal Flow Problem),Vt,Vs,V1,V2,V3,V4,2,1,4,3,4,2,4,2,2,3,3,一般来说，管道的容量有限(yuxin)，实际流量不一定等于容量，问题讨论如何充分地利用装置的能力，以取得最大的流量，这类寻优问题称为最大流问题。,第十九页，共76页。,容量(rngling)网络,Vt,Vs,V1,V2,V3,V4,2,1,4,3,4,2,4,2,2,3,3,任意(rny)一条边上的权Cij0，称为容量.,入度为0的点为发点(f din)（源source）,出度为,0,点为,收点（汇,sink,）,有向连通图,G=,称为,容量网络,。,中间点,(,转运点,),第二十页，共76页。,可行(kxng)流,任意一条边（Vi,Vj）上的流量(liling)为fij,集合f=fij 为网络G上的一个流。,Vt,V4,Vs,V1,V2,V3,2,1,4,3,4,2,4,2,2,3,3,f,12,f,s1,f,2t,W,一个流 f=fij,当fij=Cij，则称流 f 对边(Vi,Vj)是饱和(boh)的，否则称f 对(Vi,Vj)不饱和(boh)。,第二十一页，共76页。,可行(kxng)流,满足下列条件的流 f 为可行流：,(1)容量(rngling)限制条件：0 fij Cij,V4,Vt,Vs,V1,V2,V3,2,1,4,3,4,2,4,2,2,3,3,f,12,f,s1,f,2t,W,第二十二页，共76页。,可行(kxng)流,(2)平衡条件：对于中间点vi,有,收,发点有,W为网络的总流量，从源发出的物资的输入量等于(dngy)汇的输入量。最大流问题就是在容量网络中，寻找流量最大的可行流。,V4,Vt,Vs,V1,V2,V3,2,1,4,3,4,2,4,2,2,3,3,f,12,f,s1,f,2t,W,第二十三页，共76页。,最小割集,边割集,割集(S,S)中所有起点(qdin)在S,终点在S的边的容量之和，称为（S,S)的割集容量，记作C(S,S).如上图C(S,S)=4+2+3=9,C(T,T)=4+3+4=11.容量网络G的割集有多个，容量最小者为G的最小割.,Vt,Vs,V1,V2,V3,V4,2,1,4,3,4,2,4,2,2,3,3,S,Vt,Vs,V1,V2,V3,V4,2,1,4,3,4,2,4,2,2,3,3,S,T,T,第二十四页，共76页。,最大流-最小割定理(dngl),由割集的定义不难看出，在容量网络中割集是由Vs到Vt的必经之路，无论拿掉哪个割集，Vs到Vt便不再相通(xingtng)，所以任何一个可行流的流量不会超过任一割集的容量，也即网络的最大流与最小割满足以下定理。,Vt,Vs,V1,V2,V3,V4,2,1,4,3,4,2,4,2,2,3,3,T,T,Vt,Vs,V1,V2,V3,V4,2,1,4,3,4,2,4,2,2,3,3,T,T,第二十五页，共76页。,最大流-最小割定理(dngl),定理 设 f 为网络(wnglu)G=的任一可行流，流量为W，（S,S）是分离Vs,Vt的任一割集，则有W C(S,S).,最大流-最小割定理,任一个网络G中，从vs到vt的最大流的流量等于(dngy)分离vs,vt的最小割的容量。,第二十六页，共76页。,最大流问题(wnt)(Maximal Flow Problem),最小割的意义，网络从发点到收点的各通路(tngl)中，由容量决定其通过的能力，最小割则是这些路中的咽喉部分（瓶颈），其容量最小，它决定了整个网络的最大通过能力。要提高整个网络的运输能力，必须首先改造这个咽喉部分的通过能力。,第二十七页，共76页。,线性规划求解(qi ji)最大流问题,最大流问题的核心是对可行流进行最大寻优。由可行流的定义可知(k zh)，其容量限制条件及平衡条件为其约束条件，总流量求最大为目标函数，因此可列出对应的线性规划模型。,v,s,v,t,v,1,v,2,v,3,v,4,v,5,v,6,(5,5),(4,2),(3,2),(5,2),(3,3),(3,0),(4,2),(3,3),(5,4),(2,2),(2,2),W,第二十八页，共76页。,线性规划(xin xn u hu)求解最大流问题(LINGO),MODEL:,SETS:,NODES/1.8/;,!边集ARCS,CAP为容量,FLOW为流量;,ARCS(NODES,NODES)/1,2 1,3 1,4 2,5 2,6 3,6,3,7 4,7 5,8,6,8 7,8 8,1/:CAP,FLOW;,ENDSETS,!网络的总流量W=FLOW(8,1);,MAX=FLOW(8,1);,!容量限制约束;,FOR(ARCS(I,J):FLOW(I,J)总交货量，供大于求，增加哑需求dum,转换为平衡问题求解。,.案例设备交货合同问题.xls,费用率,1,2,3,4,dum,生产能力,1,12.0,12.1,12.2,12.3,0,25,2,M,11.0,11.1,11.2,0,35,3,M,M,11.5,11.6,0,30,4,M,M,M,12.5,0,20,交货量,15,20,25,20,30,第七十六页，共76页。,