快递公司送货策略

《快递公司送货策略》由会员分享，可在线阅读，更多相关《快递公司送货策略（26页珍藏版）》请在装配图网上搜索。

1、B题快递公司送货策略摘要本文主要解决快递公司送货策略问题，研究在各种运货地点，重量的确定，业务员的运输条件和工作时间等各种约束条件下，设计最优的路线，得出最优送货策略。主要研究如下三个问题。问题一：首先考虑在时间和重量两个约束条件之下，优先考虑重量，通过对送货点的分布进行分析，将分布点按照矩形，弧形和树的理念将问题分成三种模块，从而建立三种送货方案。方案一，运用矩形，将整个区域分成5个区域，以选择的点的送货质量之和小于25kg且距离尽可能小的点的集合作为一个区域。依次来分配业务员的送货地点。方案二，运用弧形，以原点为圆心画同心圆，按照就近原则确定送货区域，依次分配业务员的送货地点。方案三，运用

2、Dijkstra算法计算出每一个顶点到其它点的距离。分析点的分布，由此得到最小树，在最小树的基础上，向四周延伸，得到相应区域。且以送货质量小于25kg且距离尽可能小的点的集合作为一个区域。依次来分配业务员的送货地点。其次，再综合这三种方案所涉及到得时间，路程依次进行对比，画出柱形图，清晰可得出最优的方案为方案三。问题二，是解决送货总费用最小的问题。因此要求业务员的运行路线要尽量短，且尽早卸货。首先将该区域安排送货点均匀度分为三个小区域，以每个点的信件质量从小到大排列，以送货点最大点为中心，选择该点附近质量较大且距离较短原则的下一个送货点，依次类推，直到根据约束条件为每次携带的快件量不超过25k

3、g,找到该条路线最后一个送货点。按此方法可得路线为g10t12t11T0,0T7T14T27T0,0TIT26T28T0,0t13T19T25T0,0t2t5t16t170,0t22t129300,0t6t2A18240,0T4T3T8921230,并且利用C语言编程（见附录），算得每条路线的费用，所得总费用为14636.1元。问题三，在问题一的基础上，将业务员的工作时间延长到8小时，由此在问题一的基础上，将8小时的工作时间所需花费的费用在三个方案中进行对比，由此得到依旧是方案三的为最优。关键字：规划模型Floyd算法最小生成树MATLAB一、问题重述：目前，快递行业正蓬勃发展，为我们的生活带

4、来更多方便。一般地，所有快件到达某地后，先集中存放在总部，然后由业务员分别进行派送；对丁快递公司，为了保证快件能够在指定的时间内送达目的地，必须有足够的业务员进行送货，但是，太多的业务员意味着更多的派送费用。假定所有快件在早上7点钟到达，早上9点钟开始派送，要求丁当天17点之前必须派送完毕，每个业务员每天平均工作时间不超过6小时，在每个送货点停留的时间为10分钟，途中速度为25km/h,每次出发最多能带25千克的重量。为了计算方便，我们将快件一律用重量来衡量，平均每天收到总重量为184.5千克，公司总部位丁坐标原点处(如图2),每个送货点的位置和快件重量见下表，并且假设送货运行路线均为平行丁坐

5、标轴的折线。请你运用有关数学建模的知识，给该公司提供一个合理的送货策略(即需要多少业务员，每个业务员的运行线路，以及总的运行公里数)；(1) 如果业务员携带快件时的速度是20km/h，获得酬金3元/kmkg；而不携带快件时的速度是30km/h,酬金2元/km,请为公司设计一个费用最省的策略；(2) 如果可以延长业务员的工作时间到8小时，公司的送货策略将有何变化？送货点快件量T(kg)坐标(km)送货点快件量T(kg)坐标(km)xyxy1832163.521628.215175.86183654187.5111745.547197.815126308153.419954.5311216.222

