吴叶民 WU Ye-min
（江阴职业技术学院基础部，江阴 214405）
（Basic Department of Jiangyin Polytechnic College，Jiangyin 214405，China）
摘要：本文对2014年全国数学建模竞赛D题[1]储药柜的优化设计进行了探讨，为解决第2问储药槽宽度的优化设计，提出了0-1整数规划模型，并用Matlab编程进行了求解，得到了比较好的结果。
Abstract： The paper discusses the optimization design of medicine storage cabinet which is the title D of 2014 National Mathematical Modeling Contest. In order to solve optimization design of the width of medicine storage cabinet which is the second question， 0-1 integer programming model is proposed， and Matlab programming is used for solution， and a good result is obtained.
教育期刊网 http://www.jyqkw.com
关键词 ：储药槽；优化设计；线性规划；matlab
Key words： medicine storage cabinet；optimal design；linear programming；matlab
中图分类号：O141.4 文献标识码：A文章编号：1006-4311（2015）25-0249-02
基金项目：江阴职业技术学院科研项目（14-S-JC-07）；江苏省高等学校大学生实践创新训练项目（201313137016X）。
作者简介：吴叶民（1976-），男，江苏江阴人，江阴职业技术学院讲师，研究方向为数学建模与数学教育。
1 问题的背景及分析
2014年全国数学建模竞赛D题是关于储药柜的优化设计，解决这个问题可以提高储药柜的利用率和适应性，有利于自动分拣发药系统的实现。题目给定了储药柜的尺寸（长1.5m、宽2.5m、有效高度1.5m）以及一批药品的药盒尺寸（长、宽、高），储药柜由若个竖向隔板及横向隔板分割成许多长方体储药槽。每个储药槽内只能存放同一种药品，药品从后端放入，从前端取出。为实现药盒在储药槽内能顺利出入，要求药盒与两侧竖向隔板之间及上下横向隔板之间均要有2mm的间隙，并且推送过程中不能出现并排重叠、侧翻或水平旋转。在此条件下要求一种优化设计方案，既要使得储药槽的竖向隔板间距类型数和横向隔板间距类型数尽可能地少，又要使得平面冗余尽量可能地小。
原题分为4个问题，其中第2个问题要求找到使总宽度冗余和竖向隔板间隔类型数都尽可能小的优化设计方案是关键，因此本文主要对第2个问题进行探讨。两侧竖向隔板间隔其实就是储药槽宽度，我们首先利用所给条件得出每种药盒能放入的储药槽的宽度允许范围，然后确定储药槽宽度类型数的最小值与最大值，最后讨论如何找出储药槽宽度类型数和总宽度冗余都尽量小的优化设计方案。
2 储药槽宽度范围的确定
药盒的形状是长方体，定义最长边为长，其次为高，最短边为宽，原题附件1所给数据中有6个药盒的宽大于高，应予以调整。药盒与储药槽之间应留2mm的间隙。同时还要求药盒在储药槽内推送过程中不会出现并排重叠、侧翻或水平旋转。设第种药盒的长、高、宽分别为ai，bi，ci，（i=1，2，…，1919），其所在的储药槽宽度为wi，wi的上、下限分别为wmini、wmaxi。由药盒与储药槽之间应留2mm的间隙可得wmini=ci+2（1）
（[]表示取整数部分）。
3 储药槽宽度类型数范围的确定
首先，我们可以把D题中附件1的数据代入公式（1）和（2）进行计算，可以得出每种药盒可以放入的储药槽的宽度上下限，并按储药槽宽度下限重新升序排序，可以得到储药槽宽度下限最小为12，最大为58，共有47种，具体见表1。
要使储药槽宽度类型数最少，也就是说每种被采用的储药槽宽度要适应尽可能多的药盒种类。为找到储药槽宽度类型数的最小值，我们设计了以下算法。
第1步：从储药槽的宽度下限最小的药盒开始，计算所有该下限宽度药盒的宽度上限的最小值，记为z1。
第2步：如果z1没有达到最小下限的最大值，则搜索所有宽度下限小于等于z1，且宽度上限大于等于z1的药盒，并把其中最大宽度限所对应的最小上限值记录下来，记为z2。依次类推。
第k步：如果zk没有达到最小下限的最大值，搜索所有宽度下限小于等于zk，且宽度上限大于等于zk的药盒，并把其中最大宽度限所对应的最小上限值记录下来，记为zk+1。
如果zk小于等于宽度下限的最大值时，就以该值作为最后一个zk，这样z1，z2，…，zk是一种储药槽宽度类型数最少的方案。最后求出储药槽宽度类型数的最小值为4，储药槽宽度分别为20、34、45、58mm，对应药盒宽的范围分别为10-17mm、18-32mm、33-43mm、44-56mm。不过值得说明的是，宽度类型最少的方案有很多种。
如果把47种储药槽宽度下限直接作为储药槽宽度，则储药槽宽度类型数的最大值为47。因此储药槽宽度类型数的范围应该为4到47之间。
4 储药槽宽度类型的优化设计
对第i种药盒，我们定义宽度冗余ri为储药槽实际宽度wi与储药槽宽度下限之差wmini，即宽度冗余ri=wi-wmini，显然所有的药都应该储放在储药槽中，因此总宽度冗余
。我们注意到储药槽宽度类型越多，则总宽度冗余越小，反之储药槽宽度类型越少，则总宽度冗余越大，也就是说同时使两者达到最少的最优方案是不存在的。因此我们只能追求相对满意的方案。
因此，我们不妨固定储药槽宽度类型数N（4?燮N?燮47），在N确定的情况下，找总宽度冗余最小的方案。为此我们引进0-1变量
我们根据以上模型编写了Maltab程序，固定储药槽宽度类型数N（4?燮N?燮47）从4开始求最小总宽度冗余的方案。我们注意到，当宽度类型数增加时，程序复杂度大大增加，导致程序运行速度变慢。因此实际运行程序时，可以使用之前的结果优化程序，减少循环次数，提高运行速度。比如当储药槽宽度类型数为k时，我们得到Z1，Z2，…，Zk最优方案。那么宽度类型为k+1时，得到的第k个宽度应该介于zk-1到zk之间（假定Z0=12），这样可以减少程序复杂度，提高运行速度。我们具体运行了N=4，5，6，7，8，9，10，程序运行的结果如表2。
我们从表2发现，起初当储药槽类型数N每增大1时，总宽度冗余显著减少，但当N达到8时，再增大N的值冗余却没有明显的改善，因此这时增加储药槽类型数的意义就不大了。我们还可以通过储药槽类型数与宽度冗余率的关系来看，设宽度冗余率
，计算得结果见表3。
在Matlab中画出竖直隔板间隔类型数与宽度冗余率的关系图如图1。
我们发现当储药槽宽度类型数增加到8时，由图1可以看出冗余度已经只有6.2%，而且每增加一个隔板降低冗余度已不足1%，再增加隔板已经不合算了。
因此我们得出合理的储药槽宽度类型数为8，具体的宽度为19、23、27、32、7、43、49、58。
5 模型的改进方向
如果能够进一步知道增加1块隔板的成本以及每增加1个单位冗余的成本，那么我们就可以得到最优的储药槽宽度类型数和最少的宽度冗余，模型可以进一步在这个方面加以改进。
教育期刊网 http://www.jyqkw.com
参考文献：
[1]赵静，但琦.数学建模与数学实验[M].三版.北京：高等教育出版社，2008，6.
[2]2014年高教社杯全国大学生数学建模竞赛赛题，http：//www.mcm.edu.cn/problem/2014/cumcm2014problems.rar，2014，9，11.
[3]陈大桥.储药柜设计问题的数学模型[J].湖北第二师范学院学报，2015（02）.