两辆铁路平板车的装货问题.doc

两辆铁路平板车的装货问题郁舒阳 ，刘冲 ，孙屹（河海大学）摘要 本文将铁路平板车的装载排列问题抽象为线性规划问题中的整数规划问题，经过合理的假设，建立了问题的最小化模型，然后分别通过Matlab软件和Lingo软件的解得的结果比较，得到了包装箱所占最大空间为2039.4cm（也即浪费的空间最小）。该模型简单直观，可推广应用于集装箱装货问题，仓库装货问题等相似领域。关键词 优化排列 整数规划 最大空间1. 问题的重述 有七种规格的包装箱要装到两辆铁路平板车上去。包装箱的宽和高是一样的，但厚度（t，以厘米计）及重量（w，以公斤计）是不同的。下表给出了每种包装箱的厚度、重量以及数量。每辆平板车有10.2米长的地方可用来装包装箱（像面包片那样），载重为40吨。由于当地货运的限制，对C5,C6,C7类的包装箱的总数有一个特别的限制：这类箱子所占的空间（厚度）不能超过302.7cm。试把包装箱装到平板车上去使得浪费的空间最小。 C1 C2 C3 C4 C5 C6 C7t(cm) 48.7 52.0 61.3 72.0 48.7 52.0 64.0w(kg) 2000 3000 1000 500 4000 2000 1000件数 8 7 9 6 6 4 82. 问题的分析 由于包装箱的宽和高是一样的，但厚度和重量是不同的额，所以在解决问题的过程中可以忽略包装箱的宽和高，而仅仅考虑包装箱的厚度、重量以及数量。并且在本问题中还对两辆车的容量（有10.2米长的地方可用来装包装箱），载重（40吨），对C5,C6,C7类的包装箱的总数的限制（厚度不能超过302.7cm），还有包装箱Ci的数量限制，使得本问题变为一个线性规划问题中的整数规划问题，从而使本问题的解决思路变得明朗起来。3. 模型的假设 1）不考虑包装箱之间的装配间隙。 2）不考虑包装箱的变形，即认为包装箱至始至终体积不变。 3）假设平板车能容纳包装箱的宽和高。 4）假设每种包装箱完全一样。 5）假设装箱过程中没有磨损，及认为包装箱至始至终质量不变。4. 模型的建立 先假设C1-C7放在第一个平板车上的数量分别为x1,x2,x3,x4,x5,x6,x7,放在第二个平板车上的数量分别为x8,x9,x10,x11,x12,x13,x14.根据对问题的分析，此问题为整数线形优化问题，其问题包装箱装到平板车上去使得浪费的空间最小，也就是平板车的空间利用率最高，即装载货物的总厚度最大（当然平板车有宽度限制，每辆车装载的货物的总厚度不可能无限的大，我们就决定将平板车的宽度限制作为约束条件，在后面详述）基于此，目标函数为48.7*x1+52.0*x2+61.3*x3+72.0*x4+48.7*x5+52.0*x6+64.0*x7+48.7*x8+52.0*x9+61.3*x10+72.0*x11+48.7*x12+52.0*x13+64.0*x14;从而问题就归结为求目标函数的最大值。 再来分析题目的其它条件及优化条件，根据题目，每件货物的数量是有限制的，C1货物总共有8件，其约束条件可写为x1+x8=8,C2货物总共有7件，其约束条件可写为x2+x9=7.同理对于C3:x3+x10=9;C4:x4+x11=6;C5:x5+x12=6;C6:x6+x13=4;C7:x7+x14=8.又因为每辆车的宽度一定都为10.2米，且都有限重40吨，所以装载到每辆车上的货物总厚度不能超过10.2米，每辆车上的货物总质量不能超过40吨，因此可以列出约束条件： 48.7*x1+52.0*x2+61.3*x3+72.0*x4+48.7*x5+52.0*x6+64.0*x7=1020; 48.7*x8+52.0*x9+61.3*x10+72.0*x11+48.7*x12+52.0*x13+64.0*x14=1020; 2*x1+3*x2+x3+0.5*x4+4*x5+2*x6+x7=40; 2*x8+3*x9+x10+0.5*x11+4*x12+2*x13+x14=40; 由于题目中对C5,C6,C7类的包装箱的总数有一个特别的限制：这类箱子所占的空间（厚度）不能超过302.7cm。因此这三种货物装载到两辆平板车上的总厚度应小于302.7厘米，即列出的约束条件为48.7*x5+52.0*x6+64.0*x7+48.7*x12+52.0*x13+64.0*x14=302.7。 综上，就将问题的求解解读为最优化问题的求解，其目标函数为：max=48.7*x1+52.0*x2+61.3*x3+72.0*x4+48.7*x5+52.0*x6+64.0*x7+48.7*x8+52.0*x9+61.3*x10+72.0*x11+48.7*x12+52.0*x13+64.0*x14; 约束条件为：x1+x8=8;x2+x9=7;x3+x10=9;x4+x11=6;x5+x12=6;x5+x13=4;x7+x14=8;48.7*x1+52.0*x2+61.3*x3+72.0*x4+48.7*x5+52.0*x6+64.0*x7=1020;48.7*x8+52.0*x9+61.3*x10+72.0*x11+48.7*x12+52.0*x13+64.0*x14=1020;2*x1+3*x2+x3+0.5*x4+4*x5+2*x6+x7=40;2*x8+3*x9+x10+0.5*x11+4*x12+2*x13+x14=40;48.7*x5+52.0*x6+64.0*x7+48.7*x12+52.0*x13+64.0*x14=302.7;5. 模型的求解对于这个问题的求解，我们先运用了Matlab软件中的Yalmip工具箱，代码如下：f=-48.7 -52.0 -61.3 -72.0 -48.7 -52.0 -64.0;-48.7 -52.0 -61.3 -72.0 -48.7 -52.0 -64.0;A=1 0 0 0 0 0 0 1 0 0 0 0 0 0; 0 1 0 0 0 0 0 0 1 0 0 0 0 0; 0 0 1 0 0 0 0 0 0 1 0 0 0 0; 0 0 0 1 0 0 0 0 0 0 1 0 0 0; 0 0 0 0 1 0 0 0 0 0 0 1 0 0; 0 0 0 0 0 1 0 0 0 0 0 0 1 0; 0 0 0 0 0 0 1 0 0 0 0 0 0 1;48.7 52.0 61.3 72.0 48.7 52.0 64.0 0 0 0 0 0 0 0;0 0 0 0 0 0 0 48.7 52.0 61.3 72.0 48.7 52.0 64.0 ;2 3 1 0.5 4 2 1 0 0 0 0 0 0 0;0 0 0 0 0 0 0 2 3 1 0.5 4 2 1 ;0 0 0 0 48.7 52.0 64.0 0 0 0 0 48.7 52.0 64.0;b=8 7 9 6 6 4 8 1020 1020 40 40 302.7;xm=0 0 0 0 0 0 0 0 0 0 0 0 0 0;p=intvar(14,1);g=f*p;F=set(A*p=b)+set(xmss=p);Sol=solvesdp(F,g);p=double(p)运行结果如图：接着，我们为验证结果的准确性与合理性，我们又运用了Lingo软件，代码如下：MODEL:max=48.7*x1+52.0*x2+61.3*x3+72.0*x4+48.7*x5+52.0*x6+64.0*x7+48.7*x8+52.0*x9+61.3*x10+72.0*x11+48.7*x12+52.0*x13+64.0*x14;x1+x8=8;x2+x9=7;x3+x10=9;x4+x11=6;x5+x12=6;x5+x13=4;x7+x14=8;48.7*x1+52.0*x2+61.3*x3+72.0*x4+48.7*x5+52.0*x6+64.0*x7=1020;48.7*x8+52.0*x9+61.3*x10+72.0*x11+48.7*x12+52.0*x13+64.0*x14=1020;2*x1+3*x2+x3+0.5*x4+4*x5+2*x6+x7=40;2*x8+3*x9+x10+0.5*x11+4*x12+2*x13+x14=40;48.7*x5+52