6、577.279226.821082.396232.427991.4102247.61519106.5140259.61514114.1173261020171212.714627122113135.8129286.02420143.81012298.12516204.6714304.22818、符号说明符号描述(x,y)两质点的横纵坐标Qk一次送货的取大负何重（kg）,其中k=1,2,.,kti一个区域所用的时间（min）i=1,2,.,iT总的所用的工作时间（min）ki一个区域经过的地方数i=1,2,.,iL送货点总数qi每个送货点的快件量（kg）,i=1,2,.,Ldij两质点之问的距离

7、dijd0j配送中心到送货点的运距（knj）D总的路程（km）nk第k名业务员配送的送货点数，nk=0表示未配送第k名业务员Rk正个集合，表小弟k条路线表示送货点rta在路线k中的顺序为i（不包括配送中心），E=0表示配送中心v业务员每天送货的平均速度v=（km/min）60bij送货点i与j之间的快件密集度F快递公司一天的总费用（元）三、模型假设(1) 假设以送货运行路线均为平行丁坐标轴的折线而不是直线，类似计算也可同样处理。(2) 运货途中快件没有任何损坏，并且业务员的运送过程也十分安全，没有堵车、天气等问题，即送货过程非常顺利。(3) 每个业务员每天的工作时间不超过6小时，第三问，则不超

8、过8小时。快件一律用重量单位千克来衡量，平均每天收到总重量为184.5千克的货物，且对体积没有影响。(4) 各个业务员之间的快件运送过程是相互独立的。四、问题分析1、问题一、三：针对问题一，三，使用相同的思路，即只要在分配人员的时间上做修改。(1) 对丁时间和重量两个约束条件，我们优先考虑重量；纵观送货点的分布，将分布点按照矩形、弧形及树的理念三种方案，将重量之和接近25千克的分布点联合起来；仙遍每天收到的总重量(3)区域效=一一，斗每次出发每人最多能带的重量18竺=7.38,所以至少要有8个区25域；(3) 计算出分割好的区域内业务员完成一次任务的时间之和，最后将满足几个区域的时间之和小丁6

9、小时(问题一)或者8小时(问题三)的区域的运送任务分派给同一个业务员。(4) 对丁假设一说明如下：折线距离：已知两点A(X1,y1),B(x2,y2),距离为横坐标之差的绝对值与纵坐标之差的绝对值，即d(A,B)=|x1-x21+|y1-y2|为AB两点之间的距离，在很多点的情况下，两点间的直线距离也同时可以使用折线距离来表示，折线距离最短也就是直线距离的最短，为了方便计算也使用折线距离来表示本题中的直线距离。1.1模型建立与求解：两质点的横纵坐标(xi7i),(xj7j)各自的差的绝对值的和等价丁两质点之间的距离,即两点间距离：S=|xi-Xj|yiy.|d都是使用用excel得到的距离，即

10、a矩阵(见附录)一个区域所用时间为：ti=D,10kiv所用总时间：T=气+10x30v万案根据各个送货点的分布，以矩形把整个区域分成5个区域，在区域或区域周围找出送货质量和小丁25KG且距离尽可能小的点的集合，为一个送货区域，由一位业务员负责送货。由此，画出的送货区域为下图1-1:051015202630图1-1然后连成折线距离的如下图1-2图1-2业务员的送货路线、送货区域、送货的路程及时间（通过excel可得）、如卜表1-3:送货线路行进次序问题一业务员分配路程（knj）时间(min)6小时8小时10-1-3-9-10-036126.42I0-2-4-6-16-5-04614630-7-

11、20-17-14-8-058191.640-12-13-15-23-076227.250-19-27-30-092250.8160-25-24-18-068169.270-26-29-28-09224680-22-21-11-054159.61总计5221516.85个4个表1-3方案二以原点为圆心画同心圆，以一个圆内或圆周周围的点为一片，找出送货质量和小丁25KG且距离尽可能小的点的集合，为一个送货区域，由一位业务员负责送货。由此，画出的送货区域为下图1-4:图1-4连成折线距离的图1-5如下图1-5则业务员的送货路线、送货区域、送货的路程及时间（通过excel可得）如卜表1-6:送货线路行

