运筹学网络分析

运筹学网络分析第四章图论与网络分析第一节图的基本概念及图的模型第二节图论和网络分析中常用的名词第三节路径问题第四节最小生成树问题第五节最短路问题第六节最大流问题第七节最小费用流问题第八节中国邮递员问题第九节网络计划技术第一节图的基本概念

及图的模型

哥尼斯堡七桥问题哈密顿圈问题几个图的模型例子例4-1：化工品的贮存问题现要求贮藏8种化工品A，B，C，D，P，R，S，T。出于安全的原因，下面各组产品不能放在一起：A-R，A-C，A-T，R-P，P-S，S-T，T-B，B-D，D-C，R-S，R-B，P-D，S-C，S-D。问题：贮藏这8种化工品至少需要多少间贮藏室？例4-1的图模型例4-1的解方案1：ABS，TCP，DR方案2：DRT，ABS，CP例4-2：考试课表安排问题现有10名研究生要参加总计为六门课程的期末考试，每位研究生要考的课程数和门类是不同的，如下表4-1所示请你排一个考试课表，要求满足下列三个条件：（1）全部考试要在三天内完成；（2）每天上午和下午只能安排一门考试；（3）对每位研究生，一天只能安排一门考试。例4-2的图模型例4-2的解因此考试课表是：第一天AE，第二天BC，第三DF。例4-3：农夫，狼、羊、草过河问题有位农夫，携带一匹狼、一支羊和一挑草要过一条小河。河中只有一条小船，一次摆渡农夫只能携带一样东西（一匹狼或一支羊或一挑草）。当农夫不在场时，狼要吃羊，羊要吃草。试问：农夫怎样才能将这三样东西摆渡到对岸?至少要摆渡几次？四个对象可能形成的组合情况1、[M、W、S、G][Φ]2、[M、W][S、G]x3、[M,S][W、G]4、[M、G][W、S]x5、[M、W、S][G]6、[M、W、G][S]7、[W、S、G][M]x8、[M、S、G][W]农夫摆渡狼、羊、草过河的模型图

摆渡的最优方案用观察法不难发现这样的路线有两条即：V1—V7—V4—V10—V3—V9—V2—V1V1—V7—V4—V8—V5—V9—V2—V1。如何用图论的方法找到这条路线将会在第三节介绍。第一节网络分析中常用名词图子图和生成子图网络图链、路、圈和回路连通图简单图一、图：无向图有向图二、子图与生成子图三、网络图各边赋予一定的物理量，例如距离，则叫做网络图。所赋予的物理量叫做权。权可以是：距离、时间、成本、容量等四、链、路、圈、回路初等链：顶点和边相互交替出现的点不重复序列。路：在有向图中，方向和链的走向一致的链。圈：起点和终点相同的链叫做圈。回路：起点和终点相同的路叫做回路。五、连通图和简单图连通图：在图中，任意两点之间都有一条链相连，叫做连通图。否则是非连通图。非连通图可以由几个连通图构成。环、多重边简单图：没有环和多重边的图是简单图。不连通图六、图的矩阵表示法1、图和网络的相邻矩阵X（G）图G的相邻矩阵X（G）为一个P×P的方阵X（G）=[xij]xij为方阵中的元素

2、有向图的矩阵表示法设有向图D=[V,A]，V={v1,v2…vp}A={a1,a2…aq}则矩阵B（D）={bij}

3、边的顶点表示法对于有向图，任一边a均可用其关联的两顶点vivj表示。a={vivj}，有向图D即是这些边的集合。把这些边按节点编号组装起来就是一个图的模型。如图4-10，它的边集合是（v1v3,v2v1,v2v3,v2v4,v3v4,v4v1,）对于无向图，每一条边均可以用2条具有相同顶点，但方向相反的两条边表示。

第三节路径问题1、什么是路径问题图中的路径问题，是指在一个由顶点和弧构成的有向图中，是否存在一条从vi点到vj点通路。2、路径问题的解法原理设有向图D的相邻矩阵为B（D）={bij}，因此，bikbkj=1代表在vivj之间存在一条经过两条边的路径。而代表vivj之间存在经过两条边路径的数目。依上面的推理，代表vivj之间存在经过3条边的路径数目。一般式对于具有n个顶点的相邻矩阵B（D）=（bij）可以写出下面的一般形式

代表vivj之间存在经过n条边的路径数目。图4-11图4-11中从V1-V6经过两条边的路径

路径的跟踪方法为了找到路径，要在各级矩阵中不等于0的位置上记录到该点的路径轨迹。如从B(2)矩阵中的第3项不为0得知v1→v3存在一条经过两条边的路径v1→v2→v3。下面计算B(3)由B(3)矩阵的第一行可知v1→v4和v1→v6各有一条经过3条边的路径。

