运筹学第五章-图与网络分析ppt课件.ppt

第5章图与网络分析第章图与网络分析u.基本概念u.最小支撑树问题u.最短路问题u.最大流问题5. 基本概念1.图、子图与简单图u图：由节点和线组成的图形 记为： G = ( V, E ) V=v1,v2,vm节点集,表示研究对象. E=e1,e2,en边集，表示研究对象之间的关系.e1e2e3e5e6e4e7v3v2v1v4e1e2e3e5e6e4e7v3v2v1v4e2e3e5e6e4v3v2v1v4图图u子图：图的一部分，记为u多重边：两节点之间有多于一条边u环：首尾相接的边u简单图：无环、无多重边的图2.有向图与无向图v有向图：有方向的图v无向图：无方向的图 e1V2V1e2V3 v1 e v23.关联与相邻v关联(边与节点的关系):若e是v1、v2两节点间 的边，记e=v1，v2 ，称v1、v2 与e关联v相邻（边与边、节点与节点的关系）： 点v1与v2有公共边，称节点v1与v2相邻； 边e1与e2 有公共节点，称边e1与e2相邻圈 封闭的链称为圈如：=(1,2),(2,4),(3,4),(1,3 链:由图G中的某些相连的边构成的图形（首尾不能相接），称为图G中的一条链 如： =(1,2),(3,2),(3,4)4. 链、圈与连通图42314231连通图 任意两个节点之间至少有一条链的图称为连通图42315.网络图 给图中的节点和边赋以具体的含义和权数（如距离、时间、费用、容量等），则称这样的连通图为网络图。

4231 50 70 20 45v典例:会议日程安排某单位要在今后的三天内召开6个会议,每天上下午各安排一个会议，参加会议的领导如下会议A:朱、马、牛、姬、江、姚会议B:朱、杨、张、江会议C:马、姬、侯、王、姚会议D:朱、姬、张会议E:杨、侯、王会议F:刘、杨、王、江、姚每位领导每天最多只参加一个会议会议A要安排在第一天上午,会议F安排在第三天下午，会议B要安排在任何一天的下午试根据上述要求排出一个会议日程表，使各位领导都能参加相应的会议ABCDEF会议日程安排如下:上午下午第一天会议AE第二天会议CB第三天会议DF解:用节点表示会议，若两个会议能安排在一天，则用连线连接5.2 最小支撑树问题v树：无圈的连通图，记为Tv树的性质243512435124351如果树T有m个节点，则边的个数为m-1 树中任意两个节点间有且只有一条链 在树中任意去掉一条边，则不连通v图的支撑树图G1和G2 的节点相同，但图G1边的集合包含于G2边的集合，且 G1是树图，则 图G1是G2 的支撑树一个图的支撑树不是唯一的图G1图G2v最小支撑树树枝总长最短的支撑树特点：各节点都连通且线路总长最短v最小支撑树的求法1破圈法2避圈法5.2.1 求解最小支撑树问题的破圈法v方法：去边破圈的过程。

v步骤：1）在给定的赋权的连通图上任找 一 个圈 2）在所找的圈中去掉一条权数最 大的边 3）若所余下的图已不含圈，则计 算结束，余下的图即为最小支撑 树，否则返回 1）v例：用破圈法求右图 的最小支撑树V4V2V3V13 7 4 5 8 1V4V2V3V1V1V4V2V3V4V2V3V1V4V2V3V1总权数=3+4+1=85.2.2 求解最小支撑树的避圈法v方法：选边的过程v步骤：1）从网络中任意选一点vi，找出与vi相关联的权最小的边vi,vj，得第二个顶点vj 2）把顶点集V分为互补的两部分A,，其中： A：与已选边相关联的点集 ：不与已选边相关联的点集 3) 考虑所有这样的边vi,vj，其中viA,vj,挑选其中权最小的 4）重复3），直至全部顶点均属于A即可v例：用避圈法求图的最小 支撑树V4V2V3V13 7 4 5 8 1任选点v1，挑与之相关联的权最小的边（ v1,v4）.A= v1,v4,=v2,v3 从边（ v1,v2）,（ v1,v3）, （ v4,v2）, （ v4,v3） 中选权最小的边（ v1,v2）V4V2V3V13 7 4 5 8 1A= v1,v2 ,v4,=v3 从边（ v1,v3）, （ v2,v3）, （ v4,v3） 中选权最小的边（ v2,v3）。

