数学与应用数学论文-中国邮递员问题的数学模型

数学与应用数学 论文 政研论文下载论文大学下载论文大学下载关于长拳的论文浙大论文封面下载 -中国邮递员问题的数学模型 目 录 前 言.............................................................................................................................. 0 1 第一章 中国邮递员问题的整数 规划 污水管网监理规划下载职业规划大学生职业规划个人职业规划职业规划论文 模型 ................................................................. 1.1 图论中模型.................................................................................................... 1 [5]1.2 中国邮递员问题的整数规划模型............................................................... 5 1.2.1 传统中国邮递员问题的建模................................................................ 5 1.2.2 广义中国邮递员问题及其建模............................................................ 6 [7]1.2.3 随机中国邮递员问题及其建模....................................................... 10 第二章 中国邮递员问题的DNA计算................................................................... 13 2.1 DNA计算模型 ............................................................................................ 13 2.2 中国邮递员问题的图论模型变换................................................................ 14 [11] 中国邮递员问题的DNA算法.................................................................... 15 2.3 2.4 总结................................................................................................................ 18 第三章 中国邮路问题的数学模型 ......................................................................... 19 3.1 问题的重述.................................................................................................... 19 3.2 需解决的问题................................................................................................ 20 3.3 问题假设........................................................................................................ 20 3.4 符号说明........................................................................................................ 21 3.5 问题一的建模与求解.................................................................................... 22 (一) 模型的分析与建立.......................................................................... 23 3.6 模型的求解.................................................................................................... 26 结 语............................................................................................................................ 29 致 谢............................................................................................................................ 30 参考文献...................................................................................................................... 31 北方民族大学学士学位毕业论文 前 言 图论是一个新的数学分支，也是一门很有实用价值的学科，它在自然科学，社会科学等各领域均有很多应用。近年来，计算机技术在图论中的应用使得图论得到飞速的发展，应用范围也不断拓广，已渗透到诸如语言学，逻辑学，物理学，化学，电讯工程，计算机科学以及数学的其它分支中。特别在计算机科学中，如形式语言，数据结构，分布式系统，操作系统等方面均扮演着重要的角色。 最早的图论问题要追溯到1736年的哥尼斯堡七桥问题，而且在19世纪关于图论的许多重要结论都已相继提出。但是直到20世纪20年代图论才引起广大学者的注意并得以广泛接受和传播。 其实现实生活中的许多问题都是可以通过图论中的相关知识得以解决的，这些例子俯拾即是。例如，住在城市里的人出行的街道, 抽象出来就是由顶点(结点)和边(线) 构成的图, 在这个图上, 清洁工人必须把这个城市的所有街道清扫一遍，也就是走完所有的边，于是, 清洁工人马上遇到一个十分重要的图论问题: 怎样扫才能一条不落地把所有街道扫上一遍，而且使得所走的总路程最短，这就是典型的欧拉回路问题。再如，有一个推销员，他要去n个城市推销他的商品，因此他要从他所居住的城市出发，走遍他所有想去推销商品的城市，再回到他居住的城市，于是, 推销员马上遇到另一个十分重要的图论问题: 怎样扫才能一个城市不落地把所有城市走一遍，而且使得所走的总路程最短，这就是典型的哈密顿回路问题。 在现实生活中，由于大多数人不懂图论知识，或者虽然懂一点图论知识，但不知道如何将图论中的知识运用到我们的生活实践中去，导致我们的效率低下，有时甚至使得我们的工作难于完成。因此，研究图论知识及其应用有着非常重要的意义。本文将讨论中国邮递员问题，以帮助大家增加图论知识并解决现实生活中的一些实际问题。 第 0 页 共 34 页 北方民族大学学士学位毕业论文 第一章 中国邮递员问题的整数规划模型 关于邮递员最优投递路线问题最早是由管梅谷首先提出并进行研究的，国际上现在统称之为中国邮递员问题。早期关于中国邮递员问题的讨论总是基于无向图展开的，事实上，由于单行线或上下行路线的坡度等原因，这一问题有时必须借助于有向图来进行研究和解决。到目前为止，对中国邮递员问题的研究主要是从图论角度展开的，给出的多数都是各种启发式算法或递推算法。本章讨论了数学规划模型，数学规划建模具有借助软件包求解方便、易于修改和推广等多方面的优点，即使对于大型问题也易于建模分析和解决的优点。 1.1 图论中模型 e,E(G)任给定一个图G，对E(G)加权，即对每个，任意指定一个非负实 [1] ,(e)，求G的一个含有一切边回路W，使得W的总权数 ,(e),min. , e,W 如果G是Euler图，则所求的中国邮路W就是一条Euler回路。1921年，Fleury给出求Euler图G中一个Euler回路的算法。值得指出的是，即使已知G是Euler图，如果没有一定的路线遵循，也不是漫不经心就可以找出它的一个Euler回路 v的，例如图1-1是Euler图，设从开始，寻找一条Euler回路，如果开始三1 vvvvvK步是就失败了，因为回到之后发现左侧的上的边还没有用过，而132151 v的关联边已全用过，不能从再去通过左侧那些未用过的边了(注意每边只v11 vv能用一次)。究其失败的原因，是因为用了边之后，在未用过的边们导出的13 vvvvK子图上，是桥，提前过桥的后果是断了去左侧的后路。这里的教训32325 是，非必要时，不要通过未用过的边的导出子图的桥，根据这一思路，Fleury [2]设计了如下求Euler回路的有效算法，代号FE算法: W,vv,V(G)(1)任取，令; 000 第 页 共34页 1 中国邮递员问题的应用研究 图 1-1 eW,vvv？vE(G),E(W)(2)设行迹已选定，则从中选一条边，i，1i012i eve使得与相关联，且非必要时不要选G,E(W)的桥; i，1ii，1 e,E(G)(3)反复执行(2)，直至每边皆入选为止。 O(|E(G)|)FE算法是有效算法，其时间复杂度是。 用FE算法在上图中可选得Euler回路: W,vvvvvvvvvvvvvv 321 FE算法的正确性证明如下: W,vvv？v 令G是Euler图，是FE算法终止时得到的行迹，由算n012n vv,vWG,E(W)法知在中的次数为零，显然，于是是G的一条闭行迹，nn0nn WWV下证就是G的Euler回路，反证之，若不是G的Euler回路，设是nn1 v,VG,E(W)V,,中次数非零的顶组成的顶子集。容易看出，且。令n1n1 v,Vv,Vv,VV,V(G),V，则;设m是，而的v的下标的最大值，m1n2m，1221 eWG,E(W)V见图2-2。由于的终点在中，于是是的桥，设e是m，1nm2 vG,E(W)e,eG,E(W)中与关联的边。且，由算法知e为的桥，故emm，1mm GGVG,E(W)G,E(W)V也是在中导出的子图的桥。设是在中导出的mnmm11 GGGG,G子图，则，于是每顶皆偶次，中无桥，与e是的桥矛盾。 mmmmn 第 2 页 共 34 页 北方民族大学学士学位毕业论文 图 1-2 下面讨论加权图G中有奇次顶时中国邮路问题的解法。这种情形有的边不得 已要通过至少两次，哪些边要通过不止一次才能使得完成投递的时间最短呢,让 [3]我们通过一个实例来探讨这一问题。 ,(e)在图1-3中，边旁写的是权 图 1-3 (1)在图1-3中，奇次顶集为 V,{v,v,v,v} 01234 V(2)在中，每对顶的距离为(Dijkstra算法去求) 0 d(v,v),4,d(v,v),5,d(v,v),2121314 d(v,v),3,d(v,v),5,d(v,v),3232434 V(K),{v,v,v,v}K(3)构造完全加权图，，边权 412344 ,(vv),d(v,v),i,j,1,i,j,4，见图1-4: ijij 第 页 共34页 3 中国邮递员问题的应用研究 图 1-4 M,{vv,vv}K(4)求(3)中的最佳(总权最小)的完备匹配， M14234 P(v,v),vuvv(5)在G中求得和间最短轨;与间最短轨vvv314114142P(v,v),vuv 23243 [4]P(v,v)P(v,v)(6)在G中沿与把边变成同权“倍边”，见图5 2314 图 1-5 (7)在Euler图1—5上用FE算法求得一条Euler回路 W,vuvvuvvuuvvuuvuuvuuuuuv ， 52611W即为所求的中国邮路(不唯一) 上述解法具有代表性，一般的中国邮路解法步骤总结如下: 设G是连通加权图 V,{v|v,V(G),d(v),1(mod2)}(1)求G中奇次顶集合. 0 第 4 页 共 34 页 北方民族大学学士学位毕业论文 Vd(u,v)u,v(2)对中的每个顶对，用Dijkstra算法求距离. 0 KKV(K),Vd(u,v)uv(3)够作加权完全图,，中边之权为. |V||V||V|0000 K(4)求加权图的总权最小的完备匹配M. |V|0 (5)在G中秋M中同一边之端点间的最短轨. (6)把G中在(5)求得的每条最短轨之边变成同权倍边，得Euler图G'. (7)用FE算法求G'的一条Euler回路W'，W'即为中国邮路. [5]1.2 中国邮递员问题的整数规划模型 1.2.1 传统中国邮递员问题的建模 [6]传统的中国邮递员问题可以概述如下:一个邮递员每次送信要从其所在的邮局出发，走遍所负责投递范围内的每条街道，完成送信任务后回到原来的邮局，应该选择怎样的路线行走，才能使得所走的总路程数最小。把该问题抽象成图论 ，E)，其中:V,{V,V,？,V}问题就是给定一个连通图G(V是顶点的集合，表12n 示街道交汇的地方;E是顶点间边的集合，表示街道，即 e,EE,{e,(V,V);顶点V与V间有边e}，每个边上有非负ijijijijij w(e),w(V,V)，表示边即街道的长度。问题是要确定G的一个子图(是一个圈)，ijij 它过每条边至少1次，而且使得该圈的总权(即图上各边的和)最小。 从图论知识知，若G不含有奇点(即相邻边的个数为奇数)，则G有圈，它过每边1次且仅仅1次，所以这个圈就是所要求的圈。若G含有奇点(即相邻边的 Ve,(V,V)个数为奇数)，则G的任一过每边至少上通过了k次，设，就在与iijij eeV之间添加k-1条新边，并令这些条新边的权都等于边的权，称这些新边为ijijj 的添加边。显然，若边e上的添加边多余1条，那么去掉其中偶数条后，得到的图中任一过每边至少1次的圈的总权不会增大。因此可以假定每边上添加边的个数至多1条。这样，寻找邮递员最优投递路线的问题就可以归结为如下: VVe,(V,V),E给定连通图G(V，E)，每条边对应的顶点和之间添加1jiij 第 页 共34页 5 中国邮递员问题的应用研究 '条边，得到边数双倍于G的另一个连通图G′(V，E′)，求 E′，e,(V,V)E1ji E使不含奇点且总权为最小。 EG(V,E)w(e)1,11e,E e若 ，则记为或(i，j)，而相应的添加边为，与边e,(V,V),Ee,Ej,iijiji,j ''xVVe,E相对应，设定0-1整数变量。若e,E，即称边是从到的，或i,jjiijij,, x称为弧。这样，就可以把无向图理解为有向图。每个E惟一对应一组的值，i，j1 x反之亦然。可以借助变量(i=1，2，„，n; j=1，2，„，n)来定义最优投i，j 递员问题的约束如下: (1)过每边至少1次且添加边至多1条，E1对应的所有的xi，j的值(称为E1的值系),e,E,x，x,1满足:对 i,ji,jj,i (2)图不含奇点，即对于任意一个顶点Vi，有进向弧，必有与之等G(V,E)11 量的出向弧:这一问题的目标是使得的总权最小，即G(V,E)x,x,0,,jiij11,,ji,,ij wewxw,wmin ，其中，为边上的权，。 ,i,ji,ji,ji,jj,ii,j'(i,j),E 这样，就得到中国邮递员问题的显式整数规划模型(CPP)如下 min,wx i，ji，j’,E(i，j) ,,,,xx0,i1,2,？,njiij,,,,,ji ''jiEjiE,(,),(,),,，,,,s.t.xx1,(i,j)E,ijji,, (1) ,',,,x0或1,,(i,j)Eij,, ,, 这一模型不仅可以用于求解中国邮递员问题，而且可以确定相应的最优投 eVxV递路线:如=1，即表示邮递员应该从沿着边(即街道)到。 ijji,ji 1.2.2 广义中国邮递员问题及其建模 上节所述的邮递员问题，假定了邮递员投递范围内的每条街道的上行和下行是无差别的，而在实际信件的投递过程中可能不是这样的，如遇到单行线街道、街道有一定的坡度、街道两边不能单行中同时投递等。这样的邮递 第 6 页 共 34 页 北方民族大学学士学位毕业论文 员问题称之为广义的中国邮递员问题。这一广义的中国邮递员问题可以抽象为一个有向图问题。 类似于前面所述的邮递员问题(称为传统的中国邮递员问题)，广义的邮递员问题可以叙述为:给定一个连通有向图G(V，E)，每个弧e上有非负权w(e)，需要寻找G的一个回路，它过每个弧至少1次，且使得总权为最小。 对于广义的中国邮递员问题，添加弧的个数至多1条有时已经不再可行，即需要多条添加弧，才能使对应的连通有向图G的任一顶点的进向弧数与出 VV向弧数相同，从而使G′(V，E′)存在回路(E回路)。在此，如e=(，)ji VV?E，则称弧e是顶点的进向弧，同时也是顶点的出向弧。可以证明，ji 如G(V，E)的顶点数为n，则每条弧上至多增加(n-1)条添加弧，即可实现各顶点的进向弧数与出向弧数相等。 ex根据以上分析，对于G(V，E)的每条弧?E定义一正整数变量，表i,ji,j e(x)示弧上增加了条添加弧，由此形成另一个有向图G′(V，E′)。类i,ji,j,1 似于上节的分析，可以有如下广义中国邮递员问题的显式整数规划模型 ,,2(GCPP): minwx,i,ji,j(i,j),E ,？x,x0,,i1,2,,,n,,j,ii,j,jj.s.t,,,(j,i)E(j,i)E (2) ,x1,2,,...,或n，(i,,j)E,i,j, 通过这一模型的求解，可以得到广义中国邮递员问题的最优投递路线。下面 我们通过具体的数值示例来对上述两个模型进行应用求解: 算例1:考虑图1-6所示的中国邮递员问题: 第 页 共34页 7 中国邮递员问题的应用研究 图1-6 传统中国邮递员问题 根据前面的模型讨论，这一数值例示邮递员问题对应的整数规划模型如下: + ，，，，，，，，2x，x，4x，x，5x，x，3x，xmin1,88,18,77,81,22,18,99,8 ，，+ ，，，，，，，，，4x，x3x，x，6x，x，4x，x，5x，x9,44,96,77,62,99,29,66,93,22,3 ，，，，，，4x，x，9x，x，4x，x 5,66,53,44,34,55,4 x，x,x,x,0,2,18,11,21,8,x，x，x,x,x,x,01,29,23,22,12,92,3, ,x，x,x,x,02,34,33,23,4,x，x，x,x,x,x,03,49,45,44,34,94,5, ,x，x,x,x,06,54,55,65,4,x，x，x,x,x,x,0,7,69,65,66,76,96,5 ,x，x,x,x,06,78,77,67,8,,x，x，x,x,x,x,0s.t.,1,87,89,88,18,78,9 ,x，x，x，x,x,x,x,x,02,94,96,98,99,29,49,69,8, x，x,1,x，x,1,1,88,18,77,8,x，x,1,x，x,11,22,18,99,8, ,x，x,1,x，x,16,77,62,99,2,x，x,1,x，x,19,66,92,33,2, ,x，x,1,x，x,19,44,95,66,5,xxxxx或，,1,，,1,,01, (3) 3,44,34,55,4i,j, 应用整数规划求解工具QSB，求解得到这一问题的最优解， x,x,x,x,x,x,x,x,x,x,x,x如: 1,22,11,88,18,79,87,62,93,26,94,39,4 ,x,x,x,x,1 5,66,55,44,5 x,0V其他，最小权重为68。假定邮局在顶点，则有如下最优投递线路: i,j1 第 8 页 共 34 页 北方民族大学学士学位毕业论文 e,e,e,e,e,e,e,e,e,e,e,e,1,22,99,88,77,66,55,66,99,44,55,44,3 e,e,e,e3,22,11,88,1 注意，这一问题的最优投递路线不惟一。同理可以求得邮局从任何一顶点出发时的最优投递路线。 算例2: 考虑图1-7所示的广义中国邮递员问题。 图1-7 广义中国邮递员问题 相应的广义中国邮递员问题的整数规划模型如下: 2x，8x，x，6x，7x，x，5x，x，2x，9x，4x，min1,21,43,12,44,32,55,46,47,23,76,7 3x，2x，x，6x，3x，x，x，7x，9x，2x，4x6,58,55,99,67,97,1010,99,88,1111,910,11 x,x,x,0,3,11,21,4,,,,0xxx1,22,42,5, ,,,,0xxx4,33,13,7,x，x，x，x，x,x,01,42,45,46,47,44,3, ,，，,,,0xxxxx2,58,56,55,45,9,x,x,x,x,0,9,66,56,46,7s.t. (4) ,，,,,,0xxxxx6,73,77,47,97,10, ,,,,0xxx9,88,58,11,x，x，x，x,x,x,05,910,911,97,99,69,8, ,,,,0xxx7,1010,910,11,x，x,x,0,10,118,1111,9 ,,1,2...,10x或i,j, 应用相同的整数规划求解软件，求解这一模型得到下列最优解: x,1x,3x,1x,1x,2x,5，，，，， 1,43,12,42,51,24,3 x,1x,1x,1x,1x,2x,2， ，，，， 6,55,46,47,43,76,7 x,1x,1x,2x,4x,2，，，， 8,57,95,99,67,10 x,1x,2x,1x,2x,1，，，， 10,99,88,1111,910,11 第 页 共34页 9 中国邮递员问题的应用研究 最小权重为159。假定邮局在顶点，则有如下投递路线: V1 e,e,e,e,e,e,e,e,e,e,e,e1,22,44,33,11,44,33,11,22,55,44,33,7, e,e,e,e,e,e,e,e,e,e,e,e7,1010,1111,99,88,1111,99,66,55,99,88,55,9 ,e,e,e,e,e,e,e,e,e,e,e,9,66,77,99,66,44,33,77,1010,99,66,7 e,e,e7,44,33,1 这是一个回路。类似可以确定邮局在任一顶点时的最佳投递路线。这一最优投递路线是根据模型的最优解，采用类似接龙游戏的方法找出的。这里需要注意 xx的是，如某的值大于1，意味着该弧要重复走。所有的和应等于所走的所i,ji,j 有街道数(包括重复走的)。 [7] 1.2.3 随机中国邮递员问题及其建模 上述讨论的传统的和广义的中国邮递员问题都假定与边或弧相联系的权重是确定型的常数。实际中经常遇到权重非固定的情况，如考虑的权重是该街道上所花费的投递时间，这一参数往往不是常数，每次投递所花费的时间会由于邮件量的多少而变动，但一般会遵循某种变化形式，即权重是具有某种分布的随机变量，这时可以称对应的问题为随机中国邮递员问题。处理传统中国邮递员问题的奇偶点图上作业法及其改进算法对这一随机问题都无能为力，但借助于本文建立的整数规划模型，应用随机规划理论，可以很方便地进行处理。 随机问题的处理方法有多种，如期望值法、机会约束法、最优值分布法、相关机会约束法、多阶段(如两阶段)法。本文在此处仅讨论机会约束法，其核心是概率约束条件的确定型等价处理。其他方法可以按照随机规划理论类似处理，在此略去。 注意到，CPP或GCPP的约束中都不含有权重参数，因此，处理权重随机的问题只需要将目标函数做相应的确定型等价处理即可。权重随机时，目标函数也是随机变量，根据随机规划理论，随机的CPP问题可以转化为如下2个确定型等 [7]价模型: 1-CPP(α) min w 第 10 页 共 34 页 北方民族大学学士学位毕业论文 ,，，,Pwx,w,,,,,i,ji,j..st (5) ',,,(i,j),E，，,CPP的约束条件, 2-CPP(w) max α ,，，,Pwx,w,,,,,i,ji,j..st (6) ',,,(i,j),E，，,CPP的约束条件, x其中，1-CPP(α)指对固定的α求解以及权重w,而2-CPP(w)指对固定的i,j x权重w求解和α。此处，称α为权重w的可行度，w为总权重的希望水平。i,j w如果诸权重均服从正态分布而且相互独立，服从N(u,,)，则1-CPP(α)i,ji,j2i,j [8]和2-CPP(w)分别等价于下列2个数学规划: 1-NCPP(α) min w ,122,w,ux,Fx,(,),0,,i,ji,ji,ji,j,'st.. (7) (i,j),E, ,CPP的约束条件, 2-NCPP(w) max α ,122,wuxFx,,,(,),0,,i,ji,ji,ji,j,''st.. (8) (i,j),E(i,j),E, ,CPP的约束条件, -1 其中:F(X)为标准正态累积分布函数;F(y)为其逆函数。进一步地，可分 别等价于如下2个数学规划问题: ,1221-NCPP(α)′ minux，F(,),x,w ,,,,,,ijijijij''(,),(,),ijEijE s.t.CPP的约束条件 (9) w,ux,ijij,,'ijE(,),,12-NCPP(w)′ (10) max,F(,)22x,,ijij,,'ijE(,), s.t.CPP的约束条件 第 页 共34页 11 中国邮递员问题的应用研究 -1其中，注意到F(α)是α的单调递增函数。 对于其他类型的随机问题也可以类似地进行分析。注意上述规划是非线性的，因此需要借助非线性整数规划的求解工具和软件或两阶段法进行求解，大型问题也可以借助于现代智能优化算法进行求解。 基于传统的中国邮递员问题，建立了这一问题的显式整数规划模型，并将之推广到基于赋权有向图的广义邮递员问题和权重不确定的随机邮递员问题。另外的推广是考虑权重是模糊型或灰色型、粗糙型、信度型的中国邮递员问题，根据相应的不确定性内涵，对于目标函数进行相应的确定型转化。 本章讨论的是单目标问题，如果考虑多目标中国邮递员问题，数学规划灵活、机动、易于修正和变形的特点，可以用来非常方便地处理这一可能的拓展问题。 第 12 页 共 34 页 北方民族大学学士学位毕业论文 第二章 中国邮递员问题的DNA计算 目前，人们已对DNA计算技术展开了深入研究。应用DNA计算方法，开拓性地解决了一个给定有向图的Hamilton路径问题。给出了一种对于可满足性问题(SAT问题)的DNA计算模型。利用单链DNA分子的“发夹”结构，解决了一个3-SAT问题。给出了一种基于表面的SAT问题的算法，随后对其进行了改进。将DNA计算应用于0-1规划问题，解决了一类特殊0-1规划问题，即指派问题的推广。在其基础上完全解决了0-1规划问题，并将进而解决了两类特殊的整数规划问题。 中国邮递员问题是运筹学中的一个重要问题，本章提出了“虚拟权值”和“虚拟节点”的概念，然后基于DNA计算在并行运算方面的良好特性，提出了中国邮递员问题的一种基于DNA计算的新求解算法。新算法首先利用多聚酶链式反应技术来排除非解，从而得到中国邮递员问题的所有可行解;然后，结合基于表面的DNA计算方法与荧光标记策略等技术，最终从所有可行解中析出最优解。算法分析表明，新算法具有易于解读，编码简单等特点。 2.1 DNA计算模型 DNA是一种高分子化合物，组成它的基本单位是脱氧核苷酸，每个脱氧核苷酸由一分子磷酸，一分子脱氧核糖和一分子含氮碱基组成。含氮碱基有四种，即腺嘌呤(A)，鸟嘌呤(G)，胞嘧啶(C)和胸腺嘧啶(T)。DNA不仅具有一定的化学组成，还具有规则的双螺旋结构。DNA计算的基本思想是利用DNA特殊的双螺旋结构和碱基互补配对规律进行信息编码，把要运算的对象映射成DNA分子链，在生物酶的作用下，生成各种数据池(Data Pool)，然后按照一定的规则将原始问题的数据运算高度并行地映射成DNA分子链的可控生化反应过程，最后利用多聚酶链式反应PCR，凝胶提纯，诱变等分子生物技术检测所需要的运算结果。DNA计算的核心问题是将经过编码的DNA链作为输入，在试管内或其他载体上经过一定时间完成控制的生物化学反应，以此来完成运算，使得从反应后的产物中能得到全部的解空间。 第 页 共34页 13 中国邮递员问题的应用研究 2.2 中国邮递员问题的图论模型变换 中国邮递员问题的距离图模型无法直接应用于DNA计算，因此需要对其进行适当变换。在给出具体变换模型之前，先给出需要用到的相关概念的定义。 [9]定义1 虚拟权值:给定的连通无向图，其中为V,{v,v,...,v}G,(V,E)12n de图中的节点集合，为图中的无向弧集合，令为无向弧E,{e,e,...,e}GGjj12m 对应的距离，将按距离长度进行分组，假定可分为个组{e,e,？,e}k,112m Gd(G)，其中表示属于组中的无向弧的距G,？,Gd(G),d(G),...,d(G),jj2k23k GG离长度。我们称组对应的组号为属于组中的无向弧的虚拟权值。对属于jjj Gw组中的任意无向弧，其虚拟权值记为。 jj 中国邮递员问题的虚拟权值图模型，对于给定的连通无向图，其G,(V,E)中V,{v,v,...,v}为图中的节点集合， E,{e,e,...,e}为图中的无向弧集GG12n12m wev合，令为无向弧对应的虚拟权值，则对图中给定的节点，需要从所有Gjjs ,PP{P}可能路径集中求得一条最优路径。其中满足: jjj Pvv1) 从节点开始到节点结束; jss {e,e,...,e},P2) ; 12mj ,,PWxW(P),min{W(P)}其中满足:，其中表示路径中所有无向弧对应j(x)jj 的虚拟权值之和。 定义2 虚拟节点/路径节点:给定的连通无向图G,(V,E)，其中V,{v,v,...,v}E,{e,e,...,e}GG为图中的节点集合，为图中的无向弧集合，12n12m wee令为无向弧对应的虚拟权值，假定无向弧的两个端节点分别为A，B，则jjj eeww,1在无向弧上可增加个中间节点，将平均分为段，令N,N？,Njjjk12w,1j N,AW(NN),1W(NN)NN， N,B,即有，其中表示节点之间0tt，1tt，1tt，1wj 第 14 页 共 34 页 北方民族大学学士学位毕业论文 e的无向弧对应的虚拟权值。以上新增加的中间节点称为“虚拟节点”，而图Gj 中的节点集V中的节点成为“路径节点”。 ,,12中国邮递员问题的虚拟节点图模型:对于给定的连通无向图，G,(V,E)其中为图中的节点集合， 为图中的无向弧V,{v,v,...,v}E,{e,e,...,e}GG12n12m v集合，则对图中给定的节点，需要从所有可能路径集{Pj}中求得一条最优Gs ,PP路径j。其中满足: jj P(1) 从节点vs开始到节点vs结束; j ,,PW(2) {e,e,...,e},P;其中满足:W(P),min{W(P)}，其中表示路j(x)12mjjjx径中所有无向弧对应的虚拟权值之和。 [11]2.3 中国邮递员问题的DNA算法 对给定街区的中国邮递员问题，依据2.2节中的描述，首先给出问题对应的 ,,,,,,虚拟权值图模型，其中为连通无向图，为图V,{V,V,？,V}G,(V,E)GG12M ,中的节点集合，为图中的无向弧(路径)集合。然后，再给E,{E,E,？,E}G12M 出问题对应的虚拟节点图模型，其中G为连通无向图， G,(V,E) V,{v,v,...,v}E,{e,e,...,e}为图G中的节点集合， 为图G中的无向弧(路12n12m径)集合。 ,V,V显然有:。 针对中国邮递员问题对应的虚拟节点图模型G,(V,E)，不妨假定节点v(,V)为邮局，则对应的中国邮递员问题的DNA算法如下: 11 v,v,...,v步骤1 随机生成大量长度为20-mer的DNA单链，对，选择n个12n SS,S,？S不同的DNA单链分别与其对应。{对任意节点，用表示其所对应AA12n 的DNA单链。} 第 页 共34页 15 中国邮递员问题的应用研究 SS步骤2 ，得到对应的反转补链。并在试管T1中,S,{S,S,？S}jjj12n S生成大量的拷贝。 j ,,,,,,,,V,Vv,v,？,v,VP{V,v,v,？,v,V}步骤3 ， ，其中为12t112t一条邮局节点 (用S表示邮局)， 之间的路径。则用如下方法生成DNA单链VV1 ,,,,,,S,v,v,？,v,VS,v,v,？,v,S、来表示路径，并在Ps12tvtt,11 ,,,,,,S,v,v,？,v,VS,v,v,？,v,S试管T2中生成大量、的s12tvtt,11拷贝。 SS(1)用依次链接上最后再链接上的前10-mer寡聚核S、S、？、S,,,vv1vvv12t 苷酸，所构成的长度为20×(t+1.5)-mer的DNA单链 ,,,,,,S,v,v,？,v,VP{V,v,v,？,v,V}，来表示路径; s12t112t SS2)用依次链接上最后再链接上的前10-mer寡聚(S、S、？、S,,,vv1vvvtt,11 ,,,S,v,v,？,v,S核苷酸，所构成的长度为20×(t+1. 5)-me的DNA单链，vtt,11 ,,,P{V,v,v,？,v,V}来表示路径。 t1t,11 ,,,,,,,v,v,？,v,V,U、V,VP{U,v,v,？,v,V}步骤4 ， ，其中12t12t为一条之间的路径。则用如下方法生成DNA单链U、V ,,,,,,S,v,v,？,v,SV,v,v,？,v,U、来表示路径，并在PU12tvtt,11 ,,,,,,S,v,v,？,v,SV,v,v,？,v,U试管T3中生成大量、的拷贝。 U12tvtt,11 SS、S、？、S1)用的后10-mer寡聚核苷酸，依次链接上、最后再链,,,Uvvv12tS接上的前10-mer寡聚核苷酸所构成的长度为20×(t+1)-mer的DNA单链v ,,,,,,S,v,v,？,v,VP{U,v,v,？,v,V}，来表示路径; U12t12t SS、S、？、S 2)用的后10-mer寡聚核苷酸，依次链接上、最后再链,,,vvvvtt,11S接上的前10-mer寡聚核苷酸所构成的长度为20×(t+1)-mer的DNA单链v ,,,,,,S,v,v,？,v,UP{V,v,v,？,v,U}，来表示路径。 vtt,11tt1,1 第 16 页 共 34 页 北方民族大学学士学位毕业论文 步骤5 将试管T1、T2、T3倒入试管T4。在试管T4中将产生大量的连接酶反应。 注:连接酶反应:存在一种称为连接酶的酶，该种酶能将两条不同的DNA单链串联成为一条DNA双链。 步骤6 利用作为引物，基于多聚酶链式反应(Polymerase Chain S1 Reaction， PCR)放大技术，使得步骤5所得到的产物中，仅以起始，并以SS11结束的DNA双链得到放大。分离放大的DNA链并保存到试管T5。加热解开试管T5中的DNA双链，生成DNA单链。 ,,,,v,v,？,vE步骤7 ,E,E，其中为一条之间的无向弧，为U、V12tjj 之间的虚拟节点，则分别利用吸附到磁珠上的U、V ,,,,,,S,v,v,？,v,VS,v,v,？,v,U、来孵化(Incubate)U12tVtt,11 ,,,S,v,v,？,v,V或生成的单链DNA。由于只有包含U12t,,,,,,S,v,v,？,v,US,v,v,？,v,V的DNA单链才能与或Vtt,11U12t ,,,S,v,v,？,v,U产生连接酶反应，因此可通过磁珠的磁性分离出试Vtt,11 ,,,,,,S,v,v,？,v,VS,v,v,？,v,U管T5中包含或的DNAU12tVtt,11单链。 ,步骤8 对步骤7所得到的产物，依次对中的所有其他无向弧分别重复步E 骤8。保留最终得到的DNA单链。 步骤9 对步骤8所得到的所有DNA单链，首先，使之带上负电，然后将其放置于矩阵凝胶体(GelMatrix)的负极。基于相斥原理，所有DNA单链将向反方向移动。由于长的DNA链的移动速度小于短的DNA链，因此，可以分离出移动速度最快的DNA单链。 步骤10 对步骤9所得到的任意DNA单链，按以下方法确定其对应的路径中包含的各条无向弧的访问顺序: 1) 将得到的DNA单链固定在表面上; ,E,E,E,{E,E,？,E}2) ，其中为一条U、V之间的无向弧，jj12m 第 页 共34页 17 中国邮递员问题的应用研究 ,,,,,,v,v,？,v为之间的虚拟节点，将S,v,v,？,v,V、U、V12tU12t ,,,S,v,v,？,v,U连接上不同的荧光素; Vtt,11 ,,,,,,S,v,v,？,v,VS,v,v,？,v,U3) 将、加到表U12tVtt,11面上; 4) 重复上述步骤2)和3)，直到DNA单链构成DNA双链。 5) 利用激光共聚焦显微镜观察表面上的DNA双链的荧光素颜色，即可确定其对应的路径中包含的各条无向弧的访问顺序。 显然，针对具有n个节点的模型，步骤1的时间复杂度为O(n);G,(V、E) SS在步骤2中，由于DNA计算的并行性，针对不同的，在试管T1中生成大量jj的拷贝是同时进行的，因此其时间复杂度也为O(n);在步骤3中，假定模型 中的不同路径条数为m，则步骤3的时间复杂度为O(m);类似步骤3，G,(V、E) 易知步骤4的时间复杂度也为O(m);步骤5、6、7、8的时间复杂度显然均为O(1);而对步骤10，由于模型中的不同路径条数为m，因此得到的DNA单链G,(V、E) 至多为m，因此，其时间复杂度为O(m)。一般而言，由于m n，故综上所述，算法的总的时间复杂度为O(m)。 2.4 总结 本章描述了DNA的计算模型，模型的转换和算法，从DNA算法中可以看到其具有良好的并行性，因此在解决一类困难问题，特别是完全问题上具有硅计算机无法比拟的优势。利用多聚酶链式反应放大技术，提出了中国邮递员问题的一种基于DNA计算的求解算法。算法分析表明，新算法具有易于解读、编码简单等特点。 第 18 页 共 34 页 北方民族大学学士学位毕业论文 第三章 中国邮路问题的数学模型 3.1 问题的重述 某地区的邮政局、所分布如图1所示，分为地市中心局(简称地市局)、县级中心局(简称县局)和支局三级机构，该地区的邮政运输网络由区级邮政运输网和县级邮政运输网构成。区级邮政运输网由从地市局出发并最终返回地市局的区级邮车所行驶的全部邮路构成，县级邮政运输网由从县局出发并最终返回县局的县级邮车所行驶的全部邮路构成。为使邮政企业实现低成本运营和较高的服务质量，我们需要对该地区的邮政运输网络进行重构，确定合适的邮路规划 方案 气瓶 现场处置方案 .pdf气瓶 现场处置方案 .doc见习基地管理方案.doc关于群访事件的化解方案建筑工地扬尘治理专项方案下载 并进行邮车的合理调度。 X550 54 49 55 北 53 48 51 52 47 56 57 45 46 58 7 2 6 44 5 8 59 3 4 60 9 43 10 62 1 16 61 15 X 14 73 40 142 41 13 11 72 39 D 12 66 X63 467 71 36 38 69 17 18 68 70 37 65 64 19 35 X 229 30 27 20 28 34 31 21 32 22 26 图 例 33 25 23 X -----地市局D 324 -----县局X1~X5 -----支局1~73 -----市(县)界 图1 某地区邮政局、所分布图 第 页 共34页 19 中国邮递员问题的应用研究 (图中代号1至73依次代表支局Z, Z, „„, Z) 1273 为了满足邮政的时限要求，必须尽可能地保证各县局、支局在营业时间内收寄的多数邮件能当天运送回地市局进行分拣封发等处理，以及每天到达地市局的多数邮件能当天运送到目的地县局、支局。该地区从地市局到县局每天两班车，从县局到支局每天仅有一班车。题目给出了该地区的邮政运输 流程 快递问题件怎么处理流程河南自建厂房流程下载关于规范招聘需求审批流程制作流程表下载邮件下载流程设计 及时限规定如Step1-Step4: 假设区级两个班次邮车的行驶路线相同，要求区级邮政运输网必须至少覆盖该地市附近的16个支局Z, Z, „„, Z和5个县局X，„„，X。各县级邮政运58597315 输网必须覆盖本县内区级邮车不到达的支局。该地区邮局间公路网分布见表1，并且县级邮车平均时速为30km/h，区级邮车的平均时速为65km/h，邮车在各支局卸装邮件耗时5分钟，在各县局卸装邮件耗时10分钟。 3.2 需解决的问题 问题:以县局X1及其所辖的16个支局Z1, Z2, „„, Z16为研究对象，假设 X区级第一班次邮车08:00到达县局，区级第二班次邮车16:00从县局X1再出发1 返回地市局D，若每辆县级邮车最多容纳65袋邮件，确定最少邮车数。同时，在考虑空车损失费用(空车率=(邮车最大承运的邮件量(袋)-邮车运载的邮件量袋))/邮车最大承运的邮件量(袋)，单车由于空车率而造成的空车损失费用为( (空车率*2元/公里))的情况下，为提高邮政运输效益，设计合理的邮路规划及相应的邮车调度方案。 3.3 问题假设 根据题意，可以进行如下假设: 1 邮车在邮路上的速度是一定的，不会出现抛锚等现象 2 在各个县局、支局的邮件处理时间一定，不会出现特殊情况而延误时间 3 邮车到达各个支局时包裹的数量达到数据表中给出的数据，并且一次性取走该支局所有的包裹。 4 邮路确定后，各邮车必须按所属邮路进行支局的遍历，不能遍历邮路外的 第 20 页 共 34 页 北方民族大学学士学位毕业论文 其他支局。 3.4 符号说明 论文中涉及到的符号说明如下: :区局 D :县局 X(1,2,3,4,5)i,i :支局 Z(1,2,,75)i,？i GVEWVWE,,(),():邮政网络图(点边赋权图) ，， 其中: VDXZ,,, :顶点集合 V XXi,,{}(1,2,3,4,5)i ZZi,,{}(1,2,,75)？i E:两个节点的无向边集合 WVWvi(){()}(1,2,,75),,？i Wvab(),, iii aZ :寄达支局的邮件量 ii bZ :支局收寄的邮件量 ii WEWeij(){()}(,1,2,,75),,？ ij ZWe()Z :支局到支局的距离 jiji VX :县局包含的节点集合 ii VCount :包含的支局节点数 ii rX:县局的邮路数 ii rX:县局的最少邮路数 imini (1)(2)()sPXVVVX,,,,,？X=:县局的第j条邮路 ijiiijijiji 第 页 共34页 21 中国邮递员问题的应用研究 :运行邮路所需的时间 TPijij ()k:邮路所经过的支局 PVks(1,2,,),？ijij :邮路包含的所有非重复节点 PVP()ijij :包含的支局节点数 CountVP()ijij :县局的邮路总距离 WP()Xiji :邮路的运行成本，单位为元/公里 , :邮车最大承运的邮件袋 Cmax CP:邮路的总邮件量 ijij ()ttvPCts(1,2,,),？:邮车通过邮路所经过的支局需要装载的邮件量 ijijij x:x的上取整 ，，,, P,()P:邮车通过邮路由于空车率所产生的损失 ijij ()kkk，1QVVP:邮车通过邮路从支局到支局的空车率 ijijijij()kkk，1LVVP:邮车通过邮路从支局到支局所行使的距离 ijijijijV:县级邮车的运行速度 县 V:区级邮车的运行速度 市 hX:县局所需的最少邮车数 ii 3.5 问题一的建模与求解 上述问题可分为两个小问题: X (1)在考虑县级邮车容量限制和时限规定的条件下，遍历县局所有支局1 所需的最少邮车数。 (2)在第一小问的基础上，给出合理的邮路规划及邮车的调度安排，使得 X县局的空车损失费用达到最低。 1 第 22 页 共 34 页 北方民族大学学士学位毕业论文 下面分别对以上两个小问进行建模求解。 (一) 模型的分析与建立 1 在时限及邮车容量限制的条件下，确定最少邮车数 将图1的该地区邮政局、所分布图中，每个县局、支局看作图中的节点，任意两个县局、支局之间的邮路可以看作相应节点间的边，那么整个地区的分布图可以看成邮路网络图，针对县局，可得县局及其所属GVEWVWE,,(),()XX，，1i支局所对应的图，为县局及其各支局对应的节点集，GVEWVWE,,(),()VX，，iiiiiii 为相邻顶点构成的边。对于此问题，对应的连通图为，VGVEWVWE,,(),()E，，ii11111VZZZX,,,,,？。 ,,112161 在确定最少邮车之前，首先给出以下结论: Xr结论1 遍历县局所有支局，至少需要设置3条邮路，即=3 11min 证明:通过计算，可得县寄达各个支局所有包裹总数为176。由于每辆县X1 级邮车最多容纳65袋邮件，因此为了将所有包裹送达目的支局，并满足邮车的 176，，最大容量要求，遍历完X县所有支局，至少需要设置条邮路。证毕。 ,31,,65,, hr,结论2 同一县局的邮车数不大于邮路数，即 ii 虽然邮车数与邮路数之间不存在确定的数学关系，但在实际情况中，邮路数少，邮车数通常较少。因此在考虑邮车容量和时限要求的前提下，我们首先确定最少邮路数，并在此基础上，进一步根据时间约束，确定遍历县局所有支局的最少邮车数。由于邮路数的确定涉及到每一条邮路的时限及包裹容量的限制，下面先讨论邮路应满足的约束条件。 X由于邮政运输流畅的时限规定，市局第一班车只能在8:00到达县局，在1县局对邮件进行一小时的集中处理后，即9:00后县级邮车才能由县局出发。市 X局第二班车16:00由县局出发返回市局D，由于县级邮车回到县局时，需要在1 县局进行一个小时的集中处理，因此，县级邮车必须在15:00前全部返回县局， 第 页 共34页 23 中国邮递员问题的应用研究 故县局的邮车实际运行时间(包括邮车在其途径的各个支局邮包的装卸时间)X1 只有6个小时。考虑到县级邮车最多容纳65袋邮件，不可能由一辆车遍历所X1辖的各个支局，设此县局的总邮路数为，每辆车的邮路均形成一个包含节点rX11的圈，记为，其中圈包含的节点集合为，则有: PPP,,？PVP()1i11121r1i1 XVP,(),11i,l (11) ,1,2,...il,,VVP,():11i,,i1, (1)邮车按顺序遍历圈中所有节点的用时条件分析 P1i (1)(2)()s设邮车沿邮路遍历中各节点(由于VP()XVVVX,,,,,？1i11111iii 邮路上可能包含重复节点，因此sCount,)，根据假设3，重复节点的卸装时间ij 不重复计算，则邮车在圈中Count个县支局总的卸装时间为5Count，因此遍Pij1iij P所需的运行时间为: 历邮路1i s,1()(1)(1)()kks，WPV() = (12) (,,,)WVVWXVWVXV，，1i县，，，，，，,县111111iiiik,1 (1)(2)()svvv,,,？PXX故邮车按邮路由出发顺序节点，并最后返回节点，总iii1111i11的用时为: s,1()(1)(1)()kks，T = (13) 5(,,,)CountWVVWXVWVXV，，，，，，，，，1i,县ijiiii111111k,1 P(2)邮车沿邮路遍历回路中节点时的邮车装载量限制分析 1i ()k()kaVV 设为节点需装上邮车的邮袋数，b为节点需卸掉的邮件数，()k()k1i1iVV1i1i P考虑到邮路中可能存在重复的节点，因此增加权重因子，其取值为 ,()k1iV1i ()k,0,V和前面的节点重复,1i, ,()k,V()k1i1，为新支局V,1i, s XXP则邮车由节点出发时装载的邮袋数为。邮车由出发沿邮路,a()()kk,111iVV11ii,1k ()kV运行至节点时邮车所装载的邮件数量为: 1i 第 24 页 共 34 页 北方民族大学学士学位毕业论文 skkk =() (14) Paab,，,,Cks,1,2,？()()()()()jjjjj,,,1i1iVVVVV11111iiiii,,,111jjj 基于以上分析，显然有以下结论: 结论3 设为及中各支局节点集合，为中的个GVE,VXXrPPP,,,？，，111111121l圈，若以下条件成立: k (1); (2); (3) XVP,Tir,,,6,1Cks,,,65,1，，11i11i1i 则个圈为遍历中各节点的条邮路，并且为的最少邮路数。因此在此VXlll11基础上根据线路的运行时间调整邮车数，使之达到最少。 2 在考虑空车费的条件下，规划邮路和安排邮车的运行 由于每一个支局均有邮件的装卸操作，使得对于每一条可行的邮路，邮车的 空车费用和其经过支局的顺序有关，因此对于可行邮路，由 公式 小学单位换算公式大全免费下载公式下载行测公式大全下载excel公式下载逻辑回归公式下载 3可得邮车P1i k由X出发运行至节点时邮车的空载量为: V11i skk 65(),,，,,,aab ()()()()()()kkjjjj,,,VvVVVV111111iiiiii,,,111kjj k(1)k，因此，邮车由节点出发运行至节点时的空载率为: VV1i1i skk，，()t65()65,,，,,,aab = Q()()()()()()kkjjjj,,,,,1iVvVVVV111111iiiiiikjj,,,111，， ()()kkk(1)k，QL，则由邮车由V至的空载损失为: (4) V11ii1i1i (1)XP邮车由V运行至中节点的空载损失为: 11i1i s，，,,(1),，，65652,,aWXV，，()()jj,,,, (15) ,11iVV11ii1j,,,,,，， ()sPXV邮车由中节点运行至的空载损失为: 1i11i s，，,,s(),，，65652,,bWVX，，()()jj,,,,, (16) 11iVV11ii1j,,,,,，， XPVP()故邮车由沿运行遍历中各节点的空载损失为: 11i1i 第 页 共34页 25 中国邮递员问题的应用研究 s,1s，，,,s()()kk，，()s,,(1)=++,()PQL，65652,,，，,bWVX，，()()jj,,1i,,,,，，,65652,,aWXV11iii11，，()()jj,,,,VV,11iVV11ii11ii1j,k,1,,1j,,,,,,,，，，， (17) 在确定邮路的空车费之后，可以建立以下规划模型求出空车费用最低的邮政 路线: r1 min()(),,WPP，,ijij,1i s(t)()ts.t. ,()2PLQ,,11i1ii,1t k1,,ks， C,651i (18) T,61,,ir1i1 根据上面建立的规划模型，在最少邮路数确定的条件下，通过遍历县局X中1所有支局，即可求得空运车费最低的邮路分布方案。 3.6 模型的求解 r通过对算法一的描述可以发现，对于每一个确定的邮路数，总运行路线最1少的邮路支局分布情况实际上就转变成了多个推销员的最佳推销员回路问题，即 PPPP,,？在加权图GVEWVWE(,,(),())中求顶点集的划分，遍历1i11121riiiiiiir,1,2,....()中所有节点的圈，使得各圈的边权之和最小。针对本问题的实际i 情况，本文给出了求解此问题的近似最优解的算法如下: X算法一(邮件容量约束下的遍历县局中节点集最优圈的贪心算法) i XX(0)初始化，设为县局邮车可用的最大时间限制，县局需遍历的节点集Tii ,VV,P,,VZZZX,,,,,？为，令，; ,,12ni X,iVPV(1)首先求中距节点最远的节点及其最短路径 p WXVWXZ,max,,令 ，，,,，，ipi,,ZV 第 26 页 共 34 页 北方民族大学学士学位毕业论文 , 设中遍历中的节点数为，令(表示寄达路径PCPa(),CP()VkP,ZZVp,() ,,上所有节点的邮包数)，; VVVP,,，， WVVWVZ,min(,),，，,,pnpVVp,,,ZVnV(2)求出中与最近的相邻节点，使得并且 ; CPa()65，,Z VXni(3)判断由节点返回是否满足时间约束 若 WXVWVVWVXkT,,,/3051，，，，,，，，，，，，，，，ippnni 将加入路径，令 VPn ,,kk,，1 ， VVV,,， ， VV,CPCPa()(),，,,pnnZ VV转(2)继续探索;否则，直接由当前节点返回，即将至X的最短路径加入ppi X回路，即获得一个由出发的圈; Pi ,V,,(4)若，则结束，否则转(1)继续求下一个圈。 X利用算法一找出县局总运行里程最短的邮路分布，见表1。 1 表1 邮路规划情况表 初始运行花费邮路 支局分布情况 邮包里程时间 数 (km) (h) XZZZZZZX,,,,,,, 邮路1 60 126 4.70 14576231 XZZZZZX,,,,,, 邮路2 61 98 3.68 1109816151 XZZZZZX,,,,,, 邮路3 55 153 5.51 11311412111 合计 176 367 13.89 X通过上表可以发现，将此县局的支局分为三条邮路，由于每一条线路的时1 间都较长，因此一辆邮车只可能行驶在一条邮路上，而不可能两条邮路行驶同一辆邮车，因此此县局分为3条线路的做法是可行的，并且至少需要3辆邮车。 X综合考虑空车费用，利用算法一找出县局总运行里程最短的邮路分布，见i 第 页 共34页 27 中国邮递员问题的应用研究 表2。 表2 空车费用最低的邮路支局分布表 初始总空运行花费邮路 支局分布情况 邮包车费里程时间 数 (元) (km) (h) 邮路1 X?Z?Z?Z?Z?Z?Z?X 64 18.77 158 5.77 1154321131 邮路2 X?Z?Z?Z?Z?Z?X 60 21.94 136 4.95 1121195141 邮路3 X?Z?Z?Z?Z?Z?X 52 30.71 135 4.92 167816101 合计 176 87.02 377 15.64 从表2可以发现，空车费用最低的邮路规划并不是总运行里程最短的邮路规划，而是有一定的偏差，但是偏差不会太大，这是一个比较合理的结果。 第 28 页 共 34 页 北方民族大学学士学位毕业论文 结 语 本文基于无向图的传统中国邮递员问题,给出了相应的整数规划模型,进一步讨论了一类基于有向图的广义中国邮递员问题,给出了相应的整数规划模型;并研究了随机中国邮递员问题,建立了相应的确定型等价模型。并可以利用奇度数结点的配对来进行求解。根据此思想给出了一种新的求解思路——通过去掉原始图中的偶度数结点并利用最小生成树来确定奇度数结点的配对。提出了“虚拟权值”和“虚拟节点”的概念,同时给出了中国邮递员问题的一种基于DNA计算的求解算法。该算法首先利用多聚酶链式反应技术来排除非解,从而得到中国邮递员问题的所有可行解;然后,结合基于表面的DNA计算方法与荧光标记等技术,最终从所有可行解中析出最优解。通过各种算法分析比较表明,新算法具有易于解读、编码简单等特点。最后通过一个具体的实例—中国邮政路线的规划来说明了图论模型在实践中的应用。 第 页 共34页 29 中国邮递员问题的应用研究 致 谢 本论文是在马泽玲老师的亲切关怀和指导下完成的。从课题的选择到论文的最终完成，马老师始终给予我耐心的指导和热心的帮助。她严谨的治学精神，精益求精的工作作风，深深地感染和激励着我。本论文从选题到完成，每一步都是在导师的指导下完成的，倾注了马泽玲老师大量的心血。在此，谨向马老师表示崇高的敬意和衷心的感谢 。 感谢和我一起学习的舍友和同学们，和他们在一起度过了很多快乐，开心的日子。在他们的帮助下，我顺利的解决了生活中遇到的各种困难。 感谢我的舍友在写论文过程中对我的帮助，他们的点拨，精益求精的态度令我很钦佩。没有他们的帮助我是无法完成论文工作的。 最后深深的感谢呵护我成长的父母，向所有关心我的亲人、师长和朋友们表示深深的谢意。 第 30 页 共 34 页 北方民族大学学士学位毕业论文 参考文献 [1] 王树禾.图论[M].科学出版社，2009. [2] ALDERMAN L M. Molecular computations to combinatorial prob-lems[J]. Science, 1994. [3] 吴振奎,王全文,刘振航.中国邮路问题的一个解法[J].运筹与管理, 2004,4. [4] 管梅谷.中国投递员问题综述[J].数学研究与评论,1984,5. [5] 费 蓉,崔杜武.中国邮递员问题的动态规划算法研究[J].计算机研究与发展，2005,5. [6] 管梅谷.奇偶点图上作业法[J].数学学报,1960,3. [7] 舒兴明.利用F1oyed-Hungary法求解中国邮路问题[J].华南热带农业大学学报,2003. [8] 金 毅.对“中国邮递员问题”的数理分析[J].科技经济市场, 2009,6 [9] LIPTON R. Using DNA to solve NP-Complete Problems[J]. Science, 1995 [10] WANG LEI. DNA-based algorithm for0-1 planning roblems[C]//Computational Science and Its Applications. Berlin: Springer,2005 [11] 王雷,林亚平.一类特殊整数规划问题的DNA计算[J].计算机研究与发展, 2005. [12] 殷志祥,张凤月,许进. 0-1规划问题的DNA计算模型[J].电子与信息学报, 2003. [13] 殷志祥.图与组合优化中的DNA计算[M].北京:科学出版社, 2004. [14] 王雷,林亚平,李智勇.一类特殊整数规划问题的DNA计算[J].计算机研究与展,2005. [19]陈治平,李小龙,王雷,等.最佳匹配问题的DNA表面计算模型[J].计算机研究与展,2005 第 页 共34页 31