《运筹学ppt课件Ch6网络模型》由会员分享，可在线阅读，更多相关《运筹学ppt课件Ch6网络模型（119页珍藏版）》请在金锄头文库上搜索。
1、运筹学OperationsResearch Chapter6网络模型NetworkModeling 6 1最小 支撑 树问题Minimal Spanning TreeProblem6 2最短路问题ShortestPathProblem6 3最大流问题MaximalFlowProblem6 4旅行售货员与中国邮路问题TravelingSalesmanandChinaCarrierProblem 2020 2 9 5 v1 v2 v3 v4 v5 v6 8 4 3 7 5 2 6 1 8 图6 1 运筹学中研究的图具有下列特征 1 用点表示研究对象 用边 有方向或无方向 表示对象之间某种关系 2
2、强调点与点之间的关联关系 不讲究图的比例大小与形状 3 每条边上都赋有一个权 其图称为赋权图 实际中权可以代表两点之间的距离 费用 利润 时间 容量等不同的含义 4 建立一个网络模型 求最大值或最小值 2020 2 9 边用 vi vj 表示或简记为 i j 集合记为 如图6 1所示 点集合记为 边上的数字称为权 记为w vi vj w i j 或wij 集合记为 连通的赋权图称为网络图 记为G V E W 5 v1 v2 v3 v4 v5 v6 8 4 3 7 5 2 6 1 8 图6 1 6 1最小 支撑 树问题Minimal Spanning TreeProblem 2020 2 9 6
3、 1 1树的概念 一个无圈并且连通的无向图称为树图或简称树 Tree 组织机构 家谱 学科分支 因特网络 通讯网络及高压线路网络等都能表达成一个树图 可以证明 1 一棵树的边数等于点数减1 2 在树中任意两个点之间添加一条边就形成圈 3 在树中去掉任意一条边图就变为不连通 在一个连通图G中 取部分边连接G的所有点组成的树称为G的部分树或支撑树 SpanningTree 图6 2是图6 1的部分树 6 1最小树问题Minimaltreeproblem 2020 2 9 6 1 2最小部分树 将网络图G边上的权看作两点间的长度 距离 费用 时间 定义G的部分树T的长度等于T中每条边的长度之和 记为
4、C T G的所有部分树中长度最小的部分树称为最小部分树 或简称为最小树 最小部分树可以直接用作图的方法求解 常用的有破圈法和加边法 破圈法 任取一圈 去掉圈中最长边 直到无圈 6 1最小树问题Minimaltreeproblem 2020 2 9 5 v1 v2 v3 v4 v5 v6 8 4 3 7 5 2 6 1 8 图6 1 例6 1 用破圈法求图6 1的最小树 图6 4 图6 4就是图6 1的最小部分树 最小树长为C T 4 3 5 2 1 15 当一个圈中有多个相同的最长边时 不能同时都去掉 只能去掉其中任意一条边 最小部分树有可能不唯一 但最小树的长度相同 6 1最小树问题Mini
5、maltreeproblem 2020 2 9 加边法 取图G的n个孤立点 v1 v2 vn 作为一个支撑图 从最短边开始往支撑图中添加 见圈回避 直到连通 有n 1条边 v1 v2 v3 v4 v5 v6 图6 5 在图6 5中 如果添加边 v1 v2 就形成圈 v1 v2 v4 这时就应避开添加边 v1 v2 添加下一条最短边 v3 v6 破圈法和加边法得到树的形状可能不一样 但最小树的长度相等 MinC T 15 6 1最小树问题Minimaltreeproblem 2020 2 9 下一节 最短路问题 1 树 支撑树 最小支撑树的概念2 掌握求最小树的方法 1 破圈法 2 加边法 作业
6、 P149T1 4 5 6 1最小树问题Minimaltreeproblem 6 2最短路问题ShortestPathProblem 2020 2 9 最短路问题在实际中具有广泛的应用 如管道铺设 线路选择等问题 还有些如设备更新 投资等问题也可以归结为求最短路问题 求最短路有两种算法 一是求从某一点至其它各点之间最短离的狄克斯屈拉 Dijkstra 算法另一种是求网络图上任意两点之间最短路的Floyd 弗洛伊德 矩阵算法 最短路问题 就是从给定的网络图中找出一点到各点或任意两点之间距离最短的一条路 6 2 1最短路问题的网络模型 6 2最短路问题ShortestPathProblem 202
7、0 2 9 6 10 12 3 2 14 6 7 5 8 11 16 5 图6 6 9 例6 3 图6 6中的权cij表示vi到vj的距离 费用 时间 从v1修一条公路或架设一条高压线到v7 如何选择一条路线使距离最短 建立该问题的网络数学模型 6 2最短路问题ShortestPathProblem 2020 2 9 解 设xij为选择弧 i j 的状态变量 选择弧 i j 时xij 1 不选择弧 i j 时xij 0 得到最短路问题的网络模型 6 2最短路问题ShortestPathProblem 2020 2 9 6 2 2有向图的狄克斯屈拉 Dijkstra 标号算法 点标号 b j 起
8、点vs到点vj的最短路长 边标号 k i j b i cij 步骤 1 令起点的标号 b s 0 先求有向图的最短路 设网络图的起点是vs 终点是vt 以vi为起点vj为终点的弧记为 i j 距离为cij 2 找出所有vi已标号vj未标号的弧集合B i j 如果这样的弧不存在或vt已标号则计算结束 3 计算集合B中弧k i j b i cij的标号 4 选一个点标号返回到第 2 步 6 2最短路问题ShortestPathProblem 2020 2 9 6 10 12 3 2 14 6 7 5 8 11 16 5 图6 6 9 0 6 10 12 9 20 9 18 6 16 12 17 1
9、6 24 32 18 29 29 例6 4 用Dijkstra算法求图6 6所示v1到v7的最短路及最短路长 v1到v7的最短路为 p17 v1 v2 v3 v5 v7 最短路长为L17 29 6 2最短路问题ShortestPathProblem 14 2020 2 9 从上例知 只要某点已标号 说明已找到起点vs到该点的最短路线及最短距离 因此可以将每个点标号 求出vs到任意点的最短路线 如果某个点vj不能标号 说明vs不可达vj 6 2 3无向图最短路的求法 无向图最短路的求法只将上述步骤 2 改动一下即可 点标号 b i 起点vs到点vj的最短路长 边标号 k i j b i cij
10、步骤 1 令起点的标号 b s 0 3 计算集合B中边标号 k i j b i cij 4 选一个点标号 返回到第 2 步 2 找出所有一端vi已标号另一端vj未标号的边集合B i j 如果这样的边不存在或vt已标号则计算结束 6 2最短路问题ShortestPathProblem 2020 2 9 例6 5 求图6 10所示v1到各点的最短路及最短距离 0 4 5 2 2 3 10 3 9 6 12 6 4 11 6 6 18 8 12 24 8 24 18 所有点都已标号 点上的标号就是v1到该点的最短距离 最短路线就是红色的链 图6 10 6 2最短路问题ShortestPathProb
11、lem 2020 2 9 6 2 4最短路的Floyd算法 Floyd算法基本步骤 1 写出vi一步到达vj的距离矩阵 L1也是一步到达的最短距离矩阵 如果vi与vj之间没有边关联 则令cij 2 计算二步最短距离矩阵 设vi到vj经过一个中间点vr两步到达vj 则vi到vj的最短距离为 最短距离矩阵记为 3 计算k步最短距离矩阵 设vi经过中间点vr到达vj vi经过k 1步到达点vr的最短距离为 vr经过k 1步到达点vj的最短距离为 则vi经k步到达vj的最短距离为 6 1 6 2最短路问题ShortestPathProblem 2020 2 9 最短距离矩阵记为 4 比较矩阵Lk与Lk
12、 1 当Lk Lk 1时得到任意两点间的最短距离矩阵Lk 设图的点数为n并且cij 0 迭代次数k由式 6 3 估计得到 6 2 6 3 6 2最短路问题ShortestPathProblem 2020 2 9 例6 6 图6 14是一张8个城市的铁路交通图 铁路部门要制作一张两两城市间的距离表 这个问题实际就是求任意两点间的最短路问题 解 1 依据图6 14 写出任意两点间一步到达距离表L1 见表6 1所示 本例n 8 因此计算到L3 图6 14 6 2最短路问题ShortestPathProblem 2020 2 9 表6 1最短距离表L1 6 2最短路问题ShortestPathProb
13、lem 2020 2 9 表6 2最短距离表L2 计算说明 L 2 ij等于表6 1中第i行与第j列对应元素相加取最小值 如 6 2最短路问题ShortestPathProblem 2020 2 9 表6 3计算示例 等于表6 2中第i行与第j列对应元素相加取最小值 例如 v3经过三步 最多三个中间点4条边 到达v6的最短距离是 表6 3最短距离表L3 6 2最短路问题ShortestPathProblem 2020 2 9 例6 7 求图6 15中任意两点间的最短距离 解 图6 15是一个混合图 有3条边的权是负数 有两条边无方向 依据图6 15 写出任意两点间一步到达距离表L1 表中第一列
14、的点表示弧的起点 第一行的点表示弧的终点 无方向的边表明可以互达 见表6 4所示 计算过程见表6 5 6 7 4 4 5 7 4 3 2 7 10 2 8 图6 15 1 5 6 2最短路问题ShortestPathProblem 2020 2 9 表6 4一步到达距离表L1 6 2最短路问题ShortestPathProblem 2020 2 9 表6 7最短距离表L4 经计算L4 L5 L4是最优表 表6 7不是对称表 vi到vj与vj到vi的最短距离不一定相等 对于有负权图情形 公式 6 3 失效 6 2最短路问题ShortestPathProblem 2020 2 9 6 2 4最短路
15、应用举例 6 2最短路问题ShortestPathProblem 例6 8 设备更新问题 企业在使用某设备时 每年年初可购置新设备 也可以使用一年或几年后卖掉重新购置新设备 已知4年年初购置新设备的价格分别为2 5 2 6 2 8和3 1万元 设备使用了1 4年后设备的残值分别为2 1 6 1 3和1 1万元 使用时间在1 4年内的维修保养费用分别为0 3 0 8 1 5和2 0万元 试确定一个设备更新策略 在下例两种情形下使4年的设备购置和维护总费用最小 1 第4年年末设备一定处理掉 2 第4年年末设备不处理 解 画网络图 用点 1 i j 表示第1年年初购置设备使用到第i年年初更新 经过若
16、干次更新使用到第j年年初 第1年年初和第5年年初分别用 及 表示 使用过程用弧连接起来 弧上的权表示总费用 购置费 维护费 残值 如图6 16所示 2020 2 9 6 2最短路问题ShortestPathProblem 6 图6 16 1 2 3 1 4 1 3 4 1 2 4 1 2 3 4 1 2 1 3 第一年 第二年 第三年 第四年 5 1 0 9 1 5 0 7 3 6 2 8 1 7 0 2 1 9 1 1 2 1 0 3 0 6 0 6 网络图6 16说明 如图中点 1 3 表示第1年购置设备使用两年到第3年年初更新购置新设备 这时有2种更新方案 使用1年到第4年年初 使用2年到第5年年初 更新方案用弧表示 点 1 2 3 表示第1年购置设备使用一年到第二年年初又更新 使用一年到第三年初再更新 这时仍然有2种更新方案 使用1年到第4年年初和使用2年到第5年年初 2020 2 9 6 2最短路问题ShortestPathProblem 点 1 3 和点 1 2 3 不能合并成一个点 虽然都是第三年年初购置新设备 购置费用相同 但残值不同 点 1 3 的残值等于1 6 使用
