第四章网络计划精选PPT.ppt

第四章网络计划第1页，此课件共76页哦最小生成树(The Minimum Spanning Tree)树树(无圈的连通图无圈的连通图)是图论中结构最简单是图论中结构最简单但十分重要的图但十分重要的图.有着广泛的应用有着广泛的应用.如铁路如铁路专用线专用线,管理组织机构管理组织机构,学科分类和一般决策学科分类和一般决策过程往往都可以用树来表示过程往往都可以用树来表示.树的基本概念树的基本概念:如果无向图是连通的，且不如果无向图是连通的，且不包含圈，则该图为树（包含圈，则该图为树（TreeTree）.第2页，此课件共76页哦最小生成树(The Minimum Spanning Tree)定义定义 若连通图若连通图G G的生成子图是一棵树的生成子图是一棵树,则则称该树为称该树为G G的生成树的生成树(Spanning tree)最小生成树最小生成树:连通图连通图G G的每条边上有非负的每条边上有非负权权W(e)W(e)一棵生成树所有树枝上权的总和，一棵生成树所有树枝上权的总和，称为这可棵生成树的权具有最小权的生称为这可棵生成树的权具有最小权的生成树称为成树称为最小生成树最小生成树第3页，此课件共76页哦最小生成树的应用许多网络问题都可归结为最小生成树问题如设许多网络问题都可归结为最小生成树问题如设计长度最小的公路网把若干城市相联；设计用料最省计长度最小的公路网把若干城市相联；设计用料最省的电话线网把有关单位联系起来等的电话线网把有关单位联系起来等例例4-2-14-2-1 电信网络的设计电信网络的设计 某高科技公司准备铺设先进的光纤网络某高科技公司准备铺设先进的光纤网络.为其核心为其核心部门提供高速通信部门提供高速通信.部门位置分布部门位置分布,线路分布及每条线路线路分布及每条线路的铺设成本如下图的铺设成本如下图.请设计一个网络方案请设计一个网络方案,各部门互通且各部门互通且网络总成本最低网络总成本最低.第4页，此课件共76页哦最小生成树BAECDFG227545414317 实际上是要确定需要铺设哪些光缆使得提供给每两个部实际上是要确定需要铺设哪些光缆使得提供给每两个部门之间的高速通信的总成本最低门之间的高速通信的总成本最低.这是一个这是一个最小生成树问题最小生成树问题.第5页，此课件共76页哦Kruskal算法 每步从未选的边中选取边每步从未选的边中选取边e e，使它与已选边不构成，使它与已选边不构成圈，且圈，且e e是未选边中的最小权边，直到选够是未选边中的最小权边，直到选够n-1n-1条边止这条边止这个算法称为个算法称为避圈法避圈法.BAECDFG227545414317最低成本最低成本=1+1+2+2+3+5=1+1+2+2+3+5=14=14第6页，此课件共76页哦最小生成树问题的典型应用n电信网络的设计电信网络的设计n低负荷运输网络的设计低负荷运输网络的设计,使得网络中提供链使得网络中提供链接的部分接的部分(如公路如公路,铁路等铁路等)的总成本最小的总成本最小.n高压输电线路的设计高压输电线路的设计n电器设备线路网络电器设备线路网络(如数字计算机系统如数字计算机系统)的设的设计计,使得线路总长度最短使得线路总长度最短.n连接多个场所的管道网络设计连接多个场所的管道网络设计.第7页，此课件共76页哦最短路问题(The Shortest Path Problem)最最短短路路问问题题是是网网络络理理论论中中应应用用最最广广泛泛的的问问题题之之一一。许许多多优优化化问问题题可可以以使使用用这这个个模模型型，如如设设备备更更新新、管管道道铺铺设、线路安排等等。设、线路安排等等。最最短短路路问问题题的的一一般般描描述述：设设G=(V,E)G=(V,E)为为连连通通图图，且且任任意意一一边边(v vi i,v vj j )的的权权为为l lij ij,求求一一条条通通路路，使使该该通通路路的的权权L(L()=)=最小。最小。第8页，此课件共76页哦Dijkstra算法 目前被认为是目前被认为是求无负权网络求无负权网络最短路问题的最短路问题的最好方法。算法的基本思路：若序列最好方法。算法的基本思路：若序列vvs s,v,v1 1,v,vn-1n-1,v,vn n 是从是从 v vs s到到v vn n的最短路，则序列的最短路，则序列v vs s,v v1 1,v,vn-1n-1 必为从必为从v vs s到到v vn-1n-1的最短路。的最短路。第9页，此课件共76页哦整数规划模型n假设图有假设图有n个顶点，现需要从顶点个顶点，现需要从顶点1到顶点到顶点n的最短路。设决策变量为的最短路。设决策变量为xij,当当xij=1时，说时，说明边（明边（i,j）在最短路径上，否则）在最短路径上，否则xij=0.其数其数学表达式为：学表达式为：第10页，此课件共76页哦 例例4-2-2 设备更新问题设备更新问题 某某工工厂厂使使用用一一台台设设备备,每每年年年年初初工工厂厂都都要要作作出出决决定定,是是继继续续使使用用旧旧的的,要要付付维维修修费费;若若购购买买一一台台新新设设备备,要要付付购购买买费费.试试制制定定一一个个5年年的的更更新新计计划划,使使总总的的支支出出最最少少.该该设设备备各各年年的的购购买买费费及及不不同同机机器器役役龄龄时时的的残残值值与与维维修修费见下表费见下表.最短路问题的应用第11页，此课件共76页哦项目项目第第1 1年年第第2 2年年第第3 3年年第第4 4年年第第5 5年年购买费购买费11111212131314141414机器役龄机器役龄0-10-11-21-22-32-33-43-44-54-5维修费维修费5 56 68 811111818残值残值4 43 32 21 10 0最短路问题的应用第12页，此课件共76页哦 11+(5+6+8)-2=28第一年初购买费第一年初购买费1111，三年的维修费用，三年的维修费用5 5，6 6，8 8，减去，减去3 3年役年役龄机器的残值龄机器的残值2 2。v1v2v3v4v5v6 用点用点vivi表示第表示第i i年年初购进一台设备年年初购进一台设备,边边(vi,vj)(vi,vj)上上的数字表示第的数字表示第i i年初购进设备用到第年初购进设备用到第j j年初年初.边上的权为边上的权为使用期间的总费用使用期间的总费用.5.5年的更新计划最终转化为最短路问年的更新计划最终转化为最短路问题题.第13页，此课件共76页哦最短路问题的求解v1v2v3v4v5v61.1.决策变量决策变量x xij ij,若经过经过边若经过经过边vi-vj,vi-vj,则则xij=1,xij=1,否则为否则为0.0.即定即定义义xijxij为一个为一个0-10-1变量变量.2.目标函数目标函数min Z=.cijmin Z=.cij边边vi-vjvi-vj的权值的权值.第14页，此课件共76页哦最短路问题的求解v1v2v3v4v5v63.3.约束条件约束条件起点起点:有出度无入度有出度无入度,始于该点必有始于该点必有出出-入入 =1.=1.中间点中间点:有入有出有入有出,若过该点必有若过该点必有出出-入入 =0.=0.终点终点:有入无出有入无出,终于该点必有终于该点必有出出-入入 =-1.=-1.10-1第15页，此课件共76页哦最短路问题的LINGO LINGO 求解nModel:nSets:nNodes/v1,v2,v3,v4,v5,v6/;nOnRoute(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;nEndsetsnData:nCost=12 19 28 40 59 13 20 29 41 14 21 30 15 22 15;nEndDatanN=size(Nodes);nMin=sum(OnRoute:Cost*x);nfor(Nodes(i)|i#ne#1#and#i#ne#N:sum(OnRoute(i,j):x(i,j)=sum(OnRoute(j,i):x(j,i);nsum(OnRoute(i,j)|i#eq#1:x(i,j)=1;nsum(OnRoute(i,j)|j#eq#N:x(i,j)=1;nfor(OnRoute(i,j):bin(x(i,j);nEnd第16页，此课件共76页哦最短路问题的LINGO LINGO 求解第17页，此课件共76页哦 最大流问题(Maximal Flow Problem)VtVsV1V2V3V421434242233 将左图看作输油管道，将左图看作输油管道，Vs,VtVs,Vt 为为起始点起始点和和终止点终止点，中间各点为中间各点为中转站中转站，每，每条边的权代表该条管条边的权代表该条管道的最大输油能力，道的最大输油能力，问问如何安排各条管道的输如何安排各条管道的输油量，才能使从油量，才能使从Vs Vs 到到VtVt的总输油量最大？的总输油量最大？第18页，此课件共76页哦 最大流问题(Maximal Flow Problem)VtVsV1V2V3V421434242233 一般来说，管道一般来说，管道的容量有限，实际流的容量有限，实际流量不一定等于容量，量不一定等于容量，问题讨论如何充分地问题讨论如何充分地利用装置的能力，以利用装置的能力，以取得最大的流量，这取得最大的流量，这类寻优问题称为类寻优问题称为最大最大流问题。流问题。第19页，此课件共76页哦容量网络 VtVsV1V2V3V421434242233任意一条边上的权任意一条边上的权C Cij ij 0 0，称为，称为容量容量.入度为入度为0 0的点为的点为发发点（源点（源sourcesource）出度为出度为0 0点为点为收点收点（汇（汇sinksink）有向连通图有向连通图 G=G=称为称为容量网络容量网络。中间点中间点(转运点转运点)第20页，此课件共76页哦可行流任意一条边任意一条边（Vi,VjVi,Vj）上的）上的流量为流量为f fij,ij,集合集合f f =f fij ij 为为网络网络GG上的一个流。上的一个流。VtV4VsV1V2V321434242233f12fs1f2tW一一个个流流 f f =f fij ij ,当当f fij ij =C Cij ij，则则称称流流 f f 对对边边 (V(Vi i,V Vj j )是是饱饱和的和的，否则称，否则称f f 对对(Vi,Vj)(Vi,Vj)不饱和不饱和。第21页，此课件共76页哦可行流 满足下列条件的流满足下列条件的流 f f 为可行流：为可行流：(1)(1)容量限制条件：容量限制条件：0 0 f fij ij C Cij ijV4VtVsV1V2V321434242233f12fs1f2tW第22页，此课件共76页哦可行流 (2)平衡条件：对于中间点平衡条件：对于中间点v vi i,有有 收收,发点有发点有 WW为网络的总流量，从源发出的物资的输入量等于为网络的总流量，从源发出的物资的输入量等于汇的输入量。汇的输入量。最大流问题就是在容量网络中，寻找流量最大流问题就是在容量网络中，寻找流量最大的可行流。最大的可行流。V4VtVsV1V2V321434242233f12fs1f2tW第23页，此课件共76页哦最小割集n边割集边割集 割集割集(S,S)(S,S)中所有中所有起点在起点在S,S,终点在终点在SS的边的容量之和，的边的容量之和，称为（称为（S,S)S,S)的的割集容量，记作割集容量，记作C(S,S).C(S,S).如上图如上图C(S,S)=C(S,S)=4+2+3=9,C(T,T)=4+3+4=11.4+2+3=9,C(T,T)=4+3+4=11.容量网络容量网络G G的割集有多的割集有多个，个，容量最小者为容量最小者为G G的最小割的最小割.VtVsV1V2V3V421434242233SVtVsV1V2V3V421434242233STT第24页，此课件共76页哦最大流-最小割定理n由割集的定义不难看出，在容量网络中割集是由由割集的定义不难看出，在容量网络中割集是由VsVs到到VtVt的必经之的必经之路，无论拿掉哪个割集，路，无论拿掉哪个割集，VsVs到到VtVt便不再相通，所以便不再相通，所以任何一个可任何一个可行流的流量不会超过任一割集的容量行流的流量不会超过任一割集的容量，也即网络的最大流与最小，也即网络的最大流与最小割满足以下定理。割满足以下定理。VtVsV1V2V3V421434242233TTVtVsV1V2V3V421434242233TT第25页，此课件共76页哦最大流-最小割定理n定理定理 设设 f f 为网络为网络G=G=的任一可行的任一可行流，流量为流，流量为WW，（S,SS,S）是分离）是分离Vs,VtVs,Vt的的任一割集，任一割集，则有则有W W C(S,S).C(S,S).最大流-最小割定理 任一个网络任一个网络G G中，中，从从v vs s到到v vt t的最大流的流量的最大流的流量等于分离等于分离v vs s,v,vt t的最小割的容量。的最小割的容量。第26页，此课件共76页哦最大流问题(Maximal Flow Problem)n最小割的意义，网络从发点到收点的各通路中，由容量最小割的意义，网络从发点到收点的各通路中，由容量决定其通过的能力，最小割则是这些路中的咽喉部分决定其通过的能力，最小割则是这些路中的咽喉部分（瓶颈），（瓶颈），其容量最小，它决定了整个网络的最大通其容量最小，它决定了整个网络的最大通过能力。过能力。要提高整个网络的运输能力，必须首先改造要提高整个网络的运输能力，必须首先改造这个咽喉部分的通过能力。这个咽喉部分的通过能力。第27页，此课件共76页哦线性规划求解最大流问题 最大流问题的核心是对可行流进行最大寻优。由可行流的定义可最大流问题的核心是对可行流进行最大寻优。由可行流的定义可知，其知，其容量限制条件及平衡条件为其约束条件容量限制条件及平衡条件为其约束条件，总流量求最大为目标函，总流量求最大为目标函数，因此可列出对应的线性规划模型。数，因此可列出对应的线性规划模型。vsvtv1v2v3v4v5v6(5,5)(4,2)(3,2)(5,2)(3,3)(3,0)(4,2)(3,3)(5,4)(2,2)(2,2)W第28页，此课件共76页哦线性规划求解最大流问题(LINGO)nMODEL:nSETS:nNODES/1.8/;n!边集边集ARCS,CAP为容量为容量,FLOW为流量为流量;nARCS(NODES,NODES)/1,2 1,3 1,4 2,5 2,6 3,6n3,7 4,7 5,8,6,8 7,8 8,1/:CAP,FLOW;nENDSETSn!网络的总流量网络的总流量W=FLOW(8,1);nMAX=FLOW(8,1);n!容量限制约束容量限制约束;nFOR(ARCS(I,J):FLOW(I,J)总交货量，供大于求，增加哑需总交货量，供大于求，增加哑需求求dum,dum,转换为平衡问题求解。转换为平衡问题求解。.案例案例 设备交货合同问题设备交货合同问题.xls.xls费用率费用率1234dum生产能生产能力力112.012.112.212.30252M11.011.111.20353MM11.511.60304MMM12.5020交货量交货量1520252030第76页，此课件共76页哦