数学建模中的图论方法.docx

《数学建模中的图论方法.docx》由会员分享，可在线阅读，更多相关《数学建模中的图论方法.docx（40页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。

1、精品名师归纳总结资料word 精心总结归纳 - - - - - - - - - - - -数学建模中的图论方法一、引言我们知道， 数学建模竞赛中有问题A 和问题 B。一般而言，问题A 是连续系统中的问题，问题B 是离散系统中的问题。由于我们在高校数学训练内容中，连续系统方面的学问的比例较大，而离散数学比例较小。因此很多人有这样的感觉，A 题入手快，而B 题不好下手。另外，在有限元素的离散系统中，相应的数学模型又可以划分为两类，一类是存在有效算法的所谓 P 类问题，即多项式时间内可以解决的问题。但是这类问题在MCM 中特别少见，事实上，由于竞赛是开卷的，参考相关文献，使用现成的算法解决一个P 类

2、问题，不能显示参赛者的建模及解决实际问题才能之大小。仍有一类所谓的NP 问题，这种问题每一个都尚未建立有效的算法，或许 真的就不行能有有效算法来解决。命题往往以这种NPC问题为数学背景，找一个详细的实际模型来考查参赛者。这样增加了建立数学模型的难度。但是这也并不是说无法求解。一般来说，由于问题是详细的实例，我们可以找到特别的解法，或者可以给出一个近似解。图论作为离散数学的一个重要分支，在工程技术、自然科学和经济治理中的很多方面都能供应有力的数学模型来解决实际问题，所以吸引了很多争论人员去争论图论中的方法和算法。应当说，我们对图论中的经典例子或多或少仍是有一些明白的，比如， 哥尼斯堡七桥问题、中

3、国邮递员问题、四色定理等等。图论方法已经成为数学模型中的重要方法。很多难题由于归结为图论问题被奇妙的解决。而且，从历年的数学建模竞赛看，显现图论模型的频率极大，比如：AMCM90B扫雪问题。AMCM91B查找最优Steiner 树。AMCM92B紧急修复系统的研制最小生成树 AMCM94B运算机传输数据的最小时间边染色问题 CMCM93B 足球队排名 特点向量法 CMCM94B 锁具装箱问题最大独立顶点集、最小掩盖等用来证明最优性 CMCM98B 灾情巡察路线最优回路 等等。这里面都直接或是间接用到图论方面的学问。要说明的是，这里图论只是解决问题的一种方法，而不是唯独的方法。本文将从图论的角度

4、来说明如何将一个工程问题转化为合理而且可求解的数学模型，着重介绍图论中的典型算法。这里只是一些基础、简洁的介绍，目的在于明白这方面的学问和应用，拓宽大家的思路，期望起到抛砖引玉的作用，要把握更多仍需要我们进一步的学习和实践。可编辑资料 - - - 欢迎下载精品名师归纳总结学习资料 名师精选 - - - - - - - - - -第 1 页，共 22 页 - - - - - - - - - -可编辑资料 - - - 欢迎下载精品名师归纳总结资料word 精心总结归纳 - - - - - - - - - - - -二、基本概念和性质第一给出图论中的一些基本概念。1一个图 G 由一个 顶点集 V 和

5、一个 边的集 E 组成。E 中每个元素e 是连接顶点集V 中两个顶点 u 和 v 的边，称e 与 u， v 关联。我们规定连接两个顶点u、v 至多有一条边，且一条边的两个顶 点不重合，这种图称为简洁图 。2顶点集为V ，边集为 E 的图 G 通常记为G= （ V ，E）。图 G1=（V 1，E1）称为 G 的子图 ，假如 V 1V ， E1E。3顶点 v 的度或“次” 是指与 v 相关联的边的个数。图G 的度数之和为边数的两倍。4如图 G 中任意两个顶点u、v 之间都存在连接它们的路，称G 为连通图 。5 W=v0e1v1e2ekvk ，其中 eiE，vjV ， ei 与 vi-1 ， vi

