运筹学第8章网络规划.pptx

管理运筹学 ——模型与方法赵明霞山西大学经济与管理学院第8章　网络规划8.1　图8.2　最小树问题8.3　最短路问题8.4 最大流问题8.5 最小费用流问题(v3)孙e2(v1)赵e4e1e3(v4)李(v2)钱(v7)陈e5(v5)周(v6)吴图8-1 8.1　图 图论中图是由点和边构成，可以反映一些对象之间的关系。 例如：在一个人群中，对相互认识这个关系我们可以用图来表示，图8-1就是一个表示这种关系的图。G = (V, E)点集 V= {v1,v2,v3,...,vm}={1,2,3,…,m}边集 E= {eij=(vi,vj)}= {eij=(i, j)}e2(v1)赵e1e4e5e3(v2)钱孙(v3)李(v4)吴(v6)陈(v7)周(v5)图8-2 当然图论不仅仅是要描述对象之间关系，还要研究特定关系之间的内在规律，一般情况下图中点的相对位置如何、点与点之间联线的长短曲直，对于反映对象之间的关系并不是重要的，如对赵等七人的相互认识关系我们也可以用图8-2来表示，可见图论中的图与几何图、工程图是不一样的。 结（端）点：vi, vj关联边，e3点相邻(同一条边), v1,v3边相邻(同一个端点), e1,e3环，e2多重边, e3, e4简单图：无环无多重边次：结点的关联边数目d(v3)=4，偶点d(v4)=3，奇点d(v2)=5d(v6)=0，孤立点d(v5)=1，悬挂边图8-2链： 闭链：v1 v2 v3 v1 开链：v1 v2 v3 边不同，简单链：v3 v1 v2 v3 v4 v5边不同且结点不同，初等链：v1 v2 v3 v4 v5圈：初等闭链，且至少有3个不同结点，v1 v2 v3 v1图8-2(v2)钱a1a7a2a8a14a15(v4)李(v1)赵a3a9a4(v3)孙(v7)陈a6a12a5a11a10(v6)吴(v5)周a13图8-3 如果我们把上面例子中的“相互认识”关系改为“认识” 的关系，那么只用两点之间的联线就很难刻画他们之间的关系了，这是我们引入一个带箭头的联线，称为弧。图8-3就是一个反映这七人“认识”关系的图。相互认识用两条反向的弧表示。连通图：若任何两个不同的点之间，至少存在一条链，则G为连通图。若,则G’是G的子图，G是G’的母图若,则G’是G的真子图，若,则G’是G的支撑图。无向图：由点和边构成的图，记作G =（V，E）。有向图：由点和弧构成的图，记作D =（V，A）。无向图是有向图的基础图G(D)路：弧（边）的方向与链的方向一致。回路：若路的第一个点和最后一个点相同，则该路为回路。开路赋权图：对一个图的每一条边（弧）(vi,vj)，相应地有一个数wij，则称图G为赋权图，wij称为边(vi,vj)上的权。网络：赋权连通图例8-3：柯尼斯堡七桥问题欧拉回路：经过每边且仅一次 厄尼斯堡七桥问题、邮路问题 充要条件：图中无奇点哈密尔顿回路：经过每点且仅一次 货郎担问题、快递送货问题例8-4 节目排序问题8个节目，首尾为A, H或H,A；10名演员，不连续出演。如何安排？节目演 员12345678910A√√√√√√B√√√C√√√D√√E√√F√√G√√√H√√√√√v1v1v1v2v2v8v3v2v3v3v5v4v5v6v4v4v9v7v5v8v6v6v9v7v8v7(b)(c)(a)图8-4 8.2　最小树问题树是图论中的重要概念，所谓树就是一个无圈的连通图。 图8-4中，(a)就是一个树，而(b)因为图中有圈所以就不是树， (c)因为不连通所以也不是树。图8-5 给了一个无向图G=(V,E)，我们保留G的所有点，而删掉部分G的边或者说保留一部分G的边，所获得的图G，称之为G的支撑(生成)图。在图8-4中，(b)和(c)都是(a)的支撑图。 如果图G的一个支撑图还是一个树，则称这个支撑图为支撑（生成）树，在图8-5中，(c)就是(a)的支撑树。 最小支撑（生成）树问题就是指在一个赋权的连通的无向图G中找出一个支撑树，并使得这个支撑树的所有边的权数之和为最小。 (a)(c)(b)树的基本性质任意两点间有且仅有一条链不相邻两点间添加一条边，有且仅有一个圈任意去掉一条边，得不连通图存在悬挂点边数+1=结点数最小树的基本性质定理8-1：任意结点i的最小关联边（i, k）必在最小树中。定理8-2：点集V的非空子集,连结两子集的最小边（i, k）必在最小树中。1、破圈算法步骤：（1）在给定的赋权的连通图上任找一个圈。（2）在所找的圈中去掉一个权数最大的边（如果有两条或两条以上的边都是权数最大的边，则任意去掉其中一条）。（3）如果所余下的图已不包含圈，则计算结束，所余下的图即为最小树，否则返回第1步。例8-52、避圈算法 步骤：（1）任找一个点S，其余各点就是 。（2）在连接S与