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

两辆铁路平板车的装货问题的研究 摘要：针对将七种规格的包装箱要装到两辆铁路平板车上问题，我们将其转化为求解多个n元一次不等式最优解的数学模型，通过穷举法，利用计算机VB高级语言实现。在程序的编译过程中，我们增加了约束条件、减少了可以避免的计算量，加快了程序计算速度。最终得出了满足题目要求的6组等价最优解。 关键词：装货问题； n元一次不等式； 穷举法； VB； 最优解 问题重述 有七种规格的包装箱要装到两辆铁路平板车上去。包装箱的宽和高是一样的，但厚度（t，以厘米计）及重量（w，以公斤计）是不同的。下表给出了每种包装箱的厚度、重量以及数量。每辆平板车有10.2米长的地方可用来装包装箱（像面包片那样），载重为40吨。由于当地货运的限制，对C5,C6,C7类的包装箱的总数有一个特别的限制：这类箱子所占的空间（厚度）不能超过302.7cm。试把包装箱装到平板车上去使得浪费的空间最小。 C1 C2 C3 C4 C5 C6 C7 t(cm) 48.7 52.0 61.3 72.0 48.7 52.0 64.0 w(kg) 2000 3000 1000 500 4000 2000 1000 件数 8 7 9 6 6 4 8 问题分析 题中要求把包装箱装到平板车上去使得浪费的空间最小的所有情况做出解答。题目本身表述有些不清楚，例如包装箱的装载可否上下重叠、装载一次还是多次、是否要将所有包装箱全部装完等问题都没有表述清楚。 针对题目给定的三个约束条件（每辆车上的包装箱总长小于或等于10.2米、每辆车上的包装箱总质量小于或等于40吨、C5,C6,C7类的包装箱的总长不能超过302.7厘米），可以得出三个不等式。再结合实际情况等一些约束条件，得出其他一些不等式。通过穷举法并结合计算机软件得出符合上述条件的可能解，他们之间再相互比较，取最大利用率者即为所求最优方案。 模型假设 假设包装箱在平板车上只能排列一层，不能重叠摆放。 两辆平板车只运输一次，使两辆平板车浪费的空间总和最小。 平板车上的包装箱之间的空隙不计。 假设包装箱装载到平板车的过程中没有挤压。 不考虑一次运输过程的长度损失和质量量损失。 符号系统 ：某一辆平板车上的第i种规格的包装箱的件数。 ：第一辆平板车上的第i种规格的包装箱的件数。 ：第一辆平板车上的第i种规格的包装箱的件数。 ：第i种规格的包装箱的总件数。 ：第i种规格的包装箱的厚度（cm）。 ：第i种规格的包装箱的质量（kg）。 模型建立 由题目给定的三个约束条件可以得出三个不等式： 结合实际情况，“能装则装”的原则，可以计算出至少装15件。可得不等式： 另外，为了达到最大空间利用率，每辆平板车至少满足下列两个条件之一：1.每辆平板车的剩余空间不超过各类规格包装箱的最大厚度； 2.每辆平板车的最大剩余载重量不超过各类规格包装箱的最大质量。 根据以上约束条件，再结合两辆车同时装载的情况，通过穷举法与比较法，取两辆车利用率之和的最大者即为所求最优解。 五、模型求解 根据以上约束条件，编写VB程序（详见两辆铁路平板车的装货问题的研究算法）。遍历各规格包装箱的每种可能情况，共（）=1587000中组合情况。通过进行约束条件的判断，得出27748种符合约束条件的情况。然后任取上述情况中的两种（包括两种相同的情况），并且保证取遍所有的可能情况。之后判断每一种可能情况中是否满足一下条件： 然后在满足条件的所有可能情况中取的最大者即为所求结果。（计算方法详见两辆铁路平板车的装货问题的研究算法） 第一辆车 第二辆车 C1 C2 C3 C4 C5 C6 C7 C1 C2 C3 C4 C5 C6 C7 第一种情况 0 5 2 5 2 1 2 6 2 6 0 0 0 4 第二种情况 1 4 2 5 1 2 2 6 2 6 0 0 0 4 第三种情况 1 5 2 5 1 1 2 6 2 6 0 0 0 4 第四种情况 2 3 2 5 0 3 2 6 2 6 0 0 0 4 第五种情况 2 4 2 5 0 2 2 6 2 6 0 0 0 4 第六种情况 2 5 2 5 0 1 2 6 2 6 0 0 0 4 空间利用率 100% 模型分析 不加实际约束条件，某辆车符合条件的可能情况超过10万多。在加上一系列的约束条件可能情况被压缩到27748种。尽管比起原先的10万多已经缩小了很多，但是计算量依旧很庞大，导致计算速度还是很慢（大约四分钟）。 然而该模型的算法