《2022年产品运输线路模型 .pdf》由会员分享，可在线阅读，更多相关《2022年产品运输线路模型 .pdf（28页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、2010高教社杯全国大学生数学建模竞赛承诺书我们仔细阅读了中国大学生数学建模竞赛的竞赛规则.我们完全明白，在竞赛开始后参赛队员不能以任何方式（包括电话、电子邮件、网上咨询等）与队外的任何人（包括指导教师）研究、讨论与赛题有关的问题。我们知道，抄袭别人的成果是违反竞赛规则的,如果引用别人的成果或其他公开的资料（包括网上查到的资料），必须按照规定的参考文献的表述方式在正文引用处和参考文献中明确列出。我们郑重承诺，严格遵守竞赛规则，以保证竞赛的公正、公平性。如有违反竞赛规则的行为，我们将受到严肃处理。我们参赛选择的题号是（从A/B/C/D 中选择一项填写）：A 我们的参赛报名号为（如果赛区设置报名号
2、的话）：所属学校（请填写完整的全名）：宁 波 工 程 学 院参赛队员(打印并签名)：1.顾豪2.郑启奔3.施雪丹指导教师或指导教师组负责人(打印并签名)：数 模 组日期：2010 年 8 月 13 日赛区评阅编号（由赛区组委会评阅前进行编号）：名师资料总结-精品资料欢迎下载-名师精心整理-第 1 页，共 28 页 -2010高教社杯全国大学生数学建模竞赛编 号 专 用 页赛区评阅编号（由赛区组委会评阅前进行编号）：赛区评阅记录（可供赛区评阅时使用）：评阅人评分备注全国统一编号（由赛区组委会送交全国前编号）：全国评阅编号（由全国组委会评阅前进行编号）：名师资料总结-精品资料欢迎下载-名师精心整理
3、-第 2 页，共 28 页 -1 最佳运输线路模型摘要本文通过 dijkstra算法，贪婪算法，二边逐次修正法，穷举法，依次为问题一中的每道提问作出了令人满意的回答，同时利用穷举法对前面的计算结果进行了验证。第一小问总最短里程为2188km.第二小问小型运输车的最短运输总里程为 2339km.第三小问最优线路为：9578642319vvvvvvvvvv对于问题二，本文对附表中的数据进行了合理的分析，同时，在确定货物补充线路之前，制定了三个利于方案确定的重要原则：a.较远目的地优先原则；b.空车返回线路不重复原则；c.各连锁店一次性全部补充原则。基于以上三项原则，本文制定出一套十分合理的方案。第
4、一部分，要求小型运输车空车返回，由于是沿最短路线运输，保证了这一部分方案的最佳性。在第二部分，因为对原则a.的遵守保证了剩余货物补充点能充分靠近出发点，所以在此部分不需要对线路的大量讨论。利用 TSP近似算法，结合 floyd算法得出的最佳路径，确定最佳推销员回路作为第二部分线路，进而得出当日小型运输车总行驶里程。通过多次模拟，再取均值，得到小型运输车周平均总公里数为3088.4km.对于问题三，本着为公司盈利的目的，本文重新建立了两个新的模型：一、增设工厂；二、根据实际情况，用大型平板车运输。对于模型一，在floyd算法基础上得出需在7v 重新设立一个分厂。对于模型二，运用搜索法求得最佳路径
5、。关键词：dijkstra算法，贪婪算法，二边逐次修正法，优先原则，计算机模拟名师资料总结-精品资料欢迎下载-名师精心整理-第 3 页，共 28 页 -2 一、问题的提出在济南市，百老泉白酒是一知名品牌，此酒已有三百年的历史，深受当地及附近消费者的喜爱。百老泉白酒由济南百老泉酒厂（厂址在市区）专业生产。除了在当地销售以外，厂家还在附近的县、镇开了几家专卖连锁店，（图表见附表一，其中：9v 是酒厂所在地，18vv 是附近的县、镇上的8 个专卖连锁店，线上标记的数字表示两地相距的公里数）。厂家每隔一段时间都要向这些专卖店运送一定数量的白酒，但运输方法的优劣直接影响酒厂的经济效益，厂家希望你能提供一
6、种合理的运输方案。假设 8 个连锁店的每周销售量如表1.表 1 8个连锁店的周销售量统计表连锁店1v2v3v4v5v6v7v8v周销售(桶)20 10 5 10 20 15 25 20 1为了满足这些连锁店的供货需求，若厂家采用小型运输车（每车最多装5 桶）作为运输工具，每周至少行驶多少车公里，相应的行驶线路是什么？2假设每个连锁店每周销售量增加4%，小型运输车的最短运输线路应怎样设计？3假设厂家采用一种大型平板车（载重量足够大）每周运送一次，即可满足供货需求，从节省油耗角度考虑（平板车自重1 吨，每桶酒重 200公斤），最佳运输线路是什么？二、各连锁店店内的最大存储量分别为：6,7,5,6,
7、7,7,6,7（桶）。为了更好地满足消费者的需求，厂家要求每天各店打烊以后就清点存量并通知厂家，厂家根据各店的情况当晚用小型运输车送货到各店并装满酒桶，试估计一下小型运输车周平均总公里数。三、你对这个问题是否可以进行进一步的扩展？二、问题的分析在第一问中有 3 个小问题，这 3 个问题时层层深入的。可以通过图论中求最短路与最短回路的常用算法便可解决。同时，因为原题中线路并不复杂，可以考虑将所有可行线路全部求出的方法进行验证。第二问中，最佳路径与各连锁店销售量有关，而各连锁店销售量是随机变量，所以可以通过计算机按其分布规律模拟出其合理的销售量，所以在确定方案前，需对附表中的数据进行合理分析。另外
8、，为了能制定出较优的方案，可以制定一些重要原则，如较远目的地优先原则。总体上说，可以将方案分为两部分。第一部分，要求小型运输车空车返回，可以借鉴第一问中对最短路的求解结果，保证这一部分方案的最佳性。在第二部分，可利用 TSP近似算法，结合 floyd算法得出的最佳路径，确定最佳推销员回路作为第二部分线路，进而得出当日小型运输车总行驶里程，通过多次模拟，再取均值。对于问题三，本着为公司盈利的目的，重新建立两个新的模型：一、增设工厂；二、根据实际情况，用大型平板车运输。名师资料总结-精品资料欢迎下载-名师精心整理-第 4 页，共 28 页 -3 三、基本假设1.计算行驶里程时要考虑返程；2.各店销
9、售量不小于0，同时又不大于其最大储货量；3.各连锁店之间、每家连锁店相连销售日的销售量无关；四、定义符号说明1.iu：第 i 连锁店周销售量；2.Z：小型运输车每周总车公里数；3.x：行驶里程；4.y：大型平板车油耗量；5.n：大型平板车所载白酒量（桶）；6.iv：第 i 个连锁店；7.H：遍历所有连锁店最佳H圈总里程；8.X：货物补充模型中小型运输车周平均总行驶里程五、模型的分析、建立5.1 Dijkstra算法1求行驶路线设 G为赋权有向图或无向图，G边上的权均非负。Dijkstra算法：求 G中从顶点0u 到其余顶点的最短路。对每个顶点，定义两个标记（l v，z v），其中:l v：表示
10、从顶点0u 到v 的一条路的权；z v：v的父亲点，用以确定最短路的路线。算法的过程就是在每一步改进这两个标记，使最终l v为从顶点0u到v的最短路的权。输入为G的带权邻接矩阵,W u v。S：具有永久标号的顶点集。算法步骤：（1）赋初值：令00,0Su l u.vSVS，令0,l vW uv，0z vu，0uu.（2）更新 l v，z v：vSVS,若,l vl uW u v，则令,l vl uW u v，z vu（3）设v是使 l v 取最小值的S中的顶点，则令SSv，uv.（4）若S，转（2）；否则，停止。用上述算法求出的 l v 就是0u 到 v的最短路的权，从 v的父亲标记 z v
11、追溯到0u,就得到0u 到 v的最短路的路线。根据题目数据，可得邻接矩阵：名师资料总结-精品资料欢迎下载-名师精心整理-第 5 页，共 28 页 -4 040infinfinf35infinf384001820infinfinfinfinfinf1801012infinfinfinfinf20100inf15inf11infinfinf12inf0inf813inf35infinf15inf0inf912infinfinfinf8inf01110infinfinf11139110738infinfinfinf121070w按照算法步骤，用 C+编出求最小路径的程序，得到百老泉酒厂到各专卖连锁店
12、的最短距离，如表2 所示：表 2 酒厂到各连锁店最短距离各连锁店1v2v3v4v5v6v7v8v最短距离/km 40 58 50 56 35 48 44 38 相应最短路径如下图所示：图 1 酒厂到各连锁店最短路径由于各连锁店周销售量均为5 的整数倍，小型运输车每车只能装5 桶，故每辆运输车只抵达一处连锁店。则可得每周总车公里数为：91252188()iiiuZdkm其中iu 表示第 i 连锁店周销售量。5.2 TSP 近似算法2名师资料总结-精品资料欢迎下载-名师精心整理-第 6 页，共 28 页 -5 若各连锁店周销售量增加4%，根据各连锁店原有销售量可算得新销售量：表 3 各连锁店新周销
13、售连锁店1v2v3v4v5v6v7v8v总计周销售(桶)20 10 5 10 20 15 25 20 125 新周销售量（桶）20.8 10.4 5.2 10.4 20.8 15.6 26 20.8 130 由表可知，各专卖连锁店的周销售增加量总和正好为5 桶，因此，在第一小题的基础上，我们再派出一辆满载的小型运输车，利用 TSP近似算法算出遍历各专卖连锁店最短路径，沿最短路径遍历运输周销售量的增加量。1.用贪婪算法选出初始H圈：0121,ijnCv vvvv v.时间复杂度：22logO nn Step 1：给所有边按长度排序 Step 2：选择最短的满足条件的边加入到路径中。条件：不会构成
14、小于N条边的环路。Step 3：重复 Step 2，直至路径中有 N条边。2.对所有的,11i jijn,若,1,1,1,1ijijiijjw v vw vvw v vw vv，则在0C 中删去边,1iiv v和1,jjvv而加入边,ijv v和1,1ijvv，形成新的 H圈C，即0121111,ijjijnCv vv v vvvv v见图（a），（b）图（a）图（b）3.对C重复步骤 2，直到条件不满足为止，最后得到的C即为所求。结合第一小题得到的从厂家到各专卖连锁店的最短路径，即得到所求的最短运输线路。5.3 大型平板车最佳运输线路通过资料搜索了解到，汽车行驶一公里，载重量每增加45kg，
15、相应油耗量将增加 2%。由此可知油耗量与载重的函数关系为指数函数。同时，可认为当载重量一定时，油耗量与行驶公里数成正比。故我们可以假设油耗量与里程、载重量之间的关系表达式为：名师资料总结-精品资料欢迎下载-名师精心整理-第 7 页，共 28 页 -6(0.21)anyxe其中：y：耗油量；x：里程数；n：装运的总酒量（以桶为单位）；a：系数。每桶酒重 200 公斤，车身自重 1 吨，故(0.21)n表示平板车总重。由于a的取值不影响最优解路线，故可取值为1，即0.21nyxe由于原图路线简单，通过穷举法求得所有可行路线共11种（可行哈密顿圈），考虑到不同方向对耗油量的影响，运输方案扩展为 22
16、 种，故只需对 22种运输方案依次计算所需耗油量，便可找出耗油量最小的最佳运输线路：穷举所有 1 至 8 的自然数序列，分别代表 8 个连锁店，依先后顺序进行白酒运输，若对任意两个连锁店（或酒厂与连锁店），它们之间没有直接相连的道路，放弃该方案。5.4 小型运输车补货模型1.数据分析为满足消费者的需求，厂家要求每天各店打烊以后就清点存量并通知厂家，厂家根据各店情况当晚用小型运输车为所有连锁店补货。为确定补货线路，需要确定各店所需补充量。原题附表中提供了8 个连锁店不定期日销售量记录，在假设3.基础上我们可以对每个连锁店销售量进行总体分布的检验，根据常理，我们首先对其进行正态分布检验，通过mat
17、lab 软件中的 normplot 函数可以得到如下结果（这里只列出前 3 家店分析结果）：图 2 连锁店1v 日销售量正态分布检验名师资料总结-精品资料欢迎下载-名师精心整理-第 8 页，共 28 页 -7 图 3 连锁店2v 日销售量正态分布检验图 4 连锁店3v 日销售量正态分布检验若图中十字距离虚线越近，则其分布越接近正态分布，根据上图可以认为，连锁店日销售量服从正态分布。因此，在生成各连锁店日销售量时，可以从原数据计算得到日销售量均值与方差，通过计算机模拟生成服从相同参数正态分布的随机数作为各连锁店日销售量，即当晚各店需补充的量。计算各连锁店均值与方差，计算结果如下：表 4 各连锁店
18、日销售量均值、方差1v2v3v4v5v6v7v8v均值2.63 1.58 1.05 1.59 2.91 2.15 3.53 2.92 方差0.89 0.65 0.54 0.57 1.02 0.85 0.87 0.85 名师资料总结-精品资料欢迎下载-名师精心整理-第 9 页，共 28 页 -8 根据多个服从正态分布的无关变量之和也服从正态分布的原理，可知所有连锁店所需补充白酒总量也服从正态分布，且128，2222128代入数值，得总均值18.38，总方差26.24。由此可以估计出当晚需发送小型运输车大致为4 辆。2.方案制定原则为能得到较优线路，在确定方案之前，制定如下原则：a.较远目的地优先
19、原则；b.空车返回线路不重复原则；c.各连锁店一次性全部补充原则。越远的连锁店，为其补货所需行驶里程越大，若先为较近连锁店补货，当运输为较远连锁店补货时，很有可能补货结束后有剩余。如果先为较远连锁店补货，剩余货物可以在返回酒厂过程中为经过的连锁店补货。按此原则可以显著减少运输线路里程。最初几辆运输车补货时，由于需补货连锁店较多，返回时多是空车，但如果线路有较多重复，重复经过的连锁店的需求量的变化将会同时影响多辆运输车补货时调剂问题，往往会产生一辆运输车无剩余，而同路线运输车剩余很多的情况。因为安排路线时，以确定线路尽量不重复原则，一个连锁店一般由一辆运输车补充，所以制定各连锁店一次性全部补充原
20、则可以使运输车不必再次回到此连锁店（除非运输车剩余货量少于连锁店需求量）。根据原则 b，同时考虑到 5.1 模型已得出酒厂至连锁店最短线路，制定如下线路：图 5 补货方案初步线路因为出发路线为最短线路返回酒厂时沿原线路行驶。3.方案制定1）依次检查各线路经过的连锁店补货量之和，若和大于5，发送一辆运输车按原则 a.补货；2）运输车返回后再次检查，若还大于5，再发送一辆运输车，直到剩余补货量之和小于 5；3）将已补货连锁店从图中去除，检查剩余连锁店，若有两个连锁店没有直接相连的直线，则将两者相连，同时，在原图中用 floyd算法计算出两者间最短距离，作为权值赋给两者连线，得到新的一个图；名师资料
21、总结-精品资料欢迎下载-名师精心整理-第 10 页，共 28 页 -9 4）在新图中利用 TSP近似算法计算出最佳推销员回路（由贪婪算法得到初始 H圈，用二边逐次修正法得出较优解），发送运输车沿最佳推销员回路进行补货。4.floyd算法：求任意两点间的最短路,D i j：i到j的距离；,R i j：i到j之间的插入点；输入:带权邻接矩阵,w i j.（1）赋初值：对所有i,j,d i jw i j,r i jj,1k（2）更新,d i j,r i j：对 所 有i,j，若,di kdk jd ij，则,d ijd i kdk j,r i jk（3）若kv，停止否则1kk，转（2）5.5 问题的
22、进一步扩展对于这个问题的扩展，建立了两个模型：一、增设工厂；二、根据实际情况，用大型平板车运输。对于第一个模型，考虑到厂址在市区，这对百老泉的运输成本有些高，而有部分的专卖连锁店还在县镇，考虑到在这些县镇上设立一个分厂，或者建立一个存储酒的站点，这样可以减少运输成本，有利于工厂的可持续性发展。对后长久获利来说有着重大的意义。所以对这些连锁专卖店进行了分别统计，考虑到这些点和路径都是离散的，而且都没有联系，无法考虑中心处某一边上点到其余各点的最短路径，所以用floyed算法求出每个点到其余各点的最短路径，然后将那些最短路径相加，最终得到一个最短路径。对于第二个模型，考虑到小型运输车需要运送多次，
23、比较麻烦，所以用大型平板车来代替。考虑到油耗的最小的问题和实际每天卖出的酒量，将所有的路径遍历一遍，得出想要的路径。六、模型的求解1.Dijkstra算法结果通过 C+编程得到如下结果：表 5 酒厂至各连锁店最短行驶线路及里程目的地途经连锁店里程目的地途经连锁店里程1v无40 5v无35 2v1v58 6v8v48 3v5v50 7v5v44 4v8v、6v56 8v无38 由此计算出采用小型运输车作为运输工具，每周至少行驶总里程：2188()Zkm名师资料总结-精品资料欢迎下载-名师精心整理-第 11 页，共 28 页 -10 2.TSP近似算法结果先由贪婪算法得到一个初始H圈：957864
24、2319vvvvvvvvvv图 6 贪婪算法得到的初始H圈用二边逐次修正法完善后得：9578642319vvvvvvvvvv相应里程：H=151（km）可以看出，原图较简单，贪婪算法所得解即为最优解。因此，每个连锁店每周销售量增加4%后，小型运输车的最短运输线路为：以 dijkstra算法结果为基础，同时一辆运输车沿最佳H 圈遍历，总里程：21881512339()Hkm。3.穷举法得所有可行 H圈表 6 所有可行 H圈各方案始点终点里程线路 1 9 8 7 6 4 2 1 3 5 9 164 线路 2 9 8 6 7 4 2 1 3 5 9 172 线路 3 9 8 6 4 7 5 3 2
25、1 9 161 线路 4 9 8 6 4 2 1 3 7 5 9 161 线路 5 9 8 5 7 6 4 2 3 1 9 160 线路 6 9 8 5 3 7 6 4 2 1 9 165 线路 7 9 5 7 8 6 4 2 3 1 9 151 线路 8 9 5 8 6 7 4 2 3 1 9 163 线路 9 9 5 8 6 4 7 3 2 1 9 157 线路 10 9 5 8 7 6 4 2 3 1 9 155 线路 11 9 5 3 7 8 6 4 2 1 9 156 名师资料总结-精品资料欢迎下载-名师精心整理-第 12 页，共 28 页 -11 可以看出线路 7 为最优解，即为
26、TSP近似算法结果。4.大型平板车最优线路由于同一线路不同方向会影响耗油量，因此对于11 条线路，大型平板车共有 22 个运输方案：表 7 大型平板车运输所有方案及总油耗始点终点里程总油耗方案 1 9 8 7 6 4 2 1 3 5 9 164 7.4631 方案 2 9 8 6 7 4 2 1 3 5 9 172 7.4756 方案 3 9 8 6 4 7 5 3 2 1 9 161 7.4753 方案 4 9 8 6 4 2 1 3 7 5 9 161 7.4754 方案 5 9 8 5 7 6 4 2 3 1 9 160 7.4813 方案 6 9 8 5 3 7 6 4 2 1 9 1
27、65 7.4820 方案 7 9 5 7 8 6 4 2 3 1 9 151 6.8830 方案 8 9 5 7 3 1 2 4 6 8 9 161 6.8832 方案 9 9 5 8 6 7 4 2 3 1 9 163 6.8942 方案 10 9 5 8 6 4 7 3 2 1 9 157 6.8942 方案 11 9 5 8 7 6 4 2 3 1 9 155 6.8940 方案 12 9 5 3 7 8 6 4 2 1 9 156 6.9189 方案 13 9 5 3 1 2 4 7 6 8 9 172 6.9312 方案 14 9 5 3 1 2 4 6 7 8 9 164 6.93
28、12 方案 15 9 1 3 2 4 7 6 8 5 9 163 7.9165 方案 16 9 1 3 2 4 6 7 5 8 9 160 7.9164 方案 17 9 1 3 2 4 6 7 8 5 9 155 7.9164 方案 18 9 1 3 2 4 6 8 7 5 9 151 7.9164 方案 19 9 1 2 4 6 7 3 5 8 9 165 7.9001 方案 20 9 1 2 4 6 8 7 3 5 9 156 7.9001 方案 21 9 1 2 3 5 7 4 6 8 9 161 7.9013 方案 22 9 1 2 3 7 4 6 8 5 9 157 7.9005 方
29、案 7 为最优路径。5.小型运输车补货1.一次模拟Matlab 随机产生各连锁店销售量：1v2v3v4v5v6v7v8v3.3955 0.48994 1.142 1.422 3.4856 1.8778 4.5896 2.7586 步骤 2）结束后：已行驶里程0200()xkm各连锁店剩余需补货量：1v2v3v4v5v6v7v8v3.3955 0.48994 1.142 0 3.0752 0 0 1.0583 步骤 3）结束后：Floyd 算法得两两连锁店间最短距离（邻接矩阵）：名师资料总结-精品资料欢迎下载-名师精心整理-第 13 页，共 28 页 -12 9v1v2v3v4v5v6v7v8v
30、9v0 40 58 50 56 35 48 44 38 1v40 0 18 20 30 35 38 31 38 2v58 18 0 10 12 25 20 21 28 3v50 20 10 0 22 15 22 11 18 4v56 30 12 22 0 22 8 13 18 5v35 35 25 15 22 0 20 9 12 6v48 38 20 22 8 20 0 11 10 7v44 31 21 11 13 9 11 0 7 8v38 38 28 18 18 12 10 7 0 新图：图 7 去除已补完货连锁店后的新图步骤 4）得出最优推销员回路：9123589vvvvvvv（已在图
31、8 中画出）总行驶里程433()xkm2.多次模拟模拟 1000 次后取平均值，得日平均总行驶里程：441.2010(km)x即可得周平均总行驶里程：3088.4()Xkm6.新工厂的增设在增设工厂的模型中，由floyed算法可得如下结果：名师资料总结-精品资料欢迎下载-名师精心整理-第 14 页，共 28 页 -13 路径12vv13vv14vv15vv16vv17vv18vv距离（公里）18 20 30 35 38 31 38 所以当工厂建在1v 时，它的最短路径1s 为210；路径21vv23vv24vv25vv26vv27vv28vv距离（公里）18 10 12 25 20 21 28
32、 所以当工厂建在2v 时，它的最短路径2s 为 134；路径31vv32vv34vv35vv36vv37vv38vv距离（公里）20 10 22 15 22 11 18 所以当工厂建在3v 时，它的最短路径3s 为 118；路径41vv42vv43vv45vv46vv47vv48vv距离（公里）30 12 22 22 8 13 18 所以当工厂建在4v 时，它的最短路径4s 为 125；路径51vv52vv53vv54vv56vv57vv58vv距离（公里）35 25 15 22 20 9 12 所以当工厂建在5v 时，它的最短路径5s 为 138；路径61vv62vv63vv64vv65vv
33、67vv68vv距离（公里）38 20 22 8 20 11 10 所以当工厂建在6v 时，它的最短路径6s 为 129；路径71vv72vv73vv74vv75vv76vv78vv距离（公里）31 21 11 13 9 11 7 所以当工厂建在7v 时，它的最短路径7s 为 103；路径81vv82vv83vv84vv85vv86vv87vv距离（公里）38 28 18 18 12 10 7 名师资料总结-精品资料欢迎下载-名师精心整理-第 15 页，共 28 页 -14 所以当工厂建在8v 时，它的最短路径8s 为 131；即73468251ssssssss，所以将工厂建在7v 处，将会减
34、少路程，使车公里数减少，减少运输成本，从长远来看有利于增加收益。工厂的可持续，健康的发展。7.用大型平板车运输在这题的求解中，考虑到油耗和实际的销售量，用搜索算法对路径进行了求解。公司可以根据实际的销售额，通过对照下列表，得到满意的路线。得到如下答案：1v2v3v4v5v6v7v8v1 6 1.6573 0 0.60262 1.2404 1.7537 3.0468 2.4319 2 4.1827 0.10484 1.9302 1.0071 2.9294 0.79533 3.946 0.42551 3 1.451 1.651 0.88937 1.7204 4.0882 1.4919 3.2098
35、 2.3516 4 1.6403 2.0024 1.1796 2.1176 2.0584 2.8976 5.278 2.3261 5 1.7562 2.4641 0.2808 2.374 2.8381 2.1911 3.2927 2.7817 6 2.7986 1.9867 1.0221 2.6754 3.6927 1.6419 3.349 2.2809 7 3.2667 0.76023 0.03511 1.1945 1.9836 2.6479 1.8423 3.8338 8 2.7797 1.6122 0 1.5893 2.3558 2.3354 3.8831 3.6097 9 0.8828
36、1 1.6802 0.51689 1.8862 2.8365 1.5219 3.4607 3.5779 10 2.5884 2.3532 0.68751 0.98045 2.3719 3.2508 3.726 3.3506 11 2.3306 1.4203 1.1437 2.0855 1.6374 3.3012 1.2332 3.443 12 4.6383 2.999 1.5686 0.9113 1.4856 2.043 3.1689 3.5819 13 1.4354 0.64052 0.39059 1.8189 0.6596 3.3205 3.8581 3.5695 14 3.0323 1.
37、1226 0.63632 4.0654 2.0794 0.77703 4.8048 5.0054 15 2.5043 0.74271 0.83284 1.9902 1.1941 1.3867 4.8312 3.8746 16 0.62592 0.60613 1.2003 2.5102 0.78254 1.4269 2.7504 4.346 17 3.2026 1.1819 0.85924 2.6545 1.9907 3.0799 3.0408 4.2029 18 2.4201 2.1225 0.54359 2.198 0 0.64041 3.4454 1.2356 上表参照的实际销售量表，下表
38、为上述表所对应的路线图：路径 1 1 2 3 5 7 9 8 4 6 1 路径 2 1 6 8 4 2 3 5 7 9 1 路径 3 1 6 8 9 7 5 3 4 2 1 路径 4 1 6 8 9 7 5 3 4 2 1 路径 5 1 6 8 9 7 5 3 4 2 1 路径 6 1 6 8 9 7 5 3 4 2 1 路径 7 1 6 8 9 7 5 3 4 2 1 路径 8 1 6 8 9 7 5 3 4 2 1 路径 9 1 6 8 9 7 5 3 4 2 1 路径 10 1 6 8 9 7 5 3 4 2 1 路径 11 1 9 7 5 8 6 4 3 2 1 名师资料总结-精品资料
39、欢迎下载-名师精心整理-第 16 页，共 28 页 -15 路径 12 1 9 8 7 5 3 2 4 6 1 路径 13 1 9 8 7 5 3 2 4 6 1 路径 14 1 9 8 7 5 3 2 4 6 1 路径 15 1 9 8 7 5 3 2 4 6 1 路径 16 1 9 8 7 5 3 2 4 6 1 路径 17 1 9 8 7 5 3 2 4 6 1 路径 18 1 9 8 7 5 3 2 4 6 1 七、模型推广、评价与改进在这道题中，我们主要用了最短路径的求法（Dijkstra算法，Floyed 算法）TSP近似算法（贪心法求哈密顿圈，二边逐次修正法），穷举法，计算机模拟
40、等等。而这些方法在遇到图的问题中，我们即可用这些方法，例如用在城市规划，城市出行等这些实际问题中。用上述方法即可得到所需的解。而在考虑一个运输问题时，在实际运营过程中会有一些新的问题，如：车辆具体的一些问题（车辆维修费，磨损费，租运输公司车的问题等等），新厂房建筑费等等。所以可以根据具体的问题，再重新考虑新的因素。所以如同考虑油耗问题一样，对这些因素进行具体的分析。可以采用层次分析法，因子分析法这些方法，对新的因素进行考虑和处理，最终得到一个最优的解，使运输的费用合理化。而对于其中遍历问题的时候我们用到了TSP近似算法，而对于求解 TSP近似算法的，主要包括:一些局部优化算法,如:近邻法、最近
41、插入法、最远插入法、贪心法等等，而一些启发式算法如模拟退火算法、遗传算法、蚁群算法、免疫算法、神经网络等。单纯使用一种算法来解决TSP 问题(尤其是城市规模较大时)效果不是很好,混合方法来解决 TSP问题,这时考虑一下 memetic 算法,这是一种效果很好的混合求解算法。memetic 算法是模仿文化进化。它从本质上来说就是局部优化策略与遗传算法中交叉算子的结合,所以也被称作混合遗传算法或遗传局部优化算法。对于此题中的运输问题，用前面提到的方法贪心法即可得正确的解，而若城市规模较大时，不能运用上述方法时，就可以用memetic 算法，运用上述算法就可以得到所需遍历的路径。参考文献：1 李春葆
42、，数据结构与算法教程，清华大学出版社，2007.10；2 赵静，数学建模与数学实验，高等教育出版社，2008.1；名师资料总结-精品资料欢迎下载-名师精心整理-第 17 页，共 28 页 -16 附件附件一：dijkstra算法 C+程序代码#include#include const int MAXVEX=100;#define INF 32767 void Dijkstra(int costMAXVEX,int n,int v)int distMAXVEX,pathMAXVEX;int sMAXVEX;int mindis,i,j,u,pre;for(i=0;in;i+)disti=cos
43、tvi;si=0;if(costviINF)pathi=v;else pathi=-1;sv=1;pathv=0;for(i=0;in;i+)mindis=INF;u=-1;for(j=0;jn;j+)if(sj=0&distjmindis)u=j;mindis=distj;if(u!=-1)su=1;for(j=0;jn;j+)if(sj=0)名师资料总结-精品资料欢迎下载-名师精心整理-第 18 页，共 28 页 -17 if(costujINF&distu+costujdistj)distj=distu+costuj;pathj=u;coutn Dijkstra算法求解如下:n;for(
44、i=0;in;i+)if(i!=v)cout vi:;if(si=1)cout 路径长度为 setw(2)disti;pre=i;cout 路径逆序为;while(pre!=v)coutpre,;pre=pathpre;coutpreendl;else cout 不存在路径 endl;void main()int cost9MAXVEX=0,40,INF,INF,INF,35,INF,INF,38,40,0,18,20,INF,INF,INF,INF,INF,INF,18,0,10,12,INF,INF,INF,INF,INF,20,10,0,INF,15,INF,11,INF,名师资料总结-
45、精品资料欢迎下载-名师精心整理-第 19 页，共 28 页 -18 INF,INF,12,INF,0,INF,8,13,INF,35,INF,INF,15,INF,0,INF,9,12,INF,INF,INF,INF,8,INF,0,11,10,INF,INF,INF,11,13,9,11,0,7,38,INF,INF,INF,INF,12,10,7,0;Dijkstra(cost,9,0);coutendl;附件二：floyd 算法 C+程序代码#include#include const int MAXVEX=100;#define INF 32767 void Floyed(int co
46、stMAXVEX,int n)int AMAXVEXMAXVEX,pathMAXVEXMAXVEX;int i,j,k,pre;for(i=0;in;i+)for(j=0;jn;j+)Aij=costij;pathij=-1;for(k=0;kn;k+)for(i=0;in;i+)for(j=0;j(Aik+Akj)Aij=Aik+Akj;pathij=k;coutn Floyed算法求解如下：n;名师资料总结-精品资料欢迎下载-名师精心整理-第 20 页，共 28 页 -19 for(i=0;in;i+)for(j=0;jn;j+)if(i!=j)cout ij:;if(Aij=INF)if
47、(i!=j)cout 不存在路径 endl;else cout 路径长度为：setw(3)Aij;cout 路径为 i;pre=pathij;while(pre!=-1)coutpre;pre=pathprej;coutjendl;void main()int cost9MAXVEX=0,40,INF,INF,INF,35,INF,INF,38,40,0,18,20,INF,INF,INF,INF,INF,INF,18,0,10,12,INF,INF,INF,INF,INF,20,10,0,INF,15,INF,11,INF,INF,INF,12,INF,0,INF,8,13,INF,35,I
48、NF,INF,15,INF,0,INF,9,12,INF,INF,INF,INF,8,INF,0,11,10,INF,INF,INF,11,13,9,11,0,7,38,INF,INF,INF,INF,12,10,7,0;Floyed(cost,9);coutendl;名师资料总结-精品资料欢迎下载-名师精心整理-第 21 页，共 28 页 -20 附件三：二边逐次修正法matlab 程序代码clear;clc;w=0,40,inf,inf,inf,35,inf,inf,38;40,0,18,20,inf,inf,inf,inf,inf;inf,18,0,10,12,inf,inf,inf,i
49、nf;inf,20,10,0,inf,15,inf,11,inf;inf,inf,12,inf,0,inf,8,13,inf;35,inf,inf,15,inf,0,inf,9,12;inf,inf,inf,inf,8,inf,0,11,10;inf,inf,inf,11,13,9,11,0,7;38,inf,inf,inf,inf,12,10,7,0;r=1 6 8 9 7 5 3 4 2 1;for i=1:7 for j=i+3:10 if w(r(i),r(j-1)+w(r(i+1),r(j)w(r(i),r(i+1)+w(r(j-1),r(j)r(i+1:j-1)=fliplr(r(
50、i+1:j-1);end end end r a=0;for i=1:9 a=a+w(r(i),r(i+1);end a 附件四：穷举法得所有可行H圈的 matlab 程序代码clear;clc;w=0,40,inf,inf,inf,35,inf,inf,38;40,0,18,20,inf,inf,inf,inf,inf;inf,18,0,10,12,inf,inf,inf,inf;inf,20,10,0,inf,15,inf,11,inf;inf,inf,12,inf,0,inf,8,13,inf;名师资料总结-精品资料欢迎下载-名师精心整理-第 22 页，共 28 页 -21 35,inf