第二节最小生成树什么是树？构造生成树的方法最小生成树问题寻找最小生成树的方法一、什么是树？树：不含圈的连通图树的基本性质任意两点之间有且只有一条链若树有p个顶点，则共有q=p-1条边若图是连通的，且q=p-1，则该图不含圈，因此是树若图不含圈，且q=p-1，则该图联通，因此是树。二、构造生成树的方法破圈法避圈法避圈法三、最小生成树最小生成树的定义最小生成树的定理最小生成树的数学模型四、寻找最小生成树的方法Kruskal方法破圈法矩阵计算法Kruskal方法矩阵计算方法T矩阵计算方法TT矩阵计算方法TTT矩阵计算方法TTTT矩阵计算方法TTTTT矩阵计算方法TTTTTT矩阵计算结果什么是最短路问题？求解最短路问题的基本思路Dijstra（荷兰人）算法：标号法Ford（美国人）算法：修正标号法寻找最短路径的方法：双标号第三节最短路问题一、什么是最短路问题？在连通图中，寻找一条从始点到终点的路，该路的权之和最小。图4-8最短路图例二、求解最短路问题的基本思路使用线性规划的解法，但不能利用最短路问题的特点，使解法更有效。利用动态规划的思路，即对于在始点到终点的总体最短路径上的任意一点，从始点到该点的最短路在总体最短路径上。根据上述第二点，可以用标号法求解。三、Dijkstra算法对每个节点，用两种标号：T和P，表示从始点到该节电的距离，P是最短距离，T是目前路径的距离。通过不断改进T值，当其最小时，将其改为P表好。开始时，令始点有P=0，的P标号，其它节点有T=M。图4-8的最短路1图4-8的最短路2图4-8的最短路3图4-8的最短路4图4-8的最短路5图4-8的最短路6四、Ford算法Dijkstra算法不适用于负权网络具有负权的网络，应当用Ford算法又叫修正标号法修正标号法的特点是：不但最小T标号应当改为P标号，P标号也可以修改，修改后的P标号再次改为T表好。Ford算法算例五、寻找最短路径的方法使用双标号网络流的基本概念求解网络最大流的基本原理寻找网络最大流的标号法确定网络中最大流的方法第四节最大流问题一、网络流的基本概念流量与容量可行流：节点和边的限制条件饱和弧和非饱和弧正向弧和反向弧增广链：对于一可行流，网络的一条链满足二、求解网络最大流的基本原理数学模型二、求解网络最大流的基本原理给出一初始可行流，例如。寻找增广链，若存在，则通过该增广链调整、增加网络流。若不存在增广链，则网络流不可再增加。求得最大流。定理：可行流f为最大流的充分必要条件是当且仅当网络不存在增广链。三、寻找网络最大流的标号法Ford-Fulkson标号算法，给每个节点以一对标号，第一个标号表示箭尾节点，第二个标号表示可调整量，若终点有了标号，则找到一条增广链。否则不存在增广链。调整过程：在增广链上，正向弧加上调整量，反向弧减去调整量。经过调整网络流v(f)增加一个调整量：例4-2：第一次迭代第二次迭代第三次迭代：最优解四、确定网络中最大流的方法最大流时始节点的净流出量最大流时中介点的净流入量最小割集的容量割集割集容量最小割集最小割集最大流定理标号法求得最小割集一个简单的例子再看例4-2习题P.266，习题4，图9-5（1）、（2）。什么是最小费用流问题？求解最小费用流的赋权图法求解最小费用流的复合标号法第五节最小费用流问题一、什么是最小费用流给定网络N=(V,A,c,b)和经过网络的流量v，求流在网络上的最佳分布，使总费用最小。二、求解最小费用流的赋权图法增广链费用，最小费用增广链。对于最小费用可行流，沿最小费用增广链调整流，可使流增加，并保持流费用最小。给定初始最小费用可行流，求最小费用增广链，若存在，则沿该增广链调整网络流，直到达到给定的网络流或不存在增广链为止，后一种情况为最小费用最大流。若给定网络流超过最大流，则不可能实现。如何求最小费用增广链？生成最小费用可行流的剩余网络：将饱和弧反向将非饱和非零流弧加一反向弧零流弧不变所有正向弧的权为该弧的费用，反向弧的权为该弧费用的相反数剩余网络又叫长度网络，本教材叫做赋权图。最小费用增广链对应剩余网络的最短路最小费用流的实例第一次剩余网络最短路第一次调整网络流第二次剩余网络最短路第二次调整网络流第三次剩余网络的最短路第三次调整网络流剩余网络已不存在最短路已获最小费用最大流最小费用最大流若规定网络流为7，则第二次调整量应为2，而不是3。见图。最小费用与网络流的关系是凸的，即随着流的增加，单位流的费用在增加。请见下页的图。三、求解最小费用流的复合标号法将求最短路的标号法和求最大流的标号法相结合，即在求增广链的标号后加上一个距离标号，成为一组三标号，距离标号应采用修正标号法。并采用T标号和P标号的记法。下面以前例为例来说明符合标号的应用。第一次迭代第二次迭代第三次迭代最后结果提示思考最短路问题、最大流问题可以看作最小费用流的特殊情况，请分析如何将最小费用流问题特化成最短路问题和最大流问题？运输问题和指派问题可以用最小费用流问题建模，请将它们化为最小费用流问题。习题P.267，习题7、8。第六节中国邮递员问题哥尼斯堡七桥问题与欧拉图中国邮递员问题求解中国邮递员问题的奇偶点图作业法奇偶点图作业法的改进方法一、哥尼斯堡七桥问题与欧拉图哥尼斯堡七桥问题欧拉图与一笔画问题二、中国邮递员问题1962年，管梅谷先生提出中国邮递员问题若图中无奇点，欧拉圈即为所求若图中有奇点，则奇点必为偶数，在奇点间加边（重复走），使其变为偶数而成欧拉图。中国邮递员问题是要求所加边的权之和最小。三、求解中国邮递员问题的奇偶点图作业法在奇点间加边，构造初始可行方案。寻找改进可行方案：在两奇点间检查所有链，若某链的长度小于已加重复边的长度，则在该链的每边加上重复边，去掉原重复边。重复以上步骤，直到任意两奇点间加重复边的链是最短的为止。求解中国邮递员问题：例子例子的初始可行解例子的修正解四、奇偶点作业法的改进方法奇偶点作业法的瓶颈是需检查太多的链。可以首先求出任意一对奇点之间的最短路，从中选出总路长最小的组合方案。也可以由奇点构成偶图，求最小匹配得到最优解。一个四奇点的例子习题P.267，习题9P.268，习题10：图9-10(A)、(B)4.7网络计划技术网络计划技术的基本概念网络图的绘制网络图的时间参数计算网络优化一、网络计划技术的基本概念工程计划与甘特图不易表现工程全貌不便于对各项工作的安排进行筹划和推敲不能识别影响进度的关键工作不能反映一项工作不能按进度完成时对工程进度的影响计划评审技术(PERT)与关键路线法(CPM)系统性和协调性动态性和可控性科学性甘特图前甘特图的网络图二、网络图的绘制网络图的构成作业（工作、工序、活动），箭头表示，箭头之上表示工作名称，之下表示工作时间。可有虚工作。事项，节点表示，表示某个工作的结束和另一工作的开始。一个基建项目网络图二、网络图的绘制从开始节点到结束节点的一条路经叫做路线一个网络图的有多条路线，每条路线有一个总时间总时间最长的路线叫做关键路线，关键路线的总时间叫做工期看下面的例子网络图的路线以上网络图共有8条路线可以计算出这8条路线的总时间，最长的是16天。关键路线是当某些工作的时间调整后，可能引起关键路线的变化和工期的变化。例如将工作E的时间缩短为4天，则工期缩短为13天，关键路线将变为1346BEG5651356BFH553网络图的画法作业的串联作业的并联网络图的画法作业的交叉作业的合并绘制网络图的基本原则两事项间只能有一项作业改为绘制网络图的基本原则网络图应从左向右延伸，编号应从小到大，且不重复。箭头事项编号大于箭尾事项编号网络图只能一个开始节点，一个终止节点不能出现循环路线尽量少交叉，采用暗桥；有层次性。使用暗桥网络图的绘制步骤确定目标，做好准备工作任务分解和分析绘制网络图表4-1调查项目的任务分解和分析绘制作业图的方法试探性绘制法计算机辅助绘制法流程图过渡绘制法试探性绘制法：试探试探性绘制法：修改流程图过渡绘制法：流程图流程图过渡绘制法：加事项流程图过渡绘制法：去方框流程图过渡绘制法：修改三、网络图时间参数计算作业时间的确定事项时间参数的计算作业时间参数的计算关键路线的寻找方法按期完成计划的概率作业时间的确定对具有标准的作业，采用单一时间估计法对一般性作业，采用三点时间估计法最乐观时间：a最可能时间：m最悲观时间：b计算时间期望值和方差作业时间计算方法事项参数的计算事项最早时间事项最迟时间ii图上计算法矩阵法计算事项时间作业时间参数的计算作业开始最早时间作业结束最早时间作业开始最迟时间作业结束最迟时间总时差单时差作业最早时间作业最迟时间时差总时差单时差时差之间的关系表4-3作业时间参数计算关键路线的确定方法总时差为零的作业即是关键作业，关键作业构成关键路线破圈法也可采用最长路线法。按期完成计划的概率每项作业的时间是一个随机变量，近似服从分布，均质和标准差为工期也是一个随机变量，它的期望值为各关键作业时间期望之和。按期完成计划的概率当作业数足够多时，工期近似服从正态分布按期完成计划的概率其中按期完成的概率图