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

货运公司的运输问题108队：刘汉云、秦思谋、周彪摘要本文根据货运公司确定的运输路线图和需要完成的运输量，建立了线性规划模型，采用枚举方法，解决了在运费最小的前提下货运公司的车辆调度问题。首先建立线性规划模型。货运公司运费来自两方面的费用：派车与出车的固定成本、载重与空载行程产生的运费。由于派车成本固定，载重行程和空载行程相互联系，故独立的变量为出车次数和载重行程。以最小化运费为目标函数，以第j辆车第k次出车到i公司运载A材料的数量为决策变量，以各公司的材料需求、大小材料的卸货顺序、车辆使用时间等为约束条件，建立线性规划模型。为方便计算，建立运输车与各公司之间的关系矩阵(PN)，行对应公司编号，列分别表示A、B、C各公司对相应各种材料的需求量，港口到各公司顺时针行驶路程数，港口到各公司逆时针行驶路程数。采用枚举法求解，求得共出车28次，总运费为5264.8元。对于问题二，在问题一的基础上考虑每辆车在运输途中可随时掉头的情况，修改空载行程变量和车辆使用时间变量，。问题三中增加了运输车的种类，并区分了运输车空载时的运费，由于运输车装载材料的方式有很多种，在上面分析的基础上，增加约束条件，得出一种新的线性规划模型，通过Lingo7.0解得三种车型的调配数量，以及将材料运到每个公司所需的车次安排范围，最后再根据每辆车的工作时间的约束条件，利用穷举法，从安排车次数量最小的情况开始穷举，逐渐找到了满足约束条件，且所需安排的车次数最优的情况，即得到了问题三的最优结果。最后对模型进行了评价和推广，本文对建立的线性规划模型采用枚举算法进行求解，没有进行编程求解，在一定程度上具有误差。可通过放松约束条件，编写程序进行求解，逐步加紧约束，进行优化，逐步接近实际情况。关键词：线性规划货运公司枚举法

一、问题的重述与分析1、问题的重述某地区有8个公司（如图一编号①至⑧），某天某货运公司要派车将各公司所需的三种原材料A,B,C从某港口（编号⑨）分别运往各个公司。路线是唯一的双向道路（如图1）。货运公司现有一种载重6吨的运输车，派车有固定成本20元/辆，从港口出车有固定成本为10元/车次（车辆每出动一次为一车次）。每辆车平均需要用15分钟的时间装车，到每个公司卸车时间平均为10分钟，运输车平均速度为60公里／小时（不考虑塞车现象），每日工作不超过8小时。运输车载重运费1.8元/吨公里，运输车空载费用0.4元/公里。一个单位的原材料A,B,C分别毛重4吨、3吨、1吨，原材料不能拆分，为了安全，大小件同车时必须小件在上，大件在下。卸货时必须先卸小件，而且不允许卸下来的材料再装上车，另外必须要满足各公司当天的需求量（见表1）。2、待解决的问题问题一：货运公司派出运输车6辆，每辆车从港口出发（不定方向）后运输途中不允许掉头，应如何调度（每辆车的运载方案，运输成本）使得运费最小。问题二：每辆车在运输途中可随时掉头，若要使得成本最小，货运公司怎么安排车辆数？应如何调度？问题三：如果有载重量为4吨、6吨、8吨三种运输车，载重运费都是1.8元/吨公里，空载费用分别为0.2，0.4，0.7元/公里，其他费用一样，又如何安排车辆数和调度方案？3、问题分析问题一中的运费来自两方面的费用：派车与出车的固定成本、载重运费与空载运费。派车数由是确定的，由公司派出6辆进行运输；减少出车次数能减少运费。运输途中不能掉头，每辆车每次必须行车60公里，由载重运费与空载运费知减少载重行车距离能有效减少运费。所以最小化运费可从三个方面进行：减少出车次数，减少载重行车距离，增加空载距离。其中独立变量为出车次数和载重行车距离。以最小化运费为目标函数，以第j辆车第k次出车到i公司运载A材料的数量为决策变量，以各公司的材料需求、大小材料的卸货顺序、车辆使用时间等为约束条件，建立线性规划模型。考虑数据简单，计算过程简单，而材料配载过程复杂，故采用枚举法。问题二中在问题一的基础上增加了运输途中可以掉头的条件。仍采用枚举的方法对问题进行解答。问题三中在问题一、二的基础上增加了运输车种类：载重量分别为4吨、6吨、8吨；载重运费都是1.8元/吨公里，空载费用分别为0.2，0.4，0.7元/公里，其他费用一样。根据问题一、二的解答方式，以尽可能装满车，每辆车尽可能一次性卸载完为原则，对4，6，8吨三种车型的数量和调配方式进行安排，并以派出车辆的次数最少为最优目标解，列出目标函数和约束函数。

