箱子的摆放问题数学建模

箱子的摆放问题数学建模

循环嵌套式算法线性加权评价

箱子的摆放策略循环嵌套式算法线性加权评价

摘要

本文针对箱子的摆放的优化铺设问题，采用了循环嵌套式算法，建立了利用率最优化的整数规划模型，使用LINGO、MATLAB求解，并用Excel进行画图，实现了箱子最优摆放与评价。对于问题一，建立在不允许箱子超出底边的情况下，所能摆放最多箱子的数学模型。借助于循环嵌套式算法，采用改进后的由外至内逐步优化的模型：首先对各边的外层进行摆放，使其边界利用率最高，再对内层剩余矩形空间进行摆放，一直循环，至内部剩余空间无法放入箱子为止。用MATLAB编程、求解分析：以此模型摆放，第一种箱子个数为16、第二种箱子个数为4、第三种箱子个数为20。对于问题二，建立在允许箱子超出上、左、右边的情况下，所能摆放最多箱子的数学模型。建立由下至上逐步优化模型：以底边为基，将其两边各向外扩充半个长边的长度，先对底边进行摆放，使其边界利用率最高，再向上堆叠，使箱子间无空隙，使面积利用率最大，至上侧最多超出半个箱子边长为止。用lingo编程、求解分析：以此模型摆放，第一种箱子个数为23、第二种箱子个数为8、第三种箱子个数为28。对于问题三，我们采用左右对称，箱子横放，向上堆叠，左、右、上边各超出少许的方案。引入箱子个数、稳定性两个指标，通过线性加权评价的方式，对此方案与模型一进行评价分析。得出了在在实际情况中，当考虑不同权重的综合指数时，模型一与模型三的摆放方式各有优劣性的结论。

关键词：利用率最高

0

0

0

.

minz=1.1-a*m-b*n.其中，m、n分别表示小矩形的长边和宽边在大正方形的某边的个数。利用LINGO程序求解。（1）第一种箱子：a=0.3b=0.24L=1.1利用lingo程序求解，得：m=2,n=2摆放示意图如图1所示

图1

（2）第二种箱子：a=0.6b=0.4L=1.1利用lingo程序求解，得：m=1,n=1摆放示意图如图2所示：

图2

（3）第三种箱子：a=0.3b=0.2L=1.1利用lingo程序求解，得：m=1,n=4摆放示意图如图3所示：

0

图3

模型二：由外至内逐步优化模型改进版因为模型一过程复杂，不利于推广，我们进行了新模型的构建，即基于循环嵌套式算法[2]的改进版模型来解决二维矩形排列问题。在边长为1.1的正方形中，放入ab的小矩形（a为长，b为宽），使放入的数量最多。其等价于，利用a和b的进行各种组合，使得大正方形各个边方向上的利用率尽可能高，即在边上对a和b进行组合优化。对外层排列完成后，对内部剩余矩形面积进行排放，如此循环，至剩余面积无法放入小矩形。这种模型不断循环，利于推广。

1

图4

参照流程图设计MATLAB程序，求解每层小矩形长边、宽边的个数m和n，以及所有小矩形的个数sum。

模型求解：（1）第一种箱子：a=0.3b=0.24L=1.1利用MATLAB程序求解，得：m=2,n=2,sum=16因为该算法的思想为：由外向内的每层都分为对称的4部分，每部分都为相同形状矩形，因此此方案只有一层，摆放示意图如图5所示：

2

图5

（2）第二种箱子：a=0.6b=0.4L=1.1利用MATLAB程序求解，得：m=1,n=1,sum=4摆放示意图如图6所示：

图6

（3）第三种箱子：a=0.3b=0.2L=1.1利用MATLAB程序求解，得：m=[11],n=[41],sum=24摆放示意图如图7所示：

3

图7

问题二：模型三：由下至上逐步优化模型（1）允许箱子在正方形底板的上方，左边，右边部分超出底板。因此，为了追求面积最大化，在正方形底板的左右侧各扩充a/2，使其变成矩形。（2）正方形底板的下边不可超出。考虑以下边为基础，优化目标是使其利用率尽可能高，即先在扩充后的底边对a和b进行组合优化。

图8

参照图8设计LINGO程序，将目标函数设为：maxf=m*c+n*d得到靠近叉车壁的小矩形长边、宽边的个数m和n，以及长边、宽边向上累加的小矩形的个数c和d。我们再对剩余的上部进行填充：以整体面积利用率为优化目标（面积利用率越大，即摆放在扩展后的矩形底板上的小矩形越多），我们采用紧密相连的方案，以下边为基，逐个向上累加。4

模型求解：（1）第一种箱子：a=0.3b=0.24L=1.1利用LINGO程序求解，得：m=3,n=2,c=5,d=4摆放示意图如图9所示：