12、进次序问题一业务员分配路程（km）时间(min)6小时8小时10-1-3-2-0207820-6-5-4-7-8-9-034141.630-12-10-11-052154.8:40-16-17-20-14-13-06019450-19-25-18-064183.6.60-27-21-22-07019870-15-29-30-23-094265.680-24-26-28-092250.8总计4861466.45个4个表1-6计算赋权图中各对顶点之间最短路径，显然可以调用Floyd算法。具体方法是：每次以不同的顶点作为起点，用Floyd算法求出从该起点到其余顶点的最短路径，反复执行n-1次这样的操

13、作，就可得到从每一个顶点到其它顶点的最短路径。这种算法的时间复杂度为0(n3)。第二种解决这一问题的方法是由FloydRW提出的算法，称之为Floyd算法。假设图G权的邻接矩阵为Aoaiia2amIia2ia22a2nA0II一anian2ann其中权值，当、=vj之间有边时，aiji=j西，当Vj=vj之间无边时，aii=0,i=，2,n.对丁无向图，Ao是对称矩阵，aij=aji。Floyd算法的基本思想是：递推产生一个矩阵序列A,，Ak,，气，其中矩阵Ak的第i行第j列元素Ak(i,j)表示从顶点Vi到顶点Vj的路径上所经过的顶点序号不大丁k的最短路径长度。计算时用迭代公式：Ak(i,j

14、)=min(Ai,j),Ak项i,k)+Ak顼k,j),k是迭代次数，i,j,k=1,2，n。最后，当k=n时，An即是各顶点之间的最短通路值。许多应用问题都是求最小生成树问题。就像此模型中需要求解最小费用问题，该费用涉及到路程和载重量，所以如何设计优化的路程是相当重要的。因此运用最小生成树中的Floyd算法以此算出路线。以找出所有点所形成的图中找距离最小的最小树，并在最小数的基础上，向周围延伸，找出送货质量和小丁25KG且距离尽可能小的点的集合，为一个送货区域，由一位业务员负责送货。最小树是由MATLAB算得到的，可以保证是最小树。通过MATLAB出的最小树b矩阵（见附录），转换为图像连接在

15、一起为转化成直角坐标系中的最小树为如图1-7:051016202530图1-7在此最小树的基础上划出的送货区域为如图1-8:图1-8则业务员的送货路线、送货区域、送货的路程及时间（通过excel可得）如卜表1-9:送货线路行进次序问题一业务员分配路程（而时间(min)6小时8小时10-1-3-4-8-034121.620-2-6-5-7-038131.230-10-22-21-11-9-054179.640-12-13-14-052154.850-20-18-17-16-058179.260-19-25-24-068193.270-26-28-30-23-096270.480-15-27-29

16、-082226.8总计4821456.85个4个表1-9模型检验如表1-10:万案总路程总时间业务员人数理论上最少人数6小时8小时6小时8小时一5221516.85人4人4.2133.16二4861466.45人4人P4.1673.1251二4821456.85人4人4.0133.01表1-10通过用条形图进行各个方案进行比较得到如表1-11问题一中三种方案的时间路程比较表1-11实验结果的对比发现，用最小树理论解出来的比按几何方法划区域的解更优。对比发现，当总路程最小时，往往会使总费用最小。最终的答案为：(1) 需要5个业务员，总的运行公里数为482km,每个业务员的运行路线为上文的方案四的

17、运行路线。(2) 当业务员的工作时间延长到8小时时，依然是方案三为最优，业务员的安排变化在上文的方案三中的安排。问题二当业务员到达第一个送货点后，即以该送货点为中心，计算周围送货点与该送货点的快件密集度，快件密集度最大的作为首选下一个送货点，即di=maxbij;到达第二个送信点后，即以该送货点为中心，计算周围送货点与该送货点的快件密集度，快件密集度排名第二的作为首选第二个送货点；到达第三个送货点后，即以该送货点为中心，计算周围送货点与该送货点的快件密集度，快件密集度排名第三的作为首选第二个送货点；按此方法依次类推，直到根据约束条件为每次携带的快件量不超过25kg,找到最后一个送货点。若首选送

