数学建模最短路问题ppt课件.ppt

第11章最短路问题 1 问题的提出2 图论的基本概念3 最短路问题求解算法4 建模实例 1问题的提出 某学校行政部门u0经常有人到7个部门办事 希望在现有的道路网络中确定他们行走的路线 使他们到各部门的路程最短 图中已经标明了部门到部门之间的距离 2图论的基本概念 图论是离散数学的重要分支 在物理学 化学 系统控制 电力通讯 编码理论 可靠性理论 科学管理 电子计算机等各个领域都具有极其广泛的应用 图论的历史可以追溯到1736年 这一年发表了图论的第一篇论文 解决了著名的哥尼斯堡 K nigsberg 七桥问题 K nigsberg七桥问题 哥尼斯堡城中有七座桥将普雷格尔 Pregel 河中的两个岛与河岸联结起来 当时人们热衷于这样一个问题 一个人能否从四块陆地中的任何一块出发走过七座桥 每座桥恰走一次 最后回到起点 a 图论的基本概念 1 图的定义G V E 顶点 边 e与v连接 v与e关联 相邻 环 重边 平面图 完全图 完备图 二部图 偶图 子图 生成图 与一个顶点vi关联的边的数目称为vi的度 或次 路 圈和连通有向图 赋权图 图论的一个定理 定理 d v 2 E v V 证 因为每一条边提供给点的度为2 所以图中所有点的度数总和是边数的2倍 推论 在任何图中 奇点个数为偶数 2 图的矩阵表示 对于任意图G 定义一个n m阶矩阵M mij n m n为顶点数 m为边数 其中mij是vi和ej相关联的次数 0 1或2等 该矩阵称为G的关联矩阵 图的另一种表示形式是邻接矩阵A aij n n 其中aij是连接ai和aj的边的数目 图的矩阵表示 关联矩阵邻接矩阵 3最短路问题求解算法 设G为赋权有向图或无向图 G边上的权均非负 1 DijkstraAlgorithm 求G中从顶点u0到其余顶点的最短路 定义 对每个顶点v 定义两个标号l v z v 其中l v 为从u0到v的路长 z v 为v的父亲点 前一个点 S 具有永久标号的顶集 算法的过程就是在每一步改进这两个标号 最终l v 为u0到v的最短路长 输入带权邻接矩阵 距离矩阵 w u v 最短路问题求解算法 DijkstraAlgorithm Dijkstra算法所需时间与n2成正比 用Dijkstra求解最短路问题 例求从顶点u0到其余顶点的最短路 解 先写出距离矩阵 实际应为对称矩阵 Dijkstra算法的迭代步骤如下 迭代l ui 次数u0u1u2u3u4u5u6u7 10 2218 328 10 483 10 58610126710127912812 最后标记 l v 021736912z v u0u0u0u5u1u4u3u4 最短路问题求解算法 2 FloydAlgorithm 1962 求任意两点间的最短路 D dij n n dij是i到j的最短路长 P pij n n pij是i到j的最短路上中间节点的最大号码 pij 0 表示无中间节点 1 赋初值 dij wij pij 0 k 1 2 更新dij pij 对所有i j 若dik dkj dij 则dij dik dkj pij k 3 若k n 停止 否则k k 1 转 2 FloydAlgorithm 例已知距离矩阵为求任意两点之间的最短路 FloydAlgorithm 解 D 0 W P 0 0 n n 建模案例分析 2000B题钢管订购和运输 2000B钢管运输分析求解步骤 1 用Floyd算法求出铁道两点间的最短路长 将路长转成费用 2 与公路运价组成的矩阵D 再用Floyd求出S1 S7到A1 A15的最短路 将购买单价计入运费之中 第12章匹配与覆盖及其应用 1匹配与覆盖1 基本概念定义1设若M的边互不相邻 则称M是G的一个匹配 M的边称为匹配边 E M的边称为自由边 若 u v M 则称u 或v 是v 或u 的配偶 若顶点v与M的一条边关联 则称v是M 饱和的 否则称为M 非饱和的 若M使G中每个顶点都是M 饱和的 称M是G的完美 理想 匹配 设M是G的一个匹配 若不存在M 使 M M 则称M为G的最大匹配 匹配与覆盖 显然 完美匹配一定是最大匹配 反之不一定成立 a 最大匹配 b 完美匹配 匹配与覆盖 定义2设若G的每条边都与K的一个顶点关联 则称K是图G的一个覆盖 设K是G的一个覆盖 若不存在覆K 使 K K 则称K是一个最小覆盖 匹配与覆盖 下图为居民小区 安装消防设施 使每个相连的街道都有消防设施可用 覆盖 v1 v2 v3 v4 v5 v1 v2 v3 v4 v2 v3 v4 v1 v3 v5 而 v2 v3 v4 v1 v3 v5 是最小覆盖 c 居民小区 2 性质 定义3设M是图G V E 的匹配 G的M交错路是指边在E M和M中交错出现的路 M可扩路 增广路 是指其起点和终点都是M非饱和的M交错路 定理1 Berge1957 设M是G的一个匹配 则M是最大匹配的充要条件是 G没有M 增广路 定理2设M是G的匹配 K是覆盖 则 1 M K 2 若 M K 则M 是最大匹配 K 是最小覆盖 3 二部图的匹配 定理3 K nig 1931 若M 和K 分别是二部图G的最大匹配和最小覆盖 则 M K 定理4 Hall 1935 对二部图G X Y E G存在饱和X的每个顶点的匹配的充要条件是 对任何SX 均有 N S S 这里N S 为与S的顶点相邻的所有顶点的集合 如果G中所有顶点的度数都为k 则称图G是k正则的 推论若G是k正则二部图 k 0 则G有完美匹配 二部图的匹配 例 如果一个乡村里每位姑娘恰好认识k位小伙子 而每个小伙子也恰好认识k位姑娘 则每位姑娘能够和她认识的一个小伙子结婚 并且每个小伙子也能和他认识的一位姑娘结婚 此即为 婚姻定理 根据上面的定理 Edmonds于1965年提出了如下的匈牙利算法 解决了二部图的基数匹配问题 步骤如下 二部图的匹配 匈牙利算法 1 设G X Y E 是二部图 M是一个匹配 2 若M饱和X的每个顶点 则算法终止 M为最大匹配 否则 取M 非饱和点u X 令S u T 3 若N S T 由于 T S 1 所以 N S S 算法终止 由定理4 Hall 不存在饱和X每个顶点的匹配 否则取y N S T 4 若y是饱和的 设yz M 用S z 代替S T y 代替T 转 3 此时 T S 1仍成立 否则设P是M增广路P u y 并令M M E P 对称差 转 2 二部图的基数匹配例 x1x2x3x4x5y1y2y3y4y5 二部图的基数匹配例 x1x2x3x4x5y1y2y3y4y5 4 二部图的赋权匹配 G是完全二部图 有两个顶点集X x1 x2 xn Y y1 y2 yn 分别表示职员和工作 xi和yj之间用边相连 其权为wij表示职员xi做yj工作时的效率 对每人分配一件工作 使总效率最大 可以用Kuhn Munkres算法求赋权完全二部图的最佳匹配 二部图的赋权匹配 定义 在G的顶点集V X Y上定义一个实值函数L 使得任何x X y Y均有L x L y w x y 其中w x y 是边 x y 上的权 称函数L v 为该二部图的一个可行顶点标号 若用EL表示使上式等号成立的那些边的集合 即EL x y x y E L x L y w x y 则称以EL为边集的G的生成子图为G对应于可行顶点标号L的相等子图 记为GL 二部图的赋权匹配 可行顶点标号总是存在的 如令 二部图的赋权匹配 定理 设L是G的可行顶点标号 若GL包含完美 基数 匹配M 则M 是G的最佳 最大权 匹配 由上述定理知 欲求二部图的最佳匹配 只需用匈牙利 Hungarian 算法求相等子图GL的完美匹配 若GL不存在完美匹配 Kuhn和Munkres给出了一个修改顶点标号L的算法 可以使新相等子图的最大匹配扩大 这样 最终使相等子图具有完美匹配 二部图的赋权匹配 Kuhn Munkres算法 1 设G X Y E 是二部图 从任一可行顶点标号L开始 确定GL 并在GL中选取一个匹配M 2 若X是饱和的 则M是GL的完美匹配 是G的最佳匹配 算法终止 否则 在GL中取一个M 非饱和点u X 令S u T 二部图的赋权匹配 3 若NGL S T 则GL没有完美匹配 计算给出可行顶点标号L 以L 代替L 以GL 代替GL 否则转 4 4 在NGL S T中选择一个顶点y 若y是M饱和的 并且yz M 则用S z 代替S T y 代替T 转 3 否则取GL中一条M增广路P u y 并令M M E P 对称差 转 2 赋权匹配例1 五个人x1 x2 x3 x4 x5做五件工作y1 y2 y3 y4 y5 工作效率如下列矩阵所示 一个人只能做一件工作 问如何安排工作使总的工作效率最高 结果为14 二部图的赋权匹配例1 x1x2x3x4x5y1y2y3y4y5 赋权匹配例2 五种原材料A B C D E都可以用来生产a b c d e五种产品 成本如下列矩阵所示 一种材料只能生产一种产品 问什么生产方案使成本最低 要求写出求解过程 结果为30 2建模案例 锁具装箱问题 94B 某厂生产一种弹子锁具 每个锁具的钥匙有5个槽的高度从 1 2 3 4 5 6 中任取一数 由于工艺原因 制造锁具对5个槽的高度有两个限制 至少有3个不同的数 相邻两槽的高度之差不能为5 满足以上条件制造出来的所有互不相同的锁具称为一批 若4个相同 另一槽的高度差为1 则可能互开 其它情形不可能互开 在原来一批锁具中随机取60个装为一箱 成箱购买的顾客总抱怨购得的锁具有互开现象 如何装箱 60个为一箱 如何给箱子以标志 出售时如何利用这些标志 使团体顾客减少抱怨 第13章行遍历问题 1中国邮递员问题一 问题的提出一位邮递员从邮局出发 带着所管辖地区的信件 报纸支投递 投递结束后回到邮局 为了投递完所有邮件 当然他必须经过其所管辖的每条街道至少一次 请为他设计一条路线 使行程尽可能短 中国邮递员问题 这就是中国邮递员问题的原始模型 是我国管梅谷教授于1962年首先提出的 用图论的语言来叙述 中国邮递员问题就是在连通赋权图G上求一个回路 未必是简单的 过每边至少一次 并使回路的权最小 二 欧拉图与Fleury算法 定义设G V E 是连通无向图 1 经过G的每边至少一次的闭通路称为 巡回 回路 2 经过G的每边恰好一次的回路称为Euler回路 3 存在Euler回路的图称为Euler图 4 过每边恰好一次的 路 链称为Euler链 Euler回路 Euler链可以形象地描述为 一笔画问题 定理1连通图G是Euler图 当且仅当G中无奇度顶点 欧拉图与Fleury算法 Fleury算法 1 任取一个v0 V 令W v0 2 设链W v0e1v1e2 eivi已选定 则从E e1 e2 ei 中选取一条与ei相邻的边ei 1 除非已无选择余地 否则不要选G e1 e2 ei 的桥 3 直到 2 不能进行为止 算法终止时得到的是Euler回路 三 奇偶点图上作业法与Edmonds算法 如果G不是连通的Euler图 则G中含有奇度顶点 但奇度顶点的个数为偶数 此时图G的一条邮递路线必定在某些街着上重复走了一次或多次 它等价于在这些边上加一条或多条重复边 使新图G 不含奇度顶点 并且所加边的总权为最小 设E1表示所有新增加边的集合 它是图G边集的一个子集 如何求权最小的新增边集E1呢 奇偶点图上作业法 定理2E1为权最小的新增边集 当且仅当下列条件满足 1 E1中没有重复出现的边 2 在G的每个回路上 属于E1的边权和不超过该回路边和的一半 根据定理可以从某一可行新增边集开始 进行调整 最终得到最优解 这种方法称为 奇偶点图上作业法 奇偶点图上作业法 奇偶点图上作业法 对回路不太多的图是可行的 当回路很多时 如 田 字形的图形就有13个回路 要检查所有的回路是难以做到的 Edmonds在1965年提出了一种有效的方法 使中国邮递员问题得到了较好的解决 Edmonds算法 1 根据给定的图G 构造一个新图G G 中的顶点就是G中的所有奇度顶点 并将G 中任意两顶点都相连 此时G 是一个完全图 G 中边的权等于G中顶点与间的最短距离 2 在G 中找一个最小权完美匹配M M是G 中具有如下性质的一个边集 G 中每个点恰与M中一条边关联 且M的权最小 3 在G中将互相匹配的奇度顶点用最短路径相连 由此得到G的最小新增边集 Edmonds算法 下面用Edmonds算法求解上图的中国邮递员问题 根据图中奇度顶点v1 v2 v3 v5构造一个完全图G 如下图 求G 的最小权完美匹配M 得M v1 v2 v3 v5 其权为2 5 7 在G中加入 v1 v2 和 v3 v4 v1 v5 两条最短路 使G变为Euler图 其权值为26 7 33 2推销员问题 一 问题的提出一旅行售货员需要到邻近的50个村镇推销他的商品 最后回到出发点 问如何安排旅行路线使总行程最短 旅行售货员问题 TravelingSalesmanProblem 是NP 完备问题 推销员问题 二 Hamilton图定义1设G V E 是连通无向图 1 经过G的每个顶点正好一次的路径 称为G的一条Hamilton路径 简称H路径 2 经过G的每个顶点正好一次的圈 称为G的Hamilton圈 简称H圈 3 含Hamilton圈的图称为Hamilton图 简称H图 推销员问题 上述旅行售货员问题中顶点表示城镇 边表示连接两城镇的路 边上的权表示距离 时间 费用 于是TSP就成为在赋权图中寻找一条经过每个顶点至少一次的最短闭通路问题 定义2在赋权图G V E 中 1 权最小的Hamilton圈 称为最佳H圈 2 经过每个顶点至少一次的权最小的闭通路称为最佳推销员回路 推销员问题 一般情况 最佳Hamilton圈不一定是最佳推销员回路 反之也不一定 p213 但有下列定理 定理1设G V E 是赋权图 若对任意x y z V z x z y 都有w x y w x z w z y 则图G的最佳H圈也是最佳推销员回路 推销员问题 可以用G中任意两点的最短距离构造一个完全图G 则有定理2赋权图G的最佳推销员回路的权与G 的最佳H圈的权相同 故在赋权图中寻求最佳推销员回路的问题就可转化为在一个完全赋权图G 中寻求最佳H圈的问题 推销员问题 三 TSP近似算法二边逐次修正法 模拟退火法 弹性网法等 3建模案例 最佳灾情巡视路线 98B 下图为某县的乡 镇 村公路网示意图 公路边的数字为该路段的公里数 今年夏天该县遭受水灾 为考察灾情 组织自救 县领导决定 带领有关部门负责人到全县各乡 镇 村巡视 巡视路线指从县政府所在地出发 走遍各乡 镇 村 又回到县政府所在地的路线 若分三组 路 巡视 试设计总路程最短且各组尽可能均衡的巡视路线 假定巡视人员在各乡 镇 停留时间T 2小时 在各村停留时间t 1小时 汽车行驶速度v 35公里 小时 要在24小时内完成巡视 至少应分几组 给出这种分组下你认为最佳的巡视路线 在上述关于T t和v的假定下 如果巡视人员足够多 完成巡视的最短时间是多少 给出在这种最短时间完成巡视的要求下 你认为最佳的巡视路线 若巡视组数已定 如三组 要求尽快完成巡视 讨论T t和v改变对最佳巡视路线的影响 第14章网络流问题 1 最大流问题E油田有一个石油运输管网 Vs是石油产品产地 Vt是石油销地 边旁数子为单位时间容许的最大输油量 单位 桶 分钟 问题是决定从Vs到Vt单位时间的最大输入油量 第14章网络流问题 概念发点 source 收点 sink 中间点 C为定义在aij上的容量函数 其值cij为弧aij的容量 最大流问题 网络N上的流量指定义在弧集合A上的一个函数f 记fij f aij 若流f还满足 1 容量限制条件0 fij cij 2 流量守恒条件 fij fji 0i s t则称f为可行流 最大流问题 一个网络的可行流总是存在的 如令所有弧的流量fij 0 就得到一个流 其流量val f 0 并称该可行流为零流 确定E油田从Vs到Vt的最大输油量 也就是在所有可行流方案中确定一个使流量达到最大的方案 最大流问题 最大流问题的一般形式为 2 最大流基本定理 定义 在网络 中 若点集 被剖分为两个非空集合 使得 则把弧集称为 中的割 称为割的容量 最大流基本定理 容易证明 任何一个可行流f的流量都不会超过任一割的容量 即特别若有一可行流f和割 使上式等号成立 则f必为最大流 而必为最小割 可增路 设f是网络N的一个可行流 对于N中的每条路P 在其上定义一个非负函数 若 P 0 则称路P是f饱和的 P 0 则称路P是f非饱和的 称P为可增路 增广路 最大流基本定理 网络中f可增路P的存在意味着f不是最大流 可沿着P增加一个值为 P 的附加流量 得到由所定义的新可行流f val f val f P 称为基于P的调整流 最大流基本定理 定理1N中的可行流f是最大流当且仅当N不包含f可增路 定理2在任何网络中 最大流的流量等于最小割的容量 3 Ford和Fulkerson标号算法 1 置每个fij等于一个可行流f的对应值 若网络中没有给定f 则设f是零流 2 给发点vs标上 0 vs成为已标号而未检查的点 其它点为未标号点 3 如果不存在已标号而未检查的点 算法终