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

货运公司的运输问题队伍名称Aurora队员冯洁黎宁褚燕摘要本文根据货运公司需要完成的运输量和确定的运输路线图，分别建立了线性规划模型和0-1规划模型，解决了车辆安排问题和调度问题，得出了运费最小的最优方案。问题一，由于派车费用固定，每次出车的出车成本费用也是固定的，为了减小运输成本，就要减少出车次数，但同时又要满足各公司对材料的需求，以公司需求为约束条件，以最小出车数为目标函数，建立一个线性规划模型，并用Lingo求解，得出了最少出车次数为27辆。然后，进一步考虑运输车调度问题，由于出车方向分为逆时针和顺时针两种情况，而且这两种情况是非此即彼的对立关系，故建立了一个0-1规划模型，0表示顺时针行驶，1表示逆时针行驶，采用Lingo求解，得出了运输车在运输途中不允许掉头的调度方案（见表一）。问题二中允许运输车掉头只会影响运输车卸货后空载的行驶路程，也即运输车的空载费用，故通过修改目标函数中的相关系数，仍然建立线性规划模型和0-1规划模型，采用Lingo求解，得出需要安排的运输车为3辆，运输途中允许掉头的调度方案见表二。问题三中增加了运输车的种类，并区分了运输车空载时的运费，由于运输车装载材料的方式有很多种，在上面分析的基础上，增加约束条件，得出一种新的线性规划模型，通过Lingo解得需要安排的车辆数为5辆，调度方案见表三。关键字：线性规划模型，0-1规划模型2问题重述某地区有8个公司（如图一编号①至⑧），某天某货运公司要派车将各公司所需的三种原材料A,B,C从某港口（编号⑨）分别运往各个公司。路线是唯一的双向道路（如图一）。货运公司现有一种载重6吨的运输车，派车有固定成本20元/辆，从港口出车有固定成本为10元/车次（车辆每出动一次为一车次）。每辆车平均需要用15分钟的时间装车，到每个公司卸车时间平均为10分钟，运输车平均速度为60公里／小时（不考虑塞车现象），每日工作不超过8小时。运输车载重运费1.8元/吨公里，运输车空载费用0.4元/公里。问题：1.货运公司派出运输车6辆，每辆车从港口出发（不定方向）后运输途中不允许掉头，应如何调度（每辆车的运载方案，运输成本）使得运费最小。2.每辆车在运输途中可随时掉头，若要使得成本最小，货运公司怎么安排车辆数？应如何调度？3.（1）如果有载重量为4吨、6吨、8吨三种运输车，载重运费都是1.8元/吨公里，空载费用分别为0.2，0.4，0.7元/公里，其他费用一样，又如何安排车辆数和调度方案？（2）当各个公司间都有或者部分有道路直接相通时，分析运输调度的难度所在，给出你的解决问题的想法（可结合实际情况深入分析）。（图一）唯一的运输路线图和里程数（图二）各个公司对每种材料的需求量（单位/天）公司编号各种材料的需求量（单位/天）ABC4151522043121240432255313模型假设1．假设每辆车装载时发挥其最大的装载能力；2．假设货运公司都是先考虑节省人力和出车次数最少的情况下再考虑如何安排运输方式以减少经费支出；3．假设运输车行驶过程中不考虑塞车抛锚现象，以保证每辆车每天可以达到最大的作业时间。4符号说明C1一单位A材料和二单位C材料的装载方式；C2二单位B材料的装载方式；C3六单位C材料的装载方式；C4一单位B材料和三单位C材料的装载方式；Pij被调用车的运输经费；Sij所运载的区间的路程；Sji表示空载路程；Xij第i辆列车的调度情况；Xi0=1表示第i辆车采用顺时针运输；Xi0=0表示第i辆车不采用顺时针运输；Xi1=1表示第i辆车采用逆时针运输；Xi1=0表示第i辆车不采用顺时针运输；t0装载时间；t1路途行程时间；t2卸载时间；Gni（n=1—8，i=1，2，3）表示第n个公司分别对A，B，C产品的需求量；5问题分析对于这个货运公司的运输问题，问题一中给出了6辆可以使用的运输车，根据各公司对材料的需求，这6辆车必然会被反复的调用。要减少运输经费，首先要减少出车的次数，但是究竟要出车几次才可以满足公司对材料的需求呢？由于每辆车只能装载6吨的货物，我们考虑每次尽可能让车辆装满6吨货物，且可以在一个公司一次性卸下，6吨车全部装满原材料的方案有：6个C，2个B，1个A2个C，1个B3个C四种，这样再根据八个公司对A，B，C三种材料总的需求量就可以建立一个线性规划模型求出出车的最少次数S。在满足最少出车次数S的前提下，还要考虑运输车的调度问题，出车方向不定，分为逆时针和顺时针两种情况，而且这两种情况是非此即彼的对立关系，这属于0-1规划问题，解决的方法是令Xi0等于1表示采用第i辆车次按顺时针来运行，Xi0等于0表示不采用第i辆车次顺时针运行。Xi1等于1表示采用第i辆车次逆时针运行，等于0表示不采用这辆车次逆时针运行，再结合题目中的其他相关数据便可以建立一个0-1规划模型求解。问题二中的解决方法和第一问中的解决方法是一样的，不过由于这时候运输车可以掉头，故可以减少由于运输车在途中空载的路程，而这只会影响模型中目标函数的中的价值系数的改变，其他和第一问的求解方法是一致的。在第三问中给出了三种有不同装载力的运输车。我们可颠覆问题一中的思路，直接判定出港口至某公司的最短路径。然后将该公司所需所有材料装在一批车上，沿最短路径运抵该公司。卸下所有材料，然后原路返回。一对于这三种不同的运输车可以得出很多不同的装载方式，比如对于装载量为8吨的运输车，可以为每次装载2个A或者1个A和B等。根据每个公司对A，B，C不同材料的要求，我们再建立一个线性模型，使得这八个公司可以从这些不同的运输方式中选择最为合适的运输方式的组合以满足要求，然后对这些公司所选择的不同的运输方式再根据题目中每辆车每天最大的作业时间，可以确定出在保证完成任务的情形下，所需要不同类型运输车的最少数目这样就可以减少指派运输车的支出。再结合前面的不同运输方式的组合，就可以安排出车辆数和调度方案了。6模型的建立与求解6.1问题一的求解`首先求解出满足每个公司的需求的最少出车次数，再在此情形下考虑如何调度这些车次，使得整个运输作业所需的经费最少。模型的建立与求解根据题目中给定的各个公司对A，B，C三种不同的材料的需求，可以计算出这些公司每天所需A，B，C三种材料的总数分别为18单位，18单位，26单位，由于每辆车的载重都是6吨，在假设一的前提下我们可以得出每辆车的装载方式有如下四种方式：（a）1A+2C，（b）2B，（c）6C，（d）B+3C。我们分别设这四种方式需要调度的次数为C1，C2，C3，C4这样我们就可以建立如下数学模型：MINS=C1+C2+C3+C4C1〉=182C2+C4〉=182C1+6C3+3C4〉=26C1~~C4为正整数；用LINGO进行求解可以得到S=27，C1=18，C2=9，C3=0，C4=0；对于这个结果可以进一步分析可知，公司并不需要那么多C材料（这也正是（c）,(d)运输方式被排除在外的原因）。故只需要（a）的运输方式为13个再加上单独运输A材料的5车次和9车次（b）运输方式即可满足条件，但是这未必是最好的安排，因为通过观察知在运输方式（a）与单独运输A的方式之间，还可能存在运输A+C这种方式。故将次方案考虑在内。图三如图三，按顺时针方式对每个公司进行综合的考虑可以得到A+2C方式12种，A+C方式2种，单独运输A方式4种，2B方式9种，可以较好的满足题设条件。各种运输方式表示调用顺序表示符号A+2C方式A+C方式A方式2B方式顺时针调用Xi0（i=1~27）i=1~12i=13~14i=15~18i=19~27逆时针调用Xi1（i=1~27）i=7~18i=5~6i=1~4i=19~27，由于不考虑掉头，故可以得到其运输所需要的经费为Pij=∑（1.8w*Sij+0.4*sji）（i=1~27，j=0或1），其中w为运输车的载重，Sij为所运载的区间的路程，Sji则表示空车回到港口的距离，总费用为：P=∑Pij+S*10+20*K，其中K为所调用的车辆的个数；其中Pij的计算所得的结果参看表（1），设Xij（其中i=1~27，j=0或1）为第i辆列车的调度情况：其中Xi0=1表示第i辆车次采用顺时针运行，Xi0=0则表示不采用第i辆车次顺时针运输，Xi1=1则表示第i辆车采用逆时针运输，Xi1=0表示第i辆车不采用顺时针运输。由上可以对这个问题建立一个0-1规划模型：Min∑Pij*XijS.T∑Xij〉=27现考虑约束条件列出各公司材料所有可能的运输车次，得下表：公司A的满足B的满足C的满足顺时针逆时针顺时针逆时针顺时针逆时针11020130150161171181611902711020130171181612301511902002102512612713016134050131141405014115146016017010111112122024160131570912202302312417080111121623024025021122123190110911017809071812502602012111001101207181918100110120140180112131415126027019120114051以公司一为例，可得如下约束条件（即正向运输与逆向行驶仍选其一）。x10+x181=1;x20+x171=1;x130+x61=1;x150+x151=1; 以公司二为例，可得如下约束条件（即若有多次相同运载方案，则尽可能同向）x30+x161=1;x141-x151=0;x40+x141=1;x50-x40=0;……….（其他公司的处理方法一样）Xij=0或1结论：对上0-1模型，代入附表中的数据，用Lingo求解可得∑Pij=5227.2，又由于S=27，K=6，所以总费用为P=5617.2（元），其中所调用的车次以及每个车次的所花的经费参见表（3），对于所得的结果，由于车的速度为60公里/时，那么每辆车运行一周回到港口刚好需要1小时，而现在需要共需要转27圈，又每辆车的每天的工作时间是8小时，所以这6辆车一天的能力是运转48圈，所以即使再考虑装载时间和卸货时间所得结果也是合理的。本题求解时，通过线性规划，求出最少出车次数。但其实为了减少费用，可以单独枚举，即根据每个公司的需求，先将装满6吨货物且一次性卸载的情况排除后，针对每个公司剩余需求量进行组合，但是我们没有进行该项复杂的工作。6.2问题二的求解问题二中的车辆可以掉头，但是这只会影响每辆车在运行过程中空车运行回港口的路费，所以求解的模型和第一问中的模型是一样的，只不过这时候的Pij已经有所变化，这时候的Pij的求解是这样计算的：如果Sji>Sij，则掉头，否则继续前进，其他的计算方式则和第一问中的一样，具体的计算结果参见表（4）；结论：仍然使用Lingo进行求解，可以得到这时候的∑Pij=4615.2，这时候S仍为27，而K的确定是这样的：把所有车次的时间按时间公式∑（t0+t1+t2），求出总的时间为：1711分钟。每一辆车的最大工作时间为：60*8=480分钟，粗略计算，需车数：1711/480≈4辆，综合考虑装载和卸货时间用的时间，这个值也是合理的。那么这时的总费用P=4965.2（元）该道题跟第一问不同之处在于，当某一辆车上的原材料全部卸下之后，将它的已经走过的路程与剩余路程进行比较，如果是已走的较短，则返程，否则走一圈回到港口。6．3问题三的求解以尽可能装满车为原则，4，6，8吨三种车型有以下装法，并编好序。每辆车尽可能一次性卸完分析出每个公司所需车次。4吨（车型）6吨8吨Y1=B+CY4=2BY8=2AY2=AY5=A+2CY9=A+4CY3=4CX6=6CX10=A+B+CY7=B+3CY11=8CY15=B+CY12=2B+2CY16=B+2CY13=B+5CY14=B+AY17=B+4C对于每个公司的需求我们都是考虑尽可能用上面给出的不同的装载方式来满足，可建立模型如下：Min∑YiSTY2+Y5+2Y8+Y9+Y14=Gn1Y1+2Y4+Y7+Y15+Y16+Y11+2Y12+Y13+Y14+Y17=Gn24Y3+2Y5+3Y7+Y15+2Y16+4Y9+8Y11+2Y12+5Y13+4Y17=Gn3Yi是正整数其中Gni（n=1—8，i=1，2，3）表示第n个公司分别对A，B，C产品的需求量。代入用Lingo求解可以得出下表公司（需求）1．（4，1，5）2．（1，5，2）3．（2，0，4）4．（3，1，2）5．（1，2，4）6．（0，4，3）7．（2，2，5）8．（5，3，1）车次2Y8+X13Y4+Y14+Y122Y5Y2+Y5+Y14Y4+Y9Y4+Y15+Y16Y9+Y14+Y15Y8+Y10+2Y14现对上表分析，车辆数：考虑到增加车辆有20元的增加费用，车辆越少越好。但必须在规定时间内（8小时），完成一定车次的任务。按时间计算公式:Σ（t0+t1+t2）(t0—装载时间，t1—路途行程时间，t2—卸载时间)求出三种车所用时间分别为：4吨：83分钟6吨：567分钟8吨：621分钟一辆车的最大工作时间为：8*60=480（分钟）。易知所需车数为：1+2+2=5（辆）按运费计算公式:求出完成一天任务的总运费为：4694.6元。考虑到，4吨车只用了一次，可加开一次6吨车代替，以减少费用。事实证明6吨车加开一次时间是完全允许的，可节约费用：20-（0．4-0.2）*24=15.2（元）。那么车辆数变为：4辆;费用：4679.4元。这里我们的想法是，因为8吨的车空载费用比4吨和6吨之和要多，且4吨和6吨之和载重大于8吨，因此，如果减少八吨的车的使用辆数，可能节省的载重费用会少于增加派车辆数的派车费用。但是，这个单独实现起来比较麻烦，需要用到编程软件，因为对编程软件的使用了解不多，没有编程成功。7．参考文献[1]徐玖平，胡知能，王委，运筹学，科学出版社，2004[2]姜启源，数学模型，高等教育出版社，2003[3]谢金星，薛毅，优化建模与LINDO/LINGO软件，2005[4]货运公司的运输问题朱远鹏贾利攀李雯附录附表一经费车次iPij011107.2582107.2583180584273.6585273.6676325.6471.27408.8138.48490.4138.49519.2227.210567.2288.811574.4317.612574.4317.61392.8380.414596398.41578.4459.616221.2539.617221.2564.818398564.819142．2762010618021138．418022180365．623220448．824303．24922549251226492563．627271596附表二经费车次iPij011107.2582107.2583180584585676471.27138.48138.49227.210288.811317.612317.61392．8380.414398.415459.616539.61718197620106180211802223448．824252627附表四经费车次iPij01189．638289．6383168384268．8385268．8476324．8471.27408．8123．28476123．29519．2221.610567．2288.811574.4317.612574.4317.61375．2380.414596398.41560．8459.616220.4539.617220．4564.818398564.81948．6562016890．821168146．422365．616823448．8214．424492303．22551249226563．649227596527附表五经费车次iPij01189．638289．6383168384385476471.27123．28123．29221.610288.811317.612317.61375．2380.414398.415459.616539.617181948．6562016890．821168146．42216823214．424303．2252627LINGO代码一Model:min=107.2*x10+107.2*x20+180*x30+273.6*x40+273.6*x50+325.6*x60+408.8*x70+490.4*x80+519.2*x90+567.2*x100+574.4*x110+574.4*x120+92.8*x130+596*x140+78.4*x150+221.2*x160+221.2*x170+398*x180+58*x11+58*x21+58*x31+58*x41+67*x51+471.2*x61+138.4*x71+138.4*x81+227.2*x91+288.8*x101+317.6*x111+317.6*x121+380.4*x131+398.4*x141+459.6*x151+539.6*x161+564.8*x171+564.8*x181+76*x190+142.2*x191+106*x200+180*x201+158.4*x210+180*x211+180*x220+365.6*x221+220*x230+448.8*x231+303.2*x240+492*x241+492*x250+512*x251+492*x260+563.6*x261+527*x270+596*x271;x10+x20+x30+x40+x50+x60+x70+x80+x90+x100+x110+x120+x130+x140+x150+x160+x170+x180+x11+x21+x31+x41+x51+x61+x71+x81+x91+x101+x111+x121+x131+x141+x151+x161+x171+x181+x190+x191+x200+x201+x210+x211+x220+x221+x231+x231+x240+x241+x250+x251+x260+x261+x270+x271>=27;x10+x181=1;x20+x171=1;x130+x61=1;x150+x151=1;x30+x161=1;x141-x151=0;x40+x141=1;x50-x40=0;x131-x141=0;x101-x131=0;x111-x131=0;x121-x131=0;x60+x131=1;x101-x131=0;x111-x131=0;x121-x131=0;x60-x160=0;x60-x170=0;x70+x91=1;x70-x80=0;x91-x111=0;x91-x121=0;x101-x91=0;x90+x81=1;x90-x110=0;x100-x110=0;x120-x110=0;x71-x91=0;x81-x91=0;x80-x90=0;x140+x11=1;x100-x140=0;x110-x140=0;x120-x140=0;x180-x140=0;x11-x51=0;x21-x51=0;x31-x51=0;x140+x51=1;x41-x51=0;x21-x51=0;x31-x51=0;x41-x51=0;x190+x271=1;x200+x261=1;x210+x251=1;x220+x241=1;x230+x231=1;x240+x221=1;x250+x211=1;x260+x201=1;x270+x191=1;@BIN(x10);@BIN(X11);@BIN(X20);@BIN(X21);@BIN(X30);@BIN(X31);@BIN(X40);@BIN(X41);@BIN(X50);@BIN(X51);@BIN(X60);@BIN(X61);@BIN(X70);@BIN(X71);@BIN(X80);@BIN(X81);@BIN(X90);@BIN(X91);@BIN(x100);@BIN(X101);@BIN(X110);@BIN(X111);@BIN(X120);@BIN(X121);@BIN(X130);@BIN(X131);@BIN(X140);@BIN(X141);@BIN(X150);@BIN(X151);@BIN(X160);@BIN(X161);@BIN(X170);@BIN(X171);@BIN(X180);@BIN(X181);@BIN(x190);@BIN(X191);@BIN(X200);@BIN(X201);@BIN(X210);@BIN(X211);@BIN(X220);@BIN(X221);@BIN(X230);@BIN(X231);@BIN(X240);@BIN(X241);@BIN(X250);@BIN(X251);@BIN(X260);@BIN(X261);@BIN(X270);@BIN(X271);endLINGO代码二Model:min=89.6*x10+89.6*x20+168*x30+268.8*x40+268.8*x50+324.8*x60+408.8*x70+476*x80+519.2*x90+567.2*x100+574.4*x110+574.4*x120+75.2*x130+596*x140+60.8*x150+220.4*x160+220.4*x170+398*x180+38*x11+38*x21+38*x31+38*x41+47*x51+471.2*x61+123.2*x71+123.2*x81+221.6*x91+288.8*x101+317.6*x111+317.6*x121+380.4*x131+398.4*x141+459.6*x151+539.6*x161+564.8*x171+564.8*x181+48.6*x190+56*x191+168*x200+90.8*x201+168*x210+146.4*x211+365.6*x220+168*x221+448.8*x230+214.4*x231+492*x240+303.2*x241+512*x250+492*x251+563.6*x260+492*x261+596*x270+527*x271;x10+x20+x30+x40+x50+x60+x70+x80+x90+x100+x110+x120+x130+x140+x150+x160+x170+x180+x11+x21+x31+x41+x51+x61+x71+x81+x91+x101+x111+x121+x131+x141+x151+x161+x171+x181+x190+x191+x200+x201+x210+x211+x220+x221+x231+x231+x240+x241+x250+x251+x260+x261+x270+x271>=27;x10+x181=1;x20+x171=1;x130+x61=1;x150+x151=1