图9注：最外围实线表示最大可能利用面积。

（2）第二种箱子：a=0.6b=0.4L=1.1利用LINGO程序求解，得：m=2,n=1,c=3,d=2摆放示意图如图10所示：

图10

（3）第三种箱子：a=0.3b=0.2L=1.1利用LINGO程序求解，得：m=4,n=1,c=6,d=4摆放示意图如图11所示：

5

12

图1112

问题三：1.摆放方式的简述我们在装箱个数不一定相等的前提下，从叉车底板下方往上使每个小矩形箱按同样的方式摆放进叉车，允许小矩形箱按问题二的要求在允许箱子在正方形底板的上方，左边，右边少部分超出底板但不至于掉落出叉车底板，不允许出现矩形箱旋转情况，使摆放不存在缝隙且左右对称。以此为我们问题三的摆放方式。下图图12为问题三型号1矩形箱的摆放方式（4X5），左右对称，两边各超出底板0.05米，上方超出底板0.1米。下图图13为问题三型号2矩形箱的摆放方式（2X6），左右对称，两边各超出底板0.05米，上方超出底板0.1米。下图图14为问题三型号3矩形箱的摆放方式（4X6），左右对称，两边各超出底板0.05米，上方超出底板0.1米。

图图13

6

，我们认为，叉车的稳定性可以重心偏移量来衡量，即为每个矩形箱重心的表2个数1642012x1（摆放个数）属于“极大型指标（总是期望指标的取重心偏移量0.5216970.4301160.416874模型三图1，我们认为，叉车的稳定性可以重心偏移量来衡量，即为每个矩形箱重心的表2个数1642012x1（摆放个数）属于“极大型指标（总是期望指标的取重心偏移量0.5216970.4301160.416874模型三图1图2图3个数20624重心偏移量0.5588540.4419500.431873

2.线性加权综合法的分析（1）数据的采集和计算分别以问题一和问题三的三个小矩形箱的摆放方式为研究对象，其测评数据采自这6个摆放方式的摆放个数及摆放方式的稳定性。经查阅文献及模型简化

[3]位置到叉车底板中心位置距离的平均值。因此，在六个摆放方式中，我们以叉车底板中心位置为原点建立直角坐标系，在每个矩形箱都是密度均匀的前提下，分别确定每个矩形箱重心(即矩形中点)的坐标，计算求得重心偏移量的值。第一题的数据汇总见表1；第三题的数据汇总表见表2。

表1模型一图1图2图3

（2）数据的一致化与无量纲化处理[4]

在上表中的评价指标

值越大越好）”，x2'（重心偏移量）属于“极小型指标（总是期望指标的取值

越小越好）”，故首先应通过转化使评价指标类型一致化。经过考虑，我们此次采用倒数法将极小型化为极大型，即将重心偏移量指标的数据改为其倒数用于计算，得到的数据即为稳定性指标。

7

1x'211xij的标准观测值。问题三个数0.134030115-1.474331270.670150577912。个数稳定性-1.09622020.684811061.007088803nnn稳定性0.67015057图1-1.2062710图21.206271032-1.652356870.4131421430.643535101x'211xij的标准观测值。问题三个数0.134030115-1.474331270.670150577912。个数稳定性-1.09622020.684811061.007088803nnn稳定性0.67015057图1-1.2062710图21.206271032-1.652356870.4131421430.64353510]12(j1,2,…,m)。8

9jj在上表中的评价指标x（摆放个数）、x（稳定性）之间，存在着各自不同1的单位和数量级，使得这些指标之间存在着不可公度性，这就为综合评价带来了困难。在数学上，我们常常采用数据的无量纲化处理来使指标数据标准化，常用方法有：标准差方法、极值差方法、功效系数法。通过比较，此次我们采用标准差方法进行无量纲化处理。