A= v1,v2 , v3， v4l网络的生成树和线性规划的关系网络的一个生成树对应于线性规划的一个基生成树上的边对应于线性规划的基变量生成树的弦对应于线性规划的非基变量生成树的变换对应于线性规划单纯形法的进基和离基变换71425673734243562412破圈法举例避圈法举例1425673734243562412例 校园局域网问题某大学准备把所属个学院办公室的计算机联网这个网络的可能联通的途径如图所示边上权数为这条边的长度，单位为百米试设计一个网络联通个学院办公室，并使总长度为最短v1v4v5v3v7v6v2513724843103v1v4v5v3v7v6v2137233权和例 线网架设问题某个城市之间的道路网如图所示要求沿着已知长度的道路联结个城市的线网，并使线的总长度最短v1v4v2v6v5v3617524453v1v4v2v6v5v312453权和5.3 最短路问题问题：求网络中一定点到其它点的最短路5.3.1 最短路问题的Dijstra解法方法：给vi点标号i,vk 其中：i：vi点到起点vs的最短距离 vk: vi的前接点方法：(1) 给起点vs标号0，vs2）把顶点集v分为互补的两部分A和 其中：A：已标标号点集 ：未标号点集 （3）考虑所有这样的边vi, vj, 其中vi A,vj 挑选其中与vs距离最短的点vj标号 mini+cij,vi(4) 重复（3），直至终点vt标上号t,vk，则 t即为vs至vt的最短距。

反向追踪可求得最短路例：求v1至v8的最短路v2v3v7v1v8v4v5v66134105275934682v2v3v7v1v8v4v5v66134105275934682(1) v1:0,v1计算min0+2,0+1,0+3=min2,1,3=1v4:1.v11,v10,v1(2)A=v1检查边（v1,v2),(v1,v4),(v1,v3)v2v3v7v1v8v4v5v66134105275934682(3)A=v1,v4计算min0+2,0+3,1+10,1+2=min2,3,11,3=2v2:2,v10,v11,v12,v1考虑边（v1,v2),(v1,v6),(v4,v2),(v4,v7)v2v3v7v1v8v4v5v66134105275934682（4）A=v1,v2,v4计算min 0+3, 2+6, 2+5, 1+2 v6:3,v1 =min 3,8,7,3=3 2,v11,v10,v13,v1考虑边（v1,v6),(v2,v3),(v2,v5),(v4,v7)v2v3v7v1v8v4v5v66134105275934682(5)A=V1,V2,V4,V6计算 min 2+6, 2+5, 1+2, 3+4=min 8,7,3,7=3 v7:3,v42，V11，V10，V13，V13,v4考虑边(v2,v3),(v2,v5),(v4,v7),(v6,v7)V2V3V7V1V8V4V5V66134105275934682(6)A=V1,V2,，V4,V6,V7计算min 2+6, 2+5, 3+3, 3+8=min 8,7,6,11=6 v5:6,v72,v11,v10,v13,v13,v46,v7考虑边(v2,v3),(v2,v5),(v7,v5),(v7,v8)v2v3v7v1v8v4v5v66134105275934682(7)A=V1,V2,V4,V6,V7计算min2+6,6+9,6+4,3+8=min8,15,10,11=8v3:8,v22,V11,V10,V13,V13,V46,V78,v2考虑边(v2,v3),(v5,v3),(v5,v8),(v7,v8)v2v3v7v1v8v4v5v66134105275934682(8)A=v1,v2,v3,v4,v6,v7计算min8+6,6+4,3+7=min14,10,11=10v8:10,v52,v11,v10,v13,v13,v46,v78,v210,v5考虑边（v3,v8),(v5,v8),(v7,v8)v2v3v7v1v8v4v5v66134105275934682(9)A=v1,v2,v3,v4,v6,v7,v8v1到v10的最短路径为v1v4v7v5v8，最短路长度为10。