6、关联，称W 是图 G 的一条 道路 。v0 是起点， vk 是终点。各边相异的道路叫做行迹，各顶点相异的道路叫做轨道。起点和终点重合的道路为 回路 。起点和终点重合的轨道为圈。包含图中每条边的回路称为Euler 回路 。含 Euler 回路的图称为Euler 图。6一个无圈的连通图称为树。树是最简洁而最重要的一类图。树有以下重要性质：性质：1在树中去掉任意一条边，所得的图是不连通的。2在树中任意两个不相邻的顶点u、v 之间添加一条新的边，所得的图恰有一个圈。下述定理是树的判肯定理：定理： 如图 G 具有以下性质中的两条，就它是树，且也具有第三条性质。1 G 是连通图。2 G 没有圈。3 G 的

7、顶点数 =G 的边数 +1。7假如图G=（ V， E）的子图Gt=（ V t， Et）是一个树，且V t=V ，称 G t 是 G 的 生成树 。G 连通的充要条件是G 有生成树。生成树一般而言数量很大。8设对图G= （ V ， E）的每一条边e 给予一个实数W （ e），称为 e 的权， G 称为 赋权图 加权可编辑资料 - - - 欢迎下载精品名师归纳总结图。假设 G 是连通的赋权图，要找G 的连通子图G *= （ V， E* ），使得 W （G* ）=eW e 为最E可编辑资料 - - - 欢迎下载精品名师归纳总结小。明显G* 应为 G 的一个生成树。G 的权 最小的生成树称为G 的 最

8、小生成树 。三、算法介绍31 最短轨道问题可编辑资料 - - - 欢迎下载精品名师归纳总结学习资料 名师精选 - - - - - - - - - -第 2 页，共 22 页 - - - - - - - - - -可编辑资料 - - - 欢迎下载精品名师归纳总结资料word 精心总结归纳 - - - - - - - - - - - -背景： 给定连接如干城市的铁路网，寻求从指定城市v0 到各城 v 去的最短道路。数学模型： 图 G 为一赋权图，对任给的vVG ，寻求轨道Pv0,v ，使得WPv0,v=minWP,P取自全部v0 到 v 的轨道集合 其中 WP 是轨道 P 上各边权之和。这一问题可

9、用迪克斯特拉Dijkstra 算法解决。基本思想： 从起点v0 开头，逐步查找到达各点的最短路，在每一步都对顶点记录一个数，称之为该点的标号，它表示v0 到该点的最短距离的上界，或就是v0 到该点的最短距离。实际上每一步都通过把至少一个具有T 标号的点变成P 标号 即把一个不是最短距离标号的顶点变成是最短距离标号的顶点 ，这样最多经过|VG|-1 步就可完成。步骤： 记 lv 为 v0 到 v 的距离。1 lv0=0 ， lv =， vv0。 S0=v0 ， i=0 。2 对 vSi，minlv ， lvi+wviv代替 lv 。这样找到点vi 1 使得 lv 取最小值， vi 1Si 的余集

10、 。令 Si 1 Si vi+1。3 i=|VG|-1时停止，否就，i+1 ，转到 2。实例： CMCM94A 大路选址问题。32 求最小生成树1克罗斯克尔 Kruskal 算法 1956 年，俗称“避圈法”背景： 筑路选线问题欲修筑连接n 个城市的铁路，已知i 城与 j 城之间的铁路造价为Cij 。设计一个线路图，使总造价最低。分析： 选线问题的数学模型是在连通加权图上求权最小的连通生成子图。明显，权最小的连通生成子图是一个生成树，即求取连通加权图上的权最小的生成树，这就归结为最小生成树问题。这个问题可由克罗斯克尔Kruskal 算法解决。思路： 从“边”着手选最小生成树。步骤： 设 G 为

11、由 m 个节点组成的连通赋权图。(1) 先把G 中全部的边按权值大小由小到大重新排列，并取权最小的一条边为树T中的边。即选e1E，使得 we1 min 。(2) 从剩下的边中按1 中的排列取下一条边。如该边与前面已取进T 中的边构成一个回路，就舍弃该边，否就也把它取进T 中。如 e1， e2， ei 已经选好，就从E e1 ，e2， ei 中选取 ei 1，使得 Ge1 ， e2， ei， ei+1 中无圈，且wei+1=min 。(3) 重复步骤 2，直到 T 中有 m 1 条边为止。就T 为 G 的最小生成树。可编辑资料 - - - 欢迎下载精品名师归纳总结学习资料 名师精选 - - -