其中xx,s[(xx)jijjijiji1i1显然指标x'(i1,2,…，n,j=1,2,?，m)的均值和均方差分别为0和1，即ijx'[0,1]是无量纲的指标，称之为ij第一题的数据处理见表3；第二题的数据处理见表4。

表4表3问题一图1图2图3图3

(3)权重系数的讨论权重系数[5]是指一个整体被分解成若干因素（指标）时，用来表示每个因素在整体中所占大小的数字，简称为权重。指标的权重反映了该指标在整体中的相对重要程度；同时，也是评价主体对该指标价值认识程度的反应，即重要的指标，权重大些；反之，则小些。常见的权重系数确定方法有：层次分析法（AHP）、达尔菲法（Delphi）、主成分分析法、熵值法和均方差法等。这些方法求解较繁琐且计算量大，在本题中不太符合。由于矩形箱的摆放在实际过程中可能受矩形箱的质量、箱内货物类型等问题影响从而导致权重系数的选择不一致。因此，我们暂且用w作为指标x（摆1放个数）的权重系数，用w作为指标x（稳定性）的权重系数。2本次我们将分三种方案讨论不同权重系数下出现的结果：

8

0.2,w22j图1问题一问题三问题一问题三-0.85017016问题三122）的情况下，型号1、2、3的矩形箱在图2-0.112019950.2056490-0.48109506-0.491103150.252982600-1.18785539图3-1.042502803-0.882388402-0.394760101-0.3965644450.2,w22j图1问题一问题三问题一问题三-0.85017016问题三122）的情况下，型号1、2、3的矩形箱在图2-0.112019950.2056490-0.48109506-0.491103150.252982600-1.18785539图3-1.042502803-0.882388402-0.394760101-0.3965644450.9397011570.089259510.7375382221.0937238520.8386196900.9249030710.756082290系数为w0.8,w0.2。12方案二：要求同时考虑矩形箱的个数和稳定性，则确定权重系数为w0.5,w0.5。12方案三：要求着重考虑矩形箱的稳定性大小，以稳定性好为主要目标，

则确定权重系数为w。（4)加权综合指数计算根据公式，我们就可以计算指定摆放方式的加权综合指数：

ywxjj1式，w表示摆放指标的权重，x表示摆放指标无量纲化后的数值。最终各摆放jj方式的加权综合指数计算结果，见表5。

表5权重

w0.8,w0.212

8

w0.5,w0.512

问题一

w0.2,w0.812

由表分析可知：（1）在方案一（权重w0.8,w0.2）的情况下，型号1、2、3的矩形箱问1题三中摆放方式均优于问题一，可说明在着重考虑装箱个数的前提下，问题三的摆放方式均优于问题一。（2）在方案二（权重w0.5,w0.5）的情况下，型号1、2、3的矩形箱在1问题一中摆放方式均优于问题三，可说明在同时考虑装箱个数及稳定性的前提下，问题一的摆放方式均优于问题三。

（3）在方案三（权重w0.2,w0.812问题一中摆放方式均优于问题三，可说明在着重考虑装箱稳定性的前提下，问题一的摆放方式均优于问题三。

9

（4）综上所述，在不同权重的综合指数计算中，问题一与问题三的摆放方式各有优劣性。在实际情况中，若追求个数较多，则更适合选择问题三的摆放方式；若追求稳定性较好，则更适合选择问题一的摆放方式。

六、模型的检验

对于模型一：设底盘的总面积为S，小矩形的长宽分别为a、b，N为底盘面积利用率最大时小矩形的个数。由N=[S/（ab）]得出：N1=16N2=5N3=20，由模型一得：sum1=16sum2=4sum3=20，由模型一得出的结果面积利用率很高，结果合理。在理想情况下，第二种型号的箱子可放入5个，但根据实际情况，箱子形状固定，无法分割，故只能放入4个。因此我们得出的结果是全局最优解。

对于模型二：因为条件允许箱子在正方形底板的上方，左边，右边部分超出底板（下方紧靠叉车壁，不能超出），只要重心不超出底板，就不至于掉落出叉车底板。故我们假设另外三边各向外扩充长边的一半，对新构造的矩形底板做出如下检验：N1=23N2=9N3=29，由模型而得：sum1=23sum2=8sum3=28。根据实际情况，箱子形状固定，无法分割，而且实际情况下并不是所有箱子摆出去了长边的一半，因此我们得出的是较优解。

七、模型的评价

1.模型的优点：对于问题一和问题二使用的优化模型，有以下优点：（1）该方法计算简便，可操作性强，便于推广使用。（2）该模型得出的可行解经检验为全局最优解。对于问题三使用的线性加权综合法，有以下优点：（1）各评价指标间作用得到线性补偿，保证综合评价指标的公平性；（2）不同的权重系数的对评价结果的影响明显，即权重较大指标值对综合指标作用较大；

2.模型的缺点：对于问题一和问题二使用的优化模型，有以下缺点：（1）程序中若出现多个可行解，结果只能提供一种答案。（2）模型所得结果是基于理想化的，与实际可能不符。对于问题三使用的线性加权综合法，有以下缺点：（3）选取的评价指标较少，可能导致结果考虑不够全面。

10

八、参考文献

[1]陈靖兵、黄文奇，求解矩形packing问题的贪心算法，计算机工程，33（4）：160-162,2007。[2]隋树林、邵巍、高自友,同一尺寸货物三维装箱问题的一种启发式算法,信息与控制,34（3）:490-494，2005。[3张伯贤，港口叉式装卸车，武汉：武汉河运学校，1979。[4]叶宗裕，关于多指标综合评价中指标正向化和无量纲化方法的选择，百家争鸣，24-25,2003。[5]刘自远刘成福，综合评价中指标权重系数确定方法探讨,研究