2,v11,v10,v13,v13,v46,v78,v210,v5反向追踪：v8-v5-v7-v4-v1例6 设备更新问题某厂使用一种设备，每年年初设备科需要对该设备的更新与否作出决策五年内：购买新设备-购置费；13，14，16，19，24；使用老设备-维护费8，10，13，18，27问：在5年内如何制定更新计划，以便使新设备购置费和老设备维修费的总费用最小？341245632131323244622489224563473727v1-v3-v6minL=78例7火车调度问题某火车货运调车场，主要调运建筑材料中的黄沙、碎石和水泥该调车场有3个装运点：黄沙装运点、碎石装运点和水泥装运点；另有2个机车挂钩处（挂火车头的地方），即图1中的节点1、2、5和9、10货运火车的各节车厢在一个装运点装货后，必须由调车场的火车头把装好货的车厢拉走，按调车场的铁路网络的某一路线运行到某一机车挂钩处，由那里的火车头把满载的车厢拉走网络图中，各条弧代表铁路线，节点代表铁路交叉口，弧旁的数字代表距离（单位：百米），这里需注意的是，网络图只是描述了各换轨点(即交叉口）、装运点和机车挂钩处之间的关系，并不表示铁路线的实际走向。

调车场的调度室需要解决的问题是：各车厢在某一装运点装好货后应把它拉到哪一个机车挂钩处，而且应走哪一条运行路线最短，从而提高调车场作业的效率，减少装载的车厢等候挂钩时间而尽快拉离调车场分别求出结点1、2、5到结点9和10的最短路径及最小路径值 结果分析黄沙装运点、水泥装运点、碎石装运点到两个机车挂钩处的最短路径及最短路径值，如下 30； 35； 27； 32； - 19； - 245. 最大流问题v2v3v5v4v6v7v1f=0f=0624743793188l问题的一般提法： 有一网络D=(V,A;C) 其中V：点集；A：弧集；C=cij,cij为弧（vi,vj)上的容量 现D上要安排通过一个流f=fij，其中fij为弧(vi,vj)上的流量问题：如何安排流量fij，可使D上通过 的总流量V(f)最大？5.4.1 网络流的基本概念与基本定理(1)弧的容量和流量容量cij，流量fij(2)可行流 a、每一个节点流量平衡b、0fij cij1.弧的容量和流量、可行流jifij=5cij=5jifij=3cij=52.饱和弧、不饱和弧、流量的间隙（i，j）是饱和的(2)如果fij0，弧从j到i的方向是不饱和的；（j，i）是不饱和的间隙为ij=fij=53.可增广链（或可扩充链）网络D中st的链，记为 +：前向弧（与方向一致） -：后向弧（与方向相反） 若链 上的流量满足：所有的前向弧皆未饱和，后向 弧皆非零，则称为D中关于可行流fij的可增广链。

4,2) (3,1) (5,3) (4,1) (3,2)4.截集与截量l截集：将网络图中的起点与终点分开并使流中断的一组正向弧的集合 即将顶点V分为二个非空互补集E和，使s E,t ,称弧集（ E，)= (i,j) | i E,j 为D的截集l截量：截集上的容量之和记为C(E, ).5.流量与截量的关系n任何一个可行流的流量V(f)都不会超过任一截量即V(f) C(E, )n最大流-最小截定理：max V(f) = minC(E, )n判别最大流的条件：可行流f是最大流 D中不存在关于f 的可增广链5.4.2 最大流问题的标号解法步骤：先找一个可行流检验调整算法步骤：1.标号找可增广链（1）给vs标号,vs,选与vs相关联的流出未饱。