数学建模-校车安排问题

1、校车问题的分析报告摘要本文是解决如何有效的安排校车让教师和工作人员尽量满意的问题。根据老校区教师和工作人员所在区的分布以及各区的人数，针对如何设置乘车点使得各区距离乘车点最近，教师和工作人员最满意，以及如何有效安排车辆等问题进行了深入分析，利用改进的Floyd 算法， 综合评价方法建立了最短乘车距离模型 、 满意度评价模型对问题做出了详细合理的解答。针对问题一，考虑到需要求得每个区到达乘车点的最小距离，我们建立了最短乘车距离模型并通过改进后的Floyd 算法（见附件2）实现。首先运用Floyd算法思想得到各顶点之间的最短通路值，并得到最小距离矩阵，然后运用for 循环语句在各区中随机抽取n 个

2、区作为乘车点并在最小距离矩阵中取出对应的数据即乘车点到达任意一个区的最小距离向量。将这n 个向量按位求最小值生成一个新向量A,对A向量各元素求和得到一个数 So最后将每次循环得到的 S 比较，最小值（So）即为问题一的解。最后得出：n=2时应该在第18区和31 区设立乘车点，其最短总距离为24492 米。 n=3 时应该在第15 区、 21 区和 31区建立乘车点，最短距离为19660 米。针对问题二，考虑到教师和工作人员的满意度受到距离与人数两个因素的影响， 即满意度随着距离的增加而减小，而人数的多少会放大或减小距离对满意度的影响程度，从而建立了满意度评价模型。由于影响满意度的因素（人数、

3、距离）存在不同的单位所以我们分别对人数和距离做了无量纲化处理（见公式1、 2）并得到了满意度评价函数（见公式3） 。最后在模型一的基础上，结合满意度评价函数建立了问题二的求解算法（见附件3） 。依据模型可知当求得的数值越小表示不满意度越小即满意度越高，最终求解得到了：n=2 时最优解为16 区和36 区不满意度为0.4980 。 当 n=3 时最优解为15 区、 22 区和 32 区不满意度为0.3720 。针对问题三，由于要求使用尽可能少的车辆让教师和工作人员的满意度尽量高， 所以我们把车辆数作为一个限制满意度的条件。通过在问题二的基础上把车辆数考虑进去得到了问题三的求解公式和算法（见附4）

4、 。 最终求解得到：当 n=3时最优解为至少需要54 辆车对应的区域分别为15、 22、 32。对应的车辆数为20 、 16 、 18 。针对问题四，我们通过对前三个问题的深入分析对校车安排问题提出了合理化的建议和措施。关键词：最短乘车距离模型满意度评价模型Floyd 算法一、问题重述如今越来越多的学校需要经常将老校区的教师和工作人员用校车送到新校区，如何实现以最少的车辆让教师和工作人员尽量满意是个十分重要的问题。现已知老校区的教师和工作人员分布在50 个区，以及各区的距离与各区人员分布情况。需要对以下问题进行研究：（ 1 ） 建立 n 个乘车点，要求使各区人员到最近乘车点的距离最小，该将校车

5、乘车点应建立在哪n 个点。 建立一般模型，并给出 n 2,3时的结果。（ 2） 若考虑每个区的乘车人数，为使教师和工作人员满意度最大，该将校车乘车点应建立在哪n 个点。 建立一般模型，并给出 n 2,3时的结果。（ 3） 若建立 3 个乘车点，为使教师和工作人员尽量满意，至少需要安排多少辆车？给出每个乘车点的位置和车辆数。设每辆车最多载客 47 人。（ 4） 关于校车安排问题，你还有什么好的建议和考虑。可以提高乘车人员的满意度，又可节省运行成本。二、基本假设1 .假设乘客的满意度只与小区到车站之间的距离以及车站乘车人数有关；2 .在问题一、二中，假设每位教师及工作人员只会到最近的车站乘车；3

