数学建模优秀论文-灾情巡视路线的数学模型.doc

《数学建模优秀论文-灾情巡视路线的数学模型.doc》由会员分享，可在线阅读，更多相关《数学建模优秀论文-灾情巡视路线的数学模型.doc（25页珍藏版）》请在装配图网上搜索。

灾情巡视路线的数学模型 摘 要 本文解决的是灾情巡视路线的设计问题。由于路线图可看成网络图因此此问题可转化为在给定的加权网络图中寻找从给定点Ｏ出发行遍所有顶点至少一次再回到点Ｏ使得总权（路程或时间）最小的问题。然后针对具体问题，采用一些启发式算法，建立模型进行求解。 对于问题一：基于设计分三组巡视时使总路程最短且各组尽可能均衡的巡视路线的要求我们采用Dijkstra算法，通过对初始圈进行二边逐次修正,处理三组的巡视路线长度，用lingo软件求解出较优方案。定义分组的均衡度系数a检验分组均衡度，在均衡度为a=0.0751时得到分三组（路）巡视时，总路程最短且各组尽可能均衡的巡视路线见附表1。 对于问题二：将问题转化为图论问题，运用问题一的求解方法，得到分为四组的路线，在通过均衡度分析之后得出近似最优巡视路线。利用lingo软件求得，至少要分四组，且四组的近似最优巡视路线见附表2。 对于问题三：基于问题一二中图论的方法，考虑到从Ｏ点巡视H点的最短时间是所有巡视线路中用时最长的，将计算出的最长路线巡视所用的时间作为巡视路线的最短时间限定，在此限定下对路线进行设计。求得的最短时间为6.43小时，最佳巡视路线分为23组。（具体分组见附录二） 对于问题四：由于组数一定， T，t和V改变，对每组内的最佳巡视路线是没有影响的，但可能会影响到各组件的均衡性，因此问题实质是讨论T，t和V对分组的影响，即在不破坏原来分组均衡的条件下T，t和V允许的最大变化范围。 关键词：启发式算法 Dijkstra算法 均衡度 图论 二边逐次修正 1. 问题重述 1.1问题背景 今年夏天某县遭受水灾。为考察灾情、组织自救，县领导决定，带领有关部门负责人到全县各乡（镇）、村巡视。巡视路线指从县政府所在地出发，走遍各乡（镇）、村，又回到县政府所在地的路线。附录一中给出了该县的乡（镇）、村公路网示意图，公路边的数字为该路段的公里数。 1.2本文需解决的问题 问题一：若分三组（路）巡视，试设计总路程最短且各组尽可能均衡的巡视路线。 问题二：假定巡视人员在各乡（镇）停留时间T=2小时，在各村停留时间t=1小时，汽车行驶速度V=35公里/小时。要在24小时内完成巡视，至少应分几组；给出这种分组下你认为最佳的巡视路线。 问题三：在上述关于T , t和V的假定下，如果巡视人员足够多，完成巡视的最短时间是多少；给出在这种最短时间完成巡视的要求下，你认为最佳的巡视路线。 问题四：若巡视组数已定(如三组），要求尽快完成巡视，讨论T，t和V改变对最佳巡视路线的影响。 2. 模型的假设与符号说明 2.1模型的假设 假设1：公路不考虑等级差别，不受灾情和交通情况的影响。 假设2：各条公路段上的汽车行驶速度均匀。 假设3：各巡视组巡视的乡（镇）、村不受行政区划分的影响。 假设4：各巡视组行动统一，一个巡视组不可再分成若干小组。 假设5：巡视当中在每个乡（镇）村的停留时间一定，不会出现特殊情况而延误时间。 2.2符号说明 符号 符号说明 巡视小组在乡（镇）巡视的停留时间 巡视小组在村巡视的停留时间 汽车行驶速度 为导出子图中的最佳Ｈ圈。（其中=1，2，3，…，n.） 为的权，（其中=1，2，3，…，n.） 最大允许均衡度 分组后的实际均衡度 第个点距起始点的路线长度 点的时间权重 分组数 第组巡视时要停留的乡（镇）数 第组巡视时要停留的村数 最短时间下限 第巡视路线的长度 第巡视所用的时间 3. 问题分析 此题研究的是某县灾情巡视路线的设计问题。问题要求设计出最佳的巡视路线，即：保证总路程最短或时间最小而且各组尽可能均衡的巡视路线。基于图论相关理论，借助于几何直观和生活体验的启发作用，便于为计算机搜索制定行之有效的操作规则，接着利用图论软件包通过计算机求解出较精确的路线。再通过线路均衡性比较，对均衡性不好的线路进行微调。以此方法确定最佳巡视路线。 针对问题一：基于对问题的分析，借助图论知识，将所给公路网就转化为图论中的加权网络图，因此问题就转化为一个图论问题，即在给定的加权网络图中，寻找从给定点Ｏ出发，行遍所有顶点至少一次再回到Ｏ点，使得总权（路程或时间）最小。此即多个推销员的最佳推销员回路问题。基于以上分析，运用图论知识和图论软件包进行求解，再利用均衡度分析对得到的分组路线进行微调，均衡度越小表示路线越均衡，微调后即可得到相对较优的分组路线。可认为这样设计的分组方法和巡回路线能使总路线近似最短。 针对问题二：在问题一的基础上添加了巡视组在各乡镇停留时间T=2小时，在各村停留时间t=1小时，汽车行驶速度V=35公里/小时等条件，要求在24小时内完成巡视的最少分组数以及相应的最佳巡视路线。首先，由图中数据初步计算后判断分成四组可行，再针对分组为四组的情况进行线路设计，仍将问题转化为图论问题，运用问题一的求解方法，得到分为四组的路线，在通过均衡度分析之后得出近似最优巡视路线。 针对问题三：在问题二中关于T , t和V的假定下且巡视人员足够多时，要求在最短时间完成巡视的要求下所得的最佳的巡视路线，此时考虑到从Ｏ点巡视H点的最短时间是所有巡视线路中用时最长的，将计算出的最长路线巡视所用的时间作为巡视路线的最短时间限定，在此限定下对路线进行设计。基于问题一二中图论的方法，从一些点的路线比较少的点开始，能够使搜素容易进行，因此选择从距离Ｏ点一些较远的点（如12 10 15 22等点）开始搜索，每次搜索时都要对该点的巡视时间进行判断，直到找到近似最优路线。 针对问题四：在巡视组数已定(如三组）的情况下，为尽快完成巡视就要求每组完成的巡视时间尽量均衡，因为总的完成巡视时间按线路最长的完成巡视时间计算，由于组数一定， T，t和V改变，对每组内的最佳巡视路线是没有影响的，但可能会影响到各组件的均衡性，因此问题实质是讨论T，t和V对分组的影响，即在不破坏原来分组均衡的条件下T，t和V允许的最大变化范围。需要用控制单一变量的方法，分别讨论T、t、V三个量中任意两个量不变时第三个量的变化范围。从而确定T，t和V的改变对最佳巡视路线的影响。 4. 数据分析 4.1问题一数据分析 基于对该县公路图的初步分析，可以统计出该县有乡（镇）17个，村35个。（线路图见附录一） 应用lingo软件求解(具体程序见附录三)得出巡视点距离县政府所在地的最短距离，如表1所示： 表1：Ｏ点到其余各点的最短距离 P R 1 C 2 M 26 O 10.1 12.9 6 11.5 9.2 19.8 20.6 28 29 31 A B 3 5 O 22.2 20.8 22.1 16.3 11.9 14 17.5 N 25 20 L 6 7 D O 31.1 31.8 38.3 39 27.2 34.5 22.2 4 8 E 9 F 10 12 O 34.9 49.7 41.7 49.5 55.1 65.9 67.3 11 G H 13 14 J 19 O 55.9 62.7 77.5 64.1 72.7 54.3 46.2 18 I 15 16 17 22 K O 52.9 61.1 69.9 60.3 53.5 49 43.7 21 23 24 27 Q 30 32 O 39.6 39 44.3 28.4 28 35.7 30.2 33 35 34 O 23.7 36 27.8 由此表格画出了最短路径生成图，如图1 图 1 由上图便于在第一问分析得到分组情况。 4.2问题二数据分析 问题二中给出了巡视小组在乡（镇）村的停留时间和汽车行驶速度，分别为：巡视人员在各乡（镇）停留时间T=2小时，在各村停留时间t=1小时，汽车行驶速度V=35公里/小时。对于要在24小时内完成巡视，至少应分几组的问题，应首先求出最长路线巡视所用的时间，用停留总时间加上行走时间除以4的结果与24进行比较，以此判断最少分组能否为4组。计算如下： (17*2+35+599.8/35)/4=21.5<24(小时) （其中路线长度估算为599.8公里）因此最少分组可定为4组。 5． 问题一的解答 本文研究的是灾情巡视路线的最优设计问题，由于路线图可看成网络图，因此此问题可转化为在给定的加权网络图中寻找线路使总权（路程或时间）最小的问题。然后针对具体问题，采用一些启发式算法，建立模型。 5.1模型一的建立 5.1.1模型一的准备 经对问题的初步分析，基于图论的相关知识，将公路网图中每个乡（镇）、村看成图中的一个节点，各乡镇村之间的公路看作图中对应节点间的边，各条公路的长度（或行驶时间）看作对应边上的权，所给公路网就转化为图论中的加权网络图，问题就转化为一个图论问题，即在给定的加权网络图中寻找从定点Ｏ出发，行遍所有顶点至少一次再回到Ｏ点，使得总权（路程或时间）最小。 定义１　经过图Ｇ的每个顶点正好一次的圈，称为Ｇ的哈密尔顿圈，简称Ｈ圈。 定义２ 在加权图中 　　　　（１）权最小的哈密尔顿圈称为Ｈ圈： （２）经过每个顶点至少一次且权最小的闭通路称为最佳推销员回路。 由定义（2）可知本问题是一个寻求最佳推销员回路的问题，最佳推销员回路的问题可以转化为最佳Ｈ圈的问题，方法是由给定的图Ｇ＝（Ｖ，Ｅ）构造一个以Ｖ为顶点集的完备图Ｇ’=（Ｖ，Ｅ’）Ｅ’中每条边（x y）权等于顶点x与y在图Ｇ中最短路径的权，即。 在图论中有以下定理： 定理１ 加权图Ｇ的最佳推销员回路的权和Ｇ’的最佳Ｈ圈的权相同。 定理2 在加权完备图中求最佳Ｈ圈的问题是NP——完全问题。 我们采用一种近似算法求出该问题的一个近似最优解，来代替最优解，算法如下： 算法一 求加权图Ｇ＝（Ｖ，Ｅ）的最佳推销员回路的近似算法： ⑴用图论软件包求出Ｇ中任意两个顶点间的最短路，构造出完备图Ｇ’（Ｖ，Ｅ’） ⑵输入图Ｇ’的一个初始Ｈ圈； ⑶用对角线完全算法[2]产生一个初始Ｈ圈； ⑷随机搜索出Ｇ’中若干个Ｈ圈，例如3000个； ⑸对⑵⑶⑷步所得的每个Ｈ圈用二边逐次修正法[2]进行优化，得到近似最佳Ｈ圈； ⑹在第⑸步求出的所有Ｈ圈中，找出权最小的一个，此即要找的最佳Ｈ圈的近似解。（算法程序见附录） 由于二边主次修正法的结果与初始圈有关故本算法第⑵⑶⑷步分别用三种方法，产生初始圈，以保证能得到较优的计算结果。 在此问题是多个推销员的最佳推销员回路问题，即在加权图Ｇ中求顶点集Ｖ的划分Ｖ1，Ｖ２，…，Ｖｎ 将G分成n 个生成子图G[Ｖ１]， Ｇ［Ｖ２］，…，Ｇ[Vn]，使得： ⒈顶点ＯＶｉ，ｉ＝1,2,3，…，n. ⒉. ⒊，其中Ｃi 为导Ｖi的导出子图G[Ｖ１]中的最佳Ｈ圈，w(Ci)为Ci 的权，i，j=1，2，3，…，n. ⒋. 定义3 称为该分组的实际路线均衡度，为最大允许均衡度，显然01，越小说明分组的均衡性越好，取定一个后，与满足条件3的分组，条件4表示总巡视路程最短。 此问题包含两个方面：第一，对点分组；第二，在每组中寻求最佳推销员回路，即为单个推销员的最佳推销员问题，我们只能去寻求一种较合理的划分准则，对图进行初步划分后，求出各部分的最佳推销员回路的权，在进一步进行调整，使得各部分满足均衡性条件3. 从Ｏ点出发去其它点，要使路程较小应尽量走Ｏ点到该点的最短路，故用图论软件包求出Ｏ点到其余顶点的最短路，这些最短路构成一棵以Ｏ为树根的树，将从Ｏ点出发的树枝称干枝，如图2： 图 2 从图中可以看出，从Ｏ点出发到其它点共有6条干枝，他们的名称分别为①，②，③，④，⑤，⑥。 根据实际工作的经验及上述分析，在分组时应遵循以下准则： 准则一 尽量使同一干枝上及其分支上的点分在同一组； 准则二 应将相邻的干枝上的点分在同一组； 准则三 尽量将的干枝与短的干枝分在同一组。 由上述分组原则，为我们找到两组分组形式如下： 分组一：（⑥，①），（②，③），（⑤，④） 分组二：（①，②），（③，④），（⑤，⑥） 显然由图中可以直接看出分组一的方法极不均衡，故考虑分组二。 对分组二中每组顶点的生成子图，用算法一求出近似最优解及相应的巡视路线，使用算法一时在每个子图所构造的完备图中，取一个尽量包含图1中树上的边的Ｈ圈作为其第二步输入的初始圈。依次求解得到巡视路线的近似最优解。 5.1.1综上所述，问题一的优化模型为： 5.2问题一的解答。 在本模型的基础上，运用lingo软件求解出分三组巡视时近似最优的巡视路线（具体程序见附录三），如表2： 表2：分三组巡视的近似最优路线图 组号 路 线 路线长度 路线总长度 I OP282726N24232217 16I15I18K212025MO 191 589.8 II OR29Q303231333534 A1BC3D4D32O 192.3 III O256L19J11G1314 H12F10F9E8E765 2O 206.5 5.3问题一的结果分析 由以上分三组所得的路线结果可以看出， 第一组的巡视路线为： Ｏ－Ｐ－28－27―26―N―24―23―22―17―16―I―15―18―K―21―20―25―M―O 第二组巡视路线为： Ｏ－R－29－Q―30―32―31―33―35―34―A―1―B―C―3―D―4―D―3―2－O 第三组巡视路线为： Ｏ－2－5－6―L―19―J―11―G―13―14―H―12―F―10―F―9―E―8―E―7―6―5―2―O 将以上巡视线路的巡视距离进行均衡度分析： =7.46%=0.0746 当规定距离均衡度=0.1时，此三组的巡视路线的设计均符合要求。而且实际均衡度比0.1小得多，可见路线设计很合理。 6. 问题二的解答 6.1模型二的建立 6.1.1确定目标函数 由于T=2小时，t=1小时，V=35公里/小时，需访问的乡（镇）共有17个，村共有35个，计算出在乡镇的总停留时间为： 17*2+35=69（小时） 需要在24小时内完成巡视，考虑行走时间有： (17*2+35+599.8/35)/4=21.5<24(小时) （其中最长路线长度估算为599.8公里）因此最少分组可定为4组。 由于该网络的乡（镇）、村分布较均匀，故有可能找处停留时间计量均衡的分组，当分四组时各组停留时间大约为： 69/4=17.25（小时） 则每组分配在路途的时间大约为： 24－17.25=6.75（小时） 问题分析时有分三组路线时，巡视总路线最长的是599.8公里，分四组时的总路程更不会比599.8公里大太多，不妨以599.8公里来计算，路途时间约为： （599.8/35)/4=4.25（小时） 由于4.25<6.75（小时）因此分成四组是可以办到的。 现在尝试将顶点分为四组，分组准则为： 准则一 尽量使同一干枝上及其分支上的点分在同一组； 准则二 应将相邻的干枝上的点分在同一组； 准则三 尽量将的干枝与短的干枝分在同一组； 准则四 尽量使各组的停留时间相等。 以上原则将图1中的顶点分为四组，同时计算各组的停留时间，然后用模型一中的算法算出各组的近似最佳推销员巡回，得出路线长度及行走时间，从而得出完成巡视的近似最佳时间，用模型一的算法进行计算时，初始圈的输入与分三组时的处理方式一样。 利用lingo软件求解得出分为四组时的近近似最优巡视路线。 6.1.1综上所述，问题二的优化模型为 6.2问题二的求解 在模型二的基础上，运用lingo软件求解出分四组巡视时近似最优的巡视路线（具体程序见附录三），如表3： 表3：分四组巡视时的近似最优路线 组号 路 线 巡视时间 路线长度 路线总长度 I ORA3331323534B1 CD4D32O 22.74 166 735 II OR29Q30Q282726N 242322171617K2223N 26PO 21.91 206.9 III OM252021K18I151413 J19L6MO 21.75 166.3 IV O2567E8E9F10F 12H12G11E7652O 21.59 195.8 6.3问题二结果分析 由以上分四组所得的路线结果可以看出， 第一组的巡视路线为： Ｏ－R－A－33―31―32―35―34―B―1―C―D―4―D―3―2―O 第二组巡视路线为： Ｏ－R－29－Q―30―Q―28―27―26―N―24―23―22―17―16―17―K―22―23―N－26―P―O 第三组巡视路线为： Ｏ－M－25－20―21―K―18―I―15―14―13―J―19―L―6―M―O 第四组的巡视路线为： Ｏ－2－5－6―7―E―8― E―9―F―10―F―12―H―12―G―11―E―7―6－5―2―O 对以上巡视线路的巡视距离进行均衡度分析： =19.33%=0.1933 对以上巡视线路的巡视时间进行均衡度分析： =5.06%=0.0506 由距离均衡度和时间均衡度可以看出，所分组的巡视路线的距离均衡度较好，时间均衡度也较好。 因此，所得路线可以认为是分组的近似最优解巡视线路。 7. 问题三的解答 7.1模型三的建立 7.1.1确定目标函数 由于巡视人员足够多，故单独巡视所花的时间要小的多，所有组中完成的巡视时间最长的可看为完成巡视时间的下限tmin ，从最短生成树上可以看出，点Ｈ距离点Ｏ最长，且Ｈ的权最大（为2），故巡视Ｈ的那组所花的时间为完成整个巡视时间的下限： =（小时） 于是问题变成在6.43小时内完成巡视所需的最少分组和巡视方案。 则目标函数： minn 7.1.2确定约束条件 即使人员足够多，分组再细，完成巡视至少需要的时间不能超过巡视时间的下限，即： 7.1.3综上所述，得到问题三的优化模型 minn s.t 7.2问题三的求解 我们采用一种算法解决此问题，算法如下： ⑴ 令i=0； ⑵选最短树形图中违背标号的点中离Ｏ点最近的点，设为Ｍ，Ｍ与Ｏ的距离记为lm ,设第i个巡视点集Vi ={Ｍ}，计算V最多还可增加的点的权之和 ⑶尽可能使并入Vi的点的权之和为[l’m]，同时满足从Ｏ点出发，经历Vi中所有点并回到Ｏ点的路Li，使，为路Li的长度，分别为权为的点的个数。若同时存在几种并入方式，先取并入的点到Ｏ点距离和最大的那一种。 ⑷在图中把含有的点标上号，若还有点未标号，令i=i+1转⑵，否则，停止。 通过这种算法利用lingo软件包处理得到分组数为23组，（具体程序见附录三）结果见表3： 表3：巡视人员足够多时的近似最佳巡视路线 编号 巡视路径 停留地 所需时间 时间差 1 O-2-5-6-7-E-9-F-12-H-12-F-9-E-7-6-5-2-O H 6.43 0 2 O-2-5-6-L-19-J-13-14-13-J-19-L-6-5-2-O 13,14 6.15 0.28 3 O-2-5-6-7-E-9-F-10-F-9-E-7-6-5-2-O 10,7 5.77 0.66 4 O-2-5-6-7-E-9-F-12-F-9-E-7-6-5-2-O 12,9 5.85 0.58 5 O-M-25-21-K-18-I-15-I-18-K-21-25-M-O 15,18 5.99 0.44 6 O-2-5-6-7-E-11-G-11-E-7-6-5-2-O G 5.58 0.55 7 OM-25-K-18-I-18-K-25-M-0-O I 5.49 0.94 8 O-M-25-21-K-17-16-17-K-21-25-M-O 16,17 5.45 0.98 9 O-2-5-6-7-E-11-E-7-6-5-2-O 11,E 6.19 0.24 10 O-2-5-6-7-E-9-F-9-E-7-6-5-2-O F 5.15 1.08 11 O-2-5-6-L-19-J-19-L-6-5-2-O J,19 6.10 0.33 12 O-P-26-N-23-22-23-N-26-P-O 22,23,26 5.80 0.63 13 O-2-5-6-7-E-8-E-7-6-5-2-O 8,5,2 5.80 0.63 14 O-P-26-N-24-N-26-P-O 24,N 5.53 0.90 15 O-M-25-21-K-21-25-M-O K,21 5.50 0.93 16 O-2-5-6-L-6-5-2-O L,6 5.23 1.02 17 OM-25-20-25-M-O 20,25,M 6.19 0.24 18 O-R-31-32-35-34-A-1-O 31,32,34,35 6.32 0.11 19 O-29-Q-30-29-R-O 30,Q,29 6.04 0.39 20 O-2-3-D-4-D-3-2-O 4,D,3 5.99 0.44 21 O-1-B-C-O 1,B,C 5.98 0.45 22 OP-26-27-28-P-O- 27,P,26,28 6.38 0.05 23 O-1-A-33-A-R-O A,33,R 6.41 0.02 7.3问题三的结果分析 由上求得最短巡视时间为6.43小时。 在问题二T , t和V的假定下，若果人员足够多，甚至每个村镇都可分配一组巡视人员，此时巡视的最短时间为所有组中完成的巡视时间最长的那个时间，故计算出离出发点最远的点所需的巡视时间作为完成巡视的最短时间是切合实际的。 上表是在6.43小时内完成巡视所需的最少分组和巡视方案，可见，最少分组为23组，每组完成巡视的时间分别为： 6.43－6.15－5.77－5.85－5.99－5.58－5.49－5.45－6.19－5.15－6.10－5.80－5.53－5.50－5.23－6.19－6.32－6.04－5.99－5.98－6.38－6.41 可见以上各组完成巡视时间均在6.43小时内。 且各个小组完成巡视的时间与最短时间下限之差很小，如表中所示，时差分别为： 0―0.28―0.66―0.58―0.44―0.55―0.94―0.98―0.24―1.08―0.33―0.63―0.63―0.90―0.93―1.02―0.24―0.11―0.39―0.44―0.45―0.05―0.02 由此可见最大时差为1.08最小时差为0，时差变化范围较小。 接着利用时间均衡度来衡量分组的均衡性，得到时间均衡度为： =15.55%=0.1555 可见在这种分配方案下，巡视时间和所分组数均可以认为是近似最优解。 8. 问题四的解答 8.1模型四的建立 8.1.1确定目标函数 8.1.1.1模型准备 方法一： 正如问题三已经提到的要尽快完成巡视即要求各组巡视时间的最大值也要最小，用数学表达式就是： 这里是给定的分组数，分别是第组停留的乡（镇）数和村数，是第组巡视路线的长度（=1，2，…,k） 在上述的表达式中，由于的作用完全相仿，所以为简化起见对于任意给定的，不妨记，即，这里可简记为 ⒈若t增大而V不变，为了使的最大值尽可能小就要求的最大值尽可能小。但是当T和t的关系确定后，是定值（等于，其中是全县的乡（镇）数17，是全县的村数35）。上述要求就成为各组停留乡村数（加权之后之和）尽可能均衡，用数学式子表示即为： 这里和分别表示数的上整数和下整数，当然在调整各组的停留的乡村数使之达到均衡时，自然会给各组的路线及其长度带来影响，这时应当考虑进行适当调整。 ⒉若t不变而V增大，这种情况下，在中可能导致起主导作用。因此和1的结论类似，更应使即各组的巡视路线尽可能均衡，又因为不是常数，而且的均衡性会带来的增大，这对于尽快完成巡视会带来负面影响，所以对具体情况应做具体分析，比如可以考虑的前半部分对均衡性的修正，对路线较长的组尽量考虑停留较少的乡村。 对于T , t和V之间的交互作用会使情况变得更复杂。 此方法有助于要讨论T , t和V之间的变化，但是不能定量的求出T , t和V的变化范围，因此我们在此方法上进行改进，如方法二。 方法二： 确定T , t和V允许的最大变化范围。 在已确定组数的情况下，无论T , t和V如何改变，对每组内的最佳寻视路线是没有影响的，可能会影响各组间的均衡性，因此问题转化为在不破坏原来分组均衡的条件下，T , t和V允许的最大变化范围。 在分n组的情况下，设 Si表示第i组的最佳推销员回路路线总长度； Xi表示第i组所要停留的乡镇的数目； Yi表示第i组所要停留的村的数目； i=1，2，3，…，n. 显然，当Xi=Xj，Yi=Yj,Si=Sj，i，j=1，2，3，…，n.时即每组的乡（镇）数、村数最佳巡回的长度均相等，因而分组绝对均衡时，即=0，无论T , t和V如何改变都不会改变原来分组的均衡。 （一） 不影响分组的均衡时，T , t和V的最大允许范围的讨论： 对任意一个组i，其完成巡视的时间： 设均衡分组的最大允许时间均衡度为，即： 则有： 记，则表示均衡分组所允许的最大时间误差，称为最大允许时间误差。则： 由上式我们得到 由此式可推出以下结果： 1当Xi-Xj>0时，要保持原均衡分组不变，T必须满足的条件为： 2.当Yi-Yj>0时，要保持原均衡分组不变，t必须满足的条件为： 3.当Si-Sj>0时，有 （1）当时，有 （2）当时，有 由1.2.3.中的式子知，当T 、t、V三个变量中任意两个变量无论如何变化，都可计算出为保持均衡分组不变，三个变量所允许的最大变化范围。 （二）分三组的实例讨论。 现对分三组的情况进行实际讨论。对问题一中所得的三个分组，若考虑停留时间和行驶时间，且取T=T0=2小时，t=t0=1小时，V=V0=35公里/小时时，结果如下表4所示： 表4：分三组巡视相关表 编号 Xi Yi Si 行驶时间 总时间 I 5 13 191 5.46 28.46 II 6 11 192.3 5.49 28.49 III 6 12 206.5 5.9 29.9 由表可计算时间的实际均衡度为： ==4.8%=0.048 实际时间误差=0.048*29.9=1.44（小时） 现分别规定均衡分组的最大允许均衡度为=4.8%和=9.6%,即最大允许的时间误差分别为：1.44小时和2.88小时。 计算出T , t和V中三个参量中任意两个固定时，要不破坏原平衡分组，另一个参量所要允许的变化范围。计算结果如下表5： 表5：T ，t，V中三个参量的变化范围 T，V不变 t，V不变 T，t不变 =4.8% =1.44 =9.6% =2.88 由上表可以看出： （1）当实际均衡度=4.8%，刚好等于最大允许均衡度=4.8%时，要保持原均衡分组，当： t，V不变时，T只能减小，且下界为1.25小时，上界为2小时。 T，V不变时，t只能增大，且上界为1.38小时，下界为1小时。 T，t不变时，V只能增大，且无上界，V的下界为35公里/小时。 （2）当实际均衡度=4.8%，小于最大允许均衡度=9.6%时，要保持原均衡分组，当： t，V不变时，T的变化上界为0.51小时，下界为2.74小时。 T，V不变时，t的变化上界为0.63小时，下界为1.75小时。 T，t不变时，V无上界，V的下界为17.3公里/小时。 9. 模型的评价、改进及推广 9.1模型评价 优点： （1）本文提出的分组准则简便易行，可操作性强，且可逐步调整使分组达到均衡。 （2）引用均衡度的概念定量的刻画了分组的均衡性。 （3）再用近似法求解最佳推销员回路时采用了三种不同的方法产生初始圈，使得算法比较完善，得到了误差很小的而近似最优解。 （4）从理论上定量的讨论了T，t和V的变化对均衡分组灵敏度的影响，得到了很好的结果。 缺点：使用的方法不能求得最优解，只能求得近似最优解。 9.2模型改进 （1）求解时可建立将多组路线转化为一组路线来求解的思想，如果能够找出一种准则，使三个代表县城点之间的距离尽量大，则在最好的情况下，将使两个县城点均分整个一条路线，这种改进将简化问题的求解，并可以得到较好的解。 （2）由于线路的设计是在假设条件下取得的近似最优解，因此，需要减少假设更多的考虑实际情况下的最优路线的设计。 9.3模型推广 本文建立的模型可以广泛它应用于实际生活中涉及到图论的有关问题，例如公交线路的而选择问题，城市相关设施的布置等相关问题。 参考文献 [1] 运筹学与实验/薛毅，耿美英编著。—北京：电子工业出版社，2008.9 [2] 《运筹学》教材编写组编，运筹学（3版），北京：清华大学出版社，2005.6 [3] 图论算法及其MATLAB实现/王海英等编著. —北京：北京航空航天大学出版社，2010.2 附录 附录一：县政府线路图 附录二： 编号 巡视路径 停留地 所需时间 时间差 1 O-2-5-6-7-E-9-F-12-H-12-F-9-E-7-6-5-2-O H 6.43 0 2 O-2-5-6-L-19-J-13-14-13-J-19-L-6-5-2-O 13,14 6.15 0.28 3 O-2-5-6-7-E-9-F-10-F-9-E-7-6-5-2-O 10,7 5.77 0.66 4 O-2-5-6-7-E-9-F-12-F-9-E-7-6-5-2-O 12,9 5.85 0.58 5 O-M-25-21-K-18-I-15-I-18-K-21-25-M-O 15,18 5.99 0.44 6 O-2-5-6-7-E-11-G-11-E-7-6-5-2-O G 5.58 0.55 7 OM-25-K-18-I-18-K-25-M-0-O I 5.49 0.94 8 O-M-25-21-K-17-16-17-K-21-25-M-O 16,17 5.45 0.98 9 O-2-5-6-7-E-11-E-7-6-5-2-O 11,E 6.19 0.24 10 O-2-5-6-7-E-9-F-9-E-7-6-5-2-O F 5.15 1.08 11 O-2-5-6-L-19-J-19-L-6-5-2-O J,19 6.10 0.33 12 O-P-26-N-23-22-23-N-26-P-O 22,23,26 5.80 0.63 13 O-2-5-6-7-E-8-E-7-6-5-2-O 8,5,2 5.80 0.63 14 O-P-26-N-24-N-26-P-O 24,N 5.53 0.90 15 O-M-25-21-K-21-25-M-O K,21 5.50 0.93 16 O-2-5-6-L-6-5-2-O L,6 5.23 1.02 17 OM-25-20-25-M-O 20,25,M 6.19 0.24 18 O-R-31-32-35-34-A-1-O 31,32,34,35 6.32 0.11 19 O-29-Q-30-29-R-O 30,Q,29 6.04 0.39 20 O-2-3-D-4-D-3-2-O 4,D,3 5.99 0.44 21 O-1-B-C-O 1,B,C 5.98 0.45 22 OP-26-27-28-P-O- 27,P,26,28 6.38 0.05 23 O-1-A-33-A-R-O A,33,R 6.41 0.02 附录三 最短路径算法 % 求两点间最短路的 Dijkstra 算法 function [d index1 index2] = Dijkf(a) % a 表示图的权值矩阵; d 表示所求最短路的权和 % index1 表示标号顶点顺序； index2 表示标号顶点索引 % 参数初始化 M = max( max(a) ); pb(1 : length(a)) = 0; pb(1) = 1; index1 = 1; index2 = ones(1, length(a)); d(1 : length(a)) = M; d(1) = 0; temp = 1; % 更新1(v), 同时记录顶点顺序和顶点索引 while sum(pb) < length(a) tb = find( pb == 0 ); d(tb) = min( d(tb), d(temp) + a(temp, tb) ); tmpb = find( d(tb) == min( d(tb) ) ); temp = tb( tmpb(1) ); pb(temp) = 1; index1 = [index1, temp]; index = index1( find( d(index1) == d(temp) - a( temp, index1 ) ) ); if length(index) >= 2 index = index(1); end index2(temp) = index; end d; index1; index2; 第一组路径的程序 SETS: city/1, 2, 7, 8, 9, 16, 17, 18, 37, 38, 39,40, 41,42, 43, 44, 45, 46,47/:u; link(city, city):w, x; ENDSETS DATA: !w = @FILE('C:\Users\Administrator\Desktop\data51.txt'); w = 0 10.1 19.8 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10.1 0 10000 10.5 12.1 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 19.8 10000 0 10000 10000 14.2 12.0 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10.5 10000 0 10000 10.5 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 7.8 10000 12.1 10000 10000 0 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 7.9 10000 10000 14.2 10.5 10000 8.8 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 7.9 13.2 10000 10000 12.0 10000 10000 8.8 0 6.5 10000 10000 10000 10000 10000 10000 10000 7.8 10000 10000 10000 10000 10000 10000 10000 10000 10000 6.5 0 10000 10000 10000 10000 10000 10000 10000 7.9 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 0 8.2 10000 10000 10000 10000 9.2 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 8.2 0 8.8 11.8 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 8.8 0 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 11.8 10000 0 6.8 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 6.8 0 6.7 9.8 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 6.7 0 10.1 10000 10.0 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 9.2 10000 10000 10000 9.8 10.1 0 4.1 10000 10000 10000 10000 10000 10000 10000 10000 10000 7.8 7.9 10000 10000 10000 10000 10000 10000 4.1 0 9.1 10000 10000 10000 10000 10000 10000 10000 7.9 10000 10000 10000 10000 10000 10000 10000 10.0 10000 9.1 0 8.9 10000 10000 10000 10000 10000 10000 13.2 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 8.9 0 18.8 10000 10000 10000 7.8 7.9 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 18.8 0 ENDDATA n = @SIZE( city ); MIN = @SUM( link: w * x ); @FOR( city(k): @SUM( city(i) | i #ne# k : x(i,k) ) = 1; @SUM( city(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) ); 第二组路径的程序 SETS: city/1, 3, 4, 5, 6, 10, 11, 12, 13, 14, 22, 23, 48, 49, 50, 51, 52, 53/:u; link(city, city):w, x; ENDSETS DATA: !w = @FILE('C:\Users\Administrator\Desktop\data51.txt'); w = 0 12.9 6 11.5 9.2 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 12.9 0 10000 10000 10000 7.9 9.2 8.8 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 6 10000 0 11.2 10000 10000 10000 10.3 5.9 10000 10000 10000 10000 10000 10000 10000 10000 10000 11.5 10000 11.2 0 10000 10000 10000 10000 11 7.9 10000 10000 10000 10000 10000 10000 10000 10000 9.2 10000 10000 10000 0 10000 10000 10000 10000 4.8 10000 10000 10000 10000 10000 10000 10000 10000 10000 7.9 10000 10000 10000 0 10000 10000 10000 10000 10000 10000 7.2 10000 10000 10000 10000 10000 10000 9.2 10000 10000 10000 10000 0 10000 10000 10000 10000 10000 10000 10000 8.1 7.3 10000 10000 10000 8.8 10.3 10000 10000 10000 10000 0 10000 10000 10000 10000 10000 10000 10000 7.4 10000 11.5 10000 10000 5.9 11 10000 10000 10000 10000 0 10000 10000 10000 10000 10000 10000 10000 10000 17.6 10000 10000 10000 7.9 4.8 10000 10000 10000 10000 0 8.2 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 8.2 0 12.7 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 12.7 0 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 7.2 10000 10000 10000 10000 10000 10000 0 7.7 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 7.7 0 10.3 10000 10000 10000 10000 10000 10000 10000 10000 10000 8.1 10000 10000 10000 10000 10000 10000 10.3 0 19 14.9 10000 10000 10000 10000 10000 10000 10000 7.3 7.4 10000 10000 10000 10000 10000 10000 19 0 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 14.9 10000 0 8.2 10000 10000 10000 10000 10000 10000 10000 11.5 17.6 10000 10000 10000 10000 10000 10000 10000 8.2 0; ENDDATA n = @SIZE( city ); MIN = @SUM( link: w * x ); @FOR( city(k): @SUM( city(i) | i #ne# k : x(i,k) ) = 1; @SUM( city(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 ); 第三组路径的程序 SETS: city/1, 6, 15, 19, 20, 21, 24, 25, 26, 27, 28,29, 30,31, 32, 33, 34, 35,36/:u; link(city, city):w, x; ENDSETS DATA: !w = @FILE('C:\Users\Administrator\Desktop\data51.txt'); w = 0 9.2 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 9.2 0 8.3 1000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 8.3 0 10000 9.7 1000 11.3 10000 10000 10000 10000 10000 10000 10000 100