哈密顿灾情巡视模型分析.pdf

灾情巡视路线模型灾情巡视路线模型摘要摘要本题所研究的分组巡视的最佳路线与多个旅行推销员的问题相似，但也有不同，因为此题还有均衡性要求。这是一类图上的点的遍历性问题，即用若干条闭链覆盖图上所有的顶点，并使某些指标达到最优。首先，将乡村公路示意图转化为赋权连通图，并通过最小生成树法将原权图划分为若干个子图，然后，利用 Hamilon 圈法分别求出各个子图的最佳巡视路线。最后，利用本文中自定义的均衡度公式：，来衡量分组 maxmin()100%,maxAAAA为各组巡视路程或时间组成的集合的均衡性，如果均衡度越小，那么分组的均衡性就越好，据此来判断分组是否满足题意。而题中，在基于最小生成树法将原权图划分为若干个子图的划分情况下，就必然使得总巡视路程相对较短，而均衡度不够令人满意，此时根据实际需要，若要使总巡视路程优先，达到相对较短，则采用原划分的子图分组；若要使均衡度优先，达到满意要求，则我们可以对各分组部分边界点进行重划分调整。针对问题一，我们分别采用直观分析法和最小生成树法求解并得到不同的结果。若分三组巡视，最小生成树法求解各组的巡视路程分别为159.3km、242.2km、186.4km，总路程为 587.9km，路程均衡度为 34%。此结果下的总路程相对较短，而均衡度偏高。如果要优先考虑均衡度，在最小生成树法求解发改进的基础上得到：194.0km、205.3km、206.8km，总路程为606.1km，路程均衡度为 6.2%。针对问题二，基于计算可以发现至少分 4 组，并求出了各组的最佳巡视路线。各组巡视的路程和时间分别为125.5km19.6h、154.3km22.4h、203.9km23.8h、158.8km21.5h，时间均衡度为 18%。针对问题三，我们选取了巡视离县城最远的乡镇（点 H）所需的时间 6.4小时作为最短巡视时间，当巡视比较偏僻的乡村时，汽车从县镇府出发直至到达终点，中途不会停留，仅在终点站停留 T（或 t）小时，然后按原路返回，到达沿途各站接回巡视人员。基于最短巡视时间和制定的分组原则得到巡视人员至少需分成 7 组。针对问题四，实际上是一个变量讨论问题。在分析乡（镇）停留时间 T，村庄停留时间 t 和汽车行驶速度 v 的改变对最佳巡视路线的影响时，我们通过控制不同变量的变化，初步的得出了当 T 与 t 变化时和 v 变化时对最佳巡视路线的影响。最后，我们对模型进行了评价和推广，使其更具有实用价值。【关键词关键词】：均衡度 最小生成树 Hamilon 圈 最佳巡视路线一、问题重述一、问题重述下图为某县的乡（镇）、村公路网示意图，公路边的数字为该路段的公里数。今年夏天该县遭受水灾。为考察灾情、组织自救，县领导决定，带领有关部门负责人到全县各乡（镇）、村巡视。巡视路线指从县政府所在地出发，走遍各乡（镇）、村，又回到县政府所在地的路线。问题一：若分三组（路）巡视，试设计总路程最短且各组尽可能均衡的巡视路线。问题二：假定巡视人员在各乡（镇）停留时间 T=2 小时，在各村停留时间t=1 小时，汽车行驶速度 v=35 公里/小时。要在 24 小时内完成巡视，至少应分几组；给出这种分组下你认为最佳的巡视路线。问题三：在上述关于 T,t 和 v 的假定下，如果巡视人员足够多，完成巡视的最短时间是多少；给出在这种最短时间完成巡视的要求下，你认为最佳的巡视路线。问题四：若巡视组数已定(如三组），要求尽快完成巡视，讨论 T，t 和 v 改变对最佳巡视路线的影响。二、问题分析二、问题分析本题给出了某县的道路交通网络图，要求的是在不同条件下，灾情巡视的最佳分组方案和路线。这是一类图上的点的遍历性问题，也就是要用若干条闭链覆盖图上所有的顶点，并使某些指标达到最优。点的遍历性问题在图论中属于哈密顿问题和旅行推销员问题类似。如果巡视人员只分一组，巡视路线是指巡视人员从县政府 O 出发，走遍各乡（镇）、村最后油回到县镇府。我们可以把该题抽象为图论的赋权连通问题，即有一赋权无向连通图，且(,)G V E。两村之间的公路长度即为无向图的边权。寻找最佳巡视路线，OV()w e即在图中找到一条包含 O 点的回路，它至少经过所有的顶点一次且(,)G V E使得总路程（总时间）最短。如果将巡视人员分成若干组，每组考察部分区域且所有乡（镇）、村都考察到，实际上就是将图分为若干个连通的子(,)G V E图，然后在每个子图中寻找到一条含 O 点的最佳回路。iG完成巡视的时间应是各组巡视中最长的时间，要想提高巡视的效率则应尽量使各组的巡视时间接近，反映在图分块时应尽量均衡。G三、模型假设三、模型假设1、公路不考虑等级差别，也不受灾情或交通情况的影响；2 2、各条公路段上汽车行驶的速度可以认为是均匀的；3 3、巡视人员在各乡（镇）、村停留的时间一定，不会出现特殊情况而延误时间；4 4、各巡视组巡视的乡（镇）、村不受行政区划的影响，即某乡（镇）与隶属于它的村不一定要分在同一组内5 5、忽略不计巡视人员上、下车所用的时间；6 6、当巡视比较偏僻的乡村时，汽车从县镇府出发直至到达终点，中途不会停留，仅在终点站停留 T（或 t）小时，然后按原路返回，到达沿途各站接回巡视人员。四、符号约定四、符号约定:巡视人员的分组数;k：赋权连通图；(,)G V E：赋权连通图的第 个子图;iGi(1,2,)i L，k：子图中的最佳回路；iLiG：最佳回路的各边权之和；iciL：最佳回路的巡视时间;ihiL：第 个乡、村到第个乡、村的距离；ijwij(j1,2,53)iL，：巡视员在各乡（镇）的停留时间；T：巡视人员在各村停留的时间；t：汽车行驶的速度，单位公里小时。v五、模型建立及模型求解五、模型建立及模型求解5.15.1问题一模型的建立及求解：问题一模型的建立及求解：5.1.15.1.1 模型一的建立与求解（直观分析法）：模型一的建立与求解（直观分析法）：根据题中所给的乡（镇）、村示意图对地理位置进行粗略的划组分析。很显然，由于县政府位置偏向东面，则若分成三组巡视，县城远离的一边分为两块的可能性比邻近县城的一边大得多，这样就可以得到手工给出的三组巡视路线图见表 1：表 1编号路线路线长度/公里路线总长度/公里O-1-B-34-35-32-30-Q-28-27-26-P-29-R-31-33-A-1-O168.4O-M-25-N-24-23-21-K-22-17-16-I-15-I-18-J-19-20-L-6-5-2-O207.2 O-2-3-D-7E-11-G-13-14-H-12-F-10-F-9-E-8-4-D-3-C-O218.7 594.3为了衡量分组的合理性，于是我们定义分组的路程均衡度公式：；123123123max,min,max,c c cc c cc c c显然，值越小，说明分组的均衡性越好。由此我们可以得到01采用直观分析法时的均衡度。123%5.1.25.1.2 模型二的建立与求解（基于最小生成树法）模型二的建立与求解（基于最小生成树法）现要分三组巡视，则需要把图分成三个子图，在每个子G(1,2,3)iG i 图中寻找最佳回路。因为最小生成树中能包含图中所有的iG(1,2,3)iL i G顶点，而且最小树的边权是相邻两顶点间的距离，它描述了顶点之间的相近E程度，故可以采用最小生成树进行分组。本模型的主要思想是：首先采用 Prim 算法得到图的最小生成树，然后G基于最小生成树生成一个可行的巡视路线，求得路线的最优总路程为。采用 Prim 算法求解最小生成树步骤如下：（1）输入加权连通图的带权邻接矩阵；G(,)n nAa i j（2）建立初始候选边表；,B T（3）在候选边表中选出最短边；(,),(,)u v TTu v（4）调整候选边表；B（5）重复（2），（3），直到含有条边。T1n根据 Prim 算法进行编程求解（具体程序见附录 1），于是我们得到图的G最小生成树如图 1。图 1现对已得到的最小生成树进行分解，以获得三个子图并使得分解结果尽iG量均衡。由于在最小生成树上，边权接近可以近似认为均衡即各子图包含的顶点数应接近。因此，各个子图的顶点数应尽量接近 17 个，且遵循以下分解原则。最小生成树分解原则：(i i)分解点为 O 点或尽可能地接近 O 点；（iiii）分解所得的三个子图的iG顶点数尽可能地接近 17 个；（iiiiii）尽量是分解所得的子图是连通图；（iviv）尽量使子图与点 O 的最短路上的点在该子图内，且尽量使各子图的点在子iG图内部形成环路。依据以上分解原则得到的分解结果如图 2。图 2然后，采用哈密顿回路法求解每个子图内的最佳巡视路线。寻找最佳巡视路线实际上就是在赋权图中寻找最优的哈密顿圈，包含图的每个顶点的圈陈G为哈密顿圈。于是问题就可以转化为：现已知三个子图内乡、村与乡、村之间的距离，从县镇府 O 出发，经过子图内的所有乡、村，最后又回到点 O。现在讨论如何将寻找最佳巡视路线问题表述成整数规划问题。但是，对于规模较大的寻找最佳巡视路线问题，这里的表述会显得笨拙且效率低下。决策变量定义为:;1 0 ijx，选择从城市i 到城市j，否则其线性（整数）规划模型目标函数为：。11min nnijijijfw x目标函数给出了哈密顿圈的总长度，并使其最小。约束式保证11nijix只能到达每个城市一次，约束式保证只能离开一个城市一次，约束11nijjx式(为自定义变量)是表述问题的关键，它确保：1ijijnxn,ij（1）由解得到的任何圈一定包含城市 1（即县镇府点 O）；（2）包含全部城市的圈是可行的。于是，约束条件概括为：111 j=1,2,n1 i=1,2,n.1 ij,i,j=2,3,n 01 ij,i,j=1,2,n 0 j=1,2,n 53nijinijjijijijjxxstnxnxnLLLLL，或，按照上述思想写出相应的 Lingo 程序（程序见附录 2）求解得到三组巡视路线图见表 2：表 2编号路线路线长度/公里路线总长度/公里O-P-26-27-28-30-Q-29-R-A-33-31-32-35-34-B-1-O159.3O-25-20-L-19-18-J-13-14-H-15-I-16-17-22-K-21-23-24-N-M-O242.2 O-2-5-6-7-E-11-G-12-10-F-9-8-4-D-3-C-O186.4 587.9由此我们可以得到采用最小生成树法时的路程均衡度。234%从上述图表中不难看出，第二组走的路程过长而第一组走的路程过短，两者之间的差值较大，也就是说这样分组的均衡性较差。因此，我们需在基于最小生成树的原则之上对原来的分组进行适当的调整。为了缩小第一、二组间的路程差，首先，我们将第二组的 28 点和 N 点分到第一组；然后，再采用Hamilton 圈法分别求解三个子图内的最佳回路；最后采用 Lingo 编程求解得到初步改进后三组巡视路线图见表 3。表 3编号路线路线长度/公里路线总长度/公里O-P-26-N-24-27-28-Q-30-29-R-A-33-31-32-35-34-B-1-O194.0O-23-21-K-22-17-16-18-I-15-H-14-13-J-19-L-20-25-M-O225.1 O-2-5-6-7-E-11-G-12-10-F-9-8-4-D-3-C-O186.4 605.5由此，可以计算出对模型二初步改进后的分组的均衡度为：。217.2%分析表 3 可知，第二组与第三组走的路程间的差值还是比较大，也就是说这样分组的均衡性还有待改善。于是，我们在基于最小生成树的原则之上对初步改进后的分组进行适当的调整。为了缩小第二、三组间的路程差，首先，我们将第二组的 H 点分到第三组；然后采用上述中同样的方法求解得到最终改进后各组的巡视路线图见表 4。表 4编号路线路线长度/公里路线总长度/公里O-P-26-N-24-27-28-Q-30-29-R-A-33-31-32-35-34-B-1-O194.0O-M-N-23-21-K-22-17-16-18-I-15-14-13-J-19-L-20-25-M-O205.3 O-C-3-D-4-8-E-9-F-10-F-12-H-12-G-11-E-7-6-5-2-O206.8 606.1注：加有底纹的表示只经过此点但不停留。由此，可以计算出对模型二最终改进后的分组的均衡度为：。26.2%综上所述，对比模型一和改进后模型二的结果可知，若分成三组巡视，虽然改进后模型二的巡视总路程比模型一的长，但是，改进后模型二分组的均衡性比模型一要好很多。此外，模型二的结果是经过严谨科学的计算得到的，具有较高的可信度，相比之下，模型一的结果是人根据地理位置粗略划分得到地，具有随机性，可信度较低。经上述分析可知，若分成三组巡视，则应该采用改进后模型二的巡视路线,见图 3。图 35.25.2 问题二的模型建立及求解问题二的模型建立及求解：此问添加了巡视组在各乡（镇）停留的时间小时，在各村停留的时2T 间小时以及汽车的行驶速度公里小时的条件后，要求在 24 小时1t 35v 内完成巡视的最少分组数以及相应的最佳巡视路线。此时需访问的乡（镇）共有 17 个，村共有 35 个，于是可以计算出巡视人员在乡（镇）及村停留的总时间为小时。此外，从问题一的结果中可知，巡视的总路程至1723569少为 500 公里，则汽车行驶所需的时间和将超过 14 小时。由此可知，各组巡视所需的总时间之和超过 83 小时，要想在 24 小时内完成巡视则应满足：(i 为分的组数)。得 i 最小为 4，故至少要分 4 组。8324i 现在尝试将顶点分成 4 组。分组的原则应建立在最小生成树的分解原则之上，则分组应遵循以下原则：(i i)分解点为 O 点或尽可能地接近 O 点；（iiii）分解所得的 4 个子图的顶点数尽可能地接近 14 个；（iiiiii）尽量是分解所得的子图是连通图；（iviv）尽量使子图与点 O 的最短路上的点在该子图内，且iG尽量使各子图的点在子图内部形成环路；（v v）尽量使各组的巡视时间相接近。采用上述原则将图分为 4 个子图，并运用哈密顿回路法找出各个组的最G佳巡视路线。然后，计算出各组最佳巡视路线的总长度及汽车行驶所需时间，同时算出各组的停留时间,从而得到各组完成巡视的最佳时间。基于此，可以采用 Lingo 软件进行编程求解（程序见附录 3）得到 4 个组的巡视路线，并计算出各组巡视的总时间，具体数据见表 3。表 3（路程单位：公里；时间单位：小时）编号路线路线长度停留时间行驶时间总时间O-1-B-A-34-35-33-31-32-30-Q-29-R-O125.5163.619.6O-P-28-27-26-N-24-23-22-17-16-17-K-21-25-M-O154.3184.422.4O-M-20-18-I-15-14-H-12-G-11-G-13-J-19-L-20-M-O203.9185.823.8O-2-5-6-7-E-9-F-10-F-9-E-8-4-D-3-C-O158.8174.521.5注：加有底纹的表示只经过此点但不停留。从上述图表中可以看出所分的四个组的巡视时间均小于 24 小时，符合题意。此外，计算得到该分组的时间均衡度公式为：；1231233123max(,)min(,)max(,)h h hh h hh h h此时，计算得到均衡度：。在此基础上，我们可以得到有时间318%约束的最佳巡视路线如图 4。图 45.35.3 问题三的模型建立及求解问题三的模型建立及求解：此问题就是要求如果有足够多的巡视人员，怎样确定最佳路线是完成巡视的时间最短。实际上，完成巡视的最短时间受到单独巡视离县城最远的乡（镇）、村所需时间的制约，同时我们可以求出离县城最远的点是 H 点，距离为 77.5 公里。因此，单独巡视返回该乡所需的时间为小时。由此可知，775 226.435即使巡视人员再多，分组再细，完成巡视至少需要 6.4 小时。基于此，此题就可以转化为求在 6.4 小时内完成巡视的最少分组数和最佳巡视路线。为达到以上目标，我们制定了以下分组巡视原则：1、对图中偏西且距县政府较远的乡（镇）、村：（1）在 6.4 小时内，每组巡视人员尽可能走足够多的乡（镇）、村。（2）在巡视时，尽量按出发点到该次巡视终点最短路径的路线巡视，但在不超过 6.4 小时的原则下，为了能够途经更多的点，我们可以不走最短路线。（3）巡视车从县政府出发，途中每到达一个乡（镇）、村，部分巡视人员下车巡视，车不停留（忽略不计巡视人员上、下车的时间）继续开往下个站点，直到到达最远点，车停下等待；然后按原路返回，依次到达每点接回巡视人员，直至出发点。2、由于第一种分组原则下，在最远点必须要花 1 或者 2 个小时的停留时间，针对这一浪费时间的缺点，对图中偏东且距县政府较近的乡、村，我们改进一种按圈巡视的方法，原则如下：（1）每组巡视人员巡视路线构成一个圈，且巡视两圈。（2）第一圈巡视时，途中每到达一个乡（镇）、村，部分巡视人员下车巡视，车不停留（忽略不计巡视人员上、下车的时间）继续开往下个站点，直至出发点，仍不停留继续第二圈巡视，到达每点依次接回巡视人员，直至回到出发点，结束。（3）在遵循不超过 6.4 小时原则下，按圈巡视时，总路线不能过长，不超过112 公里；总路线也不能过短，避免车停留等待而浪费时间。依据以上原则，我们在 6.4 小时内完成巡视，总共分成了 7 组，前 5 组遵循的第一种分组原则，后 2 组依据的第二种按圈分组原则。具体的分组巡视路线和所需时间见表 4。表 4（时间单位：小时）编号路线总时间O-2-5-6-7-E-9-F-12-H-14-H-12-F-9-E-7-6-5-2-O6.43O-M-25-20-21-K-18-I-15-I-18-K-21-20-25-M-O5.87O-2-5-6-L-19-J-13-G-11-G-13-J-19-L-6-5-2-O6.15O-2-3-D-4-8-E-9-F-10-F-9-E-8-4-D-32-O6.38O-P-28-27-26-N-24-23-22-17-16-17-22-23-24-N-26-27-28-P-O6.37O-R-31-33-A-1-C-O-R-31-33-A-1-C-O4O-R-29-Q-30-32-35-34-B-1-O-O-R-29-Q-30-32-35-34-B-1-O5.64注：加有底纹的表示经过此点但无巡视人员上、下车。由此可以计算出此种分组下的时间均衡度为：。基于此，我们可以438%得到巡视人员足够多的情况下分成 7 组的最佳巡视路线如图 5。图 55.45.4 问题四的模型建立及求解：问题四的模型建立及求解：第四问要求在巡视组数已定的情况下尽快完成巡视，讨论参数 T，t 和 v 的改变对最佳巡视路线的影响。前面我们已经提到，要尽快完成巡视，即要求各组巡视时间的最大值也要最小。用数学式子表达为：；1min maxmin max+niiiiii kChmTtV 其中：是给定的分组数；：分别是第 组停留的乡(镇)数和村数；k kiimn，i：第 组巡视路线的总长度。iCii1,2,k k在上述表达式中，由于 T 和 t 的作用完全相仿，所以为简化讨论起见，ih对于任意给定的 T 和 t，不妨记。即这里可简记为：TptT ptih；iiiih+n)（mC Cp pt tp pV V它是 t 和的的线性函数，将随着 t 和增大(即 v 的减小)而增大.于是我1v1v们容易得到以下结论：（1）若 t（T）增大而 V 不变，为了使最大值尽可能小，就要求j jh h的最大值尽可能小.但是当 T 和 t 的关系确定后，实际+npC=m+niip（m）上就是定值，其中 m 是全县的乡(镇)数 17，n 是全县的村数 35。上+npC=m述要求就成为各组停留在询问乡村的总时间尽可能均匀.用数学式子表示即为:；iim+nm+nm+nkkp pp pp p这里表示数的下整数和上整数.当然，在调整各组停留的乡村 aa和a数使之达到均衡时，自然会给各组的路线及其长度带来影响.这时应当考虑进行适当调整。（2）若 t（T）不变而 v 增大.这种情况下，今起主导作用。那么，和iCV（1）中的结论类似，我们更应使即各组的巡视路线尽可能均衡。诚然，因jC为不是常数，而且的均衡性会带来的增大，这对于尽快完成巡视iCiCiC会带来负面影响。所以对具体情况应作具体分析，比如可以考虑的前半部份jh对均衡性的修正，对路程较长的组尽量考虑停留较少乡村。iim+n)pt（六、模型的推广六、模型的推广在现实生活和生产中，有许多管理、组织与计划中的优化问题，如企业管理中，如何制订管理计划或设备购置计划，使收益最大或费用最小；在生产管理中，如何使各工序衔接好，才能使生产任务完成的既快又好；在交通管理中，如何利用现有的交通网络，使调用的物资数量多且费用最小等。这类问题都可以借助图论知识得以解决。网络模型就是一种应用图论的理论与方法解决具有网络性质的管理决策问题的数学模型。由于它具有图形直观、方法简便、容易掌握等特点，因此，近年来得到迅速发展，且广泛地应用在各个领域，尤其是经济活动中许多管理决策的优化问题。基本的网络优化问题有：最短路径问题、最小支撑树问题、最大流问题和最小费用问题。在图论这个数学分支中已经有有效的算法来解决这些问题，当然这当中有很多问题都可以建立线性规划的模型，但有时若变量特别多、约束也特别多，用线性规划的方法求解效率不高甚至不能在忍受的时间内解决。根据这些问题的特点，采用网络分析的方法去求解可能会非常有效。七、模型的评价七、模型的评价优点优点本文多处使用图表，增强了文章的可读性，使建模思想更加清晰易懂。在问题三的求解中，我们假定当巡视比较偏僻的乡村时，汽车从县镇府出发直至到达终点，中途不会停留，仅在终点站停留 T（或 t）小时，然后按原路返回，到达沿途各站接回巡视人员，这样考虑可以避免车停留等待而浪费时间，提高巡视效率。缺点缺点：采用最小生成树求解最小回路，并采用 Hmilton 圈法求解各子图内的最佳回路，虽然分组的均衡度比较理想，但求的不是全局最优解。当顶点数目比较多（大于等于 20）时，采用 Lingo 软件针对Hailton 圈法编程时，程序执行的速度较慢，效率不高。(3)本文仅仅是针对具体问题具体分析，有一定的局限性；虽然也是采用图论法解决，但与图论中的经典旅行推销员模型有所区别，在实际应用中，应对各种情况作进一步分析不断对模型加以优化，才会使其更具适用性。八、参考文献及附录八、参考文献及附录【1】数学建模原理与方法，蔡锁章，海洋出版社，2000.6【2】运筹学与实验，薛毅，耿美英，电子工业出版社，2008.9【3】数学的实践与认识（第 29 卷第 1 期），田家国等，1999.1附录附录 1：D=xlsread(shuju.xls)n=53;T=;l=0;%l 记录 T 的列数q(1)=-1;for i=2:n p(i)=1;q(i)=D(i,1);endk=1;while 1 if k=n disp(T);break;else min=inf;for i=2:n if q(i)0&q(i)min min=q(i);h=i;end end end l=l+1;T(1,l)=h;T(2,l)=p(h);q(h)=-1;for j=2:n if D(h,j)q(j)q(j)=D(h,j);p(j)=h;end end k=k+1;end附录附录 2：sets:c/1.17/:u;link(c,c):w,x;endsetsdata:w=ole(第一组数据.xls,dier);enddatan=size(c);min=sum(link:w*x);for(c(k):sum(c(i)|i#ne#k:x(ik)=1;sum(c(j)|j#ne#k:x(k,j)=1;);for(link(i,j)|i#gt#1#and#j#gt#1#and#i#ne#j:u(i)-u(j)+n*x(i,j)=n-1);for(link:bin(x);endsets:c/1.17/:u;link(c,c):w,x;endsetsdata:w=ole(第二组数据.xls,dier);enddatan=size(c);min=sum(link:w*x);for(c(k):sum(c(i)|i#ne#k:x(i,k)=1;sum(c(j)|j#ne#k:x(k,j)=1;);for(link(i,j)|i#gt#1#and#j#gt#1#and#i#ne#j:u(i)-u(j)+n*x(i,j)=n-1);for(link:bin(x);endsets:c/1.17/:u;link(c,c):w,x;endsetsdata:w=ole(第三组数据.xls,dier);enddatan=size(c);min=sum(link:w*x);for(c(k):sum(c(i)|i#ne#k:x(i,k)=1;sum(c(j)|j#ne#k:x(k,j)=1;);for(link(i,j)|i#gt#1#and#j#gt#1#and#i#ne#j:u(i)-u(j)+n*x(i,j)=n-1);for(link:bin(x);end附录附录 3：sets:c/1.13/:u;link(c,c):w,x;endsetsdata:w=ole(第一组数据.xls,dier);enddatan=size(c);min=sum(link:w*x);for(c(k):sum(c(i)|i#ne#k:x(i,k)=1;sum(c(j)|j#ne#k:x(k,j)=1;);for(link(i,j)|i#gt#1#and#j#gt#1#and#i#ne#j:u(i)-u(j)+n*x(i,j)=n-1);for(link:bin(x);endsets:c/1.15/:u;link(c,c):w,x;endsetsdata:w=ole(第二组数据.xls,dier);enddatan=size(c);min=sum(link:w*x);for(c(k):sum(c(i)|i#ne#k:x(i,k)=1;sum(c(j)|j#ne#k:x(k,j)=1;);for(link(i,j)|i#gt#1#and#j#gt#1#and#i#ne#j:u(i)-u(j)+n*x(i,j)=n-1);for(link:bin(x);endsets:c/1.14/:u;link(c,c):w,x;endsetsdata:w=ole(第三组数据.xls,dier);enddatan=size(c);min=sum(link:wx);for(c(k):sum(c(i)|i#ne#k:x(i,k)=1;sum(c(j)|j#ne#k:x(k,j)=1;);for(link(i,j)|i#gt#1#and#j#gt#1#and#i#ne#j:u(i)-u(j)+n*x(i,j)=n-1);for(link:bin(x);endsets:c/1.14/:u;link(c,c):w,x;endsetsdata:w=ole(第四组数据.xls,dier);enddatan=size(c);min=sum(link:w*x);for(c(k):sum(c(i)|i#ne#k:x(i,k)=1;sum(c(j)|j#ne#k:x(k,j)=1;);for(link(i,j)|i#gt#1#and#j#gt#1#and#i#ne#j:u(i)-u(j)+n*x(i,j)=n-1);for(link:bin(x);end