6、.在问题一、二中，假设每位乘客到达车站后，都有校车乘坐；三、符号说明1. V1 , V2,Vk,Vn表小各个区；2. Ai, A2,八匕八门表示第k个区到其他区的最短距离的矩阵;3.S表示任意一种随机取得的车站方式所得到的最短距离；4.So表示所有可能存在的组合方式构成车站的最短距离；-可编辑修改-5.Y满意度评价函数四、模型的建立与求解4.1 最短乘车距离模型：4.1.1 问题分析：要求得使每个小区与车站距离最小， 可以用以下几步来实现：(1)随机选择 n个小区作为车站 V1, V2, - Vk, - Vn ; (2)求得这n个车站到任意一个小区 的最小距离，并得到n个50阶的行矩阵A1,

7、A2, - Ak/ An； (3)按位比较这n 个行向量，得到最终每个小区到达最近车站的最短距离A; (4)将A中每个元素加起来，得到S,即为最短距离。(5)将所有随机可能性得出所有最终最短距 离,进行比较，得到它们中的最小值 So,即为结果。如图1:随机取得n个小 区作为车站V, VVk,Vn求得n个最小距 离行向量AA, A,An按位比较n个行 向量，得到最终 最小距离行向量将最小距离行向量 A各项相加，得到此 随机车站的最小总 距离S将各种随机情况得到 的最小总距离S比较, 得到最小总距离So,即 为结果图1:最小距离模型建立的示意图4.1.2 随机选取n个小区作为乘车站点:我们运用n个

8、for循环语句对随机选取n个小区作为乘车站点的所有情况进 行一次历遍，以n=3为例，具体实现如算法1:fo门=1:48for j=2:49for k=3:50算法1算法1是用循环的方法，将i, j, k分别从1取到48 , 2取到49 , 3取到 50,这样就能得到从50个小区中随机选取三个作为乘车站点的所有可能，所选 取的站点即为：Vi, Vj, Vko4.1.3 求得这n乘车站点到各个小区的最短距离：1 .首先应得到由各个小区之间的距离组成的邻接矩阵（见附件1）;2 .其次考虑到要计算任意两点之间的最短距离，我们采用了 Floyd算法进行求算；Floyd算法的基本思想是：递推产生一个矩阵序

9、列其中 4«.力表示从顶点匕到顶点刀的路径上所经过的顶点序号不大于上的最短路径长 度V r计算时用迭代公式；，4&J）= min（绘04/弦）+ 4T 化 J）.k是迭代次数,=1之,融. ¥最后，当七=。时，凡即是各顶点之间的最短通路值. J示例：Floyd算法的基本步骤如图2所示问题，要求的任意两点之间的又t短距离建立相邻矩阵，见表 1 , 则从上面的表1开始，对于每两个顶点u、v,在表1中存储着一条路径uv。 现在我们考察，试着把a加到u、v的路径上能否，得到一条更短的路径，即如 果u - a+a -v<u - v的话，能够找到一条更短的路径。图2本来路

10、径上源点或终点就有a的不必考虑。对角线上的也不必考虑，并 且Dba+Dac=6+11>Dbc=2,所以如果从 a绕，反而远，又因为Dca+Dab=3+4<Dcb= 工,所以如果从a绕，更近，因此，由表 1 变成表2。从上面的表2开始，对于每两个顶点u、v,在表2中存储着一条路径uv。 现在我们考察，试着把b加到u、v的路径上能否，得到一条更短的路径，即如 果u - b+b - v<uv的话，能够找到一条更短的路径。同样地，本来路径上源 点或终点就有b 的不必考虑。对角线上的也不必考虑， Dab+Dbc=6<Dac, 所以 如果从 b 绕， 更近，Dcb+Dba=7+6&

11、gt;Dca=3,所以如果从b绕，反而远，因此表2中的数据应该变为表3。从上面的表2开始，对于每两个顶点u、v,在表2中存储。o着一条路径u - Vo现在我们考察，试着把c加到u、v的路径上能否，得到 一条更短的路径，即如果 uc+cv<uV的话，能够找到一条更短的路径。 同样地，本来路径上源点或终点就有c的不必考虑。对角线上的也不必考虑，Dac+Dcb=6+7>Dab=4,所以如果从 c 绕，反而远，Dbc+Dca=2+3<Dba=6,所以如果从c绕，更近，因此表 3应该变成表4中的数据。现在，已经把所有的顶点都试了一遍，算法结束。每两个顶点之间的路径如 表4所小。表1ab

