19个村庄铺设天然气管道

精选优质文档-倾情为你奉上摘 要本文是关于图论的问题，对19个村庄建立模型，来分别求管道铺设问题和各个最短路程问题。我们把19个村庄看成19个顶点，各村庄之间的公路看成图的边，公路的长度看成图的权重，则村庄公路图即为一无向赋权图。问题一：根据题目要求，每个村庄铺设管道，使铺设费用最少，即图论最小生成树树的问题。经过比较和实验，最终求得的解为问题的精确解。问题二：每条路至少走一遍，最终回到出发点，典型的中国邮路问题。建立模型求解，并且通过数据验证了我们所建的模型的正确性与稳定性。问题三：检修员从村庄1出发，到每个村庄检查天然气状况，最后返回村庄1，怎样走才能使检修员走的总路程最短。这是典型的旅行推销商问， 是至今为解决的难题之一。我们对题设稍做改善，使其转化为求最短H回路的问题。一、问题重述某地区共有19个村庄, 各村庄之间的距离(单位为km) 如图所示, 图中每条连线表示有公路相连. 现要沿公路铺设天然气管道. 铺设管道的人工和其他动力费用为1万元/km, 材料费用为2万元/km.(1): 如果每个村庄均通天燃气, 应如何铺设管道, 才使总的铺设费用最少?(2): 天然气公司决定在铺设管道前, 派人先查看所有公路的状况, 以便决定该公路是否可用. 他们从村庄1出发, 最后又回到村庄1. 问他们应如何走, 才使走的总路程最少?(3): 某检修员从村庄1出发, 到每个村庄检查天然气状况, 最后又回到村庄1. 他应如何走, 才使走的总路程最少?二、模型假设1、假设村庄A与村庄B之间没有公路相连，则村庄A与村庄B无法直接行走，必须绕过其他村庄。2、假设所给数据均为准确数据，无任何偏差。3、对于问题二假设铺设管道之前，公司只派一队人去视察公路状况。4、假设村庄A与村庄B之间没有公路相连，则在赋权图中两顶点之间的权重为无穷大。三、符号说明v1，v2，v19 19个村庄的标记，看成顶点S，S1 ，S2， 分别表示集合G(V，E) 村庄公路图组成的一赋权图G(V,E) 村庄公路图的等价完全赋权图W 各城市之间最短距离形成的矩阵Fi Wi中第i行中除0以外的最小值Fj Wi中第j列除0以外的最小值Fij 罚函数 Fij=Fi+Fjd（Si，SiC） 表示集合Si 到其补集的最短距离d（v，u） 表示两顶点之间的距离Pij 表示顶点两顶点vi，vj之间的最短路径w（vi，vj） 表示顶点vi，vj之间的权重四、问题分析与模型的建立19个村庄公路图看成赋权图后，我们就来研究这个问题。第一问：此问要求每个村庄均通天然气，使得铺设管道费用最少。不难看出，要使铺设费用最少，即使得要铺设管道的总长度最短，而题干说明管道要沿着公路铺设，那么就要设计一个总路程最小的线路网把这些村庄都连通起来，这就是所谓的连通问题，这就可以归结为在赋权图G=（V，E）中寻求生成树T，即找出权的最小的连通子图最小生成树。设已给出无向赋权图G(V,E)，其中V=v1，v2，vn，E=e1，e2，em。令w(T)=we 其中eT为G的生成树T的加权和，其中we为图中边e的权重。若T*为G的生成树且满足： w(T*)=minw(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)有的两顶点之间并没有边相连。 我们先求出所有顶点之中任意两顶点vi，vj之间的最短路径Pij，其权重为w（Pij）。即：w(Pij)=minw(P)|P为G（V，E）中vi到vj的所有路径求任何两点之间的最短路径，最好的方法是Dijkstra算法，其算法基本思想如下：设S是V的真子集，u0S， S=VS。如果P=u0uv是从u 0到S的最短路，则uS，并且P的（u0，u）段是最短的（u0，u）路，所以d（u0，u）= d（u0，u）+w（u，v）并且 d（u0，S）=min d（u0，u）+w（u，v） 其中uS，vS （1）（1） 式是Dijkstra算法的基础。从集S0=u0出发，计算 d（u0，S0）=minw(u0，v) 其中vS0，并选取u1S0，使d(u0，u1)= d（u0，S0）；令S1= u0，u1，P= u0u1。一般地，若Sk=u0，u1，uk及相应的最短路P1，P2，Pk已经确定，由公式（1）算出d（u0，Sk）并选取顶点uk+1Sk,使得d(u0，uk+11)= d（u0，Sk），此时d(u0，uk+11)= d(u0，uj)+w（uj，uk+1）对某个jk成立，将边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回路，我们采用分枝定界法。基本思想：分枝限界法常以广度优先或以最小耗费（最大效益）优先的方式搜索问题的解空间树。 在分枝限界法中，每一个活结点只有一次机会成为扩展结点。活结点一旦成为扩展结点，就一次性产生其所有儿子结点。在这些儿子结点中，导致不可行解或导致非最优解的儿子结点被舍弃，其余儿子结点被加入活结点表中。 此后，从活结点表中取下一结点成为当前扩展结点，并重复上述结点扩展过程。这个过程一直持续到找到所需的解或活结点表为空时为止。 以例题来说明其方法是：设有矩阵 它表示四个城市之间的距离，以此求最短回路。1) 简化并确定W的下界。各行减去最小元素，然后各列减去最小元素，得W1，显然最短H回路的解的方案不受影响，若W1中零元素对应的边构成H回路，则该H回路最短。因此，W行列简化后的总量构成原问题的一个下界L.B(各行各列最小值的总和,L.B=3+3+5+4+1=16。继续求解得的H回路之权不会优于该下界。2) 分枝并确定分枝的下界。W1中零元素对应的边不构成H回路，但仍可选择一些零元素对应边构成回路，为了在多个零元素中择优选择一个，引入罚函数Fij（假设中提到过），以零元素对应的最大罚函数maxWij=0Fij确定的v2v1（或v4v3，v3v1，）作为分枝条件，其含义是：若回路中不包含v2v1，则引起的损失最大，此时在W1中置w2 1=，化简后的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 ，其权为L.B.（W11）=177.由于除根外的各分支点的下界皆劣于17，故其为最短H回路。五、模型的求解问题一我们设村庄1到19为顶点v1，v2，v19设S1=v1，S1C=v2，v3，v19求 d（S1，S1C）= mind(v1,u)+w(u,v)， 其中uS1，vS1C容易看出，d（S1，S1C）=d（v1，v2）即把v2加入到S1中，设S2=v1，v2=S，S2C= v3，v19,再求 d（S2，S2C）=min d(u,v)， 其中uS2，vS2C同样，再把v8加入到S2中，设S3= v1，v2，v8=S，S3C= v3，v7，v9，v19，再求 d（S3，S3C）=min d(u,v)， 其中uS3，vS3C以此类推，直到把所有的顶点都加入到S中，便可求出图G(V，E)的最小生成树，如下图所示：上图即为铺设管道的图示，所铺设的管道长度为5250km又铺设管道的人工和其他动力费用为1万元/km, 材料费用为2万元/km.即得铺设管道的所有费用=5250（2+1）=15750万元即如上图铺设天燃气管道所需费用最少，费用为15750万元问题二我们设村庄1到19为顶点v1，v2，v19，村庄公路图记为G，村庄之间的距离记为权重。第一步：先找出奇节点：v2，v3，v6，v7，v8，v10，v11，v12，v16，v17，v18，v19，把节点进行配对，不妨把v2 与v8 ，v3 与v10 ，v6与v7 ，v11与v12 ，v16 与v18， v17与 v19配对，对每对配对的顶点，在G中取连接两顶点的边记为Pi（i=1，26）将 Pi上的每一条边都添加一条边，从而得到 G的一个赋权Euler生成母图G*。第二步：若G* 中关于G的某一对相邻顶点有多于2条边连接它们，则去掉其中的偶数条边，留下1条或2条边连接这两个顶点，直到每一对相邻顶点至多由2条边连接。容易得出该题的生成母图G*不需此步骤。第三步：检查G的每一个回路，如果某一个回路C上多重边的权重和超过此回路权和的一半，则将C上原来无重边的边各添加一条重边，而将C上的各多重边分别删去一条边，进行调整。重复这一过程，直至对G的所有回路，其多重边的权不超过此回路的权和的一半，得G*。容易看出我们只需对连接v11与v12的边进行调整即可。得出要求的结果如下图所示：18126119107222345133141516181719第四步：用Fleury算法求G*的欧拉环游。则工作人员可按如下方法行走：1 2 8 13 14 15 17 19 17 18 19 7 6 7 4 5 6 11 12 10 11 10 5 3 10 12 16 18 16 9 8 2 3 1按以上方法走所走路程最短，最短路程为14650km问题三我们采用c+编程来求各顶点的最短路，编程内容如下：#include #include using namespace std; const int MaxNum=; /边权最大值 int n; /节点数目 int dist501; /到节点1的最短路径值 bool state501; /节点被搜索过状态指示 int data501501; /邻接矩阵 /查找权值最小的节点 int findmin() int minnode=0, min=MaxNum; for(int i=1; i=n; i+) if (disti n; for(int p=1; p=n; p+) for(int q=1; q datapq; if (datapq=0) datapq=MaxNum; /初始化 for(int i=1; i=n; i+) disti=data1i; state1=true; int done=1; while (donen) int node=findmin(); if (node!=0) done+; /找到的点的数目加1 statenode=true; /标记已经找到了从节点1到节点node的最短路径 for(int i=1; idistnode+datanodei) & (!statei) disti=distnode+datanodei; else break; for(int k=1; k=n; k+) if (distk=MaxNum) out-1; else outdistk; if (k=n) outendl; else out ; in.close(); out.close(); return 0; 由上可求的各顶点之间的最短路如下：结合题目可知，我们应把w矩阵的对角线上的元素改为。接下来利用分枝定界法：1） 简化并确定W的下界。各行减去最小元素，然后各列减去最小元素，得W1，显然最短H回路的解的方案不受影响，若W1中零元素对应的边构成H回路，则该H回路最短。因此，W行列简化后的总量构成原问题的一个下界L.B(各行各列最小值的总和,L.B=5650。继续求解得的H回路之权不会优于该下界。2) 分枝并确定分枝的下界。W1中零元素对应的边不构成H回路，但仍可选择一些零元素对应边构成回路，为了在多个零元素中择优选择一个，引入罚函数Fij（假设中提到过），以零元素对应的最大罚函数maxWij=0Fij确定的v13v14（或v14v13，v14v54，v15v14）作为分枝条件，其含义是：若回路中不包含v13v14，则引起的损失最大，此时在W1中置w13 14=，化简后的W3，且L.B.（W3=5650+200=5850）；若回路中包含v13v14，则可使最终H回路的增值量减少最多，此时回路不能包含v14v13，否则会形成子回路v13v14v13，且以后不再考虑v13v14，故在W1中删去v13v14坐在的行列的元素，并置v14v13=，化简后的W5，并且L.B.=5650+200=5850. 3) 继续分枝定界。由于L.B.(W3)=L.B.(W5),所以可以以W5分枝，分枝边确定为v13v14。若回路中不包含v13v14，则置w13 14=，由W3并化简后得W7，且L.B.(W7)= 5850+600+400=6850；若回路中包含v13v14，则在W3中删除v13v14所在的行和列元素，并置w14 13=，得W9，且L.B.(W9)= 5850+550+200=6600，小于W7所在分枝的下界。4） 由于L.B.(W9)L.B.(W85)，以W85进行分枝，分枝边为v2v2，若回路中不包含v2v2，则置w2 2=，由W85并优化得W87，且L.B.(W87)= 7650+500=8150；若回路中不包含v2v2，则在W85中删去v2v2所在的行列的元素，得W89，且L.B.(89)=7650 5）显然，W89中的零元素构成回路，所以可得一条H回路其权为L.B.（W89）=7600。其中H回路为 v1v2 , v2v9,v9v8 , v8v13, v13v14, v14v15, v15v17, v17v19, v19v18,v18v16, v16v12, v12v10, v10v11, v11v6, v6v7 , v7v4,v4v5, v5v3, v3v1 。最短回路图如下：箭头表示的方向为行走的方向，双箭头表示需要来回走的道路则上图为所求的最短路径，路程为7400km参考文献：1.蔡锁章 数学建模原理与方法 海军出版社 2000 2.湖北省大学生数学建模竞赛专家组 数学建模（本科册） 华中科技大学出版社 20063.薛秀谦 朱开永 运筹学 中国矿业大学出版社 20024.卜月华 图论及其应用 东南大学出版社 20025.孙惠泉 图论及其应用 科学出版社 2004专心-专注-专业