12、- - - - - - -第 3 页，共 22 页 - - - - - - - - - -可编辑资料 - - - 欢迎下载精品名师归纳总结资料word 精心总结归纳 - - - - - - - - - - - -该算法的复杂度为O eloge，其中 e 是图 G 中的边数。2普莱姆 Prim 算法 思路： 从点入手来选边步骤： 1 在图 G 中任取一个节点vi1 ，并放入T 中。2令 S VG/VT ， VG 、VT 分别是 G、T 的节点集。3在全部连接VT 节点与 S 节点的边中，选出权值最小的边u0,v0，即4wu0,v0=minwu,v|uVT, v将边 u0,v0 放入 T 中。S

13、。5重复步骤 2 4 ，直到 G 中节点全部取完。该算法的复杂度为On2 ，其中 n 为图 G 的节点数。31975 年管梅谷提出的“破圈法”33 Steiner生成树实际背景： 在已有网络上挑选连通几个城市的最廉价交通或通讯网。数学模型： 从已知的加权连通图上求取最小的树状子图，使此树包含指定的顶点子集。第一个的边长为3 ，其次个的边长为1，总费用其次个更少。分析： 与传统的最小生成树相比，这里可以引入如干“虚拟站”并构造一个新的Steiner 树，这样可以降低由一组站生成的传统的最小生成树所需的费用降低的费用大致为13.4%。而且为构造一个 有 n 个顶点的网络的费用，最低的Steiner

14、 树决不需要多于n 2个虚设站。当然，有时最小Steiner 生成树与最小生成树相同。寻求最小Steiner 生成树的算法有Melzak 算法 1961 年，但是这是一个指数时间的算法，现在没有多项式时间的算法，换句话说它是一个NP 问题。而且，这里的要求是 用直折线代替欧氏直线距离，因而不能利用直接的算法。所以在解决这样的问题的时候，为削减运算的时间， 理论上的分析是必要的：比如树的长度的下界，Steiner 树的存在性， 虚设站的位置等等。常用的算法仍包括穷举法、模拟退火法等。Melzak 算法： 其基础是 3 点 steiner 树，即 3 点 Fermat 问题的几何作图法。参考2 ，

15、 Page375。模拟退火法原理：模拟退火法 Simulated annealing, SA 是模拟热力学中经典粒子系统的降温过程，来求解极值问题。当孤立粒子系统的温度以足够慢的速度下降时，系统近似处于热力学平稳状态，最终系统将达到本身的最低能量状态，即基态， 这相当于能量函数的全局微小点。其步骤如下 也称可编辑资料 - - - 欢迎下载精品名师归纳总结学习资料 名师精选 - - - - - - - - - -第 4 页，共 22 页 - - - - - - - - - -可编辑资料 - - - 欢迎下载精品名师归纳总结资料word 精心总结归纳 - - - - - - - - - - - -

16、为 Metropolis 过程 ：（ 1） 给定初始温度T0，及初始点，运算该点的函数值fx 。（ 2） 随机产生扰动x，得到新点x=x+，x运算新点函数值fx 及,函数值差f=fx -fx 。（ 3） 如 f ，0就接受新点，作为下一次模拟的初始点。（ 4） 如 f0，就运算新点接受概率：，产生 0，1区间上匀称分布的伪随机数 r,r 0,1，假如 p f ，r就接受新点作为下一次模拟的初始点。 否就舍弃新点，仍取原先的点作为下一次模拟的初始点。模拟退火法实例：1 MCM91B 通讯网络中的微小生成树是一个求 STEINER 生成树问题， 参见工科数学专辑 Page：7078。2、CMCM

17、97A题97 年全国高校生数模竞赛 A 题“零件的参数设计 ”，可以归结为非线性规划模型， 由于目标函数很复杂，且又是一个多维函数，因此求解比较困难，为应用模拟退火法进行求解，将 7 个自变量的取值范畴进行离散化，取步长为 0.0001，这样，全部 7 个变量取值就组成了一个极为巨大的离散空间, 而这个问题变成组合优化模型。这个问题算法的状态调整规章是：每次从7 个自变量中随机选取1-4 个，让选取的自变量随机移动，考虑选取的自变量在两个方向移动组合，从中选取正确的作为候选者，自变量移动的距离随着温度的降低而削减，为防止陷入局部微小，可以从多个随机选取的初始值开头运算，算法的其它步骤同上。3、

