数学建模铁路平板车问题最优化论文.doc

铁路平板车问题最优化论文摘要：为了使平板车装载包装箱所浪费空间达到最小，也就是货物占据空间达到最大，关键字：整数规划，整体最优化,问题重现：有 7 种规格的包装箱要装到两辆铁路平板车上去。包装箱的宽和高是一样的，但厚度（t，以厘米计）及重量（ ，以kg 计）是不同的。下表给出了每种包装箱的厚度、重量以及数量。每辆平板车有10.2m 长的地方可用来装包装箱（象面包片那样），载重为40t。由于当地货运的限制，对c5 ,c6,c7 类的包装箱的总数有一个特别的限制：这类箱子所占的空间（厚度）不能超过302.7cm。试把包装箱上平板车而使浪费的空间最小。 C1 C2 C3 C4 C5 C6 C7 件数 8 7 9 6 6 4 8t(cm)48.752.061.372.048.752.064.0W(kg)2000300010005004000200010001.问题分析：题中所有包装箱总重为89吨，总厚度达到2749.5cm，而两辆平板车只能承载40吨*280吨，长度为2040cm。因此所有的包装箱不能全部装在车上。那么，要在两辆车上装入多少个各种规格的箱子才合适？这需要有一个评价的标准。这标准就是遵守题中说明的厚度方面的约束条件，并且在这些条件下，能尽可能多装，确定最终的装载方案使得空间利用最大化。 由题意可知，只考虑像面包片重叠那样的装法，把问题简化，为两辆车上装箱总厚度之和尽可能大。2.模型假设：1) 各个货物装在车上的概率相同，相互之间的排放不存在关联性；2) 在该平板车装载的过程中不考虑各个货物的厚度及重量的误差性，均为题中所给的准确数值；3) 装载的过程中不考虑货物在车上的排列次序及各个货物的重量密度，排除因局部过重而造成的平板车不能行驶的情况；4) 各个货物之间排列时靠在一起，忽略其中的间隙及因搬动等带来的一些空隙；5）铁路平板车只能放置一列包装箱。3、符号说明：.第1-7种规格的包装物.第种规格的包装物的厚度 .第种规格的包装物的重量.在第一辆车上装载种包装箱的个数.在第二辆车上装载种包装物的个数模型分析与建立模型一：整体最优化模型分析：通过运筹学的相关知识可以知道，单个个体都取到最优解，总和起来不一定就能使得总体达到最优结果，模型一即以整体最优为目标建立的。题目中“c5 ,c6,c7 类的包装箱的总数有一个特别的限制：这类箱子所占的空间（厚度）不能超过”由2种理解。第一种理解为：每辆车的总厚度不能超过302.7cm；第二种理解为两辆车的总厚度不能超过302.7cm。第一种理解：每辆车的总厚度不能超过302.7cm建立目标函数：约束条件：，=0厚度条件： 载重约束：特殊限制：操作约束：取整求解的答案： 模型一（整体最优化一）求解答案装载种类C1C2C3C4C5C6C7装载后的总厚度装载后的总重第一辆车6260004102028000第二辆车0525212102031500第二种理解：两辆车的总厚度不能超过302.7cm建立目标函数：约束条件：，=0厚度条件： 载重约束：特殊限制：操作约束：取整求解得出如下值： 模型一（整体最优化二）求解答案装载种类C1C2C3C4C5C6C7装载后的总厚度装载后的总重第一辆车07640001019.829000第二辆车80323301019.638000模型二：双目标决策模型模型分析：通过上述模型，不难看出要使浪费空间最小，即求装载包装物所占空间的最大值，得解不唯一。因此我们考虑，能不能载满足浪费空间最小的情况下，再次满足“载重量最大”这一决策目标。由此模型二产生。目标函数：约束条件：，=0厚度条件： 载重约束：特殊限制：操作约束：取整求解得出值如下： 模型二（双目标决策）求解答案装载种类C1C2C3C4C5C6C7装载后的总厚度装载后的总重第一辆车0525212102031500第二辆车6260004102028000模型三:考虑在一辆车达到空间最高利用率的时候求另一辆车的配置情况。因此假设第一辆车达到空间最高利用率，求第二辆车的配置情况。第一辆车：目标函数：max约束条件：第二辆车：在满足第一辆车空间最高利用率下，解出第二辆的配置情况。通过matlab运算可以取得的最终结果：模型三中第一辆车的最终解C1C2C3C4C5C6C72281004根据matlab软件运行结果，求解得模型三中第一辆车总能装进1019.8cm的货物，与平板车长1020cm仅相差0.2cm。模型三中第二辆车的最终解C1C2C3C4C5C6C72515103根据matlab软件运行结果，求解得模型三中第二辆车总能装进1019.4cm的货物，与平板车长1020cm仅相差0.6cm。4结果分析经过以上三种模型求出的最优解，不难看出，一个问题可以有多种方案解决。对此，将各种方案以表格列示出来，进行对比分析。 模型结果对比表模型一：整体最优化（第一种理解）装载种类C1C2C3C4C5C6C7装载后的总厚度（cm）装载后的总重（kg）第一辆车6230004102028000第二辆车0525212102031500 合计204059500模型一：整体最优化（第二种理解）装载种类C1C2C3C4C5C6C7装载后的总厚度（cm）装载后的总重（kg）第一辆车07640001019.829000第二辆车80323321019.638000 合计2039.467000模型二：双目标决策装载种类C1C2C3C4C5C6C7装载后的总厚度（cm）装载后的总重（kg）第一辆车0525212102031500第二辆车6260004102028000 合计204059500模型三：个体车优化装载种类C1C2C3C4C5C6C7装载后的总厚度（cm）装载后的总重（kg）第一辆车22210041019.816500第二辆车25151031019.429500 合计2039.246000 从上表容易看出，要使第一辆车浪费空间最小，那么平板车可以装载包装箱的种C1,C2,C3,C4,C5,C6,C7分别为6，2，3，0，0，0，4，则通过验证得装载的总厚度为1020cm，刚好为装载车的长度，即第一辆车全部装满，且装载后第一辆车的载重量为28吨；接下来，在对第二辆车进行装载，但由于对第一辆车求出来的解，对第二辆车的装载有了更严格的条件约束，即在对装载第一辆车后，所剩下各类包装箱的数目有所改变，即C1,C2,C3,C4,C5,C6,C7分别为2，5，6，6，6，4，4。最后在通过，对第二辆车进行条件约束，从而求出使第二辆车浪费最小，那么平板车可以由包装箱的种类C1,C2,C3,C4,C5,C6分别为1，5，2，5，1，1，2，并且通过验证得装载的总厚度仍为1020cm，即第二辆车也能装满，且两辆车得总载量为29.5吨。 综上所述，两辆车都能装满，即没有浪费任何一点空间，且两辆车得总载量重量为57.5吨。 然后，在对模型二（整体最优1）所求得最优解进行分析。与模型一（个体最优）相比，模型二（整体最优1）则采用总体最优来考虑最优的装载方式。换句话说，就是第一辆车与第二辆车存在相互制约关系。并且，对包装箱的C5，C6，C7的这种规格的箱子所占的空间（厚度）不能超过302.7cm，理解为每一辆车的空间不超过302.7cm。载考虑在装载第一辆车的同时，不能忽略了第二辆车的存在，并且通过更为严格的约束条件去求解第一辆车与第二辆车的可以装载包装箱的种类分别为多少，即第一辆车:C1,C2,C3,C4,C5,C6,C7分别为6，2，3，0，0，0，4，则通过验证得装载的总厚度为1020cm,刚好为装载的长度，即第一辆车全部装满，且装载后第一辆车的载重为28吨。第二辆车：C1，C2，C3，C4，C5，C6，C7分别为0，5，2，5，2，1，2，通过验证得装载的总厚度为1020cm，刚好为装载的长度，即第二辆车全部装满，且两辆车的总载重为31.5吨。综上所述，两辆车都能装满，即没有浪费任何的一点空间，且两辆车的总载重量为59.5吨。随后，再对模型二（整体最优）方案进行分析模型二（整体最优）案则是再模型二（整体最优）方案的基础上进行了细微的修改，即对“装箱的C5,C6,C7的这些规格的箱子所占的空间（厚度）不能超过302.7cm”，理解为两辆车的总空间不超过302.7cm。这时所求出来的解为，即第一车：C1,C2,C3，C4，C5，C6,C7分别为0,7,6,4,0,0,0，则通过验证得装载的总厚度为1019.8cm，与第一辆的长度1020cm相差0.2cm，即浪费的空间为0.2cm且平板车的装载量为29吨；第二辆车：C1,C2,C3,C4,C5,C6,C7, 分别为8、0、3、2、3、3、0，则通过验证得装载量为29吨；第二辆车：C1、C2、C3、C4、C5、C6、C7分别为8、0、3、2、3、3、0，则通过验证得装载的总厚度为1019.6cm，与第二辆车的长度1020cm相差0.4cm，即浪费的空间为0.4cm，且装载后第二辆车的载重量为38吨。综上所述，综上所述，两辆车浪费的总空间为0.6cm，且两辆车的总在重量为67吨。再次，对模型三（双目标决策）进行分析，即在占用空间最大化的条件下，求解得载重量最大化。我们通过对目标函数的调整，求出其载重量的最大化。这时我们所求出来的解为，即第一辆车：C1、C2、C3、C4、C5、C6、C7分别为0、5、2、5、2、1、2，则通过验证得其装载量为31.5吨，第二辆车：C1、C2、C3、C4、C5、C6、C7分别为6、2、6、0、0、0、4，则通过验证得其载重量为28吨。与此同时，这时出来的解刚好与模型二（整体最优）所求的解刚好相反，即第一辆车与第二辆车装载包装箱的种类的数量数是相反的，由于这两个模型考虑的都是整体最优，所以其本质上是没有差别的。综上所述，通过对上述模型进行进一步优化，即双目标决策优化时，得出在占用空间最大化的条件下，所求得的总载重量为59.5吨，这就是经过改良和综合考虑下的最优解。最后，通过以上对比，不难看出，为使浪费空间最小，即装载总厚度达到最大值的条件下，可以采用模型一（个体最优）跟模型二（整体最优），排除模型二（整体最优）。当然，在忽略浪费总空间为0.6cm时，以最大载重量为考虑的最优的目标时，可以大胆的选择模型二（整体最优）：在浪费了0.6cm的厚度后，能够换来多出7500的载重，不失为一种更加理智的抉择，也更加显示了资源的合理优化配置。对此，模型三（双目标决策），能够在最大化利用空间的条件下载重量最大，显示了其无与伦比的优越性，故应该优先考虑模型三（双目标决策）。一、 模型评价与优化模型评价1） 该模型思路完整严密，通过两种主要的模型得出两种不同的最优方案，能够非常充分地利用空间，对比得出的空间最优并且载重最大方案，能够直接为铁道部门运输策略提供良好的数量关系。2） 该模型操作灵活便捷，能够彻底解决一维装箱问题。运用的lingo软件实用易操作，解题速度快速而精密。模型优化该模型完全适用于包装物长宽固定，且放置方式既定的一维装箱问题，然而对于二维装箱问题，三维装箱问题却无法适用。现实生活中常见的应该是三维装箱问题，对于构建此类更加复杂的模型建议采纳多箱型装箱问题禁忌算法设计。禁忌算法（Tabu Search ,TS）是一种扩展邻域、全局逐步寻优的启发式搜索方式，在搜索过程中利用禁忌表产生的记忆构成来寻找新的邻域，扩大搜索空间。与遗传算法、模拟退火算法等智能算法相比，TS有搜索速度快，“爬山“能力强等特点。二、 参考文献 （1）胡运权 主编 郭耀煌 副主编,，运筹学，清华大学出版社，2007年4月第3版 （2）J.Bartholdi，The Outstanding Railroad Flatcar Papers，Georgia Institute of Technology，v.9(1988) （3）谢金星和薛毅，优化建模与LINDO/LINGO软件，清华大学出版社,2005年7月1日 （4）韩中庚，数学建模方法及其应用，高等教育出版社，2005年6月三、 附件（lingo代码） (程序1)整体最优模型一代码：max=48.7*x1+48.7*y1+52*x2+52*y2+61.3*x3+61.3*y3+72*x4+72*y4+48.7*x5+48.7*y5+52*x6+52*y6+64*x7+64*y7;48.7*x1+52*x2+61.3*x3+72*x4+48.7*x5+52*x6+64*x7=1020;48.7*y1+52*y2+61.3*y3+72*y4+48.7*y5+52*y6+64*y7=1020;x1+y1=8;x2+y2=7;x3+y3=9;x4+y4=6;x5+y5=6;x6+y6=4;x7+y7=8;48.7*x5+52*x6+64*x7=302.7;48.7*y5+52*y6+64*y7=302.7;2*x1+3*x2+x3+0.5*x4+4*x5+2*x6+x7=40;2*y1+3*y2+y3+0.5*y4+4*y5+2*y6+y7=40;gin(x1);gin(x2);gin(x3);gin(x4);gin(x5);gin(x6);gin(x7);gin(y1);gin(y2);gin(y3);gin(y4);gin(y5);gin(y6);gin(y7);求解值Global optimal solution found. Objective value: 2040.000 Extended solver steps: 0 Total solver iterations: 5 Variable Value Reduced Cost X1 6.000000 -48.70000 Y1 1.000000 -48.70000 X2 2.000000 -52.00000 Y2 5.000000 -52.00000 X3 6.000000 -61.30000 Y3 2.000000 -61.30000 X4 0.000000 -72.00000 Y4 5.000000 -72.00000 X5 0.000000 -48.70000 Y5 1.000000 -48.70000 X6 0.000000 -52.00000 Y6 1.000000 -52.00000 X7 4.000000 -64.00000 Y7 2.000000 -64.00000 Row Slack or Surplus Dual Price 1 2040.000 1.000000 2 0.000000 0.000000 3 0.000000 0.000000 4 1.000000 0.000000 5 0.000000 0.000000 6 1.000000 0.000000 7 1.000000 0.000000 8 5.000000 0.000000 9 3.000000 0.000000 10 2.000000 0.000000 11 46.70000 0.000000 12 74.00000 0.000000 13 12.00000 0.000000 14 10.50000 0.000000（程序2）整体最优模型二代码：max=48.7*x1+48.7*y1+52*x2+52*y2+61.3*x3+61.3*y3+72*x4+72*y4+48.7*x5+48.7*y5+52*x6+52*y6+64*x7+64*y7;48.7*x1+52*x2+61.3*x3+72*x4+48.7*x5+52*x6+64*x7=1020;48.7*y1+52*y2+61.3*y3+72*y4+48.7*y5+52*y6+64*y7=1020;x1+y1=8;x2+y2=7;x3+y3=9;x4+y4=6;x5+y5=6;x6+y6=4;x7+y7=8;48.7*x5+48.7*y5+52*x6+52*y6+64*x7+64*y7=302.7;2*x1+3*x2+x3+0.5*x4+4*x5+2*x6+x7=40;2*y1+3*y2+y3+0.5*y4+4*y5+2*y6+y7=40;gin(x1);gin(x2);gin(x3);gin(x4);gin(x5);gin(x6);gin(x7);gin(y1);gin(y2);gin(y3);gin(y4);gin(y5);gin(y6);gin(y7);答案：Globaloptimalsolutionfound.Objectivevalue:2039.400Extendedsolversteps:65324Totalsolveriterations:115375VariableValueReducedCostX10.000000-48.70000Y18.000000-48.70000X27.000000-52.00000Y20.000000-52.00000X36.000000-61.30000Y33.000000-61.30000X44.000000-72.00000Y42.000000-72.00000X50.000000-48.70000Y53.000000-48.70000X60.000000-52.00000Y63.000000-52.00000X70.000000-64.00000Y70.000000-64.00000RowSlackorSurplusDualPrice12039.4001.00000020.20000000.00000030.40000000.00000040.0000000.00000050.0000000.00000060.0000000.00000070.0000000.00000083.0000000.00000091.0000000.000000108.0000000.000000110.60000000.0000001211.000000.000000132.0000000.000000（程序3）双目标决策代码：Max=2*x1+2*y1+3*x2+3*y2+x3+y3+0.5*x4+0.5*y4+4*x5+4*y5+2*x6+2*y6+x7+y7;48.7*x1+48.7*y1+52*x2+52*y2+61.3*x3+61.3*y3+72*x4+72*y4+48.7*x5+48.7*y5+52*x6+52*y6+64*x7+64*y7=2040;48.7*x1+52*x2+61.3*x3+72*x4+48.7*x5+52*x6+64*x7=1020;48.7*y1+52*y2+61.3*y3+72*y4+48.7*y5+52*y6+64*y7=1020;x1+y1=8;x2+y2=7;x3+y3=9;x4+y4=6;x5+y5=6;x6+y6=4;x7+y7=8;48.7*x5+52*x6+64*x7=302.7;48.7*y5+52*y6+64*y7=302.7;2*x1+3*x2+x3+0.5*x4+4*x5+2*x6+x7=40;2*y1+3*y2+y3+0.5*y4+4*y5+2*y6+y7=40;gin(x1);gin(x2);gin(x3);gin(x4);