《OR-10图与网络模型.ppt》由会员分享，可在线阅读，更多相关《OR-10图与网络模型.ppt（14页珍藏版）》请在三一文库上搜索。
1、1,运筹学 第十章 图与网络模型,主讲教师：李娜 管理学院 2007.3,2,10.1 基本概念 P229-231 无向图：可以描述相互认识的关系 有向图：可以描述 被认识 的关系 优点：简单明了 名词： 点，vi 边，ei，无向 弧，ai，有向 无向图：点、边构成， 记，G=(V，E) V，图G的点的集合 E，图G的边的集合,有向图：点、弧构成， 记，D=(V，A) V，图D的点的集合 A，图D的弧的集合,3,链：点、边交错的序列 圈：起点也是终点的链 连通图：任意两点间有链 权：边上对应的数字，wij 赋权图：每条边都有权wij,路：点、弧交错的序列，同向 回路：起点也是终点的路 权：弧上
2、对应的数字，cij 网络：每条弧都有权(容量cij)， 指定一个发点、一个收点 其它为中间点 。,发点,收点,4,10.2 最短路问题 动态规划中解决的是阶段明显的最短路问题 1. Dijkstra 算法 ( 双标号法，适用条件：cij 0 ) 每个点 vj 标号Lj ：起点vs到本点的最短路长 两标号( Lj, kj ) 标号kj：此最短路上前一个点的下标 例1，最短路从V1 到V6,第1步，起点标号(0，s)， 起点之前没有别的点，用s 标示,第2步，找出所有已标号的点的集合，I = v1 ， 与I直接相连的未标号的点的集合J = v2,v3,v4 所有I、J间的弧的集合, (v1,v2)
3、,(v1,v3),(v1,v4) ,(0,s),第3步，计算每个J经过直接相连的I到起点的距离， s12 = L1+ c12 = 0 + 3 = 3 s13 = L1+ c13 = 0 + 2 = 2 s14 = L1+ c14 = 0 + 5 = 5,第4步，确定最小的sij对应的未标号点，对其标号。 Min s12、s13、s14 = 2 ， 对应v3，标号 ( 2, 1 ) 到起点最短路长2，此最短路上的前点是v1 注意，如果Min对应2两个s，就加2个“(双标号)” 第5步，继续 ，直到在v6 上标号,(2,1),(3,1),(3,3),(8,4),5,应用举例： 例2 电信公司准备在
4、甲、乙两地沿路架设一条光缆线，问如何架设使其光缆线路最短？下图给出了甲乙两地间的交通图。权数表示两地间公路的长度（单位：公里）。,6,2. 最短路问题的应用 分析：无向图，边-可以看作两条方向相反的弧 也可以直接使用“双标号法”。,(0,s),(10,1),(13,3),(14,3),(16,5),(18,5),(22,6),7,10.3 最小树问题 树：无圈的连通图 1. 破圈法：找1个圈，去最大边，重复，直到无圈 2. 避圈法：连最小边，不要成圈，直到连上所有点 例4，P239 破圈法， 总长19,v1,v2,v3,v4,v5,v6,2,10,3,3,1,5,3,4,4,7,8,v7,8,
5、例5：某大学准备对其所属的7个学院办公室计算机联网，这个网络的可能联通的途径如下图，图中v1,v7 表示7个学院办公室，请设计一个网络能联通7个学院办公室，并使总的线路长度为最短。,9,避圈法， 总长19,v1,v2,v3,v4,v5,v6,2,3,3,1,3,7,v7,10,4. 最大流问题 定义，给定一个带有收点、发点的网络，求出 不超过每条弧容量前提下的网络最大流量。 1.数学模型：例6，石油公司铺管道，求最大流量P242 设，弧(vi，vj)中的实际流量fij Max Z = f12 + f14 f12 = f23 + f25 f14 = f43+f46+f47 f23+f43 = f
6、35+f36 f25+f35=f57 f36+f46=f67 f57+f67+f47=f12+f14 fijcij fij0,v1,v2,v3,v4,v7,v6,6,6,5,2,3,2,4,2,3,v5,1,目标函数：Max Z = 发点发量（或收点收量） 约束条件：每个中间点的收量 = 该点发量 发点发量 = 收点收量 每条弧的实际流量fij 该弧的容量 cij 非负条件：每条弧的实际流量fij0,2,11,2. 图解法 第1步，改造网络图，,v1,v2,v3,v4,v7,v6,6,6,5,2,3,2,4,2,3,v5,1,2,6,v1,6,0,0,0,0,0,0,0,0,0,0,0,第2步
7、，找一条v1到v7的路，确定最大的可能的流量 例，v1 v4 v7，最大可能流量 2 。 在v1旁边标注2，并将该路所有弧的顺流容量减2， 逆流容量加2，划去顺流容量为“0”的弧。 第3步，继续，直到没有路。 第4步，根据最后的顺流、逆流容量，核定实际流量。,5 ,5 ,2 ,3 ,1,2,5,3,2,2,2,12,5. 最小费用最大流问题 要求，能够建立数学模型 第一步：求出最大流 第二步：以第一步的最大流为约束求最小费用。 发点的发量=Z 其他同最大流的模型。,13,作业 P253 1、3、4,14,THE END,Management school Inner Mongolia University of Technology,