2010集训专题三图论模型.ppt

2010数学建模集训班专题讲座 图论模型的建立与分析 有图有真相 有你更精彩 赵承业2010 7 15 专题 图的表示与锁具问题最小生成树 TSP和灾区巡视问题最短路 网络流和运输问题作业 图的表示与锁具问题 不积硅步 无以至千里 荀子 劝学 图的矩阵表示 邻接矩阵 1 对无向图 其邻接矩阵 其中 以下均假设图为简单图 2 对有向图 其邻接矩阵 其中 其中 3 对有向赋权图 其邻接矩阵 对于无向赋权图的邻接矩阵可类似定义 关联矩阵 1 对无向图 其关联矩阵 其中 2 对有向图 其关联矩阵 其中 两点间长度为k的路径数目 如果已经一个图的邻接矩阵A 我们想知道任意两个顶点之间长度为k的路径有多少条怎么办 一个简单的办法如下令A A IB AXAX XA k个A相乘 那么B中元素bij的值就是从i点出发到j点的路径数目通过下面的案例我们讨论一下这个方法的应用 1994年全国大学生数学建模竞赛B题 锁具装箱 某厂生产一种弹子锁具 每个锁具的钥匙有5个槽 每个槽的高度从 1 2 3 4 5 6 中任取一数 由于工艺及其它原因 制造锁具时对5个槽的高度还有两个限制 1 至少有3个不同的数 2 相邻两槽的高度之差不能为5 满足以上条件制造出来的所有互不相同的锁具称为一批 我们的问题是如何确定每一批锁具的个数 求解上述问题的一般方法 计算机枚举排列组合计数缺点 计算量都比较大 图论方法 易见 x x1 x2 其中 x1 相邻两槽高度之差不为5的锁具数 即 满足限制条件 2 的锁具数 x2 相邻两槽高度之差不为5且槽高仅有1个或2个的锁具数 即 满足限制条件 2 但不满足限制条件 1 的锁具数 我们用图论方法计算x1和x2 图论方法 基本引理令Ak A A A k次 a k ij n n 则a k ij G中以vi vj为端点的长度为k的道路数 为利用上述引理计算x1和x2 我们构造无向图G V E 如图1所示 V 1 2 3 4 5 6 E ij i j V且 i j 5 图论方法 在G中 每一条长度为4的道路对应于一个相邻两槽高度之差不为5的锁具 即 满足限制条件 2 的锁具 反之 亦然 于是 可通过G的邻接矩阵A计算x1 具体步骤如下 图论方法 因此 又令x2 y1 y2 y3 y4 y5 y6 其中 yi 满足限制条件 2 但不满足限制条件 1 且首位为i的锁具数 i 1 2 3 4 5 6 显然 y1 y6 y3 y4 y5 y2 我们只需计算y1和y2 图论方法 计算y1可分别考虑槽高只有1 12 13 14 15的情形 若只有1 这样的锁具数只有1个 若只有1和i i 2 3 4 5 这样的锁具数 G中以1和i为顶点 长度为3的道路数 此数可通过A的子矩阵A1i i 2 3 4 5 计算得到 事实上 因为所以y1 1 4 4 4 4 1 4 61 图论方法 同理 计算y2时应考虑槽高只有2 21 22 23 24 25 26的情形 类似计算可得y2 1 4 4 4 4 4 1 5 76 于是 x2 61 2 76 4 426 x 6306 426 5880 最小生成树 TSP和灾区巡视问题 山穷水尽疑无路 柳暗花明又一村 陆游 游山西村 98年全国大学生数学建模竞赛B题最佳灾情巡视路线 今年 1998年 夏天某县遭受水灾 为考察灾情 组织自救 县领导决定 带领有关部门负责人到全县各乡 镇 村巡视 巡视路线指从县政府所在地出发 走遍各乡 镇 村 又回到县政府所在地的路线 98年全国大学生数学建模竞赛B题最佳灾情巡视路线 问题1 若分为三组巡视 设计总路程最短且各组尽可能均衡的巡视路线 分析 本题显然是一个加权图上求最短回路的问题我们可以借助图论的方法解决主要考虑两个基本的方法最小生成树方法旅行商 TSP 方法 问题1的分析与求解 最小生成树法 问题 如何分成相对均衡的三组 先求图的最小生成树 理由如下最小生成树包含图的所有顶点 且最小生成树的边权是相邻顶点之间的距离 它描述了顶点之间的相近程度 可以考虑利用它来进行分块 问题1的分析与求解 最小生成树法 利用Kruskal算法 求得最小生成树如下 问题1的分析与求解 最小生成树法 对上面的最小生成树分解成三个子树分解原则分解点为O点或尽量接近O点分解得到的子图的顶点数尽可能接近17尽量使得分解得到的子图为连通图尽量使子图与点O的最短路的上点在该子图内尽量使各子图内部的点在内部形成回路 问题1的分析与求解 最小生成树法 分解的结果 问题1的分析与求解 最小生成树法 几个优化原则扩环原则子图有孤立枝 扩环后权值应减小增环原则环路上某个顶点有两枝 且有使两枝成环的边存在 考虑增环 增环后权值应减小换枝原则环路上某顶点长出一条枝 该枝末梢和环路另一顶点接近 可考虑换枝 问题1的分析与求解 最小生成树法 问题1的分析与求解 TSP方法 公路边的数字为该路段的公里数 问题分析 本题给出了某县的公路网络图 要求的是在不 同的条件下 灾情巡视的最佳分组方案和路线 将每个乡 镇 或村看作一个图的顶点 各乡 镇 村之间的公路看作此图对应顶点间的边 各条 再回到点O 使得总权 路程或时间 最小 公路的长度 或行驶时间 看作对应边上的权 所 给公路网就转化为加权网络图 问题就转化图论中 一类称之为旅行售货员问题 即在给定的加权网络 图中寻找从给定点O出发 行遍所有顶点至少一次 问题1是三个旅行售货员问题 本题是旅行售货员问题的延伸 多旅行售货员问题 本题所求的分组巡视的最佳路线 也就是m条 众所周知 旅行售货员问题属于NP完全问题 显然本问题更应属于NP完全问题 有鉴于此 经过同一点并覆盖所有其他顶点又使边权之和达到 最小的闭链 闭迹 即求解没有多项式时间算法 一定要针对问题的实际特点寻找简便方法 想找到 解决此类问题的一般方法是不现实的 对于规模较大 的问题可使用近似算法来求得近似最优解 最佳灾情巡视路线的模型的建立与求解 问题转化为在 给定的加权网 络图中寻找从 给定点O出发 行遍所有顶点 至少一次再回 回到点O 使得 总权 路程或时 时间 最小 即 最佳旅行售货 员问题 最佳旅行售货员问题是NP 完全问题 采用一种 近似算法求其一个近似最优解 来代替最优解 算法一求加权图的最佳旅行售货员回路近似算法 1 用图论软件包求出G中任意两个顶点间的最短路 构造出完全图 2 输入图的一个初始H圈 3 用对角线完全算法 见 3 产生一个初始圈 4 随机搜索出中若干个H圈 例如2000个 5 对第2 3 4 步所得的每个H圈 用二边逐次 修正法进行优化 得到近似最优H圈 6 在第5 步求出的所有H圈中 找出权最小的一个 此即要找的最优H圈的近似解 因二边逐次修正法的结果与初始圈有关 故本算法 第2 3 4 步分别用三种方法产生初始圈 以保 证能得到较优的计算结果 问题一若分为三组巡视 设计总路程最短且各组尽可能均衡的巡视路线 此问题是多个售货员的最佳旅行售货员问题 4 此问题包含两方面 a 对顶点分组 b 在每组中求 单个售货员 最佳旅行售货员回路 因单个售货员的最佳旅行售货员回路问题不存在多项式时间内的精确算法 因此多个售货员的最佳旅行售货员回路问题也不存在多项式时间内的精确算法 定义称 为该分组的实际均衡度 为最大容许均衡度 而图中节点数较多 为53个 我们只能去寻求 一种较合理的划分准则 对图1进行粗步划分后 求 出各部分的近似最佳旅行售货员回路的权 再进一 进一步进行调整 使得各部分满足均衡性条件3 从O点出发去其它点 要使路程较小应尽量走 O点到该点的最短路 故用软件包求出O点到其余顶点的最短路 这些最短路构成一棵O为树根的树 将从O点出发的树枝称为干枝 从O点出发到其它点共有6条干枝 它们的名称 分别为 在分组时应遵从准则 准则1尽量使同一干枝上及其分枝上的点分在同一组 准则2应将相邻的干枝上的点分在同一组 准则3尽量将长的干枝与短的干枝分在同一组 由上述分组准则 我们找到两种分组形式如下 分组1 分组2 分组1极不均衡 故考虑分组2 分组2 对分组2中每组顶点的生成子图 用算法一求出近似最优解及相应的巡视路线 在每个子图所构造的完全图中 取一个尽量包含上图中树上的边的H圈作为其第2 步输入的初始圈 分组2的近似解 因为该分组的均衡度 所以此分法的均衡性很差 为改善均衡性 将第 组中的顶点C 2 3 D 4 分给第 组 顶点2为这两组的公共点 重新分 分组后的近似最优解见表2 因该分组的均衡度 所以这种分法的均衡性较好 最短路 网络流和运输问题 天下熙熙皆为利来 天下攘攘皆为利往 司马迁 史记 2000年全国数学建模竞赛B题钢管的订购与运输 钢厂的产量和销价 1单位钢管 1km管道钢管 钢厂产量的下限 500单位钢管 1单位钢管的公路运价 0 1万元 km 不足整公里部分按整公里计 1 制定钢管的订购和运输计划 使总费用最小 2 分析对购运计划和总费用影响 哪个钢厂钢管销价的变化影响最大 哪个钢厂钢管产量上限的变化影响最大 3 讨论管道为树形图的情形 问题1的分析与求解 整个铺设管道的工程看似错综复杂 其实可分为三个部分 1 各个工厂 S点 生产一定数量的钢管2 把钢管从工厂 S点 运送到铺设管道的关节点 A点 3 从关节点 A点 将管道运至铺设地点这三个部分是相互依赖的 不能简单地把三个部分孤立开来讨论 但是通过仔细观察 我们发现第二部分中的运费事实上只与出发点 S点 目标点 A点 和运量有关 并且是运量的线性函数 具备可叠加性 运输总费用 因此 我们可以简化第二部分的计算 即先从铁路与公路网络得出SAP矩阵 问题的简化 求SAP矩阵的基本思路是图的最短路算法 由于铁路的运输费用与线路的长度不是线性关系 必须对铁路网做一些预处理才能套用图的标准最短路算法 下面叙述求SAP矩阵的过程 1 利用图的标准最短路算法 从铁路网络得出图中任两个点之间的最短路径表T 如果两个点之间不连通 认为它们之间的最短路长度为 2 利用题中的铁路运价表将T中的每个元素 即最短距离 转化为运输费用 将运输费用表记为C 3 将公路的长度换算为运输费用 由公路路程图 包括要沿线铺设管道的公路 得出公路费用图G 若i j不连通 则令Gij 4 对于任一组 i j 1 n 1 m 如果Cij 且小于Gij 那么就在公路费用图中加一条边 即令Gij min Cij Gij 5 利用图的标准最短路算法 求公路费用图中任一个S点到任一个A点的最小费用路径 得出SAP矩阵 如表1所示 SAP矩阵 问题的数学描述 问题的求解 上面的数学描述中 最难处理的是Si 0或Si 500这个条件 求解过程分为三步 A 假设工厂的产量只有上限 下面的三个流网络模型都是针对这种情况的 B 假设工厂的产量有上下限C 工厂的产量 0 500 Li 我们这里只讨论A的情况 线性费用流网络模型一 线性费用流网络模型一 图中边上的 A B A表示边的流量限制 B表示边的单位流量的费用 下同 1 网络有一个源点Source 从Source到每个S点有一条边 边的流量限制为Si的最大产量Li 单位费用为Si生产钢管的单价Ri 2 从Si到Aj有一条边 边的流量限制为 单位费用为SAPij 即从Si到Aj运输单位长度钢管的费用 3 对于每一条要铺设的管道P 设其长度为Len 两端点为Aj Ak 则P对应着Len个点 分别表示要铺设的一个单位长度的钢管 如图中P11 P12 P13 从Aj到这Len个点各有一条边 边的流量限制为1 单位费用分别为1 2 3 Len 从Ak到这Len个点也各有一条边 边的流量限制为1 单位费用分别为Len Len 1 3 2 1 线性费用流网络模型一 4 从3 中的点 代表每单位长度的钢管的点 到图的汇点Target各有一条边 流量限制为1 单位费用为0 这种流网络模型最简单 效率也较低 设铺设的管道共有Tl公里 显然Tl n与m 网络中的点数大约为Tl个 边数大约为3 Tl 最大流量为Tl 标准的网络流算法的时间复杂度为O V3 MaxFlow 因此 这个模型的复杂度为O Tl4 对于题中的数据 Tl大约在5000左右 Tl4 1015不可承受 优点 可用标准的最小费用最大流算法 如最小费用路算法 来求解 最小费用路算法 标准的最小费用最大流算法 最小费用路算法 Step0 取零流f为初始可行流 Step1 如果v f 最大流量vmax 则f为D中流值为vmax的最小费用流 否则转Step2 Step2 构造增量网络D f 如果D f 中不存在 Source Target 路 则D f 中没有流值为vmax的可行流 停止 否则在D f 中找一条最小费用路U 转Step3 Step3 用c U 表示U的容量 对f沿U增广流值 增广量为c U 得到新流f 转Step1 线性费用流网络模型二 模型一之所以效率低 最主要的问题是流网络中的点太多了 通过点的合并 可以大幅减小流网络中点的个数 将线性费用流网络模型一中对应同一段要铺设的管道的点合并成一个点 即模型一图中的P11 P12 P13合并为P1 从A点到这些点的边现在全部转到一个点上 如图 从这些点到Target的边合并为流量限制为Pi Pi即要铺设的管道的长度 单位费用为0的一条边 线性费用流网络模型二 线性费用流网络模型二 模型二中的点数为n m Pcount 2 边数大约为2 Tl个 均比模型一有了大幅减小 然而边数仍然太多 而且