储药槽宽度的优化设计模型.doc

储药槽宽度的优化设计模型 吴叶民WUYe-min （江阴职业技术学院基础部，江阴214405） （BasicDepartmentofJiangyinPolytechnicCollege，Jiangyin214405，China） 摘要：本文对xx年全国数学建模竞赛D题1储药柜的优化设计进行了探讨，为解决第2问储药槽宽度的优化设计，提出了0-1整数规划模型，并用Matlab编程进行了求解，得到了比较好的结果。 Abstract：ThepaperdiscussestheoptimizationdesignofmedicinestoragecabiwhichisthetitleDofxxNationalMathematicalModelingContest.Inordertosolveoptimizationdesignofthewidthofmedicinestoragecabiwhichisthesecondquestion，0-1integerprogrammingmodelisproposed，andMatlabprogrammingisusedforsolution，andagoodresultisobtained. 关键词：储药槽；优化设计；线性规划；matlab Keywords：medicinestoragecabi；optimaldesign；linearprogramming；matlab ：O141.4：A：1006-4311（xx）25-0249-02 基金项目：江阴职业技术学院科研项目（14-S-JC-07）；江苏省高等学校大学生实践创新训练项目（xx13137016X）。 作者简介：吴叶民（1976-），男，江苏江阴人，江阴职业技术学院讲师，研究方向为数学建模与数学教育。 1问题的背景及分析 xx年全国数学建模竞赛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储药槽宽度类型的优化设计 因此，我们不妨固定储药槽宽度类型数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。 ，计算得结果见表3。 在Matlab中画出竖直隔板间隔类型数与宽度冗余率的关系图如图1。 我们发现当储药槽宽度类型数增加到8时，由图1可以看出冗余度已经只有6.2%，而且每增加一个隔板降低冗余度已不足1%，再增加隔板已经不合算了。 因此我们得出合理的储药槽宽度类型数为8，具体的宽度为19、23、27、32、7、43、49、58。 5模型的改进方向 如果能够进一步知道增加1块隔板的成本以及每增加1个单位冗余的成本，那么我们就可以得到最优的储药槽宽度类型数和最少的宽度冗余，模型可以进一步在这个方面加以改进。 参考文献： 1赵静，但琦.数学建模与数学实验M