12、ca,0411b602c3oo0-可编辑修改-abca0411B602c370a046b602c370表4abca046b502c370假设图G权的邻接矩阵为4,3来存放各边长度,其中；，% = 01 =12,，门；a% = s Lj之间没有边，在程序中以各边都不可能达到的充分大的数代高 % 二 % 却4是LJ之间边的长度，Lj = d 、在 对于无向图，4是对称矩阵，a. = a.QAo即为我们要得到的任意两点之间的最小距离的矩阵，见算法 2:b=a+a'path=zeros(length(b);for k=1:50fo门=1:50for j=1:50if b(i,j)>b(i

13、,k)+b(k,j) b(i,j)=b(i,k)+b(k,j);path(i,j尸k;endendendendb,path算法2算法2即为Floyd算法的核心程序3 .得到n个乘车站点到各个小区的最短距离的行矩阵：在2中得到的b矩阵中提取出这n个小区对应的行的行向量，例如，选取 第一个小区作为乘车站点，则将 b矩阵中的第一行取出，作为行向量 Ai,其他的依此类推即可，由此可以得到各个乘车站点最短距离的行矩阵Ai, A2,Ak,An 。4.1.4 求得各个小区到这n 个乘车站点的最短距离S：因为得到的行矩阵Ai, A2,Ak,An的阶数是相同的，因此，我们按位求最小值，得出另一个行矩阵 A,将A

14、中各个元素相加就可以得到各小区到达这n个乘车站点的最小距离S,算法见算法3:for a=i:50t=b(i,a) b(j,a) b(k,a);d(a,i)=min(t);end;f(u,i)=sum(d);f(u,2)=i;f(u,3)=j;f(u,4)=k; u=u+i;算法 34.1.5 得出最终结果S0：遍历所有可能情况后，通过比较每种情况得出的S,得出其最小值，得到的So即为最小距离，取得最小距离时随机选取的i， j， k 即为乘车站点的设置地点。具体的程序实现见程序i 。4.1.6 求解结果：n=2 时应该在第i8 区和 3i 区设立乘车点，其最短总距离为24492 米。n=3 时应

15、该在第i5 区、 2i 区和 3i 区建立乘车站，最短距离为i9660 米。4.2 满意度评价模型：-可编辑修改-4.2.1问题分析:对距离以及人数两个 指标进行无量纲化处 理，得到两个指标的量 化数据。将已经无量纲化后的 指标参数相乘得到定 义的不满意度指标。-可编辑修改-将得到后的综合指标当 作第一问中的距离指 标，建立满意度评价函 数，求解第二问中的变 化后的距离的最小值。如图3,对于满意度模型：我们对人数以及距离两个指标进行无量纲化处 理，使其量化；对两组无量纲化后的数据相乘，得到满意度评价函数，即相乘 的结果越小，其满意度越大，我们将其定义为不满意度；再对所有小区进行历 遍，选取n个

16、小区作为乘车站点，对其不满意度进行比较；最后得出最小的 不满意度即为本问的解4.2.2对指标进行无量纲化：1 .对人数进行无量纲化：我们采用每个小区人数除以总人数的方法来实现其无量纲化， Qj=Pj/P0 （公式 1）得到表5 :表5区域人数区域人数10.0259792260.006394920.0267786270.037569930.0167866280.007194240.0135891290.011590750.0151878300.02997660.0115907310.003996870.0067946320.034372580.0255795330.027977690.01558

17、75340.0223821100.0079936350.0259792110.0243805360.0103917120.018785370.0319744130.0263789380.0359712140.0083933390.018785150.0279776400.0159872160.0339728410.0227818170.0047962420.0159872180.0139888430.0275779190.0191847440.0267786200.0215827450.0079936210.0195843460.0071942220.0047962470.0271783230

18、.0215827480.028777240.0183853490.0303757250.0303757500.0247802表5表示出每个小区人数所占总人数的比例，反映出每个小区人数对于 不满意度的权重值Qj(j=050)。2 .对距离进行极值差方法处理：对附录中的数值进行极值差方法处理，得到无量纲的量化结果，Bij - ( Bi ) minBj，= (BiBi) min (公式其中：Bij表示B矩阵中的第i行第j列的元素(81) min=minB ij(1 < i <50), (Bi) max =maxB ij(1 < i <50)3 .得出满意度评价函数：Y=(Bi

19、j- (Bi) min)/( (Bi) max- (Bi) min)*(Pj/Po)(公式 3)4.2.3求解结果:n=2时最优解为16区和36区不满意度为0.4980。当n=3时最优解为15 区、22区和32区不满意度为0.3720。4.3问题三：4.3.1问题分析:通过总人数与校车的 载人数算出最少需要 的车辆数为54辆尽量少的车辆数作为 一个限制满意度的条 件建立求解函数结合问题一的算法求 出最终结果图3如图3:由于要求使用尽可能少的车辆让教师和工作人员的满意度尽量高， 所以我们把车辆数作为一个限制满意度的条件。通过在问题二的基础上把车辆数考虑进去运用问题一的算法即可求得答案。4.3.2

20、问题求解：当n=3时最优解为至少需要54辆车对应的区域分别为15、22、32。对应 的车辆数为20、16、18。不满意度为0.37204.4 问题的合理化建议与考虑：1. 可于上下班高峰期增开几次校车，在不是高峰期，减少几次校车运 行；2. 可以运行不同型号的校车，在乘车人数较多的车站运行大校车，人 数较少的车站运行较小的校车。3. 可以增加几个收费的乘车站点，因为增加站点会提高满意度，但同 时会增加运行成本，因此进行收费来降低成本。4. 可以将乘车站点不设定在小区内，设定在几个小区比较靠中央的位 置，在相同情况下回事满意度提高。5. 有一些应该使乘车站尽量靠近老年人数较多的小区，这样满意度提

21、 高。五、模型的评价首先，在解决问题一的时候，我们建立了最小距离模型后，直接用Floyd算法进行运算，得到了每一个小区到其他各个小区的最小距离的矩阵，然后随机抽取 n 个小区作为车站，对最小距离矩阵的这n 行进行求和，比较求和值得到最终结论。当 n 比较小时，用这种方法可以较好的计算出所求的n 个点。 但是，这种方法的运算量与n 的大小是成指数关系的，所以，当n 很大时运算量会迅速增大。在解决问题二的时候，我们在问题一的基础上用小区和最近车站的距离和小区人数无量纲化后的乘积来表示教师和工作人员的满意程度，之后用和问题一相同的思路得出结论。所以，第二问中也存在着第一问中，当n 很大的时候运算量过

22、大的问题。而此无量纲化的过程中我们考虑了任意两个小区最短距离的极大值和极小值，发现极小值都是0，极大值之间相差不大，因此可以使用极值无量纲化的方法。但是极值无量纲化是通过利用变量取值的最大值和最小值将原始数据转换为介于某一特定范围的数据，从而消除量纲和数量级影响，改变变量在分析中的权重来解决不同度量的问题，所以此权重没有对距离和人数进行差异化对待，而事实上人数和距离的权重肯定是不同的。解决第三个问题时，我们用到了逼近理想值排序法，假设理想的情况是共用53辆车（因为总人数为2502 ,至少需要54辆车才可以），且教师和工作人员 的满意度最大。我们延用解决问题二的方法，只是在距离与人数无量纲化后再

23、乘以因式（A53）,然后对所有的情况进行排序，找到最接近理想值D的一组数据。六、参考文献1郑洲顺 科学计算与数学建模 复旦大学出版社。2姜启源 谢金星 叶俊 数学模型 高等教育出版社。3孙祥 徐流美 吴涛Matlab7.0基础教程 清华大学出版社。附件1 :50个区之间任意两点的最短通路值CoZLufrii£- L thuUE工 W-可编辑修改-IQ5；o1N- 04 4X IL - - L«DDODD 3 G巾EE d c 7.5410127S2W1505164DJ 640161613.W10461015WMH180Q1MD师1917159S5Die?sH1Q间后195D

24、:娥M旦口药15寸J20QH3033LO15即15001?3D650BbO12201期4加1650148516ZD11：10543414小44幼ti品MO4IK230潮M53弧5101&QDO3L0410侬g!D8U电/U11?D刑DITO1"D025DEQ1QD13Q5M334633： JE54】KE543FD?ED自£口430的口同。3BDE20心口Z80把白E7094 DE加11BD1 .1.U.J ：DJ 22010DIN 口9IDiCbO?CDMOJ24D13B0母口1280划口110J515IS如152014bU3S3O也出iflro15bUJID“如1

25、J9D磔口12M1H41224JBMIJllI21L12而LLIO如口LC6S1530!30旧的L?20划W年l?B019(SSB187D12702C3515EQ1沏t»2D1630i«o21PE1QWuro2S3512。1)40?105l?D011002065ianzq 口?由ll?0北口LT*1茸口550L和01C.PQ沔Q1540UDD3QQL圾Q1" 口?9O例口50nu瓯IMO门口S6LHID11DLTE匚L&00GCcluETiE 11 thraiJih. 20ITB-S1QM21CHUM50iLT&lL IL】站口LUbLtlU由Xb

26、Lson1U4UL对，匚9F01010L2LD*uM0i4-S30J70A70330470CTOI5D2904 MD340M：1000SOL则c'lMJii13。ro17Q-310450痢。即G30鸵Q560roo却Qeiu网?5Q日id1.ES4旧1 口制I.M4133412741.4 7Q113415?4ITMQ2DienI. KOI?BO33D1L207M93。1L303204和丽dBO600300£5090/0gtu3DBU1220131Q34BU1270113DD23QLD30104UOlilJ利加8&n机U6 口 iM。EM4001160114094012

27、B01240104013401300UOOid号14351235】4钝tsaoi14 7D3 4 JUIS30'16LU1B.BOLJ70)440bwu14001520IbSU”粕T6MRM174017041MQ1飒ISMSD34Lfl14gHH13皿L134签p;1004前口饶口l另0小2别IbMLM皿12MIDOD迪口12-I0JUKri134(1L?)009DINri!泓9NiColuaric 21 rhiouEh JCD D g JDI 4Q 5 5 5 o o- £5 1 ? ,tf oJ-X-o o_o 9Mo 75gfl5D塞明例7M?90我口随4期a670a?

28、D4D05S0?&0喈0现04Mt»Q24Q90 0HOD6301BIO询?JQ而口瓯4?Q行口1090129DafDEM11 so530r；70丽S1Q解口115QM5E)1C?0伽间350d恤制85Q碗口1 口q 口】M口rn即11?0Rfinin 口 inRTfi而口HE910UD后5口阳口IDLOE£ 口乌口口Tin4E 口snn)200wud3却M IDl?®0in2nI16D9用1T2077QJ四口M4 口run&o1331D班I2LQin网sjaBioJ3ID；“日1DE0I 9fl1 HDID8Qapn6306801070USD后9

