资源描述：
《匹配,邮递员问题》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、补充：0-1规划模型0-1整数线性规划是一类特殊的整数规划，它的变量值仅取0或1。形式例4一架货运飞机，有效载重量为24t，可运输物品的质量及运费收入如下表所示，其中各物品只有一件可供选择。如何选运物品运费总收入最多？物品123456质量(t)8136957收入(万元)352423解：Lingo程序为：计算结果为：max=10，x1=1,x2=0,x3=0,x4=1,x5=0,x6=1max=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);@
2、bin(x4);@bin(x5);@bin(x6);指派问题设有m项工作需分配n个人去做，每人做一项，由于各人的工作效率不同，因而完成同一工作所需要的时间也就不同，设第i人完成工作j所需时间为,问如何分配工作，使完成所有工作的总时间最少？这类问题称为指派问题(assignmentproblem),是一类重要的0-1规划问题。用0-1变量表示分配情况,例5有一份中文说明书，需译成英、日、德、俄四种文字，分别记作A、B、C、D。现有甲、乙、丙、丁四人，他们将中文说明书译成不同语种的说明书所需时间如下表所示，问如何分派任务，可使总时间最少？任务人员ABCD甲67112乙4598丙3
3、1104丁5982解：设上述表中数据矩阵为：设例如指派甲做D、乙做C、丙做A和B、丁不指派任务。则指派矩阵为此时完成任务的总时间为max{2,9,3+1}。我们的问题为如何指派，使得上述的max达到最小值。得模型为：该条件表示一件任务只能安排给一个人做。编写lingo程序计算得x14=1，x31=1，x32=1，x43=1，即工作安排为：甲做D，乙不做任何工作，丙做A和B工作，丁做C工作。SETS:xb1/1..4/;xb2(xb1,xb1):a,x;ENDSETSDATA:a=671124598311045982;ENDDATAmin=@max(xb1(i):@sum(xb
4、1(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）工作安排问题二假设有：已知工人担任工作的效率为，可得二部图。现要求每
5、人安排一件工作，使得总效率最大。即在此二部图中能否找到一个匹配其边数最大。情况一：如果各件工作之间无关，可寻求效率和达到最大。情况二：如果是一条流水线工作，则要求效率的最小值达到最大。例出席某次国际学术报告的6个成员a、b、c、d、e、f的情况为：a：会讲汉语、法语和日语；b：会讲德语、俄语和日语；c：会讲英语和法语；d：会讲汉语和西班牙语；e：会讲英语和德语；f：会将俄语和西班牙语。欲将此6人分为每两人一组，使同一组的人能交谈，是否可行？abcdef补充中国邮递员问题1问题1962年，中国数学家管梅谷教授提出问题：邮递员发送邮件时，要从邮局出发，经过他投递范围内的每条街道至
6、少一次，然后返回邮局，但邮递员希望选择一条形成最短的路线。这就是邮递员问题。若将投递区的街道用边表示，街道的长度用边权表示，邮局交叉口用点表示，则一个投递区构成一个赋权连通无向图。邮递员问题就转化为：在一个非负赋权图中，寻求一个至少经过各条边一次的权和最小的回路，这样的回路称为最佳巡回。邮政局2相关概念及定理定义设G=（V，E）是连通无向图；（1）经过G的每边正好一次的通路称为欧拉通路，图称为半欧拉图；（2）经过G的每边正好一次且回到出发点的回路称为欧拉回路，此时图称为欧拉图；定理对于非空连通图G是欧拉图的充要条件是G中无奇次顶点。推论非空连通图G是半欧拉图的充要条件是G中只
7、有两个奇度顶点。上述邮递员问题分三种情况讨论：（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})的割边（割边就是指桥，所谓桥是指去掉这条桥边后图就不连通了）
