数学建模-货运列车编组运输问题.doc

2016高教社杯全国大学生数学建模竞赛承 诺 书我们仔细阅读了全国大学生数学建模竞赛章程和全国大学生数学建模竞赛参赛规则（以下简称为“竞赛章程和参赛规则”，可从全国大学生数学建模竞赛网站下载）。我们完全明白，在竞赛开始后参赛队员不能以任何方式（包括电话、电子邮件、网上咨询等）与队外的任何人（包括指导教师）研究、讨论与赛题有关的问题。我们知道，抄袭别人的成果是违反竞赛章程和参赛规则的，如果引用别人的成果或其他公开的资料（包括网上查到的资料），必须按照规定的参考文献的表述方式在正文引用处和参考文献中明确列出。我们郑重承诺，严格遵守竞赛章程和参赛规则，以保证竞赛的公正、公平性。如有违反竞赛章程和参赛规则的行为，我们将受到严肃处理。我们授权全国大学生数学建模竞赛组委会，可将我们的论文以任何形式进行公开展示（包括进行网上公示，在书籍、期刊和其他媒体进行正式或非正式发表等）。我们参赛选择的题号是（从A/B/C/D中选择一项填写）： B 我们的参赛报名号为（如果赛区设置报名号的话）： 所属学校（请填写完整的全名）： 许昌学院 参赛队员 (打印并签名) ：1. 徐晨曦 2. 陈永生 3. 刘志宽 指导教师或指导教师组负责人 (打印并签名)： （论文纸质版与电子版中的以上信息必须一致，只是电子版中无需签名。以上内容请仔细核对，提交后将不再允许做任何修改。如填写错误，论文可能被取消评奖资格。） 日期： 2016 年 8 月 27 日赛区评阅编号（由赛区组委会评阅前进行编号）：2016高教社杯全国大学生数学建模竞赛编 号 专 用 页赛区评阅编号（由赛区组委会评阅前进行编号）：赛区评阅记录（可供赛区评阅时使用）：评阅人评分备注全国统一编号（由赛区组委会送交全国前编号）：全国评阅编号（由全国组委会评阅前进行编号）：货运列车编组运输问题摘要 对于这次我们需要求的货车编组运输，通过不同的情况制定最佳运送方案。对于问题一，我们首先确定的是以运输货物最多，运输总量最小为目标函数的双目标优化问题，这里我们首先是将复杂的B类货物单独的分开来，看成是两种类型的货物，我们为了简化运算我们先针对单个目标数量最多对其进行优化求解，用lingo软件得出数量最多为24，分别有几组数据，然后在以数量为最多的条件下为约束，求取另一个目标总重量最小，用lingo分析得出其中最小的总重量为179吨，然后再将两者的求得结果相互结合得出，数量最多为24的情况下，总重量最小为179吨。对于问题二：问题二是下料问题，因此需要先确定可行的下料方式，即两种车厢可行的货物装载方式。以每种装载方式的使用次数为决策变量，总使用次数最少为目标函数，建立整数线性规划模型求解。用MATLAB解得：要将货物运输完毕，B,C,E分别为68、50、41件时使用的最少车厢数量为25，B,C,E分别为48,42,52件时使用的最少车厢数量为21对于问题三给出了最近100天上午和下午需要运的集装箱数目，根据所给的数据我们做出了散点图根据散点图并用MATLAB拟合我们发现最近100天需要运的集装箱数目符合正态分布。然后我们算出上午和下午的日利润，再把他们相加R=R1+R2，得到每天的利润之和。其中上午的利润我们把它分为集装箱可以全部运完和集装箱运不完两种情况分别计算，下午的同上午的，但是若上午的集装箱没有运完要加到下午需要运的集装箱数目上。关键词：lingo 线性规划 双目标优化 Matlab 正态分布一、问题重述列车编组问题 货运列车编组调度的科学性和合理性直接影响着货物运输的效率。请根据问题设定和相关数据依次研究解决下列问题：1、假设从甲地到乙地每天有5种类型的货物需要运输，每种类型货物包装箱的相关参数见附录一。每天有一列货运列车从甲地发往乙地，该列车由1节型车厢和2节型车厢编组。型车厢为单层平板车，型车厢为双层箱式货车，这两种车厢的规格见附录二。货物在车厢中必须按占用车厢长度最小方式放置（比如：A类货物占用车厢长度只能是2.81米，不能是3米；再比如：一节车厢中B类货物装载量为2件时，必须并排放置占用长度2.22米，装载量为3件时，占用长度3.72米），不允许货物重叠放置；型箱式车厢下层装载货物后剩余长度小于等于0.2米，才能在上层放置货物。试设计运输货物数量最多的条件下，运输总重量最小的装运方案。2、如果现有B,C,E三种类型的货物各69、50、51件，试设计一个使用车厢数量最少的编组方案将货物运输完毕。由于整个铁路系统型车厢较多，要求在编组中型车厢的数量多于型车厢数量，型箱式车厢下层装载货物后剩余长度小于等于5米，才能在上层放置货物，货物装车其它规则同问题1。若B,C,E三种类型的货物各有58,42,62件，请重新编组。3、从甲地到乙地每天上午和下午各发送一列由型车厢编组的货运列车，每列火车开行的固定成本为30000元，每加挂一节车厢的可变成本为1500元。为了装卸的方便，铁路部门拟将货物放置到长、宽、高分别为4米，3米及1.99米的集装箱中运输，每个集装箱的总重量不超过18吨，集装箱的运费为1000元/个。每天需要运输的集装箱数量是随机的，附录三给出了过去最近100天上午和下午分别需要运输的集装箱的数量。上午的需求如果不能由上午开行列车运输，铁路部门要支付50元/个的库存费用；下午列车开行后如果还有剩余集装箱，铁路部门将支付200元/个的赔偿，转而利用其它运输方式运输。试制定两列火车的最佳编组方案。二、问题分析2.1问题一分析对于问题一，我们首先确定的是以运输货物最多，运输总量最小为目标函数的双目标优化问题，这里我们首先是将复杂的B类货物单独的分开来，看成是两种类型的货物，我们为了简化运算我们先针对单个目标数量最多对其进行优化求解，用lingo软件得出数量最多为24，分别有几组数据，然后在以数量为最多的条件下为约束，求取另一个目标总重量最小，用lingo分析得出其中最小的总重量为179吨，然后再将两者的求得结果相互结合得出，数量最多为24的情况下，总重量最小为179吨。2.2问题二分析问题二为求解在所有货物都能运走的条件下使用车厢最少的情况。可以看出此题为最优化问题，也就是整数规划问题。针对此问题可以建立模型使用matlab和lingo取得最优值。货物类型为B，C，E，根据货物要以占用车厢长度尽可能小的要求可知，摆放货物C和E只有只有一种方式。由于货物C，E宽为3m恰好等于车厢宽度，所以根据要求只能使CE的宽的方向和车宽度的方向平行，这样才能使货物占用长度最小。针对货物B，已知尺寸为，宽度为，所以要使占用长度最小就要分情况而定了。当货物B的数量为偶数时可以两两配对竖放，为奇数时取其中一个横放，这样占用长度最小。由于货物不能重叠放置，我们可以将货物车厢中的装载问题抽象为二维矩形件的排样问题，只是增加了货物总重量的上限约束。如果将一节车厢和两节车厢一起进行分析，情况较为复杂，为减少计算负荷，我们先对两种车厢各自的可行装载方式进行分析，再将其进行组合。也就是在满足车厢空间和重量要求的前提下，列出车厢和车厢所有装载的可能情况2.3问题三分析题目中给出了最近100天上午和下午需要运的集装箱数目，根据所给的数据我们做出了散点图根据散点图并用MATLAB拟合我们发现最近100天需要运的集装箱数目符合正态分布。然后我们算出上午和下午的日利润，再把他们相加R=R1+R2，得到每天的利润之和。其中上午的利润我们把它分为集装箱可以全部运完和集装箱运不完两种情况分别计算，下午的同上午的，但是若上午的集装箱没有运完要加到下午需要运的集装箱数目上。算出每天利润之和，再根据我们对最近100天上午和下午需要运的集装箱数目分析利用它符合正态分布算出需要运输的集装箱数量是r1的概率为f(r1)，然后把它们相乘，得到上午的利润之和为同理可得下午的利润之和，然后求出利润之和最大时所上午需要运输的集装箱数和下午需要运输的集装箱数。三、模型假设1. 货物不能重叠放置，且不能直立放置2. 上午运不完的集装箱，归到下午需要运的集装箱的范畴3. 出于利润最大化的考虑，发出的列车车厢数达到最大编组量且每个车厢中装满三个集装箱4. 超过需求量的集装箱，铁路部门收不到相应的运费4、 符号说明符号名称 符号意义 第种货物放入第号车厢的数量 第 种货物占用车厢总长度 第 种货物重量 第 种货物的总数 型车厢第j种装载方式的使用次数 型车厢第j种装载方式的使用次数 上午、下午的利润总和 上午的利润 下午的利润 上午发出的车厢数 下午发出的车厢数 上午需要运输的集装箱数 下午需要运输的集装箱数五、 模型的建立与求解5.1问题一基于上述分析，对问题一进行模型的建立和求解。 5.1.1基本思路首先确定的是在运输数量最多的条件下，我们求的是运输的重量最小，这样我们建立的目标函数就是双目标类型了，这里我们为了简化模型，分别先确定数量最多的情况，然后再求解重量最小。5.1.2确定货物的装箱的各种方案1.由于货物的不能重叠放置我们这里将1节I型和2节II型分别计算各自的可以装载的运行方案，在进行组合。这里对于B类型货物相较于其他的复杂所以我们这里采用的方法是将其看成两种不同的货物具体如下两种： 然后我们分析各个车厢内的分类情况如下图所示：图1各个车厢内的分类情况 如上图中i表示的是货物的类型A,B1,B2,C,D,Ej表示的是车厢数量I II II II II2.考虑单个车厢的情况时，如下条件：1）货物占用车厢的高度车厢高度考虑实际情况以及题中所给的例子，我们假设货物不能竖直放置。此时只需考虑货物实际高度与车厢高度的关系，得到型车厢的第二层不能放置A类和B类货物的结论。2）货物按占用车厢长度最小方式放置对于A,C,D,E类的货物，他们占用车厢的最小长度就是他们的实际长度。对于B类货物，需要进行分类讨论：B1的最小长度是1.5，B2的最小长度为2.223）货物占用车厢的宽度车厢宽度货物按占用车厢长度最小的方式放置时，恰使得A,C,D,E类货物占用车厢的宽度等于车厢宽度，而对B类货物进行分类讨论时，已经考虑到了车厢宽度的限制，因此这一条件可以不单独列出。4） 型车厢下层装载货物后剩余长度小于等于0.2米时，才能在上层放置货物5） 货物占用车厢总长度车厢长度6） 货物总重量车厢载重量7） 由于每种货物数量有限所以有n为第 种货物能放的车厢的车厢数。3.对两种车厢可行的货物装载方式进行组合得到目标函数： 在lingo软件中编程（源程序见附录四）得到各种情况下的装载数量最多方式。数量最多条件下，求总重量最小 得到目标函数： 5.1.3模型一的求解由以上的目标函数在lingo中得到数量最多能装载是24，在数量最多的境况下即24时，由lingo编程可以得出总重量最小的装载重量，最小为179吨。（具体源程序可见附录表五）具体装载方案如表5-1表5-1.最优装载方案A232NANAB010NANAC40100D00023E023105.2问题二模型的建立5.2.1模型准备问题二为求解在所有货物都能运走的条件下使用车厢最少的情况。可以看出此题为最优化问题，也就是整数规划问题。针对此问题可以建立模型使用matlab和lingo取得最优值。问题二中的货物类型为B，C，E，根据货物要以占用车厢长度尽可能小的要求可知，摆放货物C和E只有只有一种方式。由于货物C，E宽为3m恰好等于车厢宽度，所以根据要求只能使CE的宽的方向和车宽度的方向平行，这样才能使货物占用长度最小。针对货物B，已知尺寸为，宽度为，所以要使占用长度最小就要分情况而定了。当货物B的数量为偶数时可以两两配对竖放，为奇数时取其中一个横放，这样占用长度最小。具体放置方式如图1.图2.货物B两种放置方式由于货物不能重叠放置，我们可以将货物车厢中的装载问题抽象为二维矩形件的排样问题，只是增加了货物总重量的上限约束。如果将一节车厢和两节车厢一起进行分析，情况较为复杂，为减少计算负荷，我们先对两种车厢各自的可行装载方式进行分析，再将其进行组合。也就是在满足车厢空间和重量要求的前提下，列出车厢和车厢所有装载的可能情况。约束条件由于重量和空间的约束条件大致和问题一相同，只改变了型箱式车厢下层装载货物后剩余长度小于等于5米，才能在上层放置货物在此不再进行讨论。在问题一中我们将货物B分类为两种类型，即和，这两种货物分别为B货物单个放置和成对放置。所以B货物放置的长度条件重新建立。求解结果在MATLAB中编程求解（源程序见附录六），通过Excel对结果进行数据分析和整合，排除明显劣解，得到只考虑B,C,E时型车厢可行的货物装载方式22种、车厢可行的货物装载方式125种（附录七）。5.2.2问题二模型的建立用表示只考虑B,C,E时型车厢第j种装载方式的使用次数，用表示只考虑B,C,E时型车厢第j种装载方式的使用次数，则、是模型二的决策变量，均为非负整数。确定约束条件题目规定将一定数量的货物B、C、E运输完毕，既是运走的各类货物数量大于等于现有数量，由此可得到：其中， 分别是型车厢型车厢第j种装载方式的使用次数， 为第 种货物各方案中货物的运载量， 为第 种货物的现有数量。型车厢的数量多于型车厢确定目标函数问题二要求使用车厢数量最少，即各装载方式使用次数之和最少，所以目标函数为：5.2.3模型求解根据目标函数利用Lingo求解模型（附录八），得到B,C,E分别为69、50、51件时使用的最少车厢数量为26，B,C,E分别为58,42,62件时使用的最少车厢数量为24。具体编组方案如表5-2，表5-3。表5-2.B,C,E分别为69、50、51件时使用车厢数量最少的编组方案方案次数X1514222NANAY29203230Y100322400Y123750110根据表格计算此种方案装载货物B,C,E的数量分别为69,53,51，比现有货物数量多出3件C。表5-3.B,C,E分别为58、42、62件时使用车厢数量最少的编组方案方案次数X1513222NANAY75213211Y107630500Y121343000根据表格计算此种方案装载货物B,C,E的数量分别为58,43,62，比现有货物数量多出1件C.5.3问题三模型建立5.3.1数据处理根据过去最近100天上午和下午需要运的集装箱数量的数据，做出散点图。系列一为上午的，系列二为下午的。图一，最近100天上午和下午需要运的集装箱数量散点图图3最近100天需要运的集装箱数量没有发现数据的明显规律，用MATLAB进行数据分布拟合，发现两组数据均服从正态分布，接受概率分别为0.2943、0.9250。5.3.2模型的建立5.3.2.1确定目标函数因为每天上午、下午需要运输的集装箱数量都是随机的，所以我们对上午、下午分别考虑，则铁路部门的日利润等于上午、下午的利润之和，即目标函数为 5.3.2.2推导过程因为集装箱和车厢的规格都固定，所以当上午发出的列车有s1节车厢时，可运输集装箱的为3s1。铁路部门上午的利润R1与上午需要运输的集装箱的数量r1有关，当时，铁路部门获得最多的运费；当时，铁路部门需要支付未被运走的集装箱的库存费用。即 对于下午，需要运输的集装箱数量r2除了原来的需求，还可能包括上午剩余的集装箱。则对上午的分析：假设上午需要运输的集装箱数量是r1的概率为f(r1),可以由过去的数据得到，用铁路部门的利润期望值来衡量利润，则 即在f(r1)已知时，求s1使得R1最大。为了便于分析，将概率f(r1)转化为概率密度函数P(r1)，则对R1(s1)求导，并让导数等于0，得到因为，所以将上式左右两边的分母都加上分子，得到由数据分析，已知r1服从正态分布，可以用正态分布的逆概率分布求解得到s1。对下午的分析：类似的，我们可以得到注意：下午需要运输的集装箱数量还包括上午未运输完的集装箱。5.3.3模型的求解用MATLAB求解正态分布的逆概率分布（源程序见附录四表1），解s1=40.3642、s2=37.3822.所以最佳编组方案是上午发的列车带41节型车厢、下午发的列车带38节型车厢。6、 模型评价优点1，模型把所述要求考虑的非常全面，能充分的利用数据。2，利用lingo和MATLAB把复杂的问题变得简单化，减少了计算难度。3，通过数形结合和软件拟合方法把看似毫无规律的数据总结出了规律。缺点1，模型涉及的问题太多，不易计算，难以理解。2，问题三中上午的数据虽然服从正态分布，但接受概率很低，对计算的结果带来了误差；7、 参考文献1 姜启源，谢金星，叶俊，数学模型（第四版），北京：高等教育出版社，20112 张志勇，杨祖樱，MATLAB教程R2010a，北京航空航天大学出版社，2013 3 薛山，MATLAB 2012 简明教程M,北京清华大学出版社,2012；l 一24 BS EN 581-3:2007 Outdoor furniture. Seating and tables for camping, domestic and contract use. Mechanical safety requirements and test methods for tables5 基于Matlab和Lingo的数学实验（第一版）M，西北工业大学出版社，2009附录附录一：货物包装箱相关参数。货物类型长度（米）宽度（米）高度（米）重量（吨）数量A2.8131.325.57B2.221.51.3510.56C1.7130.995D2.6231.187E2.5331.27.56附录二：火车车厢相关参数。车厢类型长度(米)宽度下层高度上层高度载重量（吨）型12.532.555型1531.41.370附录三：近100天上午集装箱数量：149 100106 13297 10297 123124 97103 130146 144108 110106 133144 99128 98133 10195 100144 111103 106125 105112 150105 14494 122148 137103 140121 146148 132120 115117 10393 128127 137100 121149 126130 14493 11795 91122 125120 13598 91134 107143 143146 115109 139107 97111 141149 112101 111131 140144 13095 108139 142117 115122 136129 90近100天下午集装箱数量：128 137115 106133 5693 95 113 66155 10589 108131 10798 122 102 102104 109106 97 105 8786 125124 16573 82121 82 119 6186 11362 11673 8783 136102 75106 93 124 97121 119103 12168 84108 11192 88113 8578 11290 80116 75 107 8892 125111 91 99 11398 11092 8075 10185 98 69 61103 85 112 128101 10290 82 111 118128 88 85 47附录四：Max x11+x12+x13+x21+x22+x23+x31+x32+x33+x41+x42+x43+x44+x45+x51+x52+x53+x54+x55+x61+x62+x63+x64+x65x11+x12+x13=7 x21+x22+x23+2x31+2x32+2x33=6 x41+x42+x43+x44+x45=5 x51+x52+x53+x54+x55=7 x61+x62+x63+x64+x65=6 2.81x11+1.5x21+2.22x31+1.71x41+2.62x51+2.53x61=14.8 2.81x12+1.5x22+2.22x32+1.71x42+2.62x52+2.53x62=15 2.81x13+1.5x23+2.22x33+1.71x43+2.62x53+2.53x63=14.8 1.71x44+2.62x54+2.53x64=15 1.71x45+2.62x55+2.53x65=15 5.5x11+10.5x21+21x31+9x41+8x51+7.5x61=55 5.5x12+10.5x22+21x32+9x42+8x52+7.5x62+9x44+8x54+7.5x64=70 5.5x13+10.5x23+21x33+9x43+8x53+7.5x63+9x45+8x55+7.5x65=70ENDGIN 24附录五：min 5.5x11+5.5x12+5.5x13+10.5x21+10.5x22+10.5x23+21x31+21x32+21x33+9x41+9x42+9x43+9x44+9x45+8x51+8x52+8x53+8x54+8x55+7.5x61+7.5x62+7.5x63+7.5x64+7.5x65x11+x12+x13=7 x21+x22+x23+2x31+2x32+2x33=6 x41+x42+x43+x44+x45=5 x51+x52+x53+x54+x55=7 x61+x62+x63+x64+x65=6 2.81x11+1.5x21+2.22x31+1.71x41+2.62x51+2.53x61=14.8 2.81x12+1.5x22+2.22x32+1.71x42+2.62x52+2.53x62=15 2.81x13+1.5x23+2.22x33+1.71x43+2.62x53+2.53x63=14.8 1.71x44+2.62x54+2.53x64=15 1.71x45+2.62x55+2.53x65=15 5.5x11+10.5x21+21x31+9x41+8x51+7.5x61=55 5.5x12+10.5x22+21x32+9x42+8x52+7.5x62+9x44+8x54+7.5x64=70 5.5x13+10.5x23+21x33+9x43+8x53+7.5x63+9x45+8x55+7.5x65=70x11+x12+x13+x21+x22+x23+x31+x32+x33+x41+x42+x43+x44+x45+x51+x52+x53+x54+x55+x61+x62+x63+x64+x65=24ENDGIN 24附录六：对于型车厢（problem1-1.m）p=;a11=0for a11=0:7;%aij中i表示货物ABCDE，j表示层数 for a21=0:6; for a31=0:5; for a41=0:7; for a51=0:6; if a21=0; %对B进行分类 l1=a11*2.81+a31*1.71+a41*2.62+a51*2.53; end if a21=1,3,5; l1=a11*2.81+(a21-1)*1.11+1.5+a31*1.71+a41*2.62+a51*2.53; end if a21=2,4,6; l1=a11*2.81+a21*1/2*2.22+a31*1.71+a41*2.62+a51*2.53; end w1=a11*5.5+a21*10.5+a31*9+a41*8+a51*7.5; %计算车厢载重 if l1=12.5 & w1=55 &(12.5-l1)=1.5; p=p;a11 a21 a31 a41 a51 a11+a21+a31+a41+a51 w1; end end end end endendP对于型车厢（problem1-2.m）p=;a11=0;for a11=0:5;%aij中i表示货物ABCDE，j表示层数 for a21=0:6; for a31=0:7; for a41=0:5; for a51=0:5; if a21=0; %对B进行分类 l1=a11*2.81+a31*1.71+a41*2.62+a51*2.53; end if a21=1,3,5; l1=a11*2.81+(a21-1)*1.11+1.5+a31*1.71+a41*2.62+a51*2.53; end if a21=2,4,6; l1=a11*2.81+a21*1/2*2.22+a31*1.71+a41*2.62+a51*2.53; end if l115&(15-l1)=0.2; for a32=0:7; for a42=0:5; for a52=0:5; l2=1.71*a32+2.62*a42+2.53*a52; w2=5.5*a11+10.5*a21+9*(a31+a32)+8*(a41+a42)+7.5*(a51+a52); if l2=15&w2=69c) 0Y1+1Y2+2Y3+3Y4+4Y5+0Y6+1Y7+2Y8+3Y9+1Y10+2Y11+3Y12+4Y13+1Y14+2Y15+3Y16+2Y17+3Y18+4Y19+5Y20+2Y21+3Y22+4Y23+2Y24+3Y25+3Y26+4Y27+5Y28+6Y29+3Y30+4Y31+5Y32+3Y33+4Y34+3Y35+4Y36+5Y37+6Y38+4Y39+5Y40+4Y41+5Y42+6Y43+5Y44+6Y45+5Y46+6Y47+7Y48+6Y49+6Y50+7Y51+0Y52+1Y53+2Y54+3Y55+0Y56+1Y57+2Y58+1Y59+2Y60+3Y61+4Y62+1Y63+2Y64+3Y65+1Y66+2Y67+2Y68+3Y69+4Y70+2Y71+3Y72+2Y73+3Y74+4Y75+3Y76+4Y77+3Y78+4Y79+5Y80+4Y81+4Y82+5Y83+6Y84+5Y85+6Y86+0Y87+1Y88+2Y89+0Y90+1Y91+1Y92+2