交巡警服务平台设置与调度问题的研究.doc

2011高教社杯全国大学生数学建模竞赛承 诺 书我们仔细阅读了中国大学生数学建模竞赛的竞赛规则.我们完全明白，在竞赛开始后参赛队员不能以任何方式（包括电话、电子邮件、网上咨询等）与队外的任何人（包括指导教师）研究、讨论与赛题有关的问题。我们知道，抄袭别人的成果是违反竞赛规则的, 如果引用别人的成果或其他公开的资料（包括网上查到的资料），必须按照规定的参考文献的表述方式在正文引用处和参考文献中明确列出。我们郑重承诺，严格遵守竞赛规则，以保证竞赛的公正、公平性。如有违反竞赛规则的行为，我们将受到严肃处理。我们参赛选择的题号是（从A/B/C/D中选择一项填写）： B 我们的参赛报名号为（如果赛区设置报名号的话）： GZQN201111 所属学校（请填写完整的全名）： 黔南民族师范学院 参赛队员 (打印并签名) ：1. 杨正清 2. 阳顺才 3. 陈忠霞 指导教师或指导教师组负责人 (打印并签名)： 郭德龙 日期： 2011 年 9 月 12 日赛区评阅编号（由赛区组委会评阅前进行编号）：2011高教社杯全国大学生数学建模竞赛编 号 专 用 页赛区评阅编号（由赛区组委会评阅前进行编号）：赛区评阅记录（可供赛区评阅时使用）：评阅人评分备注全国统一编号（由赛区组委会送交全国前编号）：全国评阅编号（由全国组委会评阅前进行编号）：交巡警服务平台设置与调度问题的研究摘 要本文研究的是某城区交巡警服务平台的设置与调度问题,建立了求解警车巡逻方案的模型及重大刑事案件最佳围堵方案模型。针对问题一：首先利用迪克斯特拉（Dijkstra)算法初步得到20个交巡警服务台的管辖范围（见表1），结合实际对初步得到的交巡警服务台管辖范围进行分析，得出各交巡警服务台的管辖范围（见表2）。其次建立0-1整数规划模型,利用Lingo软件进行求解，得出较合理的交巡警服务平台警力调度方案（见表3）。并得出快速封锁13条交通要道所用最短时间为480.90秒。最后以案发率和管辖路口节点数为指标，按照这两指标的优先权来确定增加的服务平台数与增加服务平台的具体位置。结合实际情况，在A区增加了5个交巡警服务平台，具体位置分别在 43、30、34、81、86等五个路口节点处。针对问题二：我们以各区巡警服务平台总数与该区每天总案发率的比值和服务率作为评价指标,综合两个评价指标分析得到全市六个区中区和区的现有交巡警服务平台的设置较为合理,而区的现有交巡警服务平台的设置最为不合理。并依据这些路口处的案发率与密集程度，选取编号为505、522的路口节点再建两个交巡警服务平台后指标的值变为0.11，比原来的0.09上升了0.2个百分点，而指标的值变为0.17，比原来的0.32下降了将近0.15个百分点，这就说明改进的方案是比较好的。对于最佳围堵方案的确定，首先求出犯罪嫌疑人案发后的所有可能行走的路线，确定出3分钟后犯罪嫌疑人所有可能出现的路口节点。再调动最近的交巡警服务平台对其进行围堵，最后得到一个最佳的围堵方案，求得最短的围堵时间为176.94秒。关键词：交巡警服务平台；Dijkstra算法；0-1整数规划；调度方案；最佳围堵方案一 问题重述“有困难找警察”，是家喻户晓的一句流行语。警察肩负着刑事执法、治安管理、交通管理、服务群众四大职能。为了更有效地贯彻实施这些职能，需要在市区的一些交通要道和重要部位设置交巡警服务平台。每个交巡警服务平台的职能和警力配备基本相同。由于警务资源是有限的，如何根据城市的实际情况与需求合理地设置交巡警服务平台、分配各平台的管辖范围、调度警务资源是警务部门面临的一个实际课题。试就某市设置交巡警服务平台的相关情况，建立数学模型分析研究下面的问题：（1） 附件1中的附图1给出了该市中心城区A的交通网络和现有的20个交巡警服务平台的设置情况示意图，相关的数据信息见附件2。请为各交巡警服务平台分配管辖范围，使其在所管辖的范围内出现突发事件时，尽量能在3分钟内有交巡警（警车的时速为60km/h）到达事发地。对于重大突发事件，需要调度全区20个交巡警服务平台的警力资源，对进出该区的13条交通要道实现快速全封锁。实际中一个平台的警力最多封锁一个路口，请给出该区交巡警服务平台警力合理的调度方案。根据现有交巡警服务平台的工作量不均衡和有些地方出警时间过长的实际情况，拟在该区内再增加2至5个平台，请确定需要增加平台的具体个数和位置。（2）针对全市（主城六区A，B，C，D，E，F）的具体情况，按照设置交巡警服务平台的原则和任务，分析研究该市现有交巡警服务平台设置方案（参见附件）的合理性。如果有明显不合理，请给出解决方案。如果该市地点P（第32个节点）处发生了重大刑事案件，在案发3分钟后接到报警，犯罪嫌疑人已驾车逃跑。为了快速搜捕嫌疑犯，请给出调度全市交巡警服务平台警力资源的最佳围堵方案。二 问题分析本题为城区交巡警服务平台的设置与调度问题。在进行设置交巡警服务平台时，首先要考虑警车在接到报警后在规定时间内赶到事发现场，以路径最短为目标，建模、求解；在制定调度方案时，要考虑交巡警调度的效果及一些隐蔽性问题。问题一是要满足在3分钟内尽量能有交巡警（警车的时速为60km/h）到达事发地的条件。在3分钟内交巡警警车从服务平台出发能到达最长的范围为。根据题目所给的数据及图像。为了确定各交巡警服务平台分配管辖范围，这将涉及到最短路问题，也就是说到达某服务平台距离小于等于的路口节点属于该服务台管理。利用迪克斯特拉（Dijkstra)算法来求解最短路，初步得到各交巡警服务平台的管辖范围。再结合实际情况与相关数据进行分析，最后得到了各交巡警服务平台的管辖范围。对于重大突发事件，要调度全区20个交巡警服务平台的警力资源，对进出该区的13条交通要道实现快速封锁问题，这是一个规划问题。我们以最少时间最大距离为目标函数，构建一个0-1整数规划模型。运用Lingo软件进行求解，最后得到最为合理的服务平台警力的调度方案。为了确定增加服务平台的数量与具体位置，我们首先计算出各交巡警服务平台管辖范围内（除服务平台）的平均案发率，及统计其管辖范围内的路口节点数。根据案发率与路口节点数的优先权来确定增加服务台数。再根据路口各节点的案发率优先权来确定服务平台的位置。问题二共有两个小问。第一小问是对该市现有的交巡警服务平台，按照设置交巡警服务平台的原则与任务，分析研究其现有交巡警服务平台的合理性。为了能够评价出该市交巡警服务平台的合理与否，我们从案发率、服务率来进行评价。首先对该市各区进行评价，得出是各区中最差的点。然后由各区得到的结果来评价该市交巡警服务平台设置方案的合理性，得出该市的交巡警服务平台的设置方案是不合理。最后我们采用改进该市合理性最差的区来改进该市的交巡警服务平台的不合理性。第二小问是为在发生重大刑事案件时给出最佳的围堵方案。根据附件2及假设条件，先确定出在3分钟内犯罪嫌疑人可能到达的路口节点或路段。应用服务平台中的交巡警动与不动原则得出最佳的围堵方案三 基本假设与符号说明3.1 基本假设 假设1 案件均发生在路口节点处； 假设2 巡警出警时道路畅通（无交通事故等发生），警车能够正常工作； 假设3 路途转弯处的时间忽略不计； 假设4 警车在路上巡逻时巡警去处理案件的时间不考虑； 假设5 发生重大突发案件时各交巡警服务平台同时接到报警； 假设6 题目所给的数据都是真实、可靠的数据。 假设7 罪犯在地点P（第32个节点）处作案后，立即逃离现场； 假设8 罪犯驾车的全程速度都是； 假设9 各交巡警服务平台接到报警电话后，立即派人员出发进行围堵。3.2 符号说明符号符号解释相关案发概率警车从交巡警服务平台出发能够到达最远的范围警车的速度时间图形比例、分别为起点和终点与两路口间的最短距离0-1矩阵第区的平均案发率区节点案发率某交巡警服务平台管辖范围内大的路口节点总数四 模型建立与求解4.1 问题一的求解题目要求是在3分钟内尽量有交巡警到达事发现场，那么有警车从交巡警服务平台出发能够到达最远的范围为，即 其中为警车从交巡警服务平台出发能够到达最远的范围，=3表示时间，表示警车行驶速度，表示图形比例。将数据代入得到（实际值为）。 4.1.1 各交巡警服务平台分配管辖范围的确定这是一个交巡警服务平台分配管辖范围问题,将区中20个交巡警服务平台，覆盖除交巡警服务平台设置的路口节点外的72个路口节点。首先根据附件2中“全市交通路口节点数据”和“全市交通路口的路线”的数据信息，得到一个的邻接权值矩阵A（其中没有通路的赋予无穷大，自身路口节点到自身路口节点赋予0，两两路口节点的权值为他们间的距离）。运用迪克斯特拉（Dijkstra）算法求解每一个交巡警服务平台到72个路口节点处的最短距离得到一个的距离矩阵。寻找矩阵中每一列最小的数为第个路口节点在第个交巡警服务平台的管辖范围之内。迪克斯特拉（Dijkstra）算法的基本思想：、分别为起点和终点，按距从近到远为顺序，依次求得到矩阵的各顶点的最短路和距离，直至（或直至的所有顶点），算法结束。为避免重复并保留每一步的计算信息，采用了标号算法，下面是该算法的步骤：（i）令，对（A中的顶点），令，；（ii）对每一个（），用代替，计算，把达到这个最小值的一个顶点记为，令；（iii）若，停止，若，用代替，转到（ii）。算法结束时，从到各顶点的距离由的最后一次的标号给出。在进入之前的标号叫标号，进入后的标号叫标号。算法就是不断修改各顶点的标号，直至获得标号。若在算法运行过程中，将每一定点获得标号所由来的边在图上标明，则算法结束，至各定点的最短路也在图上表示出来。调用程序（程序见附件1与附件2）算得20个交巡警服务平台覆盖72个路口节点的情况如表1。表1 各个交巡警服务平台管辖的路口节点交巡警服务平台编号路口节点的编号1676869717374757678239404344707235455656645760626364549505152535658596730324748618334693134354510续表1 各个交巡警服务平台管辖的路口节点交巡警服务平台编号路口节点的编号1126271225132122232414152829163637174142188081828319777920848586878889909192其中表1中的第一列表示A区20个交巡警服务平台的编号，其余各列的数字表示72个路口节点的编号，没有数据的就表示除了本身这个路口节点外没有任何一个路口节点是属于该交巡警服务平台的管辖内。这只是一个粗略的划分，为了得到更好我们将考虑各路口的平均每天发案件数，以及各交巡警服务平台到该路口节点的道路距离，再次对表1中的划分进行更为详细的划分。编号为75、76、78的路口节点原本到编号为1的交巡警服务平台的道路距离最短，可这三个路口节点到编号为19交巡警服务平台的道路距离分别为17.8565、14.3210、11.180毫米，都在30毫米以内，故满足题意的要求，因此把这三个路口节点划分给19号交巡警服务平台。同理将原本属于交巡警服务平台5的50、51路口节点划分到编号为6的交巡警服务平台，该路口到交巡警服务平台6的道路距离分别是22.7564、12.2932毫米也都在30毫米以内。为了更减少交巡警服务平台20的压力，将粗略划分的84、89路口节点划分到交巡警服务平台18中，他们到交巡警服务平台18的道路距离也是有11.7522、9.4868毫米。调整后得到20个交巡警服务平台各自的管辖范围，见表2。表2 较为精细覆盖表交巡警服务平台编号路口节点的编号16768697173741239404344707223545565663457606263644549525356585956505167303247486178334689313435459101011262711续表2 较为精细覆盖表交巡警服务平台编号路口节点的编号122512132122232413141415282915163637381617414217188081828384891819777975767819209085868788919220 4.1.2 交巡警服务平台警力合理的调度方案 这相当于一个规划问题，即有重大突发事故时，要快速地调动现有20个交巡警服务平台的警力资源对13个交通要道路口进行封锁，考虑到一个平台的警力最多封锁一个路口，所以我们采用0-1整数规划对该问题进行求解（即该平台封锁此路口值为1，不封锁该平台其值为0），以最大距离最短时间为目标函数建立如下模型：目标函数：约束条件： 运用Lingo软件与Matlab软件（程序见附件三与附件四）对该模型进行求解得到如下结果（表3）：表3 交巡警服务平台警力合理的调度方案交巡警服务平台交通要道路口标号（M）服务平台到要道路口的最短距离（mm）所需时间（s）101275.86455.16161467.42404.5281626.92161.52142132.65195.90122268.83412.98续表3 交巡警服务平台警力合理的调度方案交巡警服务平台交通要道路口标号（M）服务平台到要道路口的最短距离（mm）所需时间（s）112346.75280.50132423.85143.10152847.52285.1272980.15480.9093054.24325.4423829.82178.9254824.76148.56206264.49386.94由以上的调度方案可知：该区的13条交通要道分别由10 ，16，8，14，12，11， 13，15，7，9，2，5，20这几个交巡警服务平台对其进行快速封锁所得到的时间是所有可能的方案中最短的，因为我们以调动的最远距离为目标函数，速度恒定，取得时间亦是最短的，耗时480.90秒就能对这13条交通要道进行全面的快速封锁。 4.1.3 确定需要增加平台的具体个数和位置应用区域每天各路口（除服务平台）平均发生的事故的概率与服务平台管辖范围的点数做为增加平台数目的标准。若在服务平台管辖范围内平均发生的概率高于等于1.00时须增加巡警服务平台。增加服务台原则是：在1.00到2.00之间增加一个，在2.00到3.00之间增加2个服务台，也就是说在1.00的基础上每增加1.00就增加一个服务台。结合已划分好的管辖范围有： 其中是第区的平均发生事故概率，为各区的节点个数，表示区节点发生事故的概率。将数据代入模型计算易得到各巡警服务平台管辖范围内（除服务平台）平均发生事故的概率，见表4。表4 各巡警服务平台管辖范围平均发生事故的概率编号123456789100.851.091.001.000.950.951.441.301.520.00编号111213141516171819201.201.601.500.001.350.801.401.100.861.30由上表可以知道，根据我们所确定的服务平台增加原则具有一定的缺点，也就是说没有完全考虑到我们所选用的两个指标，得到的结果将不符合题目要求。因此为了更好确定增加的巡警服务平台的具体位置与数量，我们根据平均发案率优先与路口节点数优先方法来确定。即如果 则优先考虑发案率的区域；如果 则优先考虑点数为的区域。所以同时满足这两个因素的服务平台管辖范围才应该增加服务平台。我们结合表2、表3及题目所给的数据进行分析得到应该在2、7、9、18、20等五个交巡警服务平台管辖的范围内增加服务平台。由我们得到所增加的服务平台数及所在区域，为了确定增加的服务平台在区域内的具体位置，应用各点发案率的优先级来确定。由题目所给的数据，知道各点的发案率。则有在这五个区域内确定五个增加的服务平台的位置分别在 43、30、34、81、86等五个路口节点。4.2 问题二的求解4.2.1 交巡警服务平台设置方案的评价该问题要求按照交巡警服务平台的工作效力和分配任务的相对均衡性，对全市六个区现有的交巡警服务平台设置方案进行合理性的评价。我们假设各区一旦出现交通事故，服务台接到电话后3分钟内到达事故现场较为合理，超过的就说明工作效力的降低；再分析各个区每天总案发率与该区共设置的交巡警服务平台之间的关系。我们选取以下两个指标进行综合评价。 （5） （6）当指标的值越接近1时，说明该区的交巡警服务平台设置方案就越合理，即值越大越合理；当指标的值越接近0时，说明该区的交巡警服务平台设置方案也就越合理，即值越小越合理。我们运用迪克斯特拉（Dijkstra）算法找到各区中的路口到该区内最近的交巡警服务平台位置的道路路程，从而得到超过3分钟内不能到达的路口（因为3分钟警车行驶30毫米（图上距离），这个路程大于30毫米就说明在3分钟不能到达指定路口）。再对附件2中的数据分析与处理，得到表5，表6中的相关数据。表5 各区评价指标的值指标数据区域ABCDEF1381791511124.5066.40187.2067.80119.40119.400.10 0.12 0.09 0.13 0.13 0.09 表6 各区评价指标的值指标数据区域ABCDEF66 471233359273154531031080.07 0.08 0.31 0.23 0.320.32 表7 各路口节点被管辖的情况各区总节点数各区没有被包围在管辖范围的节点数各区被包围在管辖范围的节点数A区927.6684.34B区736.7466.26C区15452.84101.16D区5214.5137.49E区10376.7026.30F区10839.0069.00合计582197.42384.58所占的总体比例0.340.66从上表7可知，在我们假定的条件下没有在服务平台管辖范围内的路口节点数与在服务平台管辖范围内的路口节点数之比大约为1:2，这说明了该市的交巡警服务平台的服务效率较低。由这个比例及结合上表5，表6可知，该市现有交巡警服务平台设置方案较为不合理。根据表5的将六个区值按从大到小的顺序排列：，再依据表6的六个区按从小到大的顺序排列：。综合指标和指标分析得到全市六个区中区和区的现有交巡警服务平台的设置较为合理；而区的现有交巡警服务平台的设置最为不合理。区中所有交巡警服务平台在3分钟内都不能到达的路口有37个（见表8），并将这些点及对应的坐标运用MATLAB做出图1。表8未能到达的路口编号486487500506507508509510511512513514515516517518519522523524525526527528529533540541559560561566569574575578582 图1 表8中路节点的散点图从图1中我们看出，红方框所围的区域中，路口的比较密集。依据这些路口处的案发率与密集程度，我们将选取编号为505、522的路口处再建两个交巡警服务平台，运用迪克斯特拉（Dijkstra）算法找到从这两处服务台出发，在3分钟内能不能达到的路口（见表9）表9 增加两个交巡警服务平台后还未在3分钟达到的路口编号486487510511512526533540541559560561566569574575578582从表9和表8中可以看出，在编号为505、522路口处在建两个交巡警服务平台后，没在3分钟内到达的路口减少了19个路口，且没有在3分钟内到达的路口几乎都是在图1中红方框之外。指标的值变为0.11，比原的0.09上升了0.2个百分点，而指标的值变为0.17，比原来的0.32下降了将近0.5个百分点，这就说明我们改进的方案是可行的。 4.2.2 调度全市交巡警服务平台警力资源的最佳围堵方案该市地点P（第32个节点）处发生了重大刑事案件，在案发3分钟后接到报警，犯罪嫌疑人已驾车逃跑，对此问题我们要解决的是调动全市交巡警服务平台警力尽可能快地封锁住犯罪嫌疑人所有可能的出路，首先我们在图中用符号“”表示3分钟后时犯罪嫌疑人可能出现的地方，接到报警后立马调动最近的交巡警服务平台对其进行围堵。具体的围堵方案：1、 以地点为中心，向四周搜索有可能通往的路口，计算到路口的道路路程。2、 若，说明罪犯在3分钟的时间里已行驶到点连接路口之间路段的某点上，计算罪犯从点驾车逃到路口所用的时间，并计算离路口最近的交巡警服务平台派人前往该路口所用的时间，转向步骤4；否则，又以接路口为中心，向四周搜索可能通往的下一个路口，计算点到路口连接的道路路程，转向步骤3。3、 若，返回步骤2继续搜索；否则，说明罪犯在3分钟内已经驾车到路口与路口连接的路段某点上，计算罪犯从点到路口所用的时间，并计算离路口最近的交巡警服务平台派人前往该路口所用的时间，转向步骤4。4、 若，返回步骤2继续搜索；否则，就调离路口最近的交巡警服务平台的执行人员赶往该路口进行围堵。由上的围堵方案得到以下的围堵方案图（图2）。29.59.8528.130.69.86292823548473233313437394661362374045415538351530768951443217167.140.134.16.1406.755.14.319.457.68.311.711.487.841.547.59.574.38.526.917.712.845.642.512.729.469.314.614.92919.11735.3241.2823617023833.624725016724617120图2 最佳围堵方案图其中箭头的指向就是调动就近的交巡警服务平台对对犯罪嫌疑人进行围堵的方向，椭圆内的数据是各路口节点的编号，矩形内的数据是交巡警服务平台的编号。从矩形框指向椭圆箭头表示矩形内的交巡警服务平台要派执行人员前往指向的路口进行围堵任务。根据我们设计的围堵方案和所作的假设，在这过程中接到电话后立即行动得到最短的围堵时间为176.94秒。五 模型评价、推广与改进5.1 模型的评价本文解决的是巡警服务平台设置与调度问题。根据题目的要求，我们建立了相关的数学模型。利用迪克斯特拉（Dijkstra)算法求出区各路口节点到服务平台的最短距离。利用0-1变量建立规划模型求解出最佳的调度方案。由案发率优先权与各管辖区内路口节点数优先权来确定增加服务平台与其具体的位置。再建立相关的模型结合图像我们得出了该市区现有的交巡警服务平台设置方案不大合理与最佳围堵方案，并对交巡警服务平台的不合理进行一定的改进。使问题得到较好的解决。但是，模型中存在一定的缺点，原因在于这个问题是一个动态问题。我们是用迪克斯特拉（Dijkstra)算法来求解最短路，则是不大合理的做法。5.2 模型的推广本文我们是在一定的假设条件下所考虑的问题,并在此条件下对问题求解,会有一定局限性.我们通过分析得出,这些结果在现实中是合理的,符合现实情况，具有一定的实际推广意义。可以将我们所建的模型思想应用到交通事故处理、巡警巡逻、逮捕犯罪嫌疑人等相关的交通问题之中，解决类似的问题。5.3模型的改进1、 由于这个问题是一动态性问题，我们应用迪克斯特拉（Dijkstra)算法求解最短路是不大理想的方法。为了能够更好的解决这个问题，我们用动态规划的方法会更好。2、由我们得到的最佳的围堵方案看出其方案还存在一定的缺点，主要是以静态的形式来实现。为了得到更好的围堵效果，可以将其改成动静结合的方案。六 参考文献1 胡运权，郭耀煌,运筹学教程（第三版）,北京：清华大学出版社,2010。2 刘来福,曾文艺等,数学模型与数学建模 北京：北京师范大学出版社，2009。3 姜启源,谢金星,叶俊,数学模型（第三版），北京：高等教育出版社,2003。4 刘兴伟，张建刚等，复杂网络同步理论在常规公交调度中的应用J，兰州大学，第30卷 第1期，2011年2月。5 任沙沙，张晶晶等，一种城市动态交通网络紧急疏散路线确定的方法，河北工业大学， 第28卷 第7期 ，2011年7月。6 刘卫国，MATLAB程序设计教程，北京：中国水电水利出版社,2005。7 刘华，章春明，论警力资源的优化配置J，云南警官学院，第1期，2005年1月。 七 附录7.1 文中用到的数据见附件文件夹7.2 附录一：求最短路的Dijkstra程序function Spth,d=DJshortpath(A,st)%Dijkstra最短路算法程序.%其中A为网络的权矩阵,st为起点/终点向量,%Spth为最短路径,d最短路长.Spth=st(2);n=length(A);%求网络的顶点个数mark=ones(n,2);mark(:,1)=mark(:,1)*st(1);mark(:,2)=mark(:,2)*inf;mark(st(1),2)=0;%mark用于贮存各顶点的标号.P=st(1);%P用于贮存获得P标号的点.TP=st(1);%TP用于贮存刚由T标号变为P标号的点.m=0;while length(P)n %所有点均为P标号,标号结束. for k=1:length(TP) for i=1:n if A(TP(k),i)=0 if mark(TP(k),2)+A(TP(k),i)m);%求所有T标号的最小值. TP=find(mark(:,2)=m);%查找T标号值最小的点. P=P TP;%将T标号值最小的点T标号改为P标号.end%求最短路长及路径.d=mark(st(2),2);if mark(st(2),1)=st(1) T=mark(st(2),1); while T=st(1) Spth=T Spth; T=mark(T,1); end endSpth=st(1) Spth;7.3附件二：调用DJshortpath函数求出A区交通网络的邻接距离权值矩阵D1：clear all;clc;num1,char1=xlsread(2011_B题.xls,Sheet1);num2,char2=xlsread(2011_B题.xls,Sheet2);A=zeros(92,92);for i=1:length(num2) n=num2(i,1); m=num2(i,2); d=sqrt(num1(n,2)-num1(m,2)2+(num1(n,3)-num1(m,3)2); A(n,m)=d; A(m,n)=d;end for i=1:size(A,1) for j=1:size(A,2) if i=j&A(i,j)=0 A(i,j)=inf; end endendD1=;for i=1:20 D=; for j=21:92 st=i,j; Spth,d=DJshortpath(A,st); D=D,d; end D1=D1;D;endD17.4 附件三：用MATLAB对最短距离矩阵d进行求解：clear all;clc;num1,char1=xlsread(2011_B题.xls,Sheet1);num2,char2=xlsread(2011_B题.xls,Sheet2);A=zeros(92,92);for i=1:length(num2) n=num2(i,1); m=num2(i,2); d=sqrt(num1(n,2)-num1(m,2)2+(num1(n,3)-num1(m,3)2); A(n,m)=d; A(m,n)=d;end for i=1:size(A,1) for j=1:size(A,2) if i=j&A(i,j)=0 A(i,j)=inf; end endendM=12 14 16 21 22 23 24 28 29 30 38 48 62 ;d=;for i=1:20 D=; for j=1:13 st=i,M(j); Spth,d1=DJshortpath(A,st); D=D,d1; end d=d;D;endd7.5 附件四：运用LINGO对规划模型进行求解：model:sets: sever/1.20/; road/1.13/; link(sever,road):d,x;endsetsdata: d=222.4, 160.3, 92.87, 192.9, 211.0, 225.0, 228.9, 190.0, 195.2, 120.8, 58.81, 118.5, 48.85204.6, 141.3, 73.88, 173.9, 192.0, 206.0, 211.2, 172.3, 177.4, 103.1, 39.82, 103.1, 60.35183.5, 127.7, 60.26, 160.3, 178.3, 192.4, 190.1, 151.2, 156.3, 82.0, 60.94, 81.98, 43.93220.0, 150.1, 82.67, 182.7, 200.8, 214.8, 226.5, 162.3, 155.4, 81.03, 48.61, 73.96, 3.5176.3, 129.7, 62.28, 162.3, 177.5, 191.6, 182.9, 113.1, 106.2, 31.83, 94.21, 24.76, 52.55176.6, 130.0, 62.59, 162.7, 177.8, 191.9, 183.2, 113.4, 106.5, 32.14, 94.52, 25.06, 53.37149.1, 109.0, 41.6, 141.7, 150.4, 164.4, 155.7, 8