18、货点的快件量大丁总快件量(25kg)，则依次选择快件密集度乂次之且满足要求的送货点作为最后一个送货点，使总的快件量最大限度的接近25kg，最后一个送货点的选择以总的快件量为主导因子，以距离最短为次要因子。K叩目标函数：minF3qid“2dsign（n）k（ii）kiknkuk-1i-1约束条件:ZqrkiQKi=1KnkZzdrk（i2）rkidrk/ko，Si9k-1i-10nk-LKznk=LkTRk=311,2,LRk1cRk2=一，一J=k2s.t.nk1n（nk）nkv一tv6,i=1,2,nQ问题一、三都是以路程作为划分的界限，而问题二就是考虑以费用为主，费用最主要的因素就是重量

19、和路程，根据题意，每个送货点的送货的质量是已知确定的，在确定送货路线的时候，需要考虑每个业务员每次的载重量不得超过25Kg，且每个业务员每天工作量少丁6小时即满足上面论述中需要注意的一些限制条件。要使得快递公司支出费用最少，则在安排业务员的路线的时候，需要尽可能使路线短，且载重量在离原点近的时候可以卸载快件。根据送货点的均匀度，将此区域大致分为三个小区域，记为外围、中围、内围，方便下面路线确定。如下方图2-1所示。图2-1首先把快件的重量按从大到小的顺序排列，将排序的前八个送货点记为重货点，其次八个为中等点，其余的记为轻货点。显然每个送货点的信件量的大小的分布是随机分布的，排列如下方表2-2所

20、示。这对后面路线的确定非常重要。送货点重量xy送货点重量xy重货点111212.7146轻货点1135.81292271221132175.8618326102017345.5474n259.615144204.6714528.215554.53116298.125166304.228187.18327114.11738197.815128143.81012中等点11247.615199163.52162187.5111710153.4199377.2791163084226.821012232.42795106.51401382.3966216.22251491.41027136548286

21、2420表2-2第一条路线：如表所示，送货点12的送货质量最大，以这个点为中心，寻找距离较近的送货点，并且要满足前面叙述的约束条件，即每条路线上载重量不超过25Kg因为送货点12在中围里面，则尽可能再在内围寻找满足条件的送货点。此时符合的点包括8、1、11、10,这是最优化的问题，为了后面的路线，我们决定选择10-12-11这条路线。返回线出发线第二条路线：排除上面已经确定的送货点外，送货点27的送货质量是最大的，以这个点为中心，寻找距离较近的送货点，并且满足前面叙述的约束条件。因为送货点27在外围，贝俄们尽可能再在内围和中围寻找满足条件的送货点。最后优化比较后，确定路线7-14-270第三条

22、路线：排除上面已经确定的送货点外，送货点26的送货质量是最大的，以这个点为中心，寻找距离较近的送货点，并且满足前面叙述的约束条件。由图可见，送货点28距离送货点26很近，而且这两点的信件量都是比较大的，我们将这两点安排在一条路线上，因为这两个点都是在外围，贝俄们尽可能再在内围和中围寻找满足条件的送货点。最后优化比较后，确定路线1-26-28。返回线出发线第四条路线：排除上面已经确定的送货点外，送货点25的送货质量是最大的，以这个点为中心，寻找距离较近的送货点，并且满足前面叙述的约束条件。由图可见，送货点19距离送货点25很近，而且这两点的信件量都是比较大的，我们将这两点安排在一条路线上，因为这

23、两个点都是在中围，则我们尽可能再在内围和外围寻找满足条件的送货点。最后优化比较后，确定路线13-19-25。出发线第五条路线：排除上面已经确定的送货点外，送货点2的送货质量是最大的，以这个点为中心，寻找距离较近的送货点，并且满足前面叙述的约束条件。因为送货点2在内围，贝俄们尽可能再在中围和外围寻找满足条件的送货点。最后优化比较后，我们确定路线2-5-16-17。返回线第六条路线：排除上面已经确定的送货点外，送货点29的送货质量是最大的，以这个点为中心，寻找距离较近的送货点，并且满足前面叙述的约束条件。因为送货点29在外围，如图送货点30也在送货点29附近，而且送货点30距离原点（公司总部）最远