18、CMCM 98B题98 年全国高校生数学建模竞赛 B 题“水灾巡察问题 ”，是一个推销员问题，此题有 53 个点，全部可能性大约为 exp53, 目前没有好方法求出精确解，既然求不出精确解，我们使用模拟退火法求出一个较优解，将全部结点编号为1 到 53，1 到 53 的排列就是系统的结构，结构的变化规章是：从 1 到 53 的排列中随机选取一个子排列，将其反转或将其移至另一处，能量E 自然是路径总长度。详细算法描述如下：步 1： 设定初始温度T ，给定一个初始的巡察路线。步 2：步 3 -8 循环 K 次步 3：步4-7 循环 M 次步 4：随机挑选路线的一段可编辑资料 - - - 欢迎下载精

19、品名师归纳总结学习资料 名师精选 - - - - - - - - - -第 5 页，共 22 页 - - - - - - - - - -可编辑资料 - - - 欢迎下载精品名师归纳总结资料word 精心总结归纳 - - - - - - - - - - - -步 5：随机确定将选定的路线反转或移动，即两种调整方式：反转、移动。步 6：运算代价D，即调整前后的总路程的长度之差步 7：根据如下规章确定是否做调整：假如 D0 ，就根据EXP-D/T 的概率进行调整步 8： T*0.9-T ，降温34 Euler回路设 G 是一个图，如存在这样一条回路，使它经过图中的每条边且只经过一次又回到起始节点，就

20、称这样的回路为Euler 回路。背景： 哥尼斯堡七桥问题定理： 对连通图 G，以下条件是相互等价的：(1) G 是 Euler 图 。(2) G 的每个节点的度数都是偶数。(3) G 的边集可以分解为如干个回路的并。对有向图，出度入度。算法： 弗罗莱 Fleury 算法 19211 任给 v0VG ， Rv0(2) 设路 Rv0e1v1e2v2eivi 已选定，就从EGe1,e2,ei 中选边 ei+1，且满意：ei+1 与 vi 相连。除非已无挑选，ei+1 不要选 EGi EG e1,e2,ei 中的桥 注：桥，去掉之后图不连通(3) 重复 2，直到不能再选为止实例： MCM90B铲雪问题

21、中单车道单车扫雪的图是Euler 图的情形。说明： 假如图 G 不是 Euler 图，也就是说不存在Euler 回路，这时候求解就比较困难。求解前需要 做一些处理，添加一个边子集E1 ，E1G G1 构成一个Euler 图，然后再查找Euler 回路。留意图 G 不是 Euler 图时，必有偶数个奇数度的节点，可以给这些节点两两配对，求两点间的最短路，将这些最短路画在一起构成附加边子集E1。这里的困难在于：奇数度的节点较多时，配对方案也多。 35 网络中的最大流背景： 把商品从生产的运往市场，交通网上每个路段才能给定的条件下，设计一个运输方案，使得可编辑资料 - - - 欢迎下载精品名师归纳总

22、结学习资料 名师精选 - - - - - - - - - -第 6 页，共 22 页 - - - - - - - - - -可编辑资料 - - - 欢迎下载精品名师归纳总结资料word 精心总结归纳 - - - - - - - - - - - -运输最快。网络： 规定起点 s、中间点和终点t 的赋权图。数学模型： 有向图 G，每边加权ce，称 ce为边 e 之容量，设G 为严格的有向图，就称这个有向的加权图为一个网络。映射f ： EGR 满意c1任给 eEG ， 0 fe ce。可编辑资料 - - - 欢迎下载精品名师归纳总结c2任给 vVG s,t ，ef ve ef e 0。其中 av是以

23、 v 为头的边集 流进 ， bv v 可编辑资料 - - - 欢迎下载精品名师归纳总结是以 v 为尾的边集 流出 ，即除起点和终点外，各节点流入量总和等于流出量总和。称fe 为流函可编辑资料 - - - 欢迎下载精品名师归纳总结数，称Ffet e eft e可编辑资料 - - - 欢迎下载精品名师归纳总结为流量。我们的目标是查找一个流函数f，使其流量最大。1956 年，福特 Ford 和福尔克逊 Fulkerson 提出了求最大流的算法。最大流最小割定理：流过网络的最大流量等于最小割集的容量。2F 算法：(1) 对每边 e，选 fe 0。(2) 标志顶 s，其它顶未标志。(3) 选可“向前标志

