《管理运筹学》07网络规划课件.ppt

《《管理运筹学》07网络规划课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第七章　网络规划第七章　网络规划第一节：现实中的网络规划问题第二节：图的基本概念第三节：树第四节：最大流问题第五节：最短路径问题第六节：最小费用最大流问题第七节：网络计划技术第八节：网络规划的应用7.1现实中的网络规划问题许多工程和管理的问题都可以用图与网络来描述，图与网络优化问题是一类应用十分广泛的问题。图与网络优化是线性规划等理论和算法在具有图结构的问题中的应用。由于图与网络问题具有特殊的结构，相应的优化算法也不同于一般的单纯形算法，具有其独特的直观和简捷的特点。哥尼斯堡七桥问题哥尼斯堡城有条河流，河中有两个小岛，河

2、上共有七个桥，当地居民考虑这样一个问题：能否从某个地点（任意点）出发经过七个桥，且每个桥只经过一次，最后回到出发地点。哥尼斯堡七桥问题欧拉在1736年发表了图论方面的第一篇论文，解决了哥尼斯堡的七桥问题。欧拉将此问题归结为下图所示的一笔画问题。也就是能否从某一点开始，不重复地一笔画出这个图形，最后回到原来出发点。BACD欧拉证明了这是不可能完成的。因为图形中的每个点都与奇数个线相关联，不可能将这样的图形不重复地一笔画出来，这是古典的图论中的一个著名问题。7.2　图的基本概念7.2.1图:由节点（Node）和边（Edge）

3、组成。节点和边是图中最基本的概念，我们不对其作出定义。下图中，有4个节点，7条边，每一条边都与2个节点对应。因此，一条边可以用它的两个节点来标记。图7.3中的边，可以记为[v1，v2]，[v1，v3]，[v2，v3]，[v3，v2]，[v2，v4]，[v3，v4]，[v4，v1]。v3v1v4v2e1e2e3e4e5e6图的定义定义设V=｛v1，v2，…，vm｝表示节点的集合，E=｛e1，e2，…，en｝表示边的集合，若对任一ek∈E，均有vi，vj∈V与之对应，则称V∪E为图，记为G=(V，E)。称vi为G的顶点，ek

4、为G的边，记为ek=[vi，vj]=[vj，vi]。称vi，vj为ek的端点，ek为vi，vj的关联边。称vi，vj为邻接点。将图7.3用数学定义表示如下：G=(V，E)V=｛v1，v2，v3，v4｝E=｛e1，e2，e3，e4，e5，e6，｝{e1，e2，e3，e4，e5，e6，e7}={[v1，v2]，[v1，v3]，[v2，v3]，[v3，v2]，[v2，v4]，[v3，v4]，[v4，v1]}相关定义如果图中一个边的两个端点为同一个点，称这样的边为环。如果两个点之间存在两个以上的边，称为多重边。一个没有环、也没有

5、多重边的图，称为简单图。无环,允许有多重边的图称为多重图。本章讨论的图主要是指简单图。图中的边是对节点的关系描述，所以我们讨论的图如果关系表示的相同，不论图的形状如何，我们认为这样的图都是相同的。次:以点v为端点的边的个数称为v的次，表示为:d(v)。悬挂点:次为1的点。悬挂边:悬挂点的关联边。孤立点:次为0的点。奇点:次为奇数的点。偶点:次为偶数的点。两个定理定理7-1:图G=(V,E)中,所有点的次之和是边数的两倍,即:证明:计算各端点的次时，每个边都用了两次，所以次数的总和必然为边数的两倍。定理7-2:任意一图中,

6、奇点的个数为偶数。证明:设V1表示奇点的集合，V2表示偶点的集合。由有：因为偶点的次之和为偶数，总数为偶数，所以奇点的次之和必须是偶数，只有偶数个奇数之和才能是偶数。所以奇点的个数必然为偶数个。相关定义链：点边交错系列，记为：如果满足，一般简记为：圈：　　的链。初等链：点　　　均不相同。初等圈：点　　　均不相同。简单链：链中边均不相同。简单圈：圈中边均不相同。连通图：任意两点之间至少有一条链。否则称为不连通图连通分图：对不连通图，每一连通的部分称为一个连通分图。支撑子图：对G=（V，E），若G’=(V’,E’),使V’=

7、V,E’E,则G’是G的一个支撑子图（生成子图）7.2.2有向图前面讨论的图中，边是没有方向的，ek=[vi，vj]=[vj，vi]。这样的图称为无向图。但许多实际问题用无向图表示是不够的。例如，涉及交通网络中单行道、一项工程的各工序的前后次序关系等。v3v1v4v2a1a2a3a4a5a6a7定义设V=｛v1，v2，…，vm｝表示节点的集合，A=｛a1，a2，…，an｝表示边的集合，若对任一ak∈A，均有vi，vj∈V与之对应，则称V∪A为图，记为D=(V，A)。称ak为D的弧，记为ak=（vi，vj）≠（vj，vi

8、）。相关定义始点和终点:对弧a=(u,v),u为a的始点,v为a的终点。基础图:对D=(V,A),去掉图上的箭头的无向图。链:点弧交错序列,若在其基础图中对应一条链,则称为D的一条链。路：若是D中的一条链，且，t=1,2,…,k-1,称之为从到的一条路。回路:的路。初等路:路中点不相同。初等回路:回路中点不相同。7.