管理决策 第七讲 网络分析及应用.ppt

* * * * * * * * * * * * 第七讲 网络分析 运输问题——转运问题 综上，建立此例的数学模型为： 经求解，最优解如下： 第七讲 网络分析 运输问题——转运问题 归纳出转运问题的一般线性规划模型 这里xij表示从节点i到j的运量，cij表示从i到j的运价，ai表示产地i的产量，bj表示销地j的销量（需求量）。 第七讲 网络分析 最短路问题 最短路问题一般描述为：在一网络中，给定两个点vs和vt，找到一条从vs到vt的路，使这条路上所有弧的权数之和最小，这条路就是vs到vt的最短路。这条路上所有弧的权数之和称为vs到vt的距离。 最短路线问题可以采用标号法等方法进行求解，也可借助相关的运筹学软件包进行求解。 这里xij表示从节点i到j的运量，cij表示从i到j的运价，ai表示产地i的产量，bj表示销地j的销量（需求量）。 例 某电信公司计划在甲、乙两地铺设通信电缆，图是甲、乙两地间的交通图，图中 v1，v2，v3，v4，v5，v6表示6个地名点，其中v1 表示甲地，v6表示乙地，点之间的连线（边）表示两地公路，边上的数值表示两地间公路的长度（单位：千米），问如何铺设能使甲、乙两地的电缆长度最短？ 经标号法求解最短路是v1-v2-v6，最短距离是7+12=19千米，所以应在v1-v2，v2-v6间铺设线路。 (0) 14 (14) 7 8 19 (7) (8) (19) 11 (11) 练习：最短路 为提高运输效率，请找出公司（节点1）到零售店（节点11）之间的最短路径。 第七讲 网络分析 最小支撑树问题 一个连通无圈简单图称为树。若图G的一个支撑图T是树，则称T是图G的一棵支撑树。 如图示出了一个图G及其支撑树T1，T2，T3。 第七讲 网络分析 最小支撑树问题 设Tk＝（V，Ek）是网络N＝(G， )的一个棵支撑树，则Tk的边集Ek中所有边的权数之和称为树Tk的权，记为 。 即： 若支撑树T*的权 是N的所有支撑树的权中最小者，则称T*为网络N的最小支撑树，简称最小树。 即： 如何找出网络的最小树就是最小支撑树问题。最小支撑树问题可以采用避圈法和破圈法等方法进行求解，也可借助相关的运筹学软件包进行求解。 第七讲 网络分析 最小支撑树问题 例某自然景区内设有6个服务站和一个网络中心，景区的管理部门决定铺设光纤网络，为各服务站点提供通信线路。管理部门希望这个通信线路的建设成本尽可能低。图表示了服务站和网络中心的分布情况，一个圆圈表示一个服务站（或网络中心），圆圈之间连线上的数字表示两个站点（或站点与网络中心）之间铺设电缆的成本（单位：万元）。问应如何设计该通讯线路？ 经求解，结果如图所示，铺设总成本最小，为4+5+4+3+4+3=23（万元）。 练习：最小支撑树 为节约成本，请设计一个网络系统，使得城市1与乡镇2-10之间都有光纤连通，且铺设总长度最少。 地点 2 3 4 5 6 7 8 9 10 1 9 4 9 15 15 11 16 16 22 2 8 16 12 8 10 19 14 20 3 6 9 11 7 12 11 15 4 4 16 11 8 15 17 5 7 12 6 14 13 6 10 3 7 15 7 7 9 10 8 11 12 9 9 第七讲 网络分析 最大流问题 现实生活中，许多系统中都存在流量问题。如公路系统中存在车辆流，电力系统中存在电流，供水系统中存在水流，信息系统中存在信息流，金融系统中存在现金流等。 例 迅达通讯公司使用光缆网络在不同地方传递电话和其他信息。信息通过光缆线和转换点传递。该公司的传送网络如图所示。一个圆圈代表一个转换点，转换点之间的连线上的数字表示该条光缆线的最大信息传递能力。求该通讯网络的最大传输能力。 第七讲 网络分析 最大流问题 (1) 容量网络与网络流 满足如下规定的网络称之为容量网络。 ① 对于一个有向网络N＝(V，A)，各弧的方向就是流量通过的方向； ② 对网络中的每一弧（vi，vj）∈A，都赋予一个容量r（vi，vj）＝rij 0，表示容许通过该弧的最大流量； ③ 网络有一个始点vs和一