24、，则将这两个点放在一条路线上，然后我们尽可能再在内围和中围寻找满足条件的送货点。最后优化比较后，确定路线22-15-29-300第七条路线：排除上面已经确定的送货点外，送货点24的送货质量是最大的，以这个点为中心，寻找距离较近的送货点，并且满足前面叙述的约束条件。如图，送货点6、20、18、24大致在一条射线上，这样可以节省很多不必要的路程，则可以达到节约费用的效果。最后优化比较后，确定路线6-20-18-24。第八条路线：排除上面已经确定的送货点外，只剩下六个送货点，其中送货点21的送货质量是最大的，并且这六个点满足前面叙述的约束条件，那么将这六个点按照一定的顺序排列。最后优化比较后，确定路

25、线4-3-8-9-21-23.转换为图像连接在一起为转化成直角坐标系中的走向图形为图2-3:图2-3由此，画出的送货区域的折线距离图2-4图2-4通过C语舌编程以及excel的计算得到表2-5走的路线重量费用路程时间10-1-26-28-02421108825020-2-5-16-17-02210475016630-4-3-8-9-21-23-023.81900.28628240-6-20-18-24-022.718356821050-7-14-27-0231888.46820060-13-19-25-023.21890.45817570-12-11-10-023.31394.84619280

26、-22-15-29-30-022.52570.396P282合计184.514636.15601757表2-5得到每条路线的费用分别为2110元，1047元，1900.2元，1835元，1888.4元，1890.4元，1394.8元，2570.3元。快递公司应支付给所有业务员的总费用为：14636.1元。五、模型评价和改进1、模型的优点：(1) 本模型能够直观地看出各种策略的优缺点，便于决策。(2) 通过各种策略的横向比较，能直观地选出最优解。而且模型简单易懂，便于理解。(3) 模型系统的给出了业务员的运输方案，便于指导工作实践。2、模型的缺点：在最小树方案中，由于时间有限，没能穷举各种安排线

27、路。相信还会有更优的方案。方案三的6小时业务员的理论人数为4.013,8小时的理论人数为3.01,可以通过优化使得人数控制在4人和3人。而且，各个业务员的工作时间安排不其合理，这需要进一步改进。参考文献姜启源、谢金星、叶俊编，数学模型-3版，北京，高等教育出版社，2003.81 周品赵新芬编，MATLAK学建模与仿真，国防工业出版社，2009.42 基于matlab动态规划中最短路线的实现程序J电脑学习施益昌郑贤斌李自立3 物流配送问题的混沌优化算法研究中央民族大学学报(自然科学版)2009年11月第18卷第4期4 Dijkstra算法在企业物流运输网络中的应用湖南农业大学学报(自然科学版)2

28、005年8月第29卷4期附录问题一：a的值是使用excel计算得出，他们各个点相互的距离为ABCDEFGHIJKLMN0PQRSTuVWXYzABACADAB105_4699n10?.131515161710151923222322,2Q312924322939364125,055481091218181415161512IS12212221252023；31283835403450PJ9976?1313,1112131215151918191820272520253&3237465405556111717111U1110111317161720242523182623333035594950

29、68111622221613141310162019202529282621|292536333869e95606111622221611876ID1413182529262015；23203027327117586Q5101616IQ56512ID1211121923201813|2l1828253081096611115051111557W17151312131418211914叫19292S3971271116151050638910152220161516151324221725223223341Q13181317222216116Q661116212S2620131413722201

30、5232030273211IS18131722221186061116212E26201183716181317142421261215if1116To58660s10Tb222014789131614917142421261T1615121013115691111505101715971418151381613232025.14171613Ill14367101616105051210651219232012715：1222192415161512!io.137510152121151050757101724：2825133161523202516151215!u106121722232E2

31、217127061017243135321615192226232819181513j161010152025262015105606152229：33301013152020212218232219A7；20141213162020149671060916232?2467914161518191222113191311121513117551017159071418157210717141920232219172018121316143871217242216707113149961613132122211825251914151379141924312923147069211G149171

