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

货运公司的运输问题摘要货运公司的车辆调度方案直接影响货运公司的当前经济效益和长远发展。本文根据货运公司需要完成的运输量和确定的运输路线图，以线性规划为基础，通过建立数学模型，对调度方案进行分析和优化，寻找车辆调度的最佳方案，从而为货运公司提供明确的、运费最小的车辆调度方案。货运公司追求在条件允许的情况下，使运营成本最大化的降低，通过对影响运营成本的因素进行仔细的分析，对不同问题分别建立数学模型，进而推导出最佳运营方案。具体方案如下：问题一中，首先利用线性规划对每天的出车次数进行限定，并用Lingo8.0求解，得到其在满足八个工厂需求的情况下的最小出车次数；继而以此出车次数为基础，综合考虑运营成本的影响因素，并充分利用运输线路图以及材料的需求表格的特点，对具体的出车方案进行逐步推导，得出一个可行的运营方案，即方案Ⅰ(见表1)。由于方案Ⅰ的设计受到出车次数的限制，可能不是最佳方案，通过严格的计算后，对方案Ⅰ进行适当的调整，推导出完善的方案Ⅱ（见表2）。经过验证，方案Ⅱ比方案Ⅰ更加优秀。问题二中，在本题的条件下，允许运输车掉头只会影响运输车卸货后空载的行驶路程，即运输车的空载费用，故通过修改计算公式中的相关数据，并参考方案Ⅱ的调度方法，得出最佳调度方案（见表3），并计算出需要安排的运输车的数量为4辆。问题三中，由于已知条件的更改，不相邻的公司间可能存在更短路使成本更少。因此应用图论相关知识，首先依次找出各可能互相带货的公司相连的最短路，去掉其他多余路径，然后得到的这些最短路组成的图形即为新运输路径，再根据新路径决定货物分配，得出新的运营方案。关键词：线性规划图论最短路问题一．问题重述某地区有8个公司（标号=1-8\*GB3=1\*GB3①—=8\*GB3⑧如图一），某天它们各个的需求量如图二。某货运公司要派车将各个公司所需货物A.B.C从港口（标号=9\*GB3⑨如图一）运往这8个公司。路线是唯一的双向道路（如图一）。货运公司现有一种载重6吨的运输车，派车固定成本20元/辆，从港口出车固定成本为10元/车次（车辆每出动一次为一车次）。每辆车平均需要用15分钟的时间装车，到每个公司卸车时间平均为10分钟，运输车平均速度为60公里／小时（不考虑塞车现象），每日工作不超过8小时。运输车载重运费1.8元/吨公里，运输车空载费用0.4元/公里。货运公司要将各个公司所需的货物全部运到。一个单位的原材料A,B,C分别毛重4吨、3吨、1吨，原材料不能拆分，大小件同车时必须小件在上，大件在下。卸货时必须先卸小件，而且不允许卸下来的材料再装上车。问题一：货运公司派出六辆车，从港口出发（不定方向），但在运货过程中，不能掉头，应如何调度才能使得货运公司的成本最小？（要求具体列出每辆车的运输方案，运输成本。）问题二：每辆车在运输过程中可以掉头，在满足各个公司的需求条件下，应如何啊名牌车辆数，怎样调度调度才能使得货运公司的成本最小？问题三：当各个公司间都有或者部分有道路直接相通时，分析运输调度的难度所在，并针对这两种情况分别给出解决问题的想法（可结合实际情况深入分析）。（图一）唯一的运输路线图和里程数（图二）各个公司对每种材料的需求量（单位/天）公司编号各种材料的需求量（单位/天）ABC①415②152③204④312⑤124⑥043⑦225⑧531二．问题分析货运公司的车辆调度方案直接影响货运公司的当前经济效益和长远发展。为此需要对货运公司的出车调度方案进行合理的规划，从而制订出明确的最优调度方案，这样不仅能使货运公司有效地降低运营成本，而且有利于货运公司的长远发展。对比分析之下，问题一与问题二具有极大的相似性，因而可采取类似的方法来解决最优调度方案的问题。通过对问题一进行深入的分析，首先以各公司对各种材料的需求为约束条件，建立线性规划模型，从而得出出车次数的最低要求。出车次数有最低要求，而车辆数又有数量限制：6辆，每辆车的工作时间也有8小时的限制，再综合考虑运输费用的相关因素，从而逐步推导出具体的出车调度方案，通过对方案进行严格的计算，并仔细研究方案的调度缺陷，从而进行适当的调整，得出更完善的方案。对于问题二的分析，是基于问题一的最后方案进行研究的，区分二者的不同之处。经分析发现由于问题二中运输车可以掉头，故可以减少由于运输车在途中空载的路程，而这只会影响计算公式中的数值的改变，因而和第一问的求解方法基本上是一致的，能够比较轻易的推导出最优的调度方案。对于问题三，由于有可能存在各公司间的更短路，并且路程越是短，越能节约成本，因此，找出能够连接所有可能带货的公司间的最简单的最短路，以这些最短路为基础，推导出调度方案。三．模型假设假设运输车行驶过程中不考虑塞车抛锚现象，以保证每辆车每天可以达到最大的作业时间内的任何值。假设每辆车装载时发挥其最大的装载能力；假设题目中提供的数据都是准确的，可作为标准值来进行计算。四．符号说明t所有车次运输总时间p所有车次运输的总成本s货运总费用五．模型的建立与求解问题一的求解：考虑到每个公司的需求情况，根据表一表二的情况，可以得到以下有用的信息：总的的需求是18A,18B,26C.并且在使运输成本最少的情况下，首先考虑尽量使运输车次满载，满载的情况有以下四种方案：A+2C,2B,B+3C,6C.用LINGO线性规划求解可得，最少需要运输27次。但是这是不是最优化的解呢？对于这个结果加以分析主逐次推导，可以得到表一的数据，所有车次的运输总成本p：4775.6元，货运总费用为s：20*6+10*27+4775.6=5165.6元。在这个调度方案中，有一个车次的运行线路比较复杂，是将A+2C从港口逆时针运输经过=7\*GB3⑦，卸掉一个C,经过=8\*GB3⑧卸掉一个C,经过=1\*GB3①卸掉一个A，最后空载回到港口。表格显示，这个车次的费用是：421.2元，比较分析，大于某些车次费用的两倍。虽然这是车次最少情况下计算得到的成本，但这是不是最优化的解，显然还有待商榷。经过进一步的推导和分析，在方案一的基础上，以运输成本最少为根本目标，多增加一次车次，可以得到方案Ⅱ，对应有表二的数据，所有车次的运输总成本为p：4481.6元，货运总费用为s：20*6+10*28+4481.6=4881.6元。比较可得，方案二的运输总成本比方案一的运输总成本低，更为优化。结论：根据表二的数据，总的车次时间为t：2420分钟，货车的工作时间不超过8小时，6辆车的总时间就不能超过6*8*60=2880分钟>2420分钟。所以在时间上也是合理的。问题二的求解：分析允许运输车掉头只会影响运输车卸货后空载的行驶路程，即运输车的空载费用。根据运输情况，在每辆车完成了该车的装载任务后，看所处的位置在何处，如果掉头回港口更近的话，则掉头，否则继续前进，其他的计算方式则和第一问中的一样，故通过修改计算公式中的相关数据，并参考方案Ⅱ的调度方法，就可以得出最佳调度方案（见表3），并计算出需要安排的运输车的数量为4辆。结论：所有车次的运输总成本为p:4144.8。因为所有车次在运行过程中的运输成本是确定的，所以使参与货运的车辆数最少时，货运费用就越少。计算得到的总时间为t：1564分钟。每辆货车工作最大时间为8小时，即8*60=480分钟。于是最少车辆：1564/480≈4辆。问题三的求解：由于各个公司间都有或者部分有道路直接相通，导致本来简单的圆环路径变得复杂，有了更多更短的路径，因此在运输路径的选择上遇到问题，从而给合理安排好货物装载增加了困难，加大了运输调度的难度。但是这个问题不是不可解决的，首先找出全部可能互相带货的不同公司间的最短路，其次去掉多余的路，得到最为简单的图，即新的运输路径，再在新路径的基础上安排好不同车次的货物分配，于是得到新的运营方案。以问题一为例，如从①到③、④、⑤、⑥、⑦、⑧均有路，分别长10、10、12、11、12、9公里，由于①与⑤之间存在带货关系，所以依据上述方法，保留①、⑤间的路径，去掉①与③、④、⑥、⑦、⑧的路径，则当①直接到⑤而不是原来的逆时针依次经过⑧、⑦、⑥再到⑤时，节省了11公里的路程，缩短了时间，也减小了成本。六．模型的评价与推广模型的评价针对题中已知的运输问题，由于路径比较简单，且运送货物比较单一，运送要求又不繁琐，因此此模型建立较为简单粗糙，只采用了线性规划的方法，运用一些推导即得到了结果。不过第三问较前两问更接近实际，通过第三问提供出的解题思路，可以在类似问题中得以运用。模型的推广由于模型的建立很大程度上是以逻辑推理为基础的，有比较大的针对性，因此不太适合于推广，也不太适合于更进一步的完善，有比较大的局限性。比较有可能的一种推广方式就是重新建立一种更为完善的模型，有比较宽的适用面，并且以本模型结果作为参考，检验模型的精度，但由于时间的限制，未能实现。七参考文献[1]谢金星、薛毅编著，优化建模与lingo/lindo软件，北京：清华大学出版社，2005.7；[2]姜启源，数学模型，高等教育出版社，2003附录车次装载方案目的地费用时间运输方向1A+C⑧6785逆时针2A⑧5885逆时针3A⑧5885逆时针4A⑧5885逆时针5A⑧5885逆时针62B⑧7685逆时针7A+2C⑦138.485逆时针8A+2C⑦138.485逆时针92B⑦138.485逆时针102B⑥18085逆时针112B⑥18085逆时针12A+2C⑤263.285逆时针132B⑤263.285逆时针14A+2C④325.685顺时针15A+2C③273.685顺时针16A+2C③273.685顺时针17A+2C②18085顺时针182B②18085顺时针292B②18085顺时针20A+2C①107.285顺时针21A+2C①107.285顺时针22A+C①92.885顺时针23A+2C⑦→⑥→①421.2105逆时针24A+2C⑤→④317.695逆时针25A+2C⑥→④288.895逆时针262B⑧→④20695逆时针272B→②142.295顺时针总计4775.62355表格1车次装载方案目的地费用时间运输方向1A+C⑧6785逆时针2A⑧5885逆时针3A⑧5885逆时针4A⑧5885逆时针5A⑧5885逆时针62B⑧7685逆时针7A+2C⑦138.485逆时针8A+2C⑦138.485逆时针92B⑦138.485逆时针102B⑥18085逆时针112B⑥18085逆时针12A+2C⑤263.285逆时针132B⑤263.285逆时针14A+2C④325.685顺时针15A+2C③273.685顺时针16A+2C③273.685顺时针17A+2C②18085顺时针182B②18085顺时针292B②18085顺时针20A+2C①107.285顺时针21A+2C①107.285顺时针22A+C①92.885顺时针23A78.485顺时针24A④221.285顺时针25A④221.285顺时针262B⑧→④20695逆时针272B→②142.295顺时针286C⑦→⑥→⑤212.8105逆时针总计4481.62420表格2车次装载方案目的地费用时间运输方向1A+C⑧4735逆出顺回2A⑧3835逆出顺回3A⑧3835逆出顺回4A⑧3835逆出顺回5A⑧3835逆出顺回62B⑧5635逆出顺回7A+2C⑦123.247逆出顺回8A+2C⑦123.247逆出顺回92B⑦123.247逆出顺回102B⑥16855逆出顺回112B⑥16855逆出顺回12A+2C⑤257.671逆出顺回132B⑤257.671逆出顺回14A+2C④324.883顺出逆回15A+2C③268.873顺出逆回16A+2C