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

两辆铁路平板车装货问题的讨论摘要本文鉴于对题中 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 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 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车，：分别表示C1C7的厚度（厘米）：分别表示C1C7的重量（吨）：分别表示C1C7在A车中装的件数：分别表示C1C7在B车中装的件数 （见模型三）(i=1,2,36,7)五、 模型建立 基于对题目中C5、C6、C7类包装箱总数的限制的不同理解，我们将从以下两种情况建立模型并求解一、 先考虑第一种情况，即本题中对C5、C6、C7类的包装箱总数的限制为同一辆铁路平板车上这类箱子所占的厚度不能超过302.7cm，则由题意可建立模型一：s.t用LINGO计算出一组基础解：C1C2C3C4C5C6C7twC5C7X6260004102028256Y0525212102031.5277.4对上述基础解进行变换:从条件中我们观察到t1=t5=48.7, t2=t6=52.0, 所以容易得到一个结论：C1与C5, C2与C6之间可以相互调换，只要保证总数不变，则同一辆车上箱子所占的总空间也不变，此时只要满足C5,C6,C7总空间限制和重量限制的条件，就是也是满足此模型的一组最优解。观察基础解可以分析得出：1.对A车： C1与C5、C2与C6不能有数量上的变化因为X5,X6均为0, 所以不能从C1-C5, C2-C6 方向调换，而这样会造成C5,C6,C7总空间的增加，即使空间增加最小的一个单位：256+48.7=304.7 已经超过302.7的限制，所以对于X解已经不能变换。2.对B车：C5-C1一单位C1C2C3C4C5C6C7twC5C7X6260004102028256Y1525112102028.5228.7C5-C1两单位 C1C2C3C4C5C6C7twC5C7X6260004102028256Y2525012102027.5180C2-C6一单位 不可以！因为C5C7超出302.7！C6-C2一单位 不可以！因为C2已经达到最多7件！C5-C1一单位 , C2-C6一单位C1C2C3C4C5C6C7twC5C7X6260004102028256Y1425122102028.5280.7C5-C1两单位,C2-C6一单位C1C2C3C4C5C6C7twC5C7X6260004102028256Y2425022102026.5232C5-C1两单位 ,C2-C6两单位C1C2C3C4C5C6C7twC5C7X6260004102028256Y2325032102025.5284浪费空间T=2040-1020x2=0cm , 我们将上述方法总结如下：由于t1=t5、t2=t6，C5-C1一单位引起重量减少2吨、同时C5C7的总空间减少48.7cm；C2-C6一单位引起重量减少1吨、同时C5C7的总空间增加52.0cm。所以这种变换只会让重量变小，只需考虑它对C5C7总空间的影响：设C5-C1 x个单位，C2-C6 y个单位，则有解得当(x，y)=（0，0）、(1，0)、(2，0)、(1，1)、(2，1)、(2，2)共六种情况时满足约束条件，均为模型一的最优解。此外，我们用VB编程计算，程序见（附录2）设14个循环变量，在A车满足约束条件的前提下，寻找B车满足约束条件，利用了计算机程序，效率大大提高，而且正确率也大大提高。得到六组最优解如下表所示（单位：件）表一：X1X2X3X4X5X6X7Y1Y2Y3Y4Y5Y6Y7162600040525212262600041525112362600042525012462600041425122562600042425022662600042325032两者结果完全一致，之前模型的建立以及分析思路的正确性得到了验证。二、 再考虑第二种情况，即本题中对C5、C6、C7类的包装箱总数的限制为两辆铁路平板车上这类箱子所占的总厚度不能超过302.7cm，则由题意可建立模型二：S.t用lingo计算出结果C1C2C3C4C5C6C7twC5C7A车X30913201019.931.5250.1B车Y57050101019.535.552最少总浪费空间T=2040-1019.9-1019.5=0.6cm , 这是一组最优解，但是lingo软件的局限性在于有多组最优解时只给出其中的一组最优解，而由t1=t5、t2=t6分析可以得到结论：此情况最优解不止一组，又由于A、B两车中没有一辆车的装载情况（即包装箱的组合方案）是确定的，所以第一种假设中所使用的C1与C5、C2与C6相互对换，从而产生所有解的方法不适用于第二种假设。对此，我们换一个思考角度：先确定两辆车上所装包装总长度的最优解，再将总长度分配到A、B两辆车上。通过对题目的仔细分析，我们得到一个结论：对任意一组最优解，两辆车的总包装箱种类和数量是确定的（即厚度和重量一定）证明：通过计算不难得出，C1C4包装箱厚度总长为1737.3cm，占用总空间最大为2040cm，C5C7三种包装箱总厚度不能超过2040-1737.3=302.7cm，这也正好符合题目要求。所以最优解必须使前四种包装箱全部用上（即厚度达到最大），后三种包装箱的厚度在满足约束条件下达到最大，对于后三种包装箱占用空间达到最大，我们建立模型三： s.t由lingo软件编写程序（见附录4）得到最优解：Z=302.1cm，此时c5=3,c6 =3,c7 =0再用反证法，假设C1C4包装箱没有全用上，则前四种包装箱的总厚度至多为1737.3-48.7=1688.6cm，而1688.6+302.7=1991.3cm，所以达不到最优解2039.4cm，所以C1C4包装箱必须全用上。证毕所以最优解时，两辆车的总厚度为2039.4cm，总重量为67吨，至此我们可以将模型二简化，仅考虑一辆车（如A车），它的总厚度至少为2039.4-1020=1039.4cm，至多为1020cm；它的总重量至少为67-40=27吨，至多为40吨；并且由模型三的结果得x5至多为3件，x6至多为三件，x7 =0，其余约束条件不变，于是得到简化后的模型四： s.t在满足这些约束条件之后把剩余部分装到B车上，B车也满足题目要求对于这个简化后的模型，我们可以用vb编程（见附录5）来实现，运行后结果共有60组，但考虑到模型假设3中忽略A、B车次的影响，应该把结果除以2，实际的结果共30种，见下表：表二：A车中B车中编号C1C2C3C4C5C6C7C1C2C3C4C5C6C7105640208232310206900308106300307640008032330407900208006310506640008132320614433307353000715433207253010816433107153020924432306353100102505330629100011254322062531101226432106153120132743210605313014309132057050101531913105605020163291300550503017344313053532001835052305291100193543120525321020360522051911102137431105153220223705210509112023374310050532302440533304743000254091220470511026419121046051202741533204643010284253310454302029429120045051303043533004443030以上30组最优解，最终两辆车浪费的总空间最少为0.6cm。六、 模型分析 对于假设一中我们建立的模型一：我们将题目的约束条件很直观地反映出来，使人容易理解和接受。并能利用多种方法通过该模型得到问题的最优解，再一次说明了模型一的正确性和适用性。对于假设二中建立的三个模型：模型二是最直观的，也能最完整地反映题目的本意，但求解起来存在一定难度。模型三对题目本身没有直接贡献，但能帮助求解模型二，起到了缩小范围的作用。模型四是简化后的模型二，即保留了原模型的直观性又变得更加容易实现，大大降低了直接求解模型二的计算复杂性，是一种较好的模型。七、 结论对于第一种理解即每辆车C5、C6、C7这类箱子所占的空间不超过302.7cm的情况，我们建立了模型一，得到6组最优解，两辆车浪费的总空间最少为0cm。对于第二种理解即两辆车C5、C6、C7这类箱子所占的总空间不超过302.7cm的情况，我们建立了模型二、模型三、模型四，最终得到30组最优解，两辆车浪费的总空间最少为0.6cm。八、 参考文献1赵静、但琦等，数学建模与数学实验，北京：高等教育出版社，2008。2刘焕彬、库在强等，数学模型与实验 ，北京：科学技术出版社，2008。附录附录1：max=48.7*(x1+y1)+52.0*(x2+y2)+61.3*(x3+y3)+72.0*(x4+y4)+48.7*(x5+y5)+52.0*(x6+y6)+64.0*(x7+y7);48.7*x1+52.0*x2+61.3*x3+72.0*x4+48.7*x5+52.0*x6+64.0*x7=1020;48.7*y1+52.0*y2+61.3*y3+72.0*y4+48.7*y5+52.0*y6+64.0*y7=1020;2*x1+3*x2+1*x3+0.5*x4+4*x5+2*x6+1*x7=40;2*y1+3*y2+1*y3+0.5*y4+4*y5+2*y6+1*y7=40;48.7*x5+52.0*x6+64.0*x7=302.7;48.7*y5+52.0*y6+64.0*y7=302.7;x1+y1=8;x2+y2=7;x3+y3=9;x4+y4=6;x5+y5=6;x6+y6=4;x7+y7=8;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);附录2：Private Sub Command1_Click() Dim i As Integer, j As Integer, k As Integer, l As Integer, m As Integer, n As Integer, p As Integer, q As Integer Dim sum1 As Single, sum2 As Single, sum3 As Single Dim st As String, a As Single, str As String Dim i2 As Integer, p2 As Integer, j2 As Integer, k2 As Integer, m2 As Integer, n2 As Integer, q2 As Integer Dim sum4 As Single, sum5 As Single, sum6 As Single For p = 0 To 8 For i = 0 To 7 For j = 0 To 9 For k = 0 To 6 For m = 0 To 6 For n = 0 To 4 For q = 0 To 8 sum2 = p * 2 + 3 * i + 1 * j + 0.5 * k + 4 * m + 2 * n + 1 * q sum1 = 48.7 * p + 52 * i + 61.3 * j + 72 * k + 48.7 * m + 52 * n + 64 * q sum3 = 48.7 * m + 52 * n + 64 * q If sum1 = 1020 And sum2 = 40 And sum3 = 302.7 Then st = p & & i & & j & & k & & m & & n & & q & & & sum1 & & sum2 & & sum3 List1.AddItem st For p2 = 0 To 8 - p For i2 = 0 To 7 - i For j2 = 0 To 9 - j For k2 = 0 To 6 - k For m2 = 0 To 6 - m For n2 = 0 To 4 - n For q2 = 0 To 8 - q sum5 = p2 * 2 + 3 * i2 + 1 * j2 + 0.5 * k2 + 4 * m2 + 2 * n2 sum4 = 48.7 * p2 + 52 * i2 + 61.3 * j2 + 72 * k2 + 48.7 * m2 + 52 * n2 + 64 * q2 sum6 = 48.7 * m2 + 52 * n2 + 64 * q2 If sum4 = 1020 And sum5 = 40 And sum6 = 302.7 Then str = p2 & & i2 & & j2 & & k2 & & m2 & & n2 & & q2 & & & sum4 & & sum5 & & sum6 & & st List2.AddItem str End If Next Next Next Next Next Next Next End If Next Next Next Next Next Next Next End Sub附录3：max=48.7*(x1+y1)+52.0*(x2+y2)+61