2014高教社杯全国大学生数学建模竞赛

2014高教社杯全国大学生数学建模竞赛承诺书我们仔细阅读了《全国大学生数学建模竞赛章程》和《全国大学生数学建模竞赛参赛规则》（以下简称为“竞赛章程和参赛规则”，可从全国大学生数学建模竞赛网站下载）。我们完全明白，在竞赛开始后参赛队员不能以任何方式（包括电话、电子邮件、网上咨询等）与队外的任何人（包括指导教师）研究、讨论与赛题有关的问题。我们知道，抄袭别人的成果是违反竞赛章程和参赛规则的，如果引用别人的成果或其他公开的资料（包括网上查到的资料），必须按照规定的参考文献的表述方式在正文引用处和参考文献中明确列出。我们郑重承诺，严格遵守竞赛章程和参赛规则，以保证竞赛的公正、公平性。如有违反竞赛章程和参赛规则的行为，我们将受到严肃处理。我们授权全国大学生数学建模竞赛组委会，可将我们的论文以任何形式进行公开展示（包括进行网上公示，在书籍、期刊和其他媒体进行正式或非正式发表等）。我们参赛选择的题号是（从A/B/C/D中选择一项填写）：D我们的报名参赛队号为（8位数字组成的编号）：23068006所属学校（请填写完整的全名）：四川建筑职业技术学院参赛队员(打印并签名)：1.王磊2.蔡姗姗3.蒋国辉指导教师或指导教师组负责人(打印并签名)：黄磊（论文纸质版与电子版中的以上信息必须一致，只是电子版中无需签名。以上内容请仔细核对，提交后将不再允许做任何修改。如填写错误，论文可能被取消评奖资格。）日期：2014年9月15日赛区评阅编号（由赛区组委会评阅前进行编号）：2014高教社杯全国大学生数学建模竞赛编号专用页赛区评阅编号（由赛区组委会评阅前进行编号）：赛区评阅记录（可供赛区评阅时使用）：评阅人评分备注全国统一编号（由赛区组委会送交全国前编号）：全国评阅编号（由全国组委会评阅前进行编号）：储药柜的设计摘要本文针对自动补药药柜的设计进行研究。针对问题一，在只考虑储药柜竖向隔板的最小间距种类，在满足安全送药的四个条件，即侧间距2mm,无并排，无侧翻，无水平旋转下，建立单目标优化模型，并设计区间无重叠聚类算法，实现最少间距种类的求解，由程序得到最少四类列宽的分类，分别为19mm，34mm，46mm，58mm针对问题二，我们将总宽度冗余，与列间距类型数量作为目标，建立双目标规划模型。基于分层求解多目标规划模型方法，我们在问题一得到的4个不同类型的基础上，首先建立冗余权重模型，首先计算出各中药盒宽度在原始4种分类基础上的加权冗余，并按照其加权冗余累积贡献率排序，根据累积贡献率，我们讨论了90%和95%下，根据列宽优化算法，计算出新的列宽分类，经过加权冗余度和列宽类数的分析，我们确定在新增3类情况下的最优解。列宽分别为19mm，22mm，34mm，37mm，46mm，47mm，58mm并且给出相应的药盒编号。针对问题三，我们将平面总冗余度，与行间距类型最小作为目标，在以药柜给定规格为约束条件下，建立双目标规划模型。在问题二的基础上，我们通过对分布分析法，先按照比列均衡的思想确定药柜一行放置76个药槽，在此基础上为了尽量减少平面冗余，我们按照高相近归类方法，得到药柜至少需要26行，并且计算出高大致需要以下9类。34mm，41mm，47mm，54mm，60mm，72mm，85mm，101mm，125mm针对问题四，在药槽长度1.5米的条件下，我们首先计算出每一种药盒在药槽长度方向上能的个数。因此确定同一种要需要的药槽数量。又因为每天仅集中补药一次，所以设计的储药槽个数一次性能放药盒的个数大于该需求量的最大值才能满足。关键词：双目标规划区间无重叠聚类分层法一．问题重述药柜的结构与书柜相似，若干个横向隔板和竖向隔板将储药柜分割成若干个储药槽，横向隔板决定所放药品的高度，竖向隔板决定所放药品的宽度，为了方便使用和保证药品分拣的准确率，防止发药错误，一个储药槽内只能摆放同一种药品，要求药盒与两侧竖向隔板之间、与上下两层横向隔板之间应留2mm的间隙，同时还要求药盒在储药槽内推送过程中不会出现并排重叠、侧翻或水平旋转。为了更好的在实际中运用，在忽略横向和竖向隔板厚度的情况下，建立数学优化模型，给出下面几个问题的解决方案。问题一：因为药盒尺寸规格差异较大，根据提供的数据，设计药柜的竖向隔板间距类型最小种类数的数量和每种类型所对应的药盒规格。问题二：宽度冗余是药盒与两侧竖向隔板之间的间隙超出2mm的部分，当适当增加竖向隔板间距类型的数量可以减少宽度冗余，但增加竖向隔板间距类型会增加储药柜的加工成本，通过对问题一中的最佳设计求解方案，设计出合理的竖向隔板间距类型数量以及每种类型对应的药盒编号，使得总宽度冗余尽可能小，同时也希望间距的类型数量尽可能少。问题三：为了考虑拿药的方便性和补药的便利性，储药柜的尺寸要具有合理性和可行性，规定储药柜的宽度不超过2.5m，高度不超过2m，储药柜允许的最大有效高度为1.5m。药盒与两层横向隔板之间的间隙超过2mm的部分叫做高度冗余，可以得出平面冗余=高度冗余×宽度冗余，在问题二中计算结果的基础上，确定储药柜横向隔板间距的类型数量，使得储药柜的总平面余量尽可能地小，且横向隔板间距的类型数量也尽可能地少。问题四：由附件2可得每一种药品编号对应的最大日需求量。已知储药槽的宽度不超过2.5m，有效高度不超过1.5m，长度为1.5m，每天补药仅一次，请计算每一种药品需要的储药槽个数。为了保证药房储药满足需求，计算稀少需要多少个储药柜。二．模型假设1.假设每次从后端放入的药品都正立平稳放入；2.假设药盒水平旋转时中心点在一条直线上；3.假设药盒旋转角度超过90°时才为水平旋转；4.假设每个药槽都有药盒放入；5.假设一天中仅有的一次药品补给是在药店下班前或者下班后一次性补给完成；三．变量说明D：表示竖向隔板的间距；il：表示第i个型号药盒的长度；id：表示第i个型号药盒的宽度；ih：表示第i个型号药盒的高度；N：表示竖向隔板间距类型数；jC：表示定义域为`),[jjxx的有效区间集合；iK：表示冗余权重系数；iQ：表示冗余率；im：表示各药盒尺寸的频数；iM：表示药盒尺寸出现的总频次；iL：表示列宽冗余度；jH：表示第j个药盒放入的药槽可能高度；iRL：表示每个药盒放入对应药槽时的宽度冗余；iRL:表示每个药盒放入对应药槽时的宽度冗余；iRP:表示第i个药盒产生的平面冗余；ix:表示一排横向同类型列的药槽个数；iy:表示同类型高的在一列纵向中药槽个数；四．模型的建立与求解4.1问题一的模型建立与求解4.1.1基于药盒安全推出下的最小列分类规划模型模型分析药盒为了能顺利推送过程，且不出现并排重叠、侧翻或水平旋转，因此每个药盒存在对应的药槽列宽区间，下面根据三个条件我们分别讨论。设D表示药槽的宽度，il，id,ih,表示药盒的长，宽，高。(a)顺利推出根据题目，每个药盒与左右两侧间距2mm，因此，为了能顺利推出，则Dd2(1)(b)无并排现象为了不发生并排现象，则药槽的宽度不能大于两倍药盒的宽度，如图1所示，因此，药槽宽度和药盒宽度之间满足：Dd2(2)(c)无侧翻现象如图2所示，我们定义当药盒在药槽内侧倒至药槽内时称为侧翻。考虑药盒d在侧翻过程中，横向最大距离为宽与高的对角线，因此，为避免侧翻，则药槽的宽度应该大于此对角线长度，即：22hdD(3)(d)无水平旋转现象如图3所示，我们定义当药盒在药槽内平面旋转90度时为水平旋转。同样考虑药盒在水平旋转过程中，横向最大距离为宽与长的对角线，因此，为避免水平旋转，则药槽的宽度应该大于此对角线长度，即：22ldD(4）模型建立问题一即在满足以上四条的情况下，计算最小列宽分类，我们设N为药槽按照列宽的分类数，根据模型分析，建立最小列宽分类规划模型:minN(5)222222iiiiiiiiihdDldDdDd(（整数）且Nii],1919,1[)（6）4.1.2基于区间无重叠下最小聚类法的模型求解要求解4.1.1中的模型，我们首先根据约束条件，根据附表1中的原始数据算出每个药盒的宽度容许区间。以每个药盒尺寸的第一个区间为例，如下表：（程序见附录1）表1.药盒的列宽容许度区间表宽度有效区间宽度有效区间宽度有效区间宽度有效区间宽度有效区间10[12,20)20[22,40)30[32,60)40[42,80)50[52,82)11[13,22)21[23,42)31[33,43.8)41[43,58)51[53,72.8)12[14,24)22[24,38.8)32[34,51.2)42[44,60)52[54,73.5)为了将所有药盒用最少的药槽规格来放置，等价于对M个区间，我们寻找N个区间，使得这N个区间之间交集为空，且这N个区间每一个都至少完全属于原始区间中的某一个。区间无重叠聚类算法ts.dhD图1Dhd图2Ddl图3第一步，将所有区间，按照区间下限从小到大排列，记排序好的区间为[,]iiCC第二步，从第一个区间开始,比对1C的上限与2C的下限，若当021CC时，则1C为单独一类，并从分析中暂时剔除，对MCC...2继续聚类当021CC时，交集为'1C，则将'1C代替1C,2C，对MCCC...3'...1继续聚类。第三步，重复第二步，直至所有原始区间聚类完毕。聚类过程示意图如图4所示：按照上述聚类过程，显然最后得到的N个区间相互间无重叠，且每个区间一定完全包含于原始的某个区间中，即所有的药盒一定能放置于某个聚类后的药槽中,根据算法编制程序见附录2。最后聚类得到的区间见表2表2：规格聚类分析表考虑到空间节约，药槽宽度取每个区间下限即可，即最少的药槽列宽规格为19mm,34mm，46mm，58mm每个规格下可放置的药品规格如下表:表3：药盒宽度的最佳取值表药槽规格D/mm对应的药盒规格宽度最佳取值范围d/mm1910~173418~32规格种类序号聚类区间1[19,20）2[34,34.9857113690718)3[46,46.6690475583121)4[58,63.6396103067893)图4区间无重叠聚类示意图1C2C3C'1C3C4633~445845~56所以综上所述，竖向隔板间距类型最少的储药规格有4种，每种类型所对应的药盒规格如上表。模型二的建立(列宽冗余双目标规划)4.2.1模型分析与建立列宽对于超过规定尺寸以外的距离，称为宽度冗余。根据题目，列宽冗余的计算公式为：2iiidDL（7）整个药槽的总列宽冗余为iL问题二即在列分类较少的情况下使得总列宽冗余最小。将列宽冗余的最小作为目标，我们在模型一的基础上建立列宽冗余双目标规划模型如下：minminiLN（8）222222iiiiiiiiihdDldDdDd4.2.2基于分层法求解双目标规划由于模型二是双目标规划，我们根据分层法进行求解，将冗余度尽可能小作为主要目标，先求解列分类较少这一目标。这一步我们直接应用问题一的结论，在此基础上进行冗余度最小的求解。为了减少冗余度，我们首先将问题一结论中放置方案的每个药盒的冗余度计算出来，见表4(程序见附件3)表4：问题一结论基础上每个药盒的冗余度表药品编号药品规格d/mm药槽规格D/mm冗余度iS/mm6691019777410197135210197147110197为下面说明方便，我们定义：冗余权重：将同宽的药盒归类，考虑每一类在总药盒数中的比例，即MmAii(9)分类加权冗余度：同宽药盒的冗余度乘以冗余权重，即iiiASK(10)分权贡献率：将分类加权冗余度求和，考虑每一类在总加权冗余的比列，即iiiKKQ(11)在此基础上我们计算出分类加权冗余度表，并按升序排列，加权冗余度iK和分权贡献率iQ的具体值如下表5（程序见附录4和附录5）表5：各种列宽加权冗余权度和分权贡献率因此，要最尽量减少冗余度，我们首要减少在加权冗余度较高的那些列。即对此类列增加相应规格的药槽。我们取0.9作为基准，和表5反序，从大到小排列，认为%90iQ中的各个药盒，对宽度冗余和竖向隔板间距数量有较大的影响。因此