数学建模排版模板.doc

福州大学数学建模比赛二维同一规格货物的集装箱堆放模型 学 院：物理与信息工程学院专 业：数理综合班年 级：2011级姓 名：（ 111100537） 韩丽娜（队长） （ 111100534） 何 秀 （ 111100736） 曾素云 联系方式韩丽娜） 二维同一规格货物的集装箱堆放模型摘要集装箱，作为现代物流的主导载体，给世界散杂货运输带来了一场革命。集装箱运输具有装卸效率高、适用于多种运输方式、可减少货差及货损、以及便于管理等优势，适应了全球经济一体化对运输发展的客观要求，在全球运输领域内得以迅速发展。近年来随着我国成为世界工厂进程的加快，制造业物流迅速攀升。中国已成为世界集装箱运输发展最为活跃的地区。集装箱的问题研究，其中包括集装箱装箱时体积、时间、重量最优化，所以关于集装箱箱子的摆放策略的研究很有意义。集装箱问题是一个具有复杂约束条件的优化组合问题，针对集装箱装载问题，要使其效率最大化，要在满足约束条件的前提下，使目标函数达到极值。从而选取出最佳的堆放方式。问题1，在同一规格的箱子下，首先考虑箱子不能超出叉车底板， 也不允许箱子相互重叠的约束条件，所以要先对集装箱上装载的箱子与底板的长宽之间的数学关系讨论，通过一些二维数学关系的研究与确立和可行模型的建立以及最佳模型的选择，逐步建立起用于箱子摆放数量最多的优化模型，用此模型对题中三组数据进行了求解并进行了清晰、详尽的检验与评价。问题2中，结合问题一的优化模型，考虑箱子的密度都是均匀，允许箱子在正方形底板的上方，左边，右边部分超出底板（下方紧靠叉车壁，不能超出），但不至于掉落出叉车底板。通过底板外围堆放宽朝外一半悬空的箱子让利用的叉车底板以外的面积达到最大，剩下的底板面积用类似问题一的方法求解。问题3中，从另一个角度出发，在问题一堆放的基础上，考虑将边缘的箱子一半悬空，抽象成底板的各边长宽都发生了改变，重用问题一的算法对该问题进行求解。得到另一种解决方案，对比两种方法的优劣。关键词 lingo、约束条件、优化模型一、问题重述某省内知名企业生产的产品用形状为长方体的箱子包装，使用叉车将这些箱子从生产车间运输至仓库。这些箱子叠放在叉车的正方形底板上，如下图所示， 叉车置放箱子的底板是一个边长为1.1米的正方形。箱子的规格是统一的（所有箱子的长方形底面的尺寸相同）。通常在一次运输中，箱子像下图中这样横着放，或者竖着放。下图所示的便是一种可行的摆放方法，但不一定是最优的。现在这家企业需要你们帮助建立一个通用的优化模型，使得给定长方形箱子的长和宽之后，利用这个模型就能算出该如何摆放箱子（不需考虑箱子的高度，即只考虑摆放一层箱子），才能使得一次摆放的箱子数量最多。问题1 如果不允许箱子超出叉车底板（如上图所示情形）， 也不允许箱子相互重叠， 建立一个优化模型，考虑如何摆放这些箱子，才能使摆放的箱子数量最多? 利用你们构建的模型，分别计算出对于下表中型号1、型号2和型号3的箱子，最多可以摆放多少个？该如何摆放？如果你们能画出摆放示意图，那么将有助于这家企业更快地理解你们的方法。 长（米）宽（米）箱子型号1 0.30.24箱子型号20.6 0.4箱子型号30.3 0.2问题2 假设箱子的密度都是均匀的，允许箱子在正方形底板的上方，左边，右边部分超出底板（下方紧靠叉车壁，不能超出），但不至于掉落出叉车底板。对于这种情况，重新建立优化模型,并针对上表中三种型号的箱子, 分别计算最多可以摆放多少个箱子？该如何摆放? 画出摆放示意图。问题3 在不允许箱子相互重叠的条件下，你们是否还能另外设计出一种摆放方案？并将你们设计的方案与上图中的摆放方案的优劣性进行比较。设计这样一个模型需要注意：（1） 箱子堆放模型与算法必须利于程序的实现。（2） 应该从实际情况出发考虑，满足该企业的需求。二、问题分析问题中包含三个小问，但实质上讨论的是建立模型解决同一规格货物集装箱装载时的最大化空间利用率问题。分析知，问题1是多个约束条件下的的集装箱装载问题；问题2在问题1的基础上考虑箱子密度都是均匀，箱子堆放除叉车壁外其余三边都能超出但不能掉落的情况；问题3在前两个问题的基础上再进一步研究另一种堆放模型。三个问题紧密相连在同一个构型框架下，针对不同的问题加以分析。分析二维集装箱问题一般是从一维情况分析计算出一维最佳堆放的方法。也即企业在选择集装箱转载时都希望找到一种满足堆放箱子数量最多的方法。在一维堆放的基础上构建二维模型，用此模型对题中三组数据进行了求解并进行了清晰、详尽的检验与评价。从而给企业做出最佳选择提供一个参考。三、模型假设（1） 假设箱子堆放时互不叠压，尽可能最紧密且箱子不发生挤压变形。（2） 定位集装箱方位，假设正方形叉车板的下方为叉车壁。（3） 货物可以放在集装箱的任意位置，货物的摆放必须与叉车四边平行或正交而不能斜放。（4） 对于箱子密度均匀时，箱子的重心与几何中心重合，假设当箱子的重心在底板边上箱子不掉落。（5） 箱子堆放时采用先沿边缘放置，再底板中心填放的原则。（6） 不考虑装箱货物的总重量是否在叉车的承受范围之内，也就是说只要空间允许可以无限制堆放。四、符号说明L 叉车板底板长W 叉车板底板宽a 箱子长度b 箱子宽度e 代表在下边长L上放置的a边数量f代表在下边长L上放置的b边数量m 代表在右边长W上放置的a边数量n 代表在右边长W上放置的b边数量k 代表在上边长L上放置的a边数量t 代表在上边长L上放置的b边数量p 代表在左边长W上放置的a边数量q 代表在左边长W上放置的b边数量x模型二中外围长度L边上放置的b边的数量y 模型二中外围长度W边上放置的b边的数量sum1 叉车板外围能堆放的箱子数目sum1Z 堆放的箱子数量剩余未说明的符号在各模型中定义五、模型的建立与求解5.1 问题1模型的建立与求解先从一维优化方案研究，该问题可以这样描述：设给定整数L和一组数A（a,a,a）0aL i(1,2,n),经计算满足:使得L-的值能够最小。针对矩形的一条L边上放置了i个a边和j个b边，则ia+jbL同时力求L-ia-jb的余数最小。如下图所示：Lb*ja*i L一维优化堆放图进而考虑二维情况，根据一维的分析结果推广到二维，二维装箱问题可以描述为：给定集装箱长为L、宽W，如何摆放长为a、宽为b的小矩形货物，使得装填数量n最大，即：L*W-最小。如下图所示：同样，根据给出的模型，e、k和f、t分别代表在长边L上放置的a边和b边数量，m、p和n、q分别代表在边W上放置a边和b边数量，问题要求在叉车板上堆放箱子数量最多，等价于堆放所占的空间最大，所以目标函数为 MAX Z=e*q+f*m+k*n+p*t有如下约束条件：(1)L-be*a+f*bL(2)W-bm*a+n*bW(3) L-bk*a+t*bL(4)W-bp*a+q*bW(5)(e+k)*a-La(6)(p+m)*a-WL, 则(q+n)*bW, 则(f+t)*bL, 则(m+p)*aW, 则(e+k)*aL(11)自然约束e、k、f、t、m、p、n、q都为非负整数。采用lingo编译算法，带入问题中的三组数据可得到结果如下：箱子型号1：a=0.3,b=0.24堆放模型如下图1所示 图1其中，e=2,q=2,f=2,m=2,n=2,k=2,t=2,p=2此时满足约束条件下，最多总共能堆放16个箱子。箱子型号2：a=0.6，b=0.4堆放模型如下图2所示 图2其中e=1,q=1,f=1,m=1,n=1,k=1,t=1,p=1此时满足约束条件下，最多总共能堆放4个箱子箱子型号3：a=0.3，b=0.2堆放模型如下图3所示 图3其中e=3，q=1，f=1，m=1，n=4，k=1，t=4，p=3此时满足约束条件下，最多总共能堆放20个箱子。5.2问题2模型的建立与求解本题箱子的密度都是均匀的，允许箱子在正方形底板的上方，左边，右边部分超出底板（下方紧靠叉车壁，不能超出），但不至于掉落出叉车底板。箱子的重心即为几何中心，所以保持箱子的重心刚好在叉车板的边上。在这想法的基础上，假设在叉车版的上方，左边，右边上箱子超出的长度为a/2。同样x代表长边L上放置的b边数量，表达式为x=(L-a)/b，y代表宽边W上放置的b边数量,表达式为y=W/b+0.5，左右两边外围放置的b边数量相等。此时可认为长L=L+a，W=W+b/2，先计算叉车板外围能堆放的箱子数目sum1，sum1=W/b+0.5*2+(L-a)/b。然后在第二圈里面堆放箱子。第二圈部分的长为L=L-a，宽为W=W-b/2，同样根据问题1建立的模型，e、k和f、t分别代表在长边L上放置的a边和b边数量，m、p和n、q分别代表在边W上放置a边和b边数量。当e=0或q=0时，在长边L上放置的a边数量为零，在边W上放置b边的数量为零。要求在第二圈叉车板上堆放箱子数量最多，等价于堆放所占的空间最大，所以目标函数为MAX Z=e*q+f*m+k*n+p*t有如下约束条件：(1) L-be*a+f*bL(2) W-bm*a+n*bW(3) L-bk*a+t*bL(4) W-bp*a+q*bW(5)（e+k）*a- La(6)(p+m)*a- W L,则(q+n)*b W,则(f+t)*b L,则(m+p)*a W,则(e+k)*a L(11)自然约束e、k、f、t、m、p、n、q都为非负整数。采用lingo编译算法，带入问题中的三组数据课得到结果：箱子型号1：a=0.3,b=0.24堆放模型如下图4所示 图4如图4，此时先把叉车板外围先堆放，左右两边W各有5个b边的箱子，上方长边L有3个b边的箱子，即x=3，y=5,sum1=13。第二圈内堆放箱子，此时e=2,q=0,f=0,m=1,n=2,k=0，t=3，p=3此时满足约束条件下，最多总共能堆放22个箱子箱子型号2：a=0.6,b=0.4堆放模型如下图5所示 图5如图5，此时先把叉车板外围先堆放，左右两边W各有3个b边的箱子，上长边L有1个b边的箱子，即x=1，y=3，sum1=7。第二圈内堆放箱子，此时e=0,q=1,f=1,m=1,n=0,k=0,t=1,p=0此时满足约束条件下，最多总共能堆放8个箱子箱子型号3：a=0.3,b=0.2堆放模型如下图6所示 图6如图6，此时先把叉车板外围先堆放，左右两边W各有6个b边的箱子，上长边L有4个b边的箱子，即x=4，y=6，sum1=16。第二圈内堆放箱子，此时e=0,q=3,f=4,m=3,n=0,k=2，t=0，p=1此时满足约束条件下，最多总共能堆放28个箱子5.3问题3模型的建立与求解本题要求在不允许箱子相互重叠的条件下，设计出另外一种摆放模型。经过问题1与问题2模型的求解，可以从问题2 中的思考方式出发，即保持箱子的重心刚好在叉车板的边上。令e、k、f、t、m、p、n、q都为大于等于1的整数。假设在叉车版的上方k个a边箱子都超出b/2，t个b边箱子都超出a/2；左边p个a边箱子都超出b/2，q个b边箱子都超出a/2；右边上m个a边箱子都超出b/2，n个b边箱子都超出a/2。此时叉车板长可看为L=L+a/2+b/2，叉车板左边宽可看为W=W+a/2，右边宽可看为W=W+b/2。然后在问题1所给出的模型基础上， e、k和f、t分别代表在长边L上放置的a边和b边数量， p和q分别代表在边W上放置a边和b边数量，m和n分别代表在边W上放置a边和b边数量。要求在叉车板上堆放箱子数量最多，等价于堆放所占的空间最大，所以目标函数为MAX Z=e*q+f*m+k*n+p*t有如下约束条件：(1) L-be*a+f*bL(2) W-bm*a+n*bW(3) L-bk*a+t*bL(4) W-bp*a+q*bW(5)（e+k）*a-(L+a)a(6)(p+m)*a-(W+a/2)L+a, 则(q+n)*bW+a/2, 则(f+t)*bL+b, 则(m+p)*aW+b/2, 则(e+k)*al-b;a*E+b*Fl-b;a*K+b*Tw-b;a*M+b*Nw-b;a*P+b*Q=w;(E+K)*a-la;(P+M)*a-wa;l=if(M+P)*a#gt#w,G,qq);w=if(E+K)*a#gt#l,R,pp);w=if(f+t)*b#gt#l,d2,dd);l=if(n+q)*b#gt#l,c2,cc);(Q+N)*bR;(e+k)*bC2;(F+T)*bG;(m+p)*bl-b;a*E+b*Fl-b;a*K+b*Tw-b;a*M+b*Nw-b;a*P+b*Q=w;(E+K)*a-la;(P+M)*a-wa;l=if(M+P)*a#gt#w,G,qq);w=if(E+K)*a#gt#l,R,pp);w=if(f+t)*b#gt#l,d2,dd);l=if(n+q)*b#gt#l,c2,cc);(Q+N)*bR;(e+k)*bC2;(F+T)*bG;(m+p)*bl3-b;a*E+b*Fl3-b;a*K+b*Tw32-b;a*M+b*Nw31-b;a*P+b*Q