1988B铁路货车问题赵轶星大学生数学建模竞赛.docx

1988B铁路货车问题赵轶星大学生数学建模竞赛.docx

《1988B铁路货车问题赵轶星大学生数学建模竞赛.docx》由会员分享，可在线阅读，更多相关《1988B铁路货车问题赵轶星大学生数学建模竞赛.docx（5页珍藏版）》请在冰点文库上搜索。

1988B铁路货车问题赵轶星大学生数学建模竞赛

1988B：

铁路货车问题

两个铁路货车要装载七种类型的货箱。

这些货箱有一样的宽度和高度，但是它们的厚度（

，以cm作单位），和重量（

，以kg作单位）不同。

图1给出了每个货箱的厚度重量和数量。

每个车有10.2米的长度来装载货箱（像一片吐司），并且可以承受最大40公吨的重量。

因为随后的当地货车的限制，货箱

、

和

有些特别的约束：

它们占据的空间（厚度）总和不能超过302.7cm。

装载这两个铁路货车（见图1）使得浪费的空间最小。

表1.

每个种类的的货箱的厚度、重量和数量

图1.铁路货车装载图

装载两个铁路货车

摘要

这篇论文讨论了在重量、长度和当地货车规定的约束下，对一样长度和宽度但不同厚度、重量的货箱装入两量铁路货车的最优化方法。

我们目标是最小化没有使用的和被浪费的轨道车上的地面空间。

首先，我们比较解决整数线性规划问题的平面切割法和枚举法。

我们决定使用一个叫Krolak边界值法的枚举法，它通过改进变量的范围限制来减少可行解的数量。

然后我们通过观察到使用少于前四个货箱的最大分配量的方法不可能是最优解，因此我们减少了必须研究的组合的数量。

接着，我们把想法组合成算法，使用它来找到问题的最优解。

我们发现，两车浪费空间的最小值为6.0mm。

这个相同的最优化值可以由35种不同的解集得到。

此外，我们总结分析了我们假设的有效性。

我们讨论了我们模型的扩展。

包括它的速度和补足。

我们还总结了分析中的误差和敏感度。

问题重述

给我们的问题是找到一个装载不同重量、厚度和数量的货箱的最优化方法。

货箱的详述在图1中。

轨道车的物理上的限制使得装载方法有约束。

每个车只能有10.2m的可装载空间和只能承受40公吨的重量。

并且，当地的货车约束限制了货箱5、6和7的空间总和最大只能为302.7cm

图1

假设

1）货箱之间没有空隙。

2）给我们的数据是准确的，并且没有包含内在误差。

3）货箱不能被分开成为更小的部分。

4）货箱不能被悬挂在轨道车的尾部。

5）我们确定的任何方案都可以用来装载和卸载。

6）我们不需要使用每一个类型的的货箱。

问题调整

因为所有的约束和目标方程都是线性的，并且约束是不等式，因此这个问题适用于线性规划问题。

这个简单的方法是被广泛接受的解决线性最优化问题的方法。

这个方法找到了实数的解，但我们要的是整数解，因为货箱不能被切开和分开。

因此，我们把这个问题当成一个整数线性规划问题。

符号定义

=类型i的货箱在车j的数量，i∈{1,2,3,4,5,6,7}，j∈{1,2}

=类型i的货箱可用的数量

=类型i的货箱的重量

=类型i的货箱的厚度

=浪费的空间

问题陈述

作为一个整数线性规划问题，模型最好被写写成下面的形式：

最小化S，其中

约束条件为

是整数

两个主要的解决整数线性规划问题的方法是平面切割法和枚举法。

对这两种方法的比较表明了枚举法更加符合我们的需要。

平面切割法在它得到最优解之前不会产生任何整数解，因此，会否定可以接受的“一个合理的”方案。

并且，平面切割法在得到第一个最优解时就停止了：

它不会继续搜索其他的可能一样正确的解。

另一方面，枚举法能在给出可行解后会继续搜索更好的解。

并且，枚举法在少于1000个变量的问题里都是适用的。

因为有限数量的可行整数解释存在的，我们可以尝试所有可能的组合（但是一共有2,520,473,760,000个）。

相反地，我们设计了一种方法去除了那些明显不可行或不是最优的组合。

这个方法是枚举法的一种形式，叫边界值法。

我们的减少我们需要研究的值的数量的算法依靠几个问题的临界特征。

首先，每个变量都有上边界和下边界。

每个变量的上边界是货箱的最大数量，下边界是零。

第二，目标函数是用最小化问题来规划，但是和用最大化问题规划一样简单。

问题可以被表示成目标函数的系数和所有约束矩阵的系数都是非负数的形式。

这个允许我们使用Krolak边界值算法的简化法来减少每个

的可行区间。

我们是根据一个分叉树对每个变量的求值的，它的每一层代表一个变量。

这个分叉的概念包括了对称地把一个可能的解集转到另一个解集上。

我们的求值从

开始，然后

，然后到

，以此类推到

，一共14层。

为了表示的方便和解释的清晰，我们用分叉层对变量重新命名：

，例如

；

。

在一个普通节点发出的所有顶点（在前辈产生的所有继承者中），继承者会以

的值递减的方式进行测试。

一旦一个顶点在最底层完成求值了，我们回溯到一个我们没有测试的继承者。

见图1。