32、41922202520由29292318137713182328353327181160152520IS1323202523302?28262021242216Ifl1520253230241539150221715ID14g1024292S252$套20IS1922201；3141312131W106714212522067121314252120132112；U17151.39&73151372gLtj2Cl1750S715121?26323128赤W92.32122262317171615161915910914IE；157805769272&2825262C18192220141413

33、1216222Ci14,7691-：1012760107122839,3835333S30282932302424232,223262016Ti1517231410157100562936,3532痢|33272526洲2721212019202321151413142091312675053041403738323031343226262524252S2218191819251014IT912S50平问题一、MATLA睢序如下：a=0,5,6,9,11,8,14,16,15,12,14,20,20,21,22,21,18,24,28,27,28,27,21,36,34,29,37,34,44

34、,41,46;5,0,5,4,6,9,9,11,10,7,13,15,15,16,17,16,15,19,23,22,23,22,20,31,29,24,32,29,39,36,41;6,5,0,5,5,4,8,10,9,12,18,18,14,15,16,15,12,18,22,21,22,21,25,30,28,23,31,28,38,35,40;9,4,5,0,4,9,9,7,6,7,13,13,11,12,13,12,15,15,19,18,19,18,20,27,25,20,28,25,35,32,37;11,6,5,4,0,5,5,5,6,11,17,17,11,10,11,10,

35、11,13,17,16,17,20,24,25,23,18,26,23,33,30,35;8,9,4,9,5,0,6,8,11,16,22,22,16,13,14,13,10,16,20,19,20,25,29,28,26,21,29,26,36,33,38;14,9,8,9,5,6,0,6,11,16,22,22,16,11,8,7,6,10,14,13,18,25,29,26,20,15,23,20,30,27,32;16,11,10,7,5,8,6,0,5,10,16,16,10,5,6,5,12,10,12,11,12,19,23,20,18,13,21,18,28,25,30;15,

36、10,9,6,6,11,11,5,0,5,11,11,5,6,7,10,17,15,13,12,13,14,18,21,19,14,22,19,29,26,31;12,7,12,7,11,16,16,10,5,0,6,8,8,9,10,15,22,20,16,15,16,15,13,24,22,17,25,22,32,29,34;14,13,18,13,17,22,22,16,11,6,0,6,6,11,16,21,28,26,20,13,14,13,7,22,20,15,23,20,30,27,32;20,15,18,13,17,22,22,16,11,8,6,0,6,11,16,21,28

37、,26,20,11,8,7,7,16,18,13,17,14,24,21,26;20,15,14,11,11,16,16,10,5,8,6,6,0,5,10,15,22,20,14,7,8,9,13,16,14,9,17,14,24,21,26;21,16,15,12,10,13,11,5,6,9,11,11,5,0,5,10,17,15,9,6,7,14,18,15,13,8,16,13,23,20,25;22,17,16,13,11,14,8,6,7,10,16,16,10,5,0,5,12,10,6,5,12,19,23,20,12,7,15,12,22,19,24;21,16,15,1

38、2,10,13,7,5,10,15,21,21,15,10,5,0,7,5,7,10,17,24,28,25,13,8,16,15,23,20,25;18,15,12,15,11,10,6,12,17,22,28,28,22,17,12,7,0,6,10,17,24,31,35,32,16,15,19,22,26,23,28;24,19,18,15,13,16,10,10,15,20,26,26,20,15,10,5,6,0,6,15,22,29,33,30,10,13,15,20,20,21,22;28,23,22,19,17,20,14,12,13,16,20,20,14,9,6,7,10

39、,6,0,9,16,23,27,24,6,7,9,14,16,15,18;27,22,21,18,16,19,13,11,12,15,13,11,7,6,5,10,17,15,9,0,7,14,18,15,7,2,10,7,17,14,19;28,23,22,19,17,20,18,12,13,16,14,8,8,7,12,17,24,22,16,7,0,7,11,8,14,9,9,6,16,13,18;27,22,21,18,20,25,25,19,14,15,13,7,9,14,19,24,31,29,23,14,7,0,6,9,21,16,14,9,17,14,19;21,20,25,2

