两辆铁路平板车装货问题讨论.docxVIP

两辆铁路平板车装货问题的讨论 摘要 本文鉴于对题中" C5,C6,C7类的包装箱的总数的特别的限制：这类箱子所占的空间（厚度）不能超过302.7cm"的不同理解，分对一辆车上C5,C6,C7类的包装箱的总数限制和两辆车上的总数限制两种情况讨论，分别得出了各自情况下的满足题意的最优方案。 对一辆车上C5,C6,C7类的包装箱的总数限制情况，为整数线性规划问题，建立模型一，并用LINGO求的最优解（仅为多组解中一组），用枚举法得出了6组（见表一），最优解为两辆车浪费总空间为0cm。并用VB验证模型一的建立以及分析思路的正确性。 对两辆车上C5,C6,C7类的包装箱的总数限制情况，仍为整数线性规划问题，建立模型二，并用LINGO求的最优解（仅为多组解中一组），两辆车浪费的总空间为0.6cm。同时我们发现规律：所有最优解必须满足前四种包装箱厚度达到最大（即全部用上），后三种包装箱的厚度在满足约束条???下达到最大。对于后三种包装箱占用空间达到最大的问题，我们通过建立模型三，并应用LINGO求得新约束条件 c5 =3,c6=3, c7=0，两辆车的总厚度为2039.4cm，总重量为67吨。由此，可得到简化的A车上装货情况，即模型四，满足约束条件之后把剩余部分装到B车上，B车也满足题目要求，用VB求得30组最优解（见表二），大大提高了计算速度，克服了枚举法的效率低下。 关键词：整数线性规划 LINGO 最优化 VB 平板车装货 问题重述 有七种规格的包装箱要装到两辆铁路平板车上去。包装箱的宽和高是一样的，但厚度（t，以厘米计）及重量（w，以公斤计）是不同的。下表给出了每种包装箱的厚度、重量以及数量。每辆平板车有1020cm的地方可用来装包装箱（像面包片那样），载重为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 问题分析 通过读题我们不难得出此题属于整数型线性规划问题，由题目中给出的条件,我们可以算出货物的总重量为89吨，而两辆车的载重量为80吨，所以必然不能将货物全部装载完，也就是说必然会有货物剩余。我们假设平板车上只能放一排包装箱，且包装箱之间间隙忽略不计。对于题目中所说的对C5,C6,C7类包装箱的总数的特别限制我们有两种理解：一种是对于每辆车而言，车上C5,C6,C7类包装箱的总空间不超过302.7cm，另一种是对于两辆车而言，C5,C6,C7类包装箱的总空间不超过302.7cm。由此，我们打算分别对这两种情况建立模型，并利用LINGO解出该整数型线性规划的最优解。考虑到变量较多以及变量权值的特殊性，我们猜想对每种情况都可能存在多组最优解。我们准备先利用lingo软件解出一组最优解作为基础解，再根据t1=t5、t2=t6的关系，枚举讨论得出其余最优解。对于第一种假设手工假设的方法完全适用，对于第二种假设我们发现用这种方法有很大的局限性，于是我们换一种思维先确定两辆车的总数，再具体分配到每辆小车，以此来缩小题中变量的约束条件范围，再利用VB等高级语言编程找出满足条件的所有最优解。 模型假设 每辆平板车上只能装载一排的包装箱，不存在并排或者叠加等情况 包装箱之间的间隙可忽略不计 不考虑方案不同仅仅是AB车车次相互交换的情况 不考虑一辆车上同一种包装箱组合方案的不同排列 在重量符合要求的情况下，不考虑两车重量差别大小对最优解的影响 符号系统 假设两辆车分别为A车和B车， ：分别表示C1~C7的厚度（厘米） ：分别表示C1~C7的重量（吨） ：分别表示C1~C7在A车中装的件数 ：分别表示C1~C7在B车中装的件数 （见模型三） (i=1,2,3…6,7) 模型建立 基于对题目中C5、C6、C7类包装箱总数的限制的不同理解，我们将从以下两种情况建立模型并求解 先考虑第一种情况，即本题中对C5、C6、C7类的包装箱总数的限制为同一辆铁路平板车上这类箱子所占的厚度不能超过302.7cm，则由题意可建立模型一： s.t 用LINGO计算出一组基础解： C1C2C3C4C5C6C7twC5~C7X6260004102028256Y