24、”或可“向后标志”的顶v。如无此种顶可选时，停止，现流函数即为最大流。如有此种顶可选时，就得到新的标志顶v 及标志边e。如 vt ，就转 4 。否就转 3 。(4) 设已得标志之轨为此轨为无向的se1v1e2v2ett，从 t 开头沿此轨逆行，令minei ，1 il如 ei 是前进边，即在有向图中ei vi 1vis v0， t vl ，就 fei fei 。 如 ei 是后退边，即在有向图中ei vivi 1，就 fei fei 。5 转2 。向前和向后标志的含义如下：如 euv ， u 已有标志， v 没有标志，且 cefe ，就称通过边 e 可以向前标志顶点 v，且规定 e ce fe

25、 ，得到标志边 e。如 evu ， u 已有标志， v 没有标志， 且 fe0 ，就称通过边 e 可以向后标志顶 v，规定 e fe ，且得到标志边 e。 e的含义是边 e 上可以增载的上界。说明：1 假如每边之容量ce都是有理数，就2F 算法在有限步之内可以求得最大流。可编辑资料 - - - 欢迎下载精品名师归纳总结学习资料 名师精选 - - - - - - - - - -第 7 页，共 22 页 - - - - - - - - - -可编辑资料 - - - 欢迎下载精品名师归纳总结资料word 精心总结归纳 - - - - - - - - - - - -2 容量有上下界的网络，需要构造附加

26、网络。3.6 最小费用最大流问题这是在上述争论的基础上增加关于使费用最小的目标。解决的方法是采纳“对偶法原理”：1 先用上面争论的方法求出网络的最大流量。2 然后在原始的网络中福德算法找出从起点v s 到终点 v t 的最短路线最短增广链。3 在该增广链上找出最大调整量，并调整流量得到一个可行流，就此可行流的费用最小。假如此时流量等于最大流量，那么它就是最小费用最大流。否就应连续调整。应用： 运输问题，如CMCM2000B钢管的选购和运输问题。说明：1这里的介绍只是图论中的一部分内容，更多的需要我们进一步学习。2算法都是描述性的，有些可以找到现成的程序，但是最好是自己实现。3这里的例子只是解决

27、问题的一种方法，不是唯独的方法。4留意实际应用中直接利用所给算法解决问题的情形很少，通常只是解决问题的一部分，而且需要建立模型，把实际问题用图论术语描述出来。所以要善于利用这里的工具。其它方面的应用，如工序问题，最大独立集，最小掩盖集，邮递员问题，规划审核技术，关键轨道方法，牢靠通信网络的构造问题，班级人员安排等等。37 工序问题统筹方法是组织生产方案的方法，它用网络图表达生产和工程的进度，运算各项工序的有关时间参数。一项工程总是由很多相互独立的工序组成的，各道工序之间有肯定的先后次序。完成每道工序需要的时间 （不妨设单位为小时）称为工序的长度。因此我们可以用一个各条边有方向的图（称为有向图）

28、 表示各项工序之间的相互依靠关系。以一条有向变来表示一道工 序，有向边的权即为此工序的长度，有向边的起点和终点分别表示相应工序的开工和完工，称为事项， 前接工序和完工事项即为后续工序和开工事项。实例： 上海 MCM91B四、网络规划的应用可编辑资料 - - - 欢迎下载精品名师归纳总结学习资料 名师精选 - - - - - - - - - -第 8 页，共 22 页 - - - - - - - - - -可编辑资料 - - - 欢迎下载精品名师归纳总结资料word 精心总结归纳 - - - - - - - - - - - -1最小生成树 网络规划例1例 1求下图的一个最小生成树。解： 第一取G

