运筹学教程课件六图与网路分析剖析.ppt

6.4.4 多端网路问题 * 6.4.5 最小费用最大流 双权网路：每条弧不但有容量，还有单位流量的通过费用 两种解法：一种基于最小费用路径算法；一种基于可行弧集的最大流算法 基于最小费用路径算法：总是在当前找到的最小费用的路径上增广流；缺点是每次增广后要改变弧的费用，且出现负权值费用的弧 基于可行弧集的最大流算法：从 0 费用弧集开始应用最大流算法，然后根据计算信息提高费用的限界P，使可行弧集增大，再应用最大流算法，直至所有弧都进入可行弧集。这种算法是一种主-对偶规划的解法。使用这种方法的还有运输问题、匹配问题 * 6.4.5 最小费用最大流 一、基本原理 1、若f ={fi, j}是流量为V(f)的所有可行流中费用最小者，而 ?是关于f的所有增广链中费用最小的增广链，那么，沿?去调整f得到的可行流f ‘就是流量为V(f ’)的所有可行流中的最小费用流。这样，当 f ‘是最大流时，它就是所求的最小费用最大流。 2、因为di j =0, f ={fi, j}=0必是流量为0 的最小费用流，因此，可从 f ={fi, j}=0开始。 3、给定有向网络G=(V,A)，设f ={fi, j}是流量为V(f)的最小费用流，为寻找是关于f的最小费用增广链，构造年一赋权图W(f)，该图的节点与原图G相同，但将网络中的每一弧变成两个相反方向的弧，其权定义如下： * ?管理与人文学院 忻展红 1999，4 第六章 图与网路分析 图是最直观的模型 * B A C D 图论 Graph Theory 哥尼斯堡七桥问题 (K?nigsberg Bridge Problem) Leonhard Euler (1707-1783) 在1736年发表第一篇图论方面的论文，奠基了图论中的一些基本定理 很多问题都可以用点和线来表示，一般点表示实体，线表示实体间的关联 * 6.1 图与网路的基本概念 6.1.1图与网路 节点 (Vertex) 物理实体、事物、概念 一般用 vi 表示 边 (Edge) 节点间的连线，表示有关系 一般用 eij 表示 图 (Graph) 节点和边的集合 一般用 G(V,E) 表示 点集 V={v1,v2,…, vn} 边集E={eij } 网路 (Network) 边上具有表示连接强度的权值，如 wij 又称加权图(Weighted graph) * 6.1.2 无向图与有向图 边都没有方向的图称为无向图，如图6.1 在无向图中 eij=eji，或 (vi, vj)=(vj, vi) 当边都有方向时，称为有向图，用G(V,A)表示 在有向图中，有向边又称为弧，用 aij表示，i, j 的顺序是不能颠倒的，图中弧的方向用箭头标识 图中既有边又有弧，称为混合图 * 6.1.3 端点，关联边，相邻，次 图中可以只有点，而没有边；而有边必有点 若节点vi, vj 之间有一条边 eij，则称 vi, vj 是 eij 的端点(end vertex)，而 eij 是节点 vi, vj 的关联边(incident edge) 同一条边的两个端点称为相邻(adjacent)节点，具有共同端点的边称为相邻边 一条边的两个端点相同，称为自环(self-loop)；具有两个共同端点的两条边称为平行边(parallel edges) 既没有自环也没有平行边的图称为简单图(simple graph) 在无向图中，与节点相关联边的数目，称为该节点的“次”(degree)，记为 d ；次数为奇数的点称为奇点(odd),次数为偶数的点称为偶点(even)；图中都是偶点的图称为偶图(even graph) 6.1.3 端点，关联边，相邻，次 有向图中，由节点指向外的弧的数目称为正次数，记为 d+，指向该节点的弧的数目称为负次数，记为 d– 次数为 0 的点称为孤立点(isolated vertex) ，次数为 1 的点称为悬挂点(pendant vertex) 定理 1：图中奇点的个数总是偶数个 6.1.4 链，圈，路径，回路，欧拉回路 相邻节点的序列 {v1? ,v2? ,…, vn?} 构成一条链(link)，又称为行走(walk)；首尾相连的链称为圈(loop)，或闭行走 在无向图中，节点不重复出现的链称为路径(path)；在有向图中，节点不重复出现且链中所有弧的方向一致，则称为有向路径(directed path) 首尾相连的路径称为回路(circuit)； * 6.1.4 链，圈，路径，回路，连通图 走过图中所有边且每条边仅走一次的闭行走称为欧拉回路 定理 2：偶图一定存在欧拉回路(一笔画定理) 6.1.4 连通图，子图，成分