匹配邮递员问题.pptVIP

补充：0-1规划模型;例4 一架货运飞机，有效载重量为24t，可运输物品的质量及运费收入如下表所示，其中各物品只有一件可供选择。如何选运物品运费总收入最多？;Lingo程序为：;指派问题; 例5 有一份中文说明书，需译成英、日、德、俄四种文字，分别记作A、B、C、D。现有甲、乙、丙、丁四人，他们将中文说明书译成不同语种的说明书所需时间如下表所示，问如何分派任务，可使总时间最少？;解：设上述表中数据矩阵为：; 例如指派甲做D、乙做C、丙做A和B、丁不指派任务。则指派矩阵为; 得模型为：;SETS: xb1 /1..4/; 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; );;补充 匹配;3 工作安排问题 （1）工作安排问题一 假设有： 已知工人 能胜任工作 则将 与 顶点连接一条边，可得二部图。问能否存在一种安排使尽可能多的人安排到工作，即在此二部图中能否找到一个匹配其边数最大。 ;（2）工作安排问题二 假设有： 已知工人 担任工作 的效率为 ，可得二部图。现要求每人安排一件工作，使得总效率最大。即在此二部图中能否找到一个匹配其边数最大。 ;例 出席某次国际学术报告的6个成员a、b、c、d、e、f的情况为： a：会讲汉语、法语和日语； b：会讲德语、俄语和日语； c：会讲英语和法语； d：会讲汉语和西班牙语； e：会讲英语和德语； f：会将俄语和西班牙语。 欲将此6人分为每两人一组， 使同一组的人能交谈，是否可行？;补充 中国邮递员问题 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=v0e0v1e1……eivi已经选好，则从E\{e1,e2,…,ei}中选一条边ei+1，使： a)ei+1与vi相关联； b)除非不能选择，否则一定要使ei+1不是Gi=G(E\{e1,e2,…,ei})的割边（割边就是指桥，所谓桥是指去掉这条桥边后图就不连通了）； Step3 第（2）步不能进行时就停止。;桥;（2）G不是欧拉图 若G不是欧拉图，则G的任何一个巡回经过某些边必定多于一次。解决方法是在某些点对之间引入重复边（重复边与它平行的边具有相同的权），使原图称为欧拉图，但希望所有添加的重复边的权的总和为最小。;情形1 G正好有两个奇次顶点。 设G正好有两个奇次顶点u和v，求G的最佳巡回的算法如下： （1）用Floyd算法求出奇次顶点u与v之间的最佳巡回P； （2）令 ，则 为欧拉图； （3）用Fleury算法求出 的欧拉巡回，这就是G的最佳巡回。;推广：如果有4个奇次顶点，则如果走过所