29、1=（ V 1， E1）， V 1=v 0 ， E1=其次，一端属于V 1，一端不属于V 1 的最短边是v 0v 1，所以有G2=（ V 2， E2 ）， V2=v 0， v 1 ， E2=v 0v1 。现在，一端属于V 2，一端不属于V 2 的最短边是v 1v 3，所以有G3=（ V 3， E3 ）， V3=v 0， v 1， v3 ， E3=v ov 1， v1v3 。类似做下去，最终得最小生成树的边为：v 0v 1， v1v 3， v2v 3， v2v5， v5v6， v4v6。2储备粮食模型 网络规划例2例 2某乡有七个村A1 ， A2 ，.， A7 ，需储存粮食数量分别为50， 75

30、，62， 40，100， 80，35吨。各村之间有大路连通，如图。现要挑选某村建立仓库储存全部粮食，问应挑选何处最好？ 解：图上连结两村的边所注的数字表示该段大路的千米数。我们的目的是挑选仓库的位置使运粮的吨千米数最小。第一比较A1 和 A2 两处。在比较这两个村庄时，由于仓库无论建在A1 或 A2 ，其他各村的粮食都要先运到A2 ，所以我们可认为除A1 外各村的粮食都集中在A2 ，共 357 吨。现在事情很明显，仓库建在A2 时需把 50 吨粮食运3 千米到A2 ，建在A1 时需把357 吨粮食运3 千米到 A1 ，所以A2 较 A1 好。以后我们不再考虑A1 ，因此可把A1 的粮食移到A2

31、 以简化问题。同理A5 也不必考虑，它的粮食可集中到A4 。考虑其他五个村。我们猜想现在粮食数 量大的村庄可能是个好想法。假定挑选A4 ，我们考虑A6 是否会更好： A2 、 A7 的粮食少运 4 千米，而A3 、 A4 的粮食多运4 千米，可见A4 较 A6 好。同理可证A4 比其他各村都好。因此仓库应建在A4 。3工作次序模型 网络规划例3可编辑资料 - - - 欢迎下载精品名师归纳总结学习资料 名师精选 - - - - - - - - - -第 9 页，共 22 页 - - - - - - - - - -可编辑资料 - - - 欢迎下载精品名师归纳总结资料word 精心总结归纳 - -

32、- - - - - - - - - -例 3某工厂的改造工程由以下7 道工序组成： A ：拆迁。 B：工程设计。 C：土建工程设计，前接工序为B。 D：选购设备，前接工序为B。 E：厂房土建，前接工序为A 、C。 F：设备安装，前接工序为 D 、E。 G：设备调试，前接工序为F。那么我们可用图3.4 表示这个工程，其中S 表示整个工程的开工，t 表示完工。有时，为了表示工序之间的次序关系，需要引入虚工序。留意，用来表示工程进度的有向图是不答应有回路的。现在我们争论网络图的各种时间参数。考虑图3.5 表示的网络，我们把各事项（即图的顶点）编号，一般要求每一工序的开工事项（即箭尾）的编号少于完工事

33、项的编号（即箭头）。每条有向边旁所标数字为相应工序的长度。某一工序A 的最早开工时间t E A ，表示该工序最早可在整个工程开工后t E A 小时开工，这时间仅与该工序的开工事项有关，所以也可以说某一事项的最早时间t E k ，例如图3.5 中，事项4 的最早时间是 9（即工序1-4 和 2-4 都完成的时间） 。因而有以下递推公式ik 表示起点为i，终点为k 的有向边。整个工程完工事项的最早时间，就是全工程完工的最短时间，称为总工期，记为T E 。某一工序的最迟完工时间（或该工序完工事项的最迟时间）t E k ，是在不误总工期的条件下，该工序最迟应在整个工程开工后t L A 小时完成。因此实

34、际上， t E k 就是由事项1 到事项 k 的最长路的长度。t L k 就是 T E 减去 k 到 n 的最长路的长度。因而（ 2）的其次式也可写成工序 ij 的总时差定义为即不误总工期的条件下该工序的开工时间的机动时间，即可推迟开工的时间。而工序ij 的自由时差定义为即在不误下道工序最早开工时间的前提下，该工序开工时间的机动时间。可编辑资料 - - - 欢迎下载精品名师归纳总结学习资料 名师精选 - - - - - - - - - -第 10 页，共 22 页 - - - - - - - - - -可编辑资料 - - - 欢迎下载精品名师归纳总结资料word 精心总结归纳 - - - -