29、B0! 1 W1050C40SI31G201210J29DHUH201290IE钟nsorjo600600?ED卷(J俄。B301120S807M网13Q江qmD5DQ740MQ1200l(i6Q370胤q2ia耽1£D730i3501D001*901150g如MQ47Q5? D2?D7l0iMOHLiO11001200loroS5Q42Cratid£DS5011301300ISOM501260L09Q60in 口行口C4Q?do5L01500lOfiO870随093口如口1 sD，印鲂口1D2U13101170自刈圈口K1U阳口3&D3卬1DB0i.2aj1510

30、1370lLL矶LU1Ueao9-DSID?909回口35口a4aa30o5 0 0IF1L85o 0口 o o 9 d fiT 7 G 4D513n *o oT 95 111211 J 1 i1cru EE U,ft U能 MS TSO -IM 52fi M。3州 184)1 11 111 11111tsu 16U 史b 划 535 ATO J50 520 BIO no 2«01111111 i i1iii i1LIO a10 KO 210 3=0 2J0 3：0 12E 1-10 MQ31Q "Q 邮n l?0 Mfl rrn MO Brn 6in 翁口 Lin 3 =

31、 0 MD031-ri Leo 2!=6 4Z5 3口 nu r'4U ELU Ll?U 0：,U 2门 11 11 1112JD on 15D 加口 20 D WE) ISO <31S OJD 3JD 13D 南口 N 口 010 9SD 900 门口 5 口 5口口 之目口 240 iJD 制口 .38 DD 匕口 5 31D ：日口 ign 33D SBO fio 算口 92 口 160u b b 2 F ar 3 o 41 2 Jo -u -u B D rj 13s1A -Asooo帅Looo如oo而5570W随制即新3n廊就20TQ却MLOu4D4IDD03szn3nT

32、nuij* 则如Ju IL IL IL 1 1 I 1 LarDQ61D fl fl o & J J .3 6 A3 9 11D4U12?DkGd&口1410neoS?Ddio148014101DEO13IDItlQ口|仙OLDS80：0M14gli13301匹。相打即Q16201 II1汴口wi的口l：Jnfio露口6如雨0泗11曲融口1Ei；nliillucmRh 5uD, 5 qyDJ21 53144 1514 ds57 d-4 dpo2沌-I14ICo _D o D fl- u 0 T g2J'li J D s UL口口口 2 6 34 G 8ny o 0 41

33、- 9口 o o 0 ssllJN o b 2 .4a(7,:)=zeros(1,7),170,M,M,M,M,M,M,M,M,M,160,M,M,M,M,M,M,M,M,M,附件 2：问题一的算法clear;clc;M=10000;a(1,:)=0,400,450,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M, M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M;a(2,:)=zeros(1,2),M,300,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,230,M, M,M,M,M,

34、M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,140,M,M, M;a(3,:)=zeros(1,3),600,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M, M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M;a(4,:)=zeros(1,4),210,M,M,M,M,M,M,M,M,M,M,M,M,M,310,M,M,M,M,M, M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M;a(5,:)=zeros(1,5),2

35、30,200,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M, M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M;a(6,:)=zeros(1,6),320,340,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M, M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M;M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M;a(8,:)=zeros(1,8),200,M,M,M,M,M,285,M,M,M,M,M,M,M

36、,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M;a(9,:)=zeros(1,9),180,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M;a(10,:)=zeros(1,10),150,M,M,M,160,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M;a(11,:)=zeros(1,11),140,M,130,M,M,M,M

37、,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M;a(12,:)=zeros(1,12),200,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M;a(13,:)=zeros(1,13),M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,400,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M;a(14,:)=zeros(1,14),190,M,M,M,M,M,M,M,M,M

38、,M,190,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M;a(15,:)=zeros(1,15),170,250,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M;a(16,:)=zeros(1,16),140,130,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M;a(17,:)=zeros(1,17),M,M,M,M,M,M,M,M,M,240,M,M,M,M,M,M,M,M,M

39、,M,M,M,M,M,M,M,M,M,M,M,M,M,M;-可编辑修改-a(18,:)=zeros(1,19),204,M,M,M,M,M,180,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M;a(19,:)=zeros(1,19),140,M,M,M,175,M,M,M,M,M,M,M,M,M,M,M,M,M,M, M,M,M,M,M,M,M,M,M,M,M,M;a(20,:)=zeros(1,20),180,M,M,190,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M, M,M,M,M,M,M,M,M,M,M,M;a(21

40、,:)=zeros(1,21),300,270,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M, M,M,M,M,M,M,350,M,M,M;a(22,:)=zeros(1,22),M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M, M,160,270,M,M,180,M,M;a(23,:)=zeros(1,23),240,M,M,M,M,210,290,M,M,M,M,M,M,M,M,M,M,M,M,M,150,M,M,M,M,M,M;a(24,:)=zeros(1,24),170,M,M,130,M,M,M,M,M,M,M,M,M,M,M,

41、M,M,M,M, M,M,M,M,M,M,M;a(25,:)=zeros(1,25),M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M, M,M,M,M,M;a(26,:)=zeros(1,26),140,M,M,M,M,M,M,320,M,M,M,M,M,M,M,M,M,M,M, M,M,M,M,M;a(27,:)=zeros(1,27),190,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M, M,M,M;a(28,:)=zeros(1,28),260,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,

42、M;-可编辑修改-a(29,:)=zeros(1,29),M,190,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M;a(30,:)=zeros(1,30),240,M,M,M,M,M,M,M,M,M,M,130,210,M,M,M,M,M, M,M;a(31,:)=zeros(1,31),230,M,M,M,260,M,M,M,M,M,M,M,M,M,M,M,M,M,21 0;a(32,:)=zeros(1,32),190,M,140,240,M,M,M,M,M,M,M,M,M,M,M,M,M,M;a(33,:)=zeros(1,33),210,M,M,M,M,M

43、,M,M,M,M,M,M,M,M,M,M,M;a(34,:)=zeros(1,34),M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M;a(35,:)=zeros(1,35),M,160,M,M,M,M,M,M,M,M,M,M,M,M,M;a(36,:)=zeros(1,36),M,M,180,190,M,M,M,M,M,M,M,M,M,M;a(37,:)=zeros(1,37),135,M,M,M,M,M,M,M,M,M,M,M,M;a(38,:)=zeros(1,38),130,M,M,M,M,M,M,M,M,M,M,M;a(39,:)=zeros(1,39),M,310,M

44、,M,M,M,M,M,M,M,M;a(40,:)=zeros(1,40),140,M,M,M,M,M,M,M,M,190;a(41,:)=zeros(1,41),M,M,M,M,M,M,M,M,M;a(42,:)=zeros(1,42),M,M,M,M,M,M,M,200;a(43,:)=zeros(1,43),260,210,M,M,M,M,M;a(44,:)=zeros(1,44),M,M,M,M,M,M;a(45,:)=zeros(1,45),240,M,M,M,M;a(46,:)=zeros(1,46),M,280,M,M;a(47,:)=zeros(1,47),M,M,M;-可编辑修

45、改-a(48,:)=zeros(1,48),200,M;a(49,:)=zeros(1,49),M;a(50,:)=zeros(1,50);b=a+a'path=zeros(length(b);for k=1:50for i=1:50for j=1:50if b(i,j)>b(i,k)+b(k,j) b(i,j)=b(i,k)+b(k,j); path(i,j)=k;endendendendu=1;d=zeros(50,1);f=zeros(19600,4);for i=1:48for j=2:49for k=3:50for a=1:50t=b(i,a) b(j,a) b(k,a

46、);d(a,1)=min(t);end;f(u,1)=sum(d);f(u,2)=i;f(u,3)=j;f(u,4)=k;u=u+1;endendend;x,m=min(f(:,1);e=f(m,:);e-可编辑修改-附件 3：问题二的算法clear;M=10000;w=65;67;42;34;38;29;17;64;39;20;61;47;66;21;70;85;12;35;48;54;49;12;54;46;76;16;94;18;29;75;10;86;70;56;65;26;80;90;47;40;57;40;69;67;20;18;68;72;76;62*(1/2502);a(1,:

47、)=0,400,450,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M;a(2,:)=zeros(1,2),M,300,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,230,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,140,M,M,M; a(3,:)=zeros(1,3),600,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M, M,M,M,M,M,

48、M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M;a(4,:)=zeros(1,4),210,M,M,M,M,M,M,M,M,M,M,M,M,M,310,M,M,M,M,M, M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M;a(5,:)=zeros(1,5),230,200,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M, M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M;a(6,:)=zeros(1,6),320,340,M,M,

49、M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M, M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M;a(7,:)=zeros(1,7),170,M,M,M,M,M,M,M,M,M,160,M,M,M,M,M,M,M,M,M, M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M;a(8,:)=zeros(1,8),200,M,M,M,M,M,285,M,M,M,M,M,M,M,M,M,M,M,M,M, M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M;a(9

50、,:)=zeros(1,9),180,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M, M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M;a(10,:)=zeros(1,10),150,M,M,M,160,M,M,M,M,M,M,M,M,M,M,M,M,M,M, M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M;a(11,:)=zeros(1,11),140,M,130,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M, M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M;a(12,:)=zeros(1,12),200,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M, M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M;a(13,:)=zeros(1,13),M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,4 00,M,M,M,M,M,M,M,M