资源描述：
《OR-10图与网络模型.ppt》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
1、《运筹学》第十章图与网络模型主讲教师：李娜管理学院2007.31§10.1基本概念P229-231无向图：可以描述相互认识的关系有向图：可以描述被认识的关系优点：简单明了名词：点，vi边，ei，无向弧，ai，有向无向图：点、边构成，记，G=(V，E)V，图G的点的集合E，图G的边的集合e2V1V2V3V4V5V6e1e3e4e5V1a1V2有向图：点、弧构成，记，D=(V，A)V，图D的点的集合A，图D的弧的集合2链：点、边交错的序列圈：起点也是终点的链连通图：任意两点间有链权：边上对应的数字，wij赋权图：每条边都有权wij路：点、弧交错的序列，同向回路：起点也是终点的路权：弧上对应
2、的数字，cij网络：每条弧都有权(容量cij)，指定一个发点、一个收点 其它为中间点。e2V1V2V3V4e1e3e4V1a1V2a2V3V4a3a4V5e5发点收点3§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间的弧的集合,
3、{(v1,v2),(v1,v3),(v1,v4)}(0,s)v1v2v3v4v5v63252715351第3步，计算每个J经过直接相连的I到起点的距离，s12=L1+c12=0+3=3s13=L1+c13=0+2=2s14=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)4应用举例： 例2电信公司准备在甲、乙两地沿路架设一条光缆线，问如何架
4、设使其光缆线路最短？下图给出了甲乙两地间的交通图。权数表示两地间公路的长度（单位：公里）。V1（甲地）1517624431065v2V7（乙地）v3v4v5v65v1v2v3v4v5v6v715103617526442.最短路问题的应用分析：无向图，边-可以看作两条方向相反的弧也可以直接使用“双标号法”。(0,s)(10,1)(13,3)(14,3)(16,5)(18,5)(22,6)6§10.3最小树问题树：无圈的连通图1.破圈法：找1个圈，去最大边，重复，直到无圈2.避圈法：连最小边，不要成圈，直到连上所有点例4，P239破圈法，总长19v1v2v3v4v5v62103315344
5、78v77例5：某大学准备对其所属的7个学院办公室计算机联网，这个网络的可能联通的途径如下图，图中v1,…,v7表示7个学院办公室，请设计一个网络能联通7个学院办公室，并使总的线路长度为最短。v1331728541034v7v6v5v4v2v3图11-148避圈法，总长19v1v2v3v4v5v6233137v79§4.最大流问题定义，给定一个带有收点、发点的网络，求出不超过每条弧容量前提下的网络最大流量。1.数学模型：例6，石油公司铺管道，求最大流量P242设，弧(vi，vj)中的实际流量fijMaxZ=f12+f14f12=f23+f25f14=f43+f46+f47f23+f43
6、=f35+f36f25+f35=f57f36+f46=f67f57+f67+f47=f12+f14fij≤cijfij≥0v1v2v3v4v7v6665232423v51目标函数：MaxZ=发点发量（或收点收量）约束条件：每个中间点的收量=该点发量发点发量=收点收量每条弧的实际流量fij≤该弧的容量cij非负条件：每条弧的实际流量fij≥02102.图解法第1步，改造网络图，v1v2v3v4v7v6665232423v5126v1v26v1v20v1v2466v1v2400000000000第2步，找一条v1到v7的路，确定最大的可能的流量例，v1—v4—v7，最大可能流量2。在v1旁
7、边标注2，并将该路所有弧的顺流容量减2，逆流容量加2，划去顺流容量为“0”的弧。第3步，继续，直到没有路。第4步，根据最后的顺流、逆流容量，核定实际流量。5523125322211§5.最小费用最大流问题要求，能够建立数学模型第一步：求出最大流第二步：以第一步的最大流为约束求最小费用。发点的发量=Z其他同最大流的模型。12作业P2531、3、413THEENDManagementschoolInnerMongoliaUni