35、- - - - - - - -从事项 1 到事项 n 的一条最长路称为网络图的一条关键路，明显在关键路上的每一事项k 满意t L k=t E k ，关键路上每一工序的总时差为0，反之亦然。明显，如关键路上工序能提前完成，整个工程才有可能提前完成。如关键路上工序未能按时完成，整个工程必定不能按期完成。求总工期和关键路的方法如下：第一对全部 t E i 置初始值零，然后利用公式（ 1）进行迭代， 直到全部的 t E i 不再转变，而自由时差为 0 的工序就是关键路上的工序。例如图 3.5 中网络图的总工期为 28 天，关键路为 1-3-5-6-8 。4求网络的最小费用最大流求网络的最小费用最大流，

36、弧旁的数字是容量运费 。一 Ford 和 Fulkerson 迭加算法 .基本思路：把各条弧上单位流量的费用看成某种长度,用求解最短路问题的方法确定一条自 V1 至 Vn 的最短路 ;在将这条最短路作为可扩充路,用求解最大流问题的方法将其上的流量增至最大可能值 ;而这条最短路上的流量增加后,其上各条弧的单位流量的费用要重新确定,如此多次迭代,最终得到最小费用最大流.迭加算法：设图中双线所示路径为最短路径，费用有向图为W （ fij ）1) 给定目标流量F 或 ,给定最小费用的初始可行流fij=02) 如 Vf=F, 停止 ,f 为最小费用流 ;否就转 3.3) 构造 fij相应的新的费用有向图

37、Wfij, 在 Wfij 查找 Vs 到 Vt 的最小费用有向路P最短路 ,沿 P 增加流 f 的流量直到F,转2; 如不存在从Vs 到 Vt 的最小费用的有向路P,停止 .f 就是最小费用最大流.在图 a中给出零流f,在图 b中找到最小费用有向路,修改图 a中的可行流 , =min4,3,5=3,得图 c, 再做出 c 的调整容量图,再构造相应的新的最小费用有向路得图d,修改图 c 中的可行流, =min1,1,2,2=1,得图 e,以此类推 , 始终得到图 h, 在图 h 中以无最可编辑资料 - - - 欢迎下载精品名师归纳总结学习资料 名师精选 - - - - - - - - - -第

38、11 页，共 22 页 - - - - - - - - - -可编辑资料 - - - 欢迎下载精品名师归纳总结小费用有向路 ,停止 ,经运算 :图h中 最小费用 =1*4+3*3+2*4+4*1+1*1+4*2+1*1+3*1=38图g中 最大流 =5二圈算法：详细解题步骤:1) 利用 Ford 和 Fulkson 标号算法找出流量为F= 最大流 的流 f.2) 构造 f 对应的调整容量的流网络Nf.3) 搜寻 Nf 中的负费用有向图CFloyd 算法 ,如没有就停止,否就转 4.4) 在 C 上找出最大的循环流,并加到 N 上去 ,同时修改NF 中 C 的容量 ,转3.利用 Ford 和 F

39、ulkson 标号算法 ,得网络的最大流F=5, 见图 a,由图 a 构造相应的调整容量的流网络 b, 图b 中不存在负费用有向图,故停止经运算:图b中 最小费用 = 4*1+3*1+1*1+3*3+4*2+1*1+4*1+2*4=38图a中 最大流为F=5可编辑资料 - - - 欢迎下载精品名师归纳总结附录一： Ford 和 Fulkerson 迭加算法求网络的最小费用最大流问题的C 语言程序/*Ford 和 Fulkerson 迭加算法 */#includestdio.h void mainint a,b,i,j,k,p,n,B1010,C1010,D1010,P101010;printf

40、please input n:n; scanf%d,&n;printfplease input C%d%d,B%d%d:n,n,n,n,n; fori=0;i=n;i+forj=0;j=n;j+scanf%7d,%7d,&Cij,&Bij; /输入各点 i,j 之间的容量Cij 和运费 Bij fori=0;i=n;i+forj=0;j=n;j+Dij=Bij;fork=0;k=n;k+ Pijk=0;ifDij100 /注： 100 表示 Vi 到 Vj 之间无可行路Piji=1;Pijj=1;fork=0;k=n;k+ fori=0;i=n;i+ forj=0;j=n;j+ ifDik+DkjDijDij=Dik+Dkj;forp=0;p=n;p+ Pijp=Pikp|Pkjp; /