数学建模max.doc

西北大学数学建模竞赛承 诺 书我们仔细阅读了西北大学数学建模竞赛的参赛规则与竞赛纪律。我们完全明白，在竞赛开始后参赛队员不能以任何方式（包括电话、电子邮件、网上咨询等）与队外的任何人研究、讨论与赛题有关的问题。我们知道，抄袭别人的成果是违反竞赛纪律的, 如果引用别人的成果或其他公开的资料（包括网上查到的资料），必须按照规定的参考文献的表述方式在正文引用处和参考文献中明确列出。我们郑重承诺，严格遵守参赛规则和竞赛纪律，以保证竞赛的公正、公平性。如有违反竞赛纪律的行为，我们将受到严肃处理。我们授权西北大学数学建模竞赛组委会，可将我们的论文以任何形式进行公开展示（包括进行网上公示，在书籍、期刊和其他媒体进行正式或非正式发表等）。参赛的题目 (从A/B中选择一项填写)B物资的配送报名院系（请填写完整的全名）物理学系参赛队编号31参 赛 队 员姓 名（打印）学 号 （打印）签 名李智2012112042陈臻博2012112077雒蒙2012112046 日期： 2013 年 5 月 1 日评阅编号（由校组委会评阅前进行编号）：西北大学数学建模竞赛编号专用页评阅编号(由校组委会评阅前进行编号):评阅记录:评阅人评分备注 评奖结果:物资的配送摘要本文是解决该物流公司的运输配送问题，属于分配组合问题，我们建立了单（多）目标规划模型，在各个运输限制因素的影响下，选择最优的运送路线，使得所有运送车辆的总行驶路程最小，为解决此问题我们建立了如下模型，计算出最优的运输路径。首先根据题目要求分析不难看出，问题二为问题一的实际情况的一般化表现，因此这里以对问题二的特殊说明来描述问题一的抽象概念。第一步：因为根据问题一所推得的结论可知，货车数越少路径越短，首先我们进行模型最理想化的假设-货车的载重量为无穷大，即得出最优路径为一辆车的最短运行路线，以不同客户之间的距离进行排序，得出最短的行进路程即可。第二步：然后考虑约束条件的限制，先进行考虑用户所需货物量的限制因素，若排列出货车的运行路径为1-2-3-4-5-6-，则进行m1+m2+m3+m4+m5是否小于等于货车最大载重量的判断，eg：m1+m2+m3+m4Q,m1+m2+m3X3，X1+X3X2，X2+X3X1；若A点为供应中心（称为出发地），且B，C两点为每一个顾客接受地（称为目的地）所需货物质量mb+mc0，故得在车辆能够满足顾客需求的情况下，车辆数N值越少其总行驶路程越少。情况二：A X1 B X2 C如图所示，若B点为供应中心（称为出发地），且A，C两点为每一个顾客接受地（称为目的地）所需货物质量mb+mcM,，在不考虑车辆有等待时间与延时受处罚的情况下，方案一：派遣一辆汽车沿B-C-A-B方向行进，所得路程之和为S1=2（X1+X2）。派遣两辆汽车分别沿B-C-B，B-A-B行进，所得总路程为S2=2（X1+X2）。此时S1=S2。故综上两种情况所述：在车辆行驶过程中路程S为理想情况（即为直线，亦称之为车辆不走弯路），且所需货物质量mb+mcb表示a-b的边的权值，d（i）即为最短路径）1.置集合S=1,2n数组d（0）=0，d（i）=wl-i(1,i之间存在边)2.在S中，令d(j)=mind(i),i属于S，令S=S-j，若S为空集则算法结束，否则转33.对于i属于S，如果存在边j-I,那么d(i)=mind(i),d(i)+wj-i,转2 Dijkstra算法思想为：设G=(V,E)是一个带权有向图，把图中顶点的集合V分成俩组，第一组为已求出最短路径的顶点的集合（用S表示，初始时S只有一个源点，以后每求得一条最短路径，就将顶点加入S中。再加入过程中，总保持从源点V到S中各顶点的最短路径长度不大于从源点V到U中任何顶点的最短路径长度。此外，每个顶点对应一个距离，S中的顶点的距离就是从V到此顶点的最短路径长度，U中的顶点的距离，是从V到此顶点只包括S中的顶点为中间顶点的当前最短路径长度。算法具体步骤(1)初始时，S只包括源点，即S=V的距离为0.V包含除V外的其他顶点，U中顶点U距离边上的权。(2)从U中选取一个距离V最小的顶点k，把k加入S中（该选定的距离就是V到k的最短路径的长度。）(3)以k为新考虑的中间点，修改U中各顶点的距离；若从源点V到顶点U（uU）的距离（经过顶点k）比原来距离（不经过顶点k）短，则修改顶点u的距离值，修改后距离值的顶点k的距离加上边上的权。(4)重复步骤（2）和（3）直到所有的点都包含在S中。【2】4.3问题一的解答从物流中心开出任一辆货车对物资进行调运，到任意的未配送点。要求每辆车的行驶速度为vkm/h，货车最大载重量为M，现在客户总需求量为M总，所以至少应为M总/M辆车去运输。为使总运费最小，则应使货车从每一个点客户到下一个客户的距离最短。现在假设一辆货车载重量无限，首先，使货车从中心到客户i的路径最短，再从i地运往j地的路径最短，以此类推，货车所走的路径是最短路径，则费用最低。 由此可知最短路径为0i1i2i3i S=S1km现在需要把这一辆理想货车拆分成Q辆去运输，沿着最短路径行驶，当第一辆车运完所装载物资后，即空载撤回，第二辆车接着向下一个客户运送物资，在经过最短路上相应客户运送完所载物资后，也空载撤回，如此类推，直至最后一辆货车送完全部货物。各车辆可按具体需求量装载货物（可以满载也可以非满载）比如，根据最短路径的连接站点，如果前3个站点需要总物资m吨（mM），这样的情况我们可以把第一辆车装载m吨货物，那么第一辆车运货到第三个站点恰好运完货物，此时它空载撤回，第二辆车通过计算下几个站点需要的具体物资去装载具体的物资量，进行运输，以此类推，直到最后一个站点运输完毕。由于i1,i2,i3,客户需要货物重量为m1t，所以派出x1货车满载货物去这三个客户地，由于i3,i4,i5客户需要货物重量为m2吨。所以再派x2货车运输，知道满足客户需求。 则他们的配送方案：车辆1车辆2车辆x路线0i1i2i30i4i5i60in-2in-1in货物重量（吨）m1m2mn 假设货车运载货物的单价为q元/吨千米。总费用为W元又因为送货车辆必须在一定的时间范围内到达客户处，早到将产生等待损失g元/小时，迟到达将给于一定的惩罚j元/小时路线一：0i1运输时间t=a01/v 卸货时间：s1 总时间T1 等待时间T1 迟到时间 T1 i1i2运输时间t=b12/v卸货时间：s2 总时间T2 等待时间T2 迟到时间T2 i2i3运输时间t=b23/v 卸货时间：s3 总时间T3等待时间 T3 迟到时间T3路线二：0i4运输时间t=a04/v 卸货时间：s4 总时间T4 等待时间 T4 迟到时间 T4 i4i5运输时间t=b45/v 卸货时间：s5 总时间T5 等待时间 T5 迟到时间 T5 i5i6 运输时间t=b56/v 卸货时间：s6 总时间T6 等待时间 T6 迟到时间 T6路线二：0in-2 运输时间t=a0(n-2)/v 卸货时间：sn-2 总时间Tn-2 等待时间TN-2 迟到时间 Tn-2 in-2in-1 运输时间t=b(n-2)(n-1)/v 卸货时间：sn-1 总时间Tn-1 等待时间 Tn-1 迟到时间Tn-2 in-1in 运输时间t=b(n-1)n/v 卸货时间：sn总时间Tn 等待时间Tn 迟到时间 TnW=M总*q*S1+g+j五、问题二的解答说明：问题二的解答也遵循问题一的假设与求解方法。从物流中心开出任一辆货车对物资进行调运，到任意的未配送点。要求每辆车的行驶速度为50km/h，货车最大载重量为8t，现在客户总需求量为22t，所以至少应为3辆车去运输。为使总运费最小，则应使货车从每一个点客户到下一个客户的距离最短。现在假设一辆货车载重量无限，首先，使货车从中心到客户i的路径最短，再从i地运往j地的路径最短，以此类推，货车所走的路径是最短路径，则费用最低。 由此可知最短路径为013567284 S=520km现在需要把这一辆理想货车拆分成n辆去运输，沿着最短路径行驶，当第一辆车运完所装载物资后，即空载撤回，第二辆车接着向下一个客户运送物资，在经过最短路上相应客户运送完所载物资后，也空载撤回，如此类推，直至最后一辆货车送完全部货物。各车辆可按具体需求量装载货物（可以满载也可以非满载）比如，根据最短路径的连接站点，如果前3个站点需要总物资m吨（m8），这样的情况我们可以把第一辆车装载m吨货物，那么第一辆车运货到第三个站点恰好运完货物，此时它空载撤回，第二辆车通过计算下几个站点需要的具体物资去装载具体的物资量，进行运输，以此类推，直到最后一个站点运输完毕。由于1,3,5,客户需要货物重量为8t，所以派出1辆货车满载货物去这三个客户地，由于6,7,2客户需要货物重量也为8吨。所以再派出一辆货车运输，由于8,4客户，所需货物总量为6t，所以派第3辆货车载6t运输。 则他们的配送方案：车辆1车辆2车辆3路线01350672084货物重量（吨）886 假设货车运载货物的单价为q元/吨千米。总费用为W元又因为送货车辆必须在一定的时间范围内到达客户处，早到将产生等待损失g元/小时，迟到达将给于一定的惩罚j元/小时路线一：01运输时间t=40/50=0.8h 卸货时间：s=1h 总时间T=1.8h 等待时间T=0h 13运输时间t=40/50=0.8h 卸货时间：s=1h 总时间T=1.8h 迟到时间T=0.6h 35 运输时间t=50/50=1h 卸货时间：s=2h 总时间T=3h 迟到时间T=0h路线二：06 运输时间t=100/50=2h 卸货时间：s=2.5h 总时间T=4.5h 迟到时间 T=0h 67 运输时间t=70/50=1.4h 卸货时间：s=3h 总时间T=4.4h 等待时间 T=0h 72 运输时间t=75/50=1.5h 卸货时间：s=2h 总时间T=3.5h 迟到时间 T=3.6h路线三：08 运输时间t=80/50=1.6h 卸货时间：s=0.8h 总时间T=2.4h 等待时间 T=0h 84 运输时间t=100/50=2h 卸货时间：s=3h 总时间T=5h 迟到时间T=0h W=520*22q+（0.6+3.6）j六、模型结果的分析与检验1.1.在研究物资调配问题是，我们忽略了交通，天气等客观因素，大大简化了最短路径的建立与求解。1.2.在第二问中，我们最终选择八辆车非满载的调配方案，并求解出了相对最低的运输费用。因为在问题中我们已经给出了每辆车要经过的具体路线以及需要的承载量，于是便可以按着具体的运输方案进行检验，经过多次求解调配，发现每次的误差并不大，这便一定程度说明此模型的稳定性与可行性；而在第二问中，我们通过同样的方法，结合利用matlab软件，计算检验。1.3.物流中心每天要运送的物资在早上出发之前已经全到了，没有到的当天就不运送这种模型现在已经很成熟，因此采用这种解法应该能够达到减少运费的要求。且总费用控制在了一个较为合理的范围内。但是由于物资调运是一个比较复杂的问题，涉及到众多变量，上述模型尚有许多因素没有考虑在内。【3】七、模型的推广目前，物流配送车辆优化调度在国外已广泛应用于生产和生活的各个方面，如报纸牛奶投递及线路优化，工业原料和成品的运输，电话或网络购物的车辆装配及线路设计，航运公司轮船经过港口和货物装卸的优化设计，连锁商店的送配货等等，并已取得了极大的经济效益，如美国沃尔玛特百货有限公司，其成为全球零售业霸主的首要因素时拥有了最先进的物流配送指挥系统，全球哥们店通过卫星实现联网，可以最大限度地降低其商品物流成本和增加销售量，从而在竞争中始终处于优势地位，在我国，随着国民经济健康稳步的高速发展，市场经济日益发达，各种生产经营方式发展的十分迅速，在生产活动中，提出了以零库存为目标的just2in2time模式；而各式连锁经营的便利店和直送业务的蓬勃发展，也使零售业物流配送呈现出多频度、小批次的特点，这些都对以运输为中心的物流配送活动提出了更高的要求，但就目前情况而言，我国的VRP研究仍然有限，可以说仍未能满足经济发展的需要，首先是起步较晚，通用理论研究较少；其次，对于具体问题提出的应用研究相对较多，但多为具体算法的部分改进，且限于各自的使用条件，局限性较强。【3】八、模型的评价与改进8.1.模型的优缺点分析8.1.1模型的优点1、花费最小路的思想。将总费用最小分解为任意两个需求点间费用最小，即若每一需求点到下一需求点的花费最小，则总花费最小。从而由通过计算每两个需求点间费用最小而得到总费用最小。避免了通过穷举法搜索。2、在研究物资调配问题时，我们忽略了交通，天气等客观因素，大大简化了最短路径的建立与求解。3、在最短路的总体思想下，综合考虑时间与运费等客观约束条件，使模型更贴近实际，同事使运输车的调配更合理清晰。8.1.2模型的缺点1、虽然我们运用模型求解时，完全根据题中所给出的约束条件，但是交通状况，车速变化等客观因素仍然对模型的紧缺度有较大影响。2、我们虽然通过“化零为整”，“人工优化”等措施最大程度上保证了运输车的最优调配，但是仍然不排除个别点间距离与花费的误差8.1.3模型评价：1.首先对于该题而言，假设的是每辆车仅出动一次，因此等待所产生的费用而言，本应该根据其实际产生的效果做以分析，如，两车同时运送货物物不同地点，其中一车因等待而延迟若干分钟，那么如果这两辆车相差等待时间长度返回物流中心，只是时间上的早晚问题，并且较早返回物流中心的车辆并没有在这段时间内再次运送货物为物流中心怎家效益，那么则等待时间在实际效果中并没有产生影响，所以等待损失为0，相反，如果相差时间较长，且较早返回的车辆可以在另一辆车所等待的时间内为该物流中心产生经济效益，那么由此才会产生等待损失。再者就数学模型本身而言，本应该忽略次要影响因素，而注重主要影响因素，避免为模型产生较为显著的影响，因此我们将模型假设为理想模型，从而假设其只要等待就会产生损失，而非根据其实际产生的作用效果分析，因此会造成认为方面的微笑误差，基本上可以忽略。2.在用数学运算工具matlab计算用户与物流中心距离及用户与用户之间的距离时，当在同一地点时若同时出现两个相距该地距离一致的点时，系统会自动选取第一个点作为最近点，从而对后续路径产生影响，因此不同的选择会产生不同的结果，从而对最短路径造成影响。3.最重要的是，该模型首先选取距离物流中心的最近的点，然后依次选取最近的点排列，然而有一点疑问，若第一次选取的点不为最近的点，而为次近的点，第二次选取的点有可能比第一次选取最优路径的点的距离小，由此可得最优路径未必就是每次选取最近的点的路径，由此可知模型依然存在可优化说明的方面，若能根据已知定理给予证明更好!附录一：S=0 40 60 75 90 200 100 160 80; 0 0 65 40 100 50 75 110 100;0 0 0 75 100 100 75 75 75;0 0 0 0 100 50 90 90 150; 0 0 0 0 0 100 75 75 100;0 0 0 0 0 0 70 90 75;0 0 0 0 0 0 0 70 100;0 0 0 0 0 0 0 0 100;0 0 0 0 0 0 0 0 0S = 0 40 60 75 90 200 100 160 80 0 0 65 40 100 50 75 110 100 0 0 0 75 100 100 75 75 75 0 0 0 0 100 50 90 90 150 0 0 0 0 0 100 75 75 100 0 0 0 0 0 0 70 90 75 0 0 0 0 0 0 0 70 100 0 0 0 0 0 0 0 0 100 0 0 0 0 0 0 0 0 0ans = Columns 1 through 7 0 0.8000 1.2000 1.5000 1.8000 4.0000 2.0000 0 0 1.3000 0.8000 2.0000 1.0000 1.5000 0 0 0 1.5000 2.0000 2.0000 1.5000 0 0 0 0 2.0000 1.0000 1.8000 0 0 0 0 0 2.0000 1.5000 0 0 0 0 0 0 1.40