匹配,邮递员问题.ppt

补充：0-1规划模型 0-1整数线性规划是一类特殊的整数规划，它的 变量值仅取0或1。 形式 例4 一架货运飞机，有效载重量为24t，可运输物品 的质量及运费收入如下表所示，其中各物品只有一 件可供选择。如何选运物品运费总收入最多？ 物品1 2 3 4 5 6 质质量(t)8 13 6 9 5 7 收入(万元) 3 5 2 4 2 3 解 ： Lingo程序为： 计算结果为：max=10， x1=1,x2=0,x3=0,x4=1,x5=0,x6=1 max=3*x1+5*x2+2*x3+4*x4+2*x5+3*x6; 8*x1+13*x2+6*x3+9*x4+5*x5+7*x6=24; bin(x1); bin(x2); bin(x3); bin(x4); bin(x5); bin(x6); 指派问题 设有m项工作需分配n个人去做，每人做一项， 由于各人的工作效率不同，因而完成同一工作所需 要的时间也就不同，设第i人完成工作j所需时间为 ,问如何分配工作，使完成所有工作的总时间最少 ？这类问题称为指派问题(assignment problem), 是一类重要的0-1规划问题。 用0-1变量 表示分配情况, 例5 有一份中文说明书，需译成英、日、德、 俄四种文字，分别记作A、B、C、D。现有甲、乙 、丙、丁四人，他们将中文说明书译成不同语种的 说明书所需时间如下表所示，问如何分派任务，可 使总时间最少？ 任务 人员 ABCD 甲67112 乙4598 丙31104 丁5982 解：设上述表中数据矩阵为： 设 例如指派甲做D、乙做C、丙做A和B、丁不指 派任务。则指派矩阵为 此时完成任务的总时间为max2,9,3+1。 我们的问题为如何指派，使得上述的max达到 最小值。 得模型为： 该条件表示一件任务 只能安排给一个人做 。 编写lingo程序计算得x14=1，x31=1，x32=1，x43=1， 即工作安排为：甲做D，乙不做任何工作，丙做A和 B工作，丁做C工作。 SETS: xb1 /14/; xb2 (xb1,xb1):a,x; ENDSETS DATA: a= 6 7 11 2 4 5 9 8 3 1 10 4 5 9 8 2; ENDDATA min=max(xb1(i): sum(xb1(j):a(i,j)*x(i,j); ); for( xb2(i,j): bin(x(i,j); ); for(xb1(j): sum(xb1(i):x(i,j)=1; ); 程序为： 补充 匹配 1 匹配概念 设图G=（V，E）， ，若M的边互不相邻， 则称M是G的一个匹配。 最大匹配完美匹配 2 二部图概念 有一个比较重要的问题 是最大匹配如何寻找 3 工作安排问题 （1）工作安排问题一 假设有： 已知工人 能胜任工作 则将 与 顶点连接 一条边，可得二部图。问能否存在一种安排使尽可能 多的人安排到工作，即在此二部图中能否找到一个匹 配其边数最大。 （2）工作安排问题二 假设有： 已知工人 担任工作 的效率为 ，可得二部 图。现要求每人安排一件工作，使得总效率最大。即 在此二部图中能否找到一个匹配其边数最大。 情况一：如果各件工作之间无关，可寻求效率和达到最 大。 情况二：如果是一条流水线工作，则要求效率的最小值 达到最大。 例 出席某次国际学术报告的6个成员a、b、c、d、e、f的 情况为： a：会讲汉语、法语和日语； b：会讲德语、俄语和日语； c：会讲英语和法语； d：会讲汉语和西班牙语； e：会讲英语和德语； f：会将俄语和西班牙语。 欲将此6人分为每两人一组， 使同一组的人能交谈，是否可行？ a b c d e f 补充 中国邮递员问题 1 问题 1962年，中国数学家管梅谷教授提出问题：邮递 员发送邮件时，要从邮局出发，经过他投递范围内的 每条街道至少一次，然后返回邮局，但邮递员希望选 择一条形成最短的路线。这就是邮递员问题。 若将投递区的街道用边表示，街道的长度用边权表 示，邮局交叉口用点表示，则一个投递区构成一个赋 权连通无向图。邮递员问题就转化为：在一个非负赋 权图中，寻求一个至少经过各条边一次的权和最小的 回路，这样的回路称为最佳巡回。 邮政局 2 相关概念及定理 定义 设G=（V，E）是连通无向图； （1）经过G的每边正好一次的通路称为欧拉通路，图称 为半欧拉图； （2）经过G的每边正好一次且回到出发点的回路称为欧 拉回路，此时图称为欧拉图； 定理 对于非空连通图G是欧拉图的充要条件是G中无奇 次顶点。 推论 非空连通图G是半欧拉图的充要条件是G中只有两 个奇度顶点。 上述邮递员问题分三种情况讨论： （1）G是欧拉图 此时G得任何一个欧拉回路都是最佳巡回，欧拉回路由 Fleury算法可求出。 Fleury算法（能不走桥就不走桥）： Step1 任选一个顶点v0，令道路w0=v0； Step2 假定道路wi+1=v0e0v1e1eivi已经选好， 则从Ee1,e2,ei中选一条边ei+1，使： a)ei+1与vi相关联； b)除非不能选择，否则一定要使ei+1不是 Gi=G(Ee1,e2,ei)的割边（割边就是指桥，所谓桥是 指去掉这条桥边后图就不连通了）； Step3 第（2）步不能进行时就停止。 桥 桥 （2）G不是欧拉图 若G不是欧拉图，则G的任何一个巡回经过某些边必 定多于一次。解决方法是在某些点对之间引入重复边（ 重复边与它平行的边具有相同的权），使原图称为欧拉 图，但希望所有添加的重复边的权的总和为最小。 边被重复走两次 边被重复走两次 情形1 G正好有两个奇次顶点。 设G正好有两个奇次顶点u和v，求G的最佳巡回的算 法如下： （1）用Floyd算法求出奇次顶点u与v之间的最佳巡回P ； （2）令 ，则 为欧拉图； （3）用Fleury算法求出 的欧拉巡回，这就是G的最 佳巡回。 1 3 5 2 4 推广：如果有4个奇次顶点，则如果走过所有的边一次 不给重复走的话一定停在某个奇次顶点，如果想到达新 的顶点必须要经过已走过的边，那么如何走边使得经过 的边权重总和最小呢？ 3 1 2 4 4 1 1 1 3 4 2 1 1 4 1 1 情形2 G有2n个奇次顶点 注：解决方案为考虑奇度顶点添加奇数条边，偶度顶点添加偶数条 边（当然也可不添加），使得新图为欧拉图，同时新添加的边权重 之和达到最小。此种方法等价于下述方法。 Edmonds最小对集算法（1965年）： 先将图G中的奇次顶点配对，求最佳配对，即点对之 间距离总和最小。再沿点对之间的最短路径添加重复 边得欧拉图 ， 的欧拉回路即原图的最佳巡回。 算法： （1）用Floyd算法求出所有奇次顶点之间的最短路径 和最短距离； （2）将2n个奇次顶点两两配对添加n条边（该边即为 上述求出的最短距离），将这n条边添加到G中得新图 ，则 为欧拉图，其任一欧拉回路即为G的最佳巡回 ； （3）用Fleury算法求出 的欧拉回路，即G的最佳 巡回。 注：添加的n条配对边有什么要求？ G的最佳巡回（即 的欧拉回路）是在原图G中 所有的边经过一次且仅一次，又在新添加的n条新边中 经过一次且仅一次。原图G中所有边的权重和是固定 不变的，可变的是添加的n条新边的权重之和，所以我 们需要找出哪一种配对边其权重之和最小（可穷举）。 例 1 100 100 1 1 100 1 100 1 1 100 100 奇次顶点奇次顶点奇次顶点 奇次顶点奇次顶点奇次顶点 3 1 2 应用 例如送奶工送奶线路，物流公司的物流配送等问 题都可以转化为最佳巡回。 例 求下图G的一条最佳邮递路线。 v1 4 v2 2 v3 1 2 5 1 v7 9 v8 3 v4 1 6 3 8 1 v9 v6 10 v5 解：图G中有4个奇度顶点，v4、v7、v8、v9。用 Floyd算法求出它们之间的最短路径和距离如下： Pv4v7=v4v3v2v7, d(v4,v7)=5 Pv4v8=v4v8, d(v4,v8)=3 Pv4v9=v4v8v9, d(v4,v9)=6 Pv7v8=v7v8, d(v7,v8)=9 Pv7v9=v7v9, d(v7,v9)=6 Pv8v9=v8v9, d(v8,v9)=3 以v4、v7、v8、v9为顶点，它们之间的最短距离 为边权构造完备图G1如下： v8 v7 5 v4 9 3 3 6 6 v9 求出最小权完美匹配M=(v4,v7),(v8,v9)。 v1 4 v2 2 v3 1 2 5 1 v7 9 v8 3 v4 1 6 3 8 1 v9 v6 10 v5 补充 推销员问题 1 引例 1895年，爱尔兰数学家哈密尔顿，发明了一种叫做周 游世界的遊戏，他用一个正十二面体的20个顶点代表 20个城市，要求从一个城市出发沿着棱，经过每个城 市恰好一次，然后回到出发的城市。这个问题已由哈 密尔顿本人解决。 2 哈密尔顿图 定义 经过连通图G的每一个顶点一次且仅一次回到出 发点，这种回路称为哈密尔顿回路。存在哈密尔顿回 路的图称为哈密尔顿图。 注意: 经过顶点要求一次且仅一次，边不要 求全部经过，但经过的只能经过一次 。 例 下图不是哈密尔顿图，但存在哈密尔顿通路。例 如abcgedf 是一条哈密尔顿通路。 判断某图是否为哈密尔顿图至今还是一个难题 ！ 目前只有一些充分条件，还没有适合可行的充要条件 。 3 推销员问题 流动推销员需要访问某地区的所有城镇，最后 回到出发点。问如何安排旅行线路使总路程最短。 在图中则上述问题等价为： 在加权图中寻找一条经过每个顶点至少一次的 最短回路问题。 最佳推销员回路问题可以转化为最佳哈密尔顿回 路问题。方法为： 由给定的图（，）构造一个以为顶点 集的图 ， 的每条边的权等于顶点与 在图中最短路的权。即： 加权图的最佳推销员回路的权与 的最佳哈 密尔顿回路的权相同。 因此，在加权图中寻找最佳推销员回路的问题就 转化为在一个完备加权图 中寻求最佳哈密尔顿回路 的问题，称为问题。 近似算法 （二边逐次修正法）： （）任取初始回路： （）对所有的 ，若 则在 中删去边 和 而加入边 和 ，形成新的回路C，即 v1 vi+1 vi vn vj+1 vj vj-1 v1 vi vi+1 vn vj+1 vj vj-1 例 某快递公司业务员小王发送货物给v1、v2、v3、v4 、v5、v6地方的购物者，自己所在地为v1，之间的路 线距离如下图，请为他设计一个比较好的路线使得走尽 可能少的路程。 注：不同的H回路的选取方法则最后结果可能不同 。TSP近似算法得到的解不一定是最优解。 v1 v2 v3 v5 v4 v6 60 51 2 35 70 78 57 21 13 68 61 36 68 51 56 邻接矩阵为： 解：首先任选一H回路v1v2v3v4v5v6v1，可以看出， w(v1,v4)+w(v2,v5)w(v1,v2)+w(v4,v5)， 所以删去边(v1,v2),(v4,v5)，加入边(v1,v4),(v2,v5) 得新的H回路v1v4v3v2v5v6v1, v1 v4 v3 v2 v5 v6 (b) 60 78 56 70 v1 v2 v3 v4 v5 v6 56 51 2 78 (a) v1 v5 v6 v2 v3 v4 (c) 51 36 35 51 v1 v3 v2 v6 v5 v4 (d) 例 某城市有一著名的湖泊，沿湖泊四周建了6个城镇， 城镇之间有如下图中的交通路线相连，路程亦如下图。 政府建在v2点，某年夏天突降暴雨城镇受灾，政府拟派 出一队巡查组，到6个城镇巡查受灾情况。请安排最优 巡查路线。 v1 v2 v3