《匹配,邮递员问题》由会员分享，可在线阅读，更多相关《匹配,邮递员问题（44页珍藏版）》请在金锄头文库上搜索。
1、补充：0-1规划模型,0-1整数线性规划是一类特殊的整数规划，它的变量值仅取0或1。形式,例4 一架货运飞机，有效载重量为24t，可运输物品的质量及运费收入如下表所示，其中各物品只有一件可供选择。如何选运物品运费总收入最多？,解：,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
2、项工作需分配n个人去做，每人做一项，由于各人的工作效率不同，因而完成同一工作所需要的时间也就不同，设第i人完成工作j所需时间为 ,问如何分配工作，使完成所有工作的总时间最少？这类问题称为指派问题(assignment problem), 是一类重要的0-1规划问题。,用0-1变量 表示分配情况,例5 有一份中文说明书，需译成英、日、德、俄四种文字，分别记作A、B、C、D。现有甲、乙、丙、丁四人，他们将中文说明书译成不同语种的说明书所需时间如下表所示，问如何分派任务，可使总时间最少？,解：设上述表中数据矩阵为：,设,例如指派甲做D、乙做C、丙做A和B、丁不指派任务。则指派矩阵为,此时完成任务的总
3、时间为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 24 5 9 83 1 10 45 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
4、(i,j)=1;);,程序为：,补充 匹配,1 匹配概念设图G=（V，E）， ，若M的边互不相邻，则称M是G的一个匹配。,最大匹配,完美匹配,2 二部图概念,有一个比较重要的问题是最大匹配如何寻找,3 工作安排问题 （1）工作安排问题一 假设有：已知工人 能胜任工作 则将 与 顶点连接一条边，可得二部图。问能否存在一种安排使尽可能多的人安排到工作，即在此二部图中能否找到一个匹配其边数最大。,（2）工作安排问题二 假设有：已知工人 担任工作 的效率为 ，可得二部图。现要求每人安排一件工作，使得总效率最大。即在此二部图中能否找到一个匹配其边数最大。,情况一：如果各件工作之间无关，可寻求效率和达到最
5、大。 情况二：如果是一条流水线工作，则要求效率的最小值达到最大。,例 出席某次国际学术报告的6个成员a、b、c、d、e、f的情况为： a：会讲汉语、法语和日语； b：会讲德语、俄语和日语； c：会讲英语和法语； d：会讲汉语和西班牙语； e：会讲英语和德语； f：会将俄语和西班牙语。 欲将此6人分为每两人一组， 使同一组的人能交谈，是否可行？,补充 中国邮递员问题 1 问题1962年，中国数学家管梅谷教授提出问题：邮递员发送邮件时，要从邮局出发，经过他投递范围内的每条街道至少一次，然后返回邮局，但邮递员希望选择一条形成最短的路线。这就是邮递员问题。若将投递区的街道用边表示，街道的长度用边权表示
6、，邮局交叉口用点表示，则一个投递区构成一个赋权连通无向图。邮递员问题就转化为：在一个非负赋权图中，寻求一个至少经过各条边一次的权和最小的回路，这样的回路称为最佳巡回。,2 相关概念及定理 定义 设G=（V，E）是连通无向图； （1）经过G的每边正好一次的通路称为欧拉通路，图称为半欧拉图； （2）经过G的每边正好一次且回到出发点的回路称为欧拉回路，此时图称为欧拉图；,定理 对于非空连通图G是欧拉图的充要条件是G中无奇次顶点。 推论 非空连通图G是半欧拉图的充要条件是G中只有两个奇度顶点。上述邮递员问题分三种情况讨论： （1）G是欧拉图 此时G得任何一个欧拉回路都是最佳巡回，欧拉回路由Fleury
7、算法可求出。,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的任何一个巡回经过某些边必定多于一次。解决方法是在某些点对之间引入重复边（重复边与它平行的边具有相同的权），使原图称为欧拉图，但希望所有
8、添加的重复边的权的总和为最小。,边被重复走两次,边被重复走两次,情形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,11,3 4 2,1,1,4,11,情形2 G有2n个奇次顶点,注：解决方案为考虑奇度
9、顶点添加奇数条边，偶度顶点添加偶数条边（当然也可不添加），使得新图为欧拉图，同时新添加的边权重之和达到最小。此种方法等价于下述方法。,Edmonds最小对集算法（1965年）：先将图G中的奇次顶点配对，求最佳配对，即点对之间距离总和最小。再沿点对之间的最短路径添加重复边得欧拉图 ， 的欧拉回路即原图的最佳巡回。,算法： （1）用Floyd算法求出所有奇次顶点之间的最短路径和最短距离； （2）将2n个奇次顶点两两配对添加n条边（该边即为上述求出的最短距离），将这n条边添加到G中得新图 ，则 为欧拉图，其任一欧拉回路即为G的最佳巡回； （3）用Fleury算法求出 的欧拉回路，即G的最佳巡回。 注
10、：添加的n条配对边有什么要求？G的最佳巡回（即 的欧拉回路）是在原图G中所有的边经过一次且仅一次，又在新添加的n条新边中经过一次且仅一次。原图G中所有边的权重和是固定不变的，可变的是添加的n条新边的权重之和，所以我们需要找出哪一种配对边其权重之和最小（可穷举）。,例,1 100 100 1,1 100 1 100 1,1 100 100,奇次顶点,奇次顶点,奇次顶点,奇次顶点,奇次顶点,奇次顶点,3 1 2,应用 例如送奶工送奶线路，物流公司的物流配送等问题都可以转化为最佳巡回。,例 求下图G的一条最佳邮递路线。,解：图G中有4个奇度顶点，v4、v7、v8、v9。用Floyd算法求出它们之间的
11、最短路径和距离如下： 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如下：,求出最小权完美匹配M=(v4,v7),(v8,v9)。,补充 推销员问题,1 引例 1895年，爱尔兰数学家哈密尔顿，发明了一种叫做周游世界的遊戏，他用一个正十二面体的20个顶点代表20个城市，要求从一个城市出发
12、沿着棱，经过每个城市恰好一次，然后回到出发的城市。这个问题已由哈密尔顿本人解决。,2 哈密尔顿图 定义 经过连通图G的每一个顶点一次且仅一次回到出发点，这种回路称为哈密尔顿回路。存在哈密尔顿回路的图称为哈密尔顿图。,注意:,经过顶点要求一次且仅一次，边不要求全部经过，但经过的只能经过一次。,例 下图不是哈密尔顿图，但存在哈密尔顿通路。例如abcgedf 是一条哈密尔顿通路。,判断某图是否为哈密尔顿图至今还是一个难题 ！ 目前只有一些充分条件，还没有适合可行的充要条件。,3 推销员问题流动推销员需要访问某地区的所有城镇，最后回到出发点。问如何安排旅行线路使总路程最短。 在图中则上述问题等价为：在
13、加权图中寻找一条经过每个顶点至少一次的最短回路问题。,最佳推销员回路问题可以转化为最佳哈密尔顿回路问题。方法为：由给定的图（，）构造一个以为顶点集的图 ， 的每条边的权等于顶点与在图中最短路的权。即：, 加权图的最佳推销员回路的权与 的最佳哈密尔顿回路的权相同。因此，在加权图中寻找最佳推销员回路的问题就转化为在一个完备加权图 中寻求最佳哈密尔顿回路的问题，称为问题。, 近似算法 （二边逐次修正法）： （）任取初始回路： （）对所有的 ，若则在 中删去边 和 而加入边 和 ，形成新的回路C，即,例 某快递公司业务员小王发送货物给v1、v2、v3、v4、v5、v6地方的购物者，自己所在地为v1，之
14、间的路线距离如下图，请为他设计一个比较好的路线使得走尽可能少的路程。,注：不同的H回路的选取方法则最后结果可能不同。TSP近似算法得到的解不一定是最优解。,邻接矩阵为：,解：首先任选一H回路v1v2v3v4v5v6v1，可以看出， w(v1,v4)+w(v2,v5)w(v1,v2)+w(v4,v5)， 所以删去边(v1,v2),(v4,v5)，加入边(v1,v4),(v2,v5) 得新的H回路v1v4v3v2v5v6v1,例 某城市有一著名的湖泊，沿湖泊四周建了6个城镇，城镇之间有如下图中的交通路线相连，路程亦如下图。政府建在v2点，某年夏天突降暴雨城镇受灾，政府拟派出一队巡查组，到6个城镇巡查受灾情况。请安排最优巡查路线。,湖泊,解：由Floyd算法计算得：,D =0 3 4 4 1 73 0 1 3 2 54 1 0 2 3 44 4 3 0 3 31 2 3 3 0 67 5 4 3 6 0 R =1 5 5 5 5 55 2 3 3 5 32 2 3 4 2 65 3 3 4 5 61 2 2 4 5 65 3 3 4 5 6,
