中南大学 数学建模 lingo matlab 优化建模论文 货运公司的运输问题

货运公司的运输问题摘要本文根据货物种类，各公司的货物需求以及运输路线，建立线性规划数学模型，并运用图上作业法优化，提出了运输费用最低的运输方案。首先，用lingo11.0计算最少发车次数。减少发车次数，尽量保证每趟车满载，能够有效利用资源，减少运输费用。然后，运用图上作业法，寻找最优运输路线。分析观察港口到各公司的距离，确定两条最优运输路线：，。最后，根据“先卸小件”的题目要求，设计调运方案表，确定最终最优运输方案。如果“次数最少”和“路线最优”的方案无法满足“先卸小件”这一条件，则优先考虑加运载次数来达到要求。通过建模求解，得到以下结果：1.若货运公司派出运输车6辆，每辆车从港口出发（不定方向）后运输途中不允许掉头，按照最优路线满载运输28次，得最小运输成本为4864元；2.每辆车在运输途中可随时掉头，若要使得成本最小，货运公司需要安排4辆车，并按照最优路线，满载运行约8小时，成本为4487.2元。3.如果有载重量为4吨、6吨、8吨三种运输车，载重运费都是1.8元/吨公里，空载费用分别为0.2，0.4，0.7元/公里，其他费用一样，需要安排3辆8吨货车，运输成本为4435.5元。本文运用线性规划方法寻找最少发车次数，并运用图上作业法寻找最优行车路线，对问题进行了2次优化，使得所建模型更加接近实际问题，所得的解具有很高的实际参考价值；不足之处在于本文费用计算较为繁琐，公司数量如果过多，数据量会很大，处理起来不方便，不适合广泛推广一、问题重述某地区有8个公司（如图一编号①至⑧），某天某货运公司要派车将各公司所需的三种原材料A,B,C从某港口（编号⑨）分别运往各个公司。路线是唯一的双向道路（如图一）。货运公司现有一种载重6吨的运输车，派车有固定成本20元/辆，从港口出车有固定成本为10元/车次（车辆每出动一次为一车次）。每辆车平均需要用15分钟的时间装车，到每个公司卸车时间平均为10分钟，运输车平均速度为60公里／小时（不考虑塞车现象），每日工作不超过8小时。运输车载重运费1.8元/吨公里，运输车空载费用0.4元/公里。一个单位的原材料A,B,C分别毛重4吨、3吨、1吨，原材料不能拆分，为了安全，大小件同车时必须小件在上，大件在下。卸货时必须先卸小件，而且不允许卸下来的材料再装上车，另外必须要满足各公司当天的需求量（见图二）。问题：1.货运公司派出运输车6辆，每辆车从港口出发（不定方向）后运输途中不允许掉头，应如何调度（每辆车的运载方案，运输成本）使得运费最小。2.每辆车在运输途中可随时掉头，若要使得成本最小，货运公司怎么安排车辆数？应如何调度？3.（1）如果有载重量为4吨、6吨、8吨三种运输车，载重运费都是1.8元/吨公里，空载费用分别为0.2，0.4，0.7元/公里，其他费用一样，又如何安排车辆数和调度方案？（2）当各个公司间都有或者部分有道路直接相通时，分析运输调度的难度所在，给出你的解决问题的想法（可结合实际情况深入分析）。（图一）唯一的运输路线图和里程数（图二）各个公司对每种材料的需求量（单位/天）公司编号各种材料的需求量（单位/天）ABC①415②152③204④312⑤124⑥043⑦225⑧531二、问题假设1.假设货物运输过程中不会发生抛锚、塞车等意外情况，保证工作时间仅仅花在货物运输及装卸上；2.假设货物的调配仅由港口调配，各公司对货物的先后到达没有特别要求；三、符号说明X1：A+2C（一单位A加两单位C的运载方式，以下各项同理）；X2：2B；X3：6C；X4：B+3C；Y1：A；Y2：B+C；Y3：4C；Y4：A+2C；Y5：B+3C；Y6：2B；Y7：6C；Y8：2A；Y9：A+B+C；Y10：A+4C；Y11：2B+2C；Y12：8C；M：运输成本；四、问题分析本题是一个货物运输问题。根据题意，我们需要在满足各公司需求，保证工作时间不超过8小时的情况下，寻找最佳的运输方案，尽可能降低运输成本。首先，考虑减少运输的次数。减少运输次数，能够减少车行驶的路程，降低成本。因此，优先考虑每辆车满载在满载的情况下运输，运用lingo11.0，求解最少的运输次数。接着，运用图上作业法（见附录1），判别最佳的运输线路。从⑨顺时针到④共29公里，从⑨逆时针到⑤共23公里，两者路程都小于总路程的一半30公里且行车路线无对流为单向。由图上作业法得，规定车不跨过④或者⑤进行负载运输为最优运输方案。最后，根据题目中“先卸小件”的条件对方案进行调整。如果“次数最少”和“路线最优”的方案无法满足“先卸小件”这一条件，则优先考虑加运载次数来达到模型要求（证明见附录2）。对于“每辆车在运输过程中可随时掉头”的情况，依旧遵循上述的分析步骤。“掉头”的意义在于减少空载行驶的路程以及减少车辆运输的时间。如果负载掉头，会为货物的运输附加额外的路程，增加运输费用，故空载“掉头”才有意义。五、模型的建立与求解问题一：首先考虑计算最少的运输次数。在满载情况下，共有以下四种运输方式：X1：A+2C（一单位A加两单位C的运载方式，以下各项同理）；X2：2B；X3：6C；X4：B+3C；建立求解最少次数的数学模型：MINX1+X2+X3+X4STX1>=182X2+X4>=182X1+6X3+3X4>=26End用lingo11.0求解（见附录3），解得，X1=18，X2=9，X3=X4=0，最小发车次数为27。然后，使用图上作业法，画出路线图并设计合理的调运方案。结合题目“先卸小件”的实际条件，27次运输无法满足，故将一次X2：2B拆成运2次B材料，运输次数修正为28次。优化后的最终运输方案如下表：顺时针调运方案装载方式卸货方式A+2C①*2，②，③*2，④A+C①A①，④*22B①，②*3逆时针调运方案装载方式卸货方式A+2C⑤,⑦*2A+C⑧A⑧*42B④,⑥*2,⑦,⑧*2B+3C⑤*3,⑥*2,⑦根据调运方案，计算运输费用（详见附录4）。结合发车次数、车辆数、出车费用，最终计算得到运输成本M=4864元。此批货物共需运输28次，共有6把车。每次运输至多停止卸货2次。假设每趟车都停止卸货2次，平均每辆车工作6.758小时，满足题意。问题二：在货车运输过程中“允许调头”的情况下，会出现以下几种情况影响运输成本：1.通过掉头，选择最短的返回路径，节省了空载运费的支出；2.通过掉头，选择最短的返回路径，节省了运输时间；3.货车载重调头可以解决大小货物的卸货顺序问题，减少出车总次数，但增加了货物的运输距离，导致载重费用的增加。针对情况3，使用图上作业法进行最优判别，发现货车载重折返，相比增加出车次数会带来更高的成本，不可取。由上述分析，得出问题二的解题思路与调运方案与问题一相同；“允许掉头”只是能让空载的车及时折返，节省了空载费以及运输时间。使用问题一的调运方案。得到结果如下（附录5）：空载费为167.2元完成所有运输任务的总时间为26.47h则需要安排的车辆数应是4则完成运输任务的总费用应为：4487.2元问题三：假设车辆允许掉头：仿照问题一的解决思路，首先计算最少的发车次数。在满载的条件下，共有以下12种运输方式：4吨6吨8吨Y1AY4A+2CY82AY2B+CY5B+3CY9A+B+CY34CY62BY10A+4CY76CY112B+2CY128C建立求最少运输次数的数学模型：MINY1+Y2+Y3+Y4+Y5+Y6+Y7+Y8+Y9+Y10+Y11STY1+Y4+2Y8+Y9+Y10>=18Y2+Y5+2Y6+Y9+2Y11>=18Y2+4Y3+2Y4+3Y5+6Y7+Y9+4Y10+2Y11+8Y12>=26END使用lingo11.0，求解（详见附录6）得到最少的发车次数为19次，其中Y8：2A需9次，Y11：2B+2C需9次，Y12：8C需要1次。使用图上作业法，画出路线图并设计合理的调运方案。结合题目“先卸小件”的实际条件，将2个Y11改运为B+C和B+5C，Y12改为Y7。具体调运方案如下表：顺时针调运方案装载方式卸货方式2A①*2，③，④，①+④2B+2C(①+②)*3B+5C②+③+④逆时针调运方案装载方式卸货方式2A⑧+⑤,⑦,⑧*22B+2C⑦,(⑦+⑥)*2,⑤B+C⑧6C⑦+⑤+④根据调运方案，用一辆8t的货车完成所有任务所需时间约为20小时（小于24小时），故至少应派3辆车来完成此任务，于是这3辆车还有继续工作4小时的能力。如按照原计划，调用6t和4t的货车，虽然节省了空载费用，但比继续使用原来的3辆8t的货车增加的用车费。经过计算（见附录7），继续派用8t的货车去完成运输任务更优。则将方案调整为全部使用8t的货车。根据图上作业法的最优调度方案，计算运输总费用为4435.5元六、参考文献[1]陈汝栋，于延荣，数学模型与数学建模，国防工业出版社，2006[2]姜启源，数学模型，高等教育出版社，2003附录1.图上作业法假设：调度时，不能安排货物跨④运输。证明：根据图上作业法的最优判别准则“2，图中的每一圈中满足s1＜1/2s且s0＜1/2s(记圈的总长为s，s0，s1分别表示顺时针，逆时针的流量。)”.由此，结合本模型分析可得，调度时货车不能跑④⑤之间的路线。但考虑到，当④所需货物正好可由⑤顺便带过去的情况下，到底是跑④⑤之间的路线运输还是重新安排发车的问题。下面给予证明：因为卸货的先后顺序决定了跨⑤运输顺带给④的货物，必定是A或B,由于A重于B，如果A能跨线运输则B必能跨线运输。现探讨A跨线运输与重新安排发车的运费问题。A跨过⑤给④顺带货物，导致④所需货物增加了31－29=2m从而导致增加的载重费用为2*1.8=3.6元而重新安排发车，所增加的发车费为10元以及重新发车必定增加了空载路程，即另又增加了额外的空载费。故，重新安排发车不可取。综上述，安排调度时，遵循图上作业法德最优判别准则，不跑④⑤之间的线路运输，当且仅当不跨线运输就必须要增加发车次数时，选择跨线运输。即假设成立。证毕。并在此结论的指导下完成图上作业法的安排运输计划。并进行调整，优化，最终得到最优调度方案。2.假设：调度时，货车载重返回会造成更高的成本。证明：倘若货车载重返回，必定是载A或B，由于A重于B，如果能证明调度时，不能载B返回，则假设成立。分析实际调度情况，要载B返回，目的是到较远站先卸下C.这个目的也能通过增加发车次数来达到，即发两次车分别向两个目的地运送货物B,C。现在只要证明增加发车次数比载B返回来达到同样的目的更省钱即可。令货车载重返回所增加的载重距离为2m则载B返回增加的运费为1.8*3*2mm又增加一次发车所增加的的出港费为10m增加一次发车所增加的空载距离为m+n增加的空载费用为0.4*（m+n）本模型中，取m=4时，有l10+0.4*（m+n）—1.8*3*2m=11.6+0.4n-43.2=0.4n-31.6l令0.4n-31.6》01则有n》79而n的取值不可能满足n》79易知，当m的取值增大时，满足不等式1的n值随之增大。而本模型中的m值均大于4，则不等式1始终成立。即，增加一次发车所增加的费用必定比载重返回所增加的载重费要少。故，假设成立。证毕。3.问题一求解：MINX1+X2+X3+X4STX1>=182X2+X4>=182X1+6X3+3X4>=26EndGlobaloptimalsolutionfound.Objectivevalue:27.00000Infeasibilities:0.000000Totalsolveriterations:0VariableValueReducedCostX118.000000.000000X29.0000000.000000X30.0000001.000000X40.0000000.5000000RowSlackorSurplusDualPrice127.00000-1.00000020.000000-1.00000030.000000-0.5000000410.000000.0000004.方案1计算：总的卸货次数为33次，卸货时间装车次数为28，装货时间运行时间所需总时间平均每辆车的运行时间载重的总路程：S货车卸空处的公司编号；：港口到号公司的调运距离；：货车在公司处的卸空次数由不能调头可知空载费用元：公司编号，取值1,2…8;:各公司所需A,B,C货物的总重量；:港口到号公司的调运距离；载重费用元；出港口费用：元派车费用：元总费用：元5.问题二：方案2计算：总得卸货时间：总得装车时间：计算空载路程：考虑到党货车没到达=4\*GB3④点的时候，按原路程返回路程会比跨过=4\*GB3④点返回要短，所以确定此种情况货车按原路返回。当货车到达=4\*GB3④点的时候，都使货车按路线=4\*GB3④=3\*GB3③=2\*GB3②=1\*GB3①=9\*GB3⑨返回。所以参照方案1的计算可知又由于调运方案不变，所以载重路程不变，即货车运行时间所需总时间假设派出的车辆都满天工作（即每天工作8h），则需要派出的车辆n最少为，取，即只需要配出4辆车就能满足调运工作要求。计算费用：=1\*GB2⑴空载费用：=2\*GB2⑵载重费用：=3\*GB2⑶出港口费用：=4\*GB2⑷派车费用：总费用：6.问题三求解：MINY1+Y2+Y3+Y4+Y5+Y6+Y7+Y8+Y9+Y10+Y11STY1+Y4+2Y8+Y9+Y10>=18Y2+Y5+2Y6+Y9+2Y11>=18Y2+4Y3+2Y4+3Y5+6Y7+Y9+4Y10+2Y11+8Y12>=26ENDGlobaloptimalsolutionfound.Objectivevalue:18.00000Infeasibilities:0.000000Totalsolveriterations:0VariableValueReducedCostY10.0000000.5000000Y20.0000000.5000000Y30.0000001.000000Y40.0000000.5000000Y50.0000000.5000000Y60.0000000.000000Y70.0000001.000000Y89.0000000.0000