19个村庄铺设天然气管道

共13页第1页摘要本文是关于图论的问题，对19个村庄建立模型，来分别求管道铺设问题和各个最短路程问题。我们把19个村庄看成19个顶点，各村庄之间的公路看成图的边，公路的长度看成图的权重，则村庄公路图即为一无向赋权图。问题一：根据题目要求，每个村庄铺设管道，使铺设费用最少，即图论最小生成树树的问题。经过比较和实验，最终求得的解为问题的精确解。问题二：每条路至少走一遍，最终回到出发点，典型的中国邮路问题。建立模型求解，并且通过数据验证了我们所建的模型的正确性与稳定性。问题三：检修员从村庄1出发，到每个村庄检查天然气状况，最后返回村庄1，怎样走才能使检修员走的总路程最短。这是典型的旅行推销商问，是至今为解决的难题之一。我们对题设稍做改善，使其转化为求最短H回路的问题。一、问题重述某地区共有19个村庄,各村庄之间的距离(单位为km)如图所示,图中每条连线表示有公路相连.现要沿公路铺设天然气管道.铺设管道的人工和其他动力费用为1万元/km,材料费用为2万元/km.(1):如果每个村庄均通天燃气,应如何铺设管道,才使总的铺设费用最少?(2):天然气公司决定在铺设管道前,派人先查看所有公路的状况,以便决定该公路是否可用.他们从村庄1出发,最后又回到村庄1.问他们应如何走,才使走的总路程最少?(3):某检修员从村庄1出发,到每个村庄检查天然气状况,最后又回到村庄1.他应如何走,才使走的总路程最少?共13页第2页二、模型假设1、假设村庄A与村庄B之间没有公路相连，则村庄A与村庄B无法直接行走，必须绕过其他村庄。2、假设所给数据均为准确数据，无任何偏差。3、对于问题二假设铺设管道之前，公司只派一队人去视察公路状况。4、假设村庄A与村庄B之间没有公路相连，则在赋权图中两顶点之间的权重为无穷大。三、符号说明v1，v2，…，v1919个村庄的标记，看成顶点S，S1，S2，…分别表示集合G(V，E)村庄公路图组成的一赋权图G′(V,E)村庄公路图的等价完全赋权图W各城市之间最短距离形成的矩阵FiWi中第i行中除0以外的最小值FjWi中第j列除0以外的最小值Fij罚函数Fij=Fi+Fjd（Si，SiC）表示集合Si到其补集的最短距离d（v，u）表示两顶点之间的距离Pij表示顶点两顶点vi，vj之间的最短路径w（vi，vj）表示顶点vi，vj之间的权重四、问题分析与模型的建立19个村庄公路图看成赋权图后，我们就来研究这个问题。第一问：此问要求每个村庄均通天然气，使得铺设管道费用最少。不难看出，要使铺设费共13页第3页用最少，即使得要铺设管道的总长度最短，而题干说明管道要沿着公路铺设，那么就要设计一个总路程最小的线路网把这些村庄都连通起来，这就是所谓的连通问题，这就可以归结为在赋权图G=（V，E）中寻求生成树T，即找出权的最小的连通子图——最小生成树。设已给出无向赋权图G(V,E)，其中V={v1，v2，…，vn}，E={e1，e2，…，em}。令w(T)=∑w(e)其中e∈T为G的生成树T的加权和，其中w(e)为图中边e的权重。若T*为G的生成树且满足：w(T*)=min{w(T)|T为G的生成树}则称T*为G的最小生成树。我们不妨选用Prim算法。Prim算法思想如下：先从E中任选一点构成E*，然后在E-E*中任选一条到E*中某点（比如v）权最小的边uv进入解，并令E*=E*∪{u}，直至E*=E，即得最小生成树。第二问：铺设管道之前，派人查看所有公路状况，先从村庄1出发，最后又回到村庄1。由于公司只派一队人查看所有村庄的状况，即问题转化为由我国的管梅谷教授于1962年提出的中国邮递员问题（邮递员从邮局取走信件，需走遍他所管理的所有街道把信件发出去，然后返回邮局退回未送走的信件），就是要在赋权图G(V，E)中找一条最优环游。用图论的术语，即在一个连通的赋权图G(V，E)中，要寻找一个回路，使包含G中每条边至少一次，且该回路的权重最小。该题G(V，E)不是欧拉图，即存在奇度数的节点。我们用奇偶点图上作业法来求最优环游。奇偶点图上作业法（求最优环游算法）：(1)把G中度为奇数的顶点两两配对，记为。对每个，G中取一条路Pi，将Pi上的每一条边都添加一条边，从而得到G的一个赋权Euler生成母图G*。(2)去掉G*中关于G的某一对相邻顶点有多于2条边连接它们，则去掉其中的偶数条边，留下1条或2条边连接这两个顶点。直到每一对相邻顶点至多由2条边连接。(3)检查G的每一个回路，如果某个回路C上多重边的权和超过此回路权和的一半，则将C进行调整：删除，的边重数增加1。(4)用Fleury算法求G*的Euler环游。Fleury算法给出了寻找Euler回路的一个简单算法：任选G中一顶点为初始点v0，如果通路u=v0，e1，v1，…，ei，vi已选出，那么则在E-{e1，e2，…，ei}中选出与vi关联的边ei+1，且不是Gi=G-{e1，e2，…，ei}的断边，即Gi-{ei+1}仍连通，从而得通路u=v0，e1，v1，…，ei+1，vi+1。如此反复，直至G的所有边被选出，即得G的Euler回路。第三问：某检修员从村庄1出发，到每个村庄检查天然气状况，最后又回到村庄1，即对于图G(V,E)求从顶点v1开始，寻找一回路H，使其经过图G(V,E)的每一个顶点至少一次，最终又回到v1。这是典型的旅行推销商问题。我们对题设做些改变，使其转化为求H回路的问题。由于有些村庄之间并没有公路直接相通，无法直接行走，即赋权图G(V,E)有的两顶点之间并没有边相连。我们先求出所有顶点之1212,,,,,,,kkxxxyyy(1,2,,)iikiixyeeeC共13页第4页中任意两顶点vi，vj之间的最短路径Pij，其权重为w（Pij）。即：w(Pij)=min{w(P)|P为G（V，E）中vi到vj的所有路径}求任何两点之间的最短路径，最好的方法是Dijkstra算法，其算法基本思想如下：设S是V的真子集，u0∈S，S=V\S。如果P=u0…uv是从u0到S的最短路，则u∈S，并且P的（u0，u）段是最短的（u0，u）路，所以d（u0，u）=d（u0，u）+w（u，v）并且d（u0，S）=min{d（u0，u）+w（u，v）}其中u∈S，v∈S（1）（1）式是Dijkstra算法的基础。从集S0={u0}出发，计算d（u0，S0）=min{w(u0，v)}其中v∈S0，并选取u1∈S0，使d(u0，u1)=d（u0，S0）；令S1={u0，u1}，P=u0u1。一般地，若Sk={u0，u1，…，uk}及相应的最短路P1，P2，…，Pk已经确定，由公式（1）算出d（u0，Sk）并选取顶点uk+1∈Sk,使得d(u0，uk+11)=d（u0，Sk），此时d(u0，uk+11)=d(u0，uj)+w（uj，uk+1）对某个j≤k成立，将边ujuk+1连接到路Pj上，可得（u0，uk+11）的最短路。如果v0=uk+11,则结束，否则重复上述过程。算法具体步骤（1）初始时，S只包含源点，即S=v的距离为0。U包含除v外的其他顶点，U中顶点u距离为边上的权（若v与u有边）或U中顶点u距离小于边上的权（若u不是v的出边邻接点）。（2）从U中选取一个距离v最小的顶点k，把k，加入S中（该选定的距离就是v到k的最短路径长度）。（3）以k为新考虑的中间点，修改U中各顶点的距离；若从源点v到顶点u的距离（经过顶点k）比原来距离（不经过顶点k）短，则修改顶点u的距离值，修改后的距离值的顶点k的距离加上边上的权。（4）重复步骤（2）和（3）直到所有顶点都包含在S中。用上述方法求的任何两顶点之间的最短路后，由这些最短路我们可以绘制一完全Euler图G′，其权重我们可以组成一19阶的矩阵。我们对G′来求H回路，则求得的解我们可以转化成在原赋权图G(V,E)上的行走路线，此时每个村庄至少行走一次。对于求H回路，我们采用分枝定界法。基本思想：分枝限界法常以广度优先或以最小耗费（最大效益）优先的方式搜索问题的解空间树。在分枝限界法中，每一个活结点只有一次机会成为扩展结点。活结点一旦成为扩展结点，就一次性产生其所有儿子结点。在这些儿子结点中，导致不可行解或导致非最优解的儿子结点被舍弃，其余儿子结点被加入活结点表中。共13页第5页此后，从活结点表中取下一结点成为当前扩展结点，并重复上述结点扩展过程。这个过程一直持续到找到所需的解或活结点表为空时为止。以例题来说明其方法是：设有矩阵它表示四个城市之间的距离，以此求最短回路。1)简化并确定W的下界。各行减去最小元素，然后各列减去最小元素，得W1，显然最短H回路的解的方案不受影响，若W1中零元素对应的边构成H回路，则该H回路最短。因此，W行列简化后的总量构成原问题的一个下界L.B(各行各列最小值的总和,L.B=3+3+5+4+1=16。继续求解得的H回路之权不会优于该下界。2)分枝并确定分枝的下界。W1中零元素对应的边不构成H回路，但仍可选择一些零元素对应边构成回路，为了在多个零元素中择优选择一个，引入罚函数Fij（假设中提到过），以零元素对应的最大罚函数max𝑊𝑖𝑗=0{𝐹𝑖𝑗}确定的v2v1（或v4v3，v3v1，）作为分枝条件，其含义是：若回路中不包含v2v1，则引起的损失最大，此时在W1中置w21=∞，化简后的W3，且L.B.（W3=16+1=17）；若回路中包含v2v1，则可使最终H回路的增值量减少最多，此时回路不能包含v14v13，否则会形成子回路v2v1v2，且以后不再考虑v2v1，故在W1中删去v2v1坐在的行列的元素，并置w12=∞，化简后的W5，并且L.B.=16+3+1=203)继续分枝定界。由于L.B.(W3)L.B.(W5),故从W3分枝，分枝变为v3v1，若回路中不包含v3v1，则置w31=∞，，有W3得W7，且L.B..（W7）=17+5=22；若回路中包含v3v1,则在W3中删去v3v1所在的行列元素，并置w13=∞，得W8，且L.B.(W8)=17.由于L.B.(W8)L.B.(W5)L.B.(W7)，故对W8分枝，以v1v2为分枝边。若回路中不包含v1v2，则置w12=∞，由W8得W9，化简的W10，且L.B.（W10）=17+3+3=23；若回路中包含v1v2，则在W8中删去v1v2所在的行列元素，得W11，且L.B.(W11)=17。显然，W11中的零元素构成回路，故H回路为{v3v1，v1v2，v2v4，v4v2}，W397365566974W1063031010530W306320010530W5300020W706320010030W8032030W1002030W11200共13页第6页其权为L.B.（W11）=177.由于除根外的各分支点的下界皆劣于17，故其为最短H回路。五、模型的求解问题一我们设村庄1到19为顶点v1，v2，…，v19设S1={v1}，S1C={v2，v3，…，v19}求d（S1，S1C）=min{d(v1,u)+w(u,v)}，其中u∈S1，v∈S1C容易看出，d（S1，S1C）=d（v1，v2）即把v2加入到S1中，设S2={v1，v2}=S，S2C={v3，…，v19},再求d（S2，S2C）=min{d(u,v)}，其中u∈S2，v∈S2C同样，再把v8加入到S2中，设S3={v1，v2，v8}=S，S3C={v3，…，v7，v9，…，v19}，再求d（S3，S3C）=min{d(u,v)}，其中u∈S3，v∈S3C以此类推，直到把所有的顶点都加入到S中，便可求出图G(V，E)的最小生成树，如下图所示：共13页第7页上图即为铺设管道的图示，所铺设的管道长度为5250km又铺设管道的人工和其他动力费用为1万元/km,材料费用为2万元/km.即得铺设管道的所有费用=5250×（2+1）=15750万元即如上图铺设天燃气管道所需费用最少，费用为15750万元问题二我们设村庄1到19为顶点v1，v2，…，v19，村庄公路图记为G，村庄之间的距离记为权重。第一步：先找出奇节点