40、0,24,29,29,23,18,13,7,7,13,18,23,28,35,33,27,18,11,6,0,15,25,20,18,13,23,20,25;36,31,30,27,25,28,26,20,21,24,22,16,16,15,20,25,32,30,24,15,8,9,15,0,22,17,15,10,14,9,10;34,29,28,25,23,26,20,18,19,22,20,18,14,13,12,13,16,10,6,7,14,21,25,22,0,5,7,12,10,13,14;29,24,23,20,18,21,15,13,14,17,15,13,9,8,7,8,

41、15,13,7,2,9,16,20,17,5,0,8,7,15,12,17;37,32,31,28,26,29,23,21,22,25,23,17,17,16,15,16,19,15,9,10,9,14,18,15,7,8,0,5,7,6,9;34,29,28,25,23,26,20,18,19,22,20,14,14,13,12,15,22,20,14,7,6,9,13,10,12,7,5,0,10,7,12;44,39,38,35,33,36,30,28,29,32,30,24,24,23,22,23,26,20,16,17,16,17,23,14,10,15,7,10,0,5,6;41,

42、36,35,32,30,33,27,25,26,29,27,21,21,20,19,20,23,21,15,14,13,14,20,9,13,12,6,7,5,0,5;46,41,40,37,35,38,32,30,31,34,32,26,26,25,24,25,28,22,18,19,18,19,25,10,14,17,9,12,6,5,0;functionb,u,w=mintrees(a,k)%最小生成树，a邻接矩阵，k起点ifnargout=1k=1;endm,n=size(a);fori=1:mforj=1:nifa(i,j)=0a(i,j)=inf;endendendb=zeros(

43、n);u(1)=k;j=1;v=zeros(1,n);v(k)=1;foro=1:n-1sn=ones(3,n)*inf;forxk=1:jk=u(xk);p=max(a(k,:);fori=1:nifv(i)1&a(k,i)pp=a(k,i);endendfori=1:nifv(i)1&a(k,i)=pbreak;endendsn(123,k)=i,p,u(xk);endw(j),k=min(sn(2,:);j=j+1;u(j)=sn(1,k);b(sn(1,k),sn(3,k)=sn(2,k);v(u(j)=1;endb=mintrees(a)b=Columns1through230000

44、000000000000000000050000000000000000000000050000000000000000000000400000000000000000000000040000000000000000000004000000000000000000000000500000000000000000000005000000000000000000000000050000000000000000000000050000000000000000000000060000000000000000000000060000000000000000000050000000000000000000

45、005000000000000000000000000000050000000000000000500000000000000000000060000000000000000000000000000000500000000000000000000060000000000000000000000500000000000000000000070000000000000000000000000000000600000000007000000000000000000000000000000008000000000000000000000000000000000000000000002000000000

46、0000000000000000000000000000000000000600000000000000000000000000000000000000000000000000000000000000000000000Columns24through3100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000500000000000000000000600000000000000000000000000000000000000000000000000000

47、000000000000000000000000000000000000000000000000000000050000000005000000050问题二C语言源程序#include#includevoidmain()floatQ86=24,16,6,0,0,0,22,13.8,9.3,5.8,0,0,23.8,18.3,12.3,10,8.6,2.4,22.7,19.7,15.1,7.6,0,0,23,15.8,12,0,0,0,23.2,17.4,9.6,0,0,0,23.3,16.8,4.1,0,0,0,23.5,15.7,12.3,4.2,0,0;floatD86=5,32,7,0,0,0,6,8,6,6,0,0,11,4,6,5,15,9,8,13,7,6,0,0,6,6,12,0,0,0,21,6,2,0,0,0,14,6,6,0,0,0,21,11,13,5,0,0;floatd8=44,24,36,34,34,29,20,46;floata=3,b=2,m,M;inti,j;for(i=0;i8;i+)for(j=0;j6;j+)m=a