表1各个公司对每种材料的需求量（单位/天）公司编号各种材料的需求量（单位/天）ABC①415②152③204④312⑤124⑥043⑦225⑧531图1运输路线图和里程数

二、基本假设1、各个公司对在材料的需求量在一天中均衡，即材料只要能在当天运到即可；2、假设货运公司都是先考虑节省人力和出车次数最少的情况下再考虑如何安排运输方式以减少经费支出；3、假设运输车行驶过程中不考虑塞车等现象，以保证每辆车每天可以达到最大的作业时间。4、材料的运输途中不会损坏；5、每日的工作时间只包括装卸时和在公路行走时间；6、港口的材料能保证充足，并装材料及时。三、符号说明符号含义总路程第j辆车第k次出车到i公司运载A材料的数量出车的方向，0表示顺时针，1表示逆时针为0，到达i公司的距离；为0，到达i公司的距离；,,,,材料的重量，，i公司对,,材料的需求量；第j辆车在第k次是否出车，=1表示出车，=0表示不出车；第j辆车在第k次出车途中卸材料的次数第j辆车在第k次出车卸完材料的公司编号其他符号在文中均有说明。四、问题一模型的建立与求解4.1模型分析货运公司运费来自两方面的费用：派车与出车的固定成本、载重与空载行程产生的运费。由于派车成本固定，载重行程和空载行程相互联系，故独立的变量为出车次数和载重行程。以最小化运费为目标函数，以第j辆车第k次出车到i公司运载A材料的数量为决策变量，以各公司的材料需求、大小材料的卸货顺序、车辆使用时间等为约束条件，建立线性规划模型。4.2模型的建立首先由于从港口出发有两个不同的方向，所以我们要考虑每车次出发的方向。另外，每天的运输方案必须满足一定的约束条件。根据这些我们建立一般的规划模型：目标函数：约束条件：（1）保证各个公司每天所需的每种材料得到满足，即所有运到该公司的材料在当天运抵；，，；（2）每辆车每天的工作时间不超过8小时；；（3）保证每次大小件同车时小件在上，大件在下，卸货时先卸小件再卸大件。当=0，时，，，时，，当，时，，，时，，。4.3模型的求解由于每辆最大的载重为6吨，运输时A材料只能和C材料进行组合。我们首先安排A材料的运输，并尽量和C材料。同时某个公司如果需要的B材料数量为偶数，也优先安排，剩下的材料在进行优化。这样可以大大地减少工作量。由于经过以下处理以后所剩情况不多，我们采用枚举的方法求解即可。4.3.1附加符号说明构造一个8行5列的矩阵如图2。其中行号对应公司编号；列号用A、B、C、D、E表示，其中A、B、C表示各公司对相应各种材料的需求量；D表示从港口到各公司顺时针行驶相应的路程数；E表示从港口到各公司逆时针行驶相应的路程数。矩阵左侧的数字表示出车次数，“顺”“逆”表示相应的出车方向。4.3.2求解方法由于A、B、C三种材料毛重和运输车载重吨位的特殊性，因而材料的搭配种类是可以枚举的，其中A与B材料明显不能同时装车，而C可以任意搭配，比较灵活。故A、B材料的多少是决定出车次数的关键，而C可以不予考虑。而要求费用最少，则尽量使每次出车时运输车都满载，此种情况优先考虑，满载搭配方案只有A+C+C、B+C+C+C、B+B三种，在上面的矩阵中优先对这三种满载情况进行相应的变换，然后在根据所得矩阵再进行相应的灵活调度。由上述各图统计可得相应的总出车次数为28，由于途中的卸货次数最多为4次。当运输途中一次卸货时，若出车时间相同，则各运输车几乎同时抵达港口，因而6辆运输车同时出车，则每辆车最多出车5车次。图3至图9为运输车运载方式和各公司所需材料数量变化图。图2图3图4图5图6图7图8图9具体的车辆调度，时间安排，运输费用见表2。表2运输车调度信息运输方式卸货顺序载重距离（km）空载距离（km）所用时间（min）费用（元）1A+C+C(顺)185285107.22A+C+C(顺)185285107.23A+C+C(顺)21545851804A+C+C(顺)3243685273.65A+C+C(顺)3243685273.66A+C+C(顺)4293185325.67A+C+C(逆)5233785263.28A+C+C(逆)7114985138.49A+C+C(逆)7114985138.410B+C+C+C（逆）615458518011B+B（顺）215458518012B+B（顺）215458518013B+B（逆）5233785263.214B+B（逆）615458518015B+B（逆）7114985138.416B+B（逆）8555857617B+C+C+C（顺）1à5à64515105396.618A+C+C(逆)8à7à43127105263.619B+B（顺）1à2154595142.220B+B（逆）8à431299520621A（顺）3243685187.222A（顺）3243685187.223A（顺）3243685187.224A（逆）8555855825A（逆）8555855826A（逆）8555855827A（逆）8555855828A（逆）85558558总计24404864.8注：表中费用不包括派车固定成本和出车固定成本。总运输费用为派车费用、出车费用、载重费用、空载费用总和，求得计算得运输总费用为元。五、问题二模型的建立与求解5.1模型的分析在问题一的基础上增加了运输途中可掉头的条件，故问题一建立的模型不再适用，需要进行改进。在运输途中可掉头，对问题一建立的目标函数和约束条件的影响为空载行程变量和车辆使用时间变量。对这两个变量进行修改即可适用于问题二。5.2模型的建立当矩阵中D列数值大于E列数值时，=0，=1；反之，=1，=0。目标函数：约束条件（2）：5.3模型的求解5.3.1符号说明建立问题二中运输车与各公司之间的关系矩阵。符号新增“”“”标记。“”表示该车卸货后掉头回跑；“”表示该车卸货后不调头，继续直走。图10图11图12图13图14图15图16图17由于A、B、C三种材料毛重和运输车载重吨位的特殊性，因而材料的搭配种类是可以枚举的，其中A与B材料明显不能同时装车，而C可以任意搭配，比较灵活。故A、B材料的多少是决定出车次数的关键，而C可以不予考虑。而要求费用最少，则尽量使每次出车时运输车都满载，此种情况优先考虑，满载搭配方案只有A+C+C、B+C+C+C、B+B三种（不考虑C单独满载的情况），在上面的矩阵中我们优先对这三种满载情况进行相应的变换，在同意公司卸货时不需要考虑大小件的卸货顺序；不同公司搭配送货时在图中卸货顺序用箭头标记。然后在根据所得矩阵再进行相应的灵活调度。运输车顺时针还是逆时针运行由相应公司的D、E的大小决定。由上述各图统计可得相应的总出车次数为28，由于途中的卸货次数最多为4次，当开始出车时间相同时，我们可认为各运输车几乎同时抵达港口，因而6辆运输车同时出车，则每辆车最多出车5车次。具体的车辆调度，时间安排，运输费用见表3。表3运输车调度信息运输方式卸货顺序载重距离（km）空载距离（km）所用时间（min）车次费用（元）1A+C+C(顺)188411（1）89.62A+C+C(顺)188412（1）89.63A+C+C(顺)21515553（1）1684A+C+C(顺)32424734（1）268.85A+C+C(顺)32424735（1）268.86A+C+C(顺)42929836（1）324.87A+C+C(逆)52323711（2）257.68A+C+C(逆)71111472（2）123.29A+C+C(逆)71111473（2）123.210B+C+C+C（逆）61515554（2）168.11B+B（顺）21515555（2）168.12B+B（顺）21515556（2）16813B+B（逆）52323711（3）257.214B+B（逆）61515552（3）168.15B+B（逆）71111473（3）123.216B+B（逆）855354（3）56.17B+C+C+C（顺3）396.618A+C+C(逆)878115676（3）153.219B+B（顺）121515652（4）130.220B+B（逆）843129953（4）206.21A（顺）32424734（4）139.222A（顺）32424731（4）139.223A（顺）32424736（4）139.224A（逆）855355（4）29.25A（逆）855352（5）2926A（逆）855354（5）29.27A（逆）855353（5）29.28A（逆）855351（5）2945141316304270.6注：表中费用不包括派车固定成本和出车固定成本。计算总费用：元。六、问题三模型的建立与求解3.1模型分析在问题一、二的基础上增加了运输车种类：载重量分别为4吨、6吨、8吨；载重运费都是1.8元/吨公里，空载费用分别为0.2，0.4，0.7元/公里，其他费用一样。根据问题一、二的解答方式，以尽可能装满车，每辆车尽可能一次性卸载完为原则，对4，6，8吨三种车型的数量和调配方式进行安排，并以派出车辆的次数最少为最优目标解，列出目标函数和约束函数。3.2模型的建立三种运输车的所有装载方式如下表所示：表4三种运输车的装载方式载重4吨载重6吨载重8吨根据对于每个公司的需求我们都是考虑尽可能用上面给出的不同的装载方式来满足，可建立模型如下：S.T.是正整数其中表示第n个公司分别对A，B，C产品的需求量。代入用LinGo7.0求解可以得出下表：表5问题三运输车调度信息表公司编号各种材料的需求量（单位/天）所需车次所需车型ABC①4158吨②1526吨、8吨③2046吨④3124吨、6吨、8吨⑤1246吨、8吨⑥0436吨⑦2256吨、8吨⑧5318吨现对上表分析，考虑到增加车辆有20元的增加费用，车辆越少越好。但必须在规定时间内（8小时），完成一定车次的任务。所需的车辆数至少为：4吨、6吨、8吨各一辆。每辆车的工作时间的约束条件为：接下来采用穷举法，根据上表所得情况，以尽可能保留6吨车型，优先加开8吨车型为原则，以下表所列的情况按顺序依次进行计算：表6三种运输车穷举顺序穷举顺序载重4吨载重6吨载重8吨①1辆1辆1辆②1辆2辆1辆③1辆2辆2辆④1辆3辆2辆⑤1辆3辆3辆⑥1辆4辆3辆⑦1辆4辆4辆依次穷举后，得到第三种情况，即所需车数为：1+2+2=5（辆）的情况是最优的。按运费计算公式，求出完成一天任务的总运费为：4588.7元。考虑到，4吨车只用了一次，可加开一次6吨车代替，以减少费用。事实证明6吨车加开一次时间是完全允许的，可节约费用：那么车辆数变为：4辆；费用：4573.5元。七、模型的评价与改进本文对建立的线性规划模型采用枚举算法进行求解，简化了计算过程，但没有进行编程求解，在一定程度上具有误差。可通过放松约束条件，编写程序进行求解，逐步加紧约束，进行优化，逐步接近实际情况。八、模型的推广可把问题抽象为网络图，利用图论理论这一数学工具把实际问题抽象为网络图问题，进而建立数学模型。再用图论的相关算法求解。【参考文献】陈东彦，李冬梅，王树忠．数学建模．北京．科学出版社，2007附录：LINGO代码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-x