资源预览内容
第1页 / 共30页
第2页 / 共30页
第3页 / 共30页
第4页 / 共30页
第5页 / 共30页
第6页 / 共30页
第7页 / 共30页
第8页 / 共30页
第9页 / 共30页
第10页 / 共30页
亲,该文档总共30页,到这儿已超出免费预览范围,如果喜欢就下载吧!
资源描述
2014 高教社杯全国大学生数学建模竞赛高教社杯全国大学生数学建模竞赛 承承 诺诺 书书 我们仔细阅读了全国大学生数学建模竞赛章程和全国大学生数学建模竞赛参赛规则(以下简称为 “竞赛章程和参赛规则” , 可从全国大学生数学建模竞赛网站下载) 。 我们完全明白,在竞赛开始后参赛队员不能以任何方式(包括电话、电子邮件、网上咨询等)与队外的任何人(包括指导教师)研究、讨论与赛题有关的问题。 我们知道,抄袭别人的成果是违反竞赛章程和参赛规则的,如果引用别人的成果或其他公开的资料(包括网上查到的资料) ,必须按照规定的参考文献的表述方式在正文引用处和参考文献中明确列出。 我们郑重承诺,严格遵守竞赛章程和参赛规则,以保证竞赛的公正、公平性。如有违反竞赛章程和参赛规则的行为,我们将受到严肃处理。 我们授权全国大学生数学建模竞赛组委会,可将我们的论文以任何形式进行公开展示(包括进行网上公示,在书籍、期刊和其他媒体进行正式或非正式发表等) 。 我们参赛选择的题号是(从 A/B/C/D 中选择一项填写) : D 我们的参赛报名号为(如果赛区设置报名号的话) : 14051009 所属学校(请填写完整的全名) : 江西应用技术职业学院 参赛队员 (打印并签名) :1. 赖辉 2. 刘传鸿 3. 李雪钰 指导教师或指导教师组负责人 (打印并签名): 凌巍炜 (论文纸质版与电子版中的以上信息必须一致,只是电子版中无需签名。以上内容 请仔细核对,提交后将不再允许做任何修改。如填写错误,论文可能被取消评奖资格。) 日期: 2014 年 9 月 15 日 赛区评阅编号(由赛区组委会评阅前进行编号) : 2014 高教社杯全国大学生数学建模竞赛高教社杯全国大学生数学建模竞赛 编编 号号 专专 用用 页页 赛区评阅编号(由赛区组委会评阅前进行编号) : 赛区评阅记录(可供赛区评阅时使用) : 评 阅 人 评 分 备 注 全国统一编号(由赛区组委会送交全国前编号) : 全国评阅编号(由全国组委会评阅前进行编号) : 1 储药柜的优化设计 摘 要 本文围绕储药柜设计的问题,首先对并排重叠、侧翻、水平旋转的情况做了详细的 定义,并从中给出了各情况下所对应应满足的条件及相关的图示说明。然后在满足一定 的约束条件下,建立了相应的优化模型,同时基于模型的 NP 难属性,给出了具有普适 性的基于装箱问题的改进算法,利用 MATLAB 软件和 LINGO 软件对其编程求解,最后得 到了在满足各类要求下的储药柜优化设计方案,从而较为完善的解决了此问题。 针对问题一,本文首先在模型建立方面,建立以药盒在储药槽内推送过程中不发生 并排重叠、侧翻、水平旋转,药盒与两侧竖向隔板之间应留 2mm 的间隙,每种竖向隔板 间距类型中的储药槽宽度都应小于所有规格药盒中宽度最大的药盒宽度的基础上加 2mm,每种规格的药盒只能放在一种竖向隔板间距类型的储药槽中为约束;以储药柜中 竖向隔板间距类型最少为目标的 0-1 非线性整数规划模型。然后在模型求解方面,利用 两种方法进行求解,第一种方法是利用 LINGO 软件进行求解,运行时间大约在 15 分 32 秒前后的范围内得出结果,最终求得 4 种竖向隔板间距类型,分别为 58mm、45mm、35mm、 20mm。第二种方法是在基于装箱算法的改进算法对模型进行启发式计算,利用 MATLAB 求出 4 种竖向隔板间距类型,分别为 58mm、43mm、32mm、17mm,其两种方法的计算结果 较好的说明了模型的正确性和算法的有效性。 针对问题二,在模型建立方面,在考虑宽度冗余的前提下,首先建立以药盒在储药 槽内推送过程中不发生并排重叠、侧翻、水平旋转,药盒与两侧竖向隔板之间应留 2mm 的间隙,每种竖向隔板间距类型中的储药槽宽度都应小于所有规格药盒中宽度最大的药 盒宽度的基础上加 2mm,每种规格的药盒只能放在一种竖向隔板间距类型的储药槽中为 约束,以总宽度冗余尽可能小和竖向隔板的间距类型数量尽可能少为目标的双目标非线 性 0-1 规划模型。其次,利用多目标规划的约束法将总宽度冗余最小的目标函数转化为 约束条件,从而将双目标优化模型转化为单目标模型。在模型求解方面,基于问题是 NP 难问题,给出了基于问题一启发式算法的改进算法,根据构建的算法利用 MATLAB 软件 快速地求得结果,最终求得在合理的冗余水平之下 6 种不同竖向隔板间距类型以及每种 类型所对应的药品编号。 针对问题三,本文基于求使总平面冗余尽可能小的目标,转化为求总高度冗余量尽 可能小的目标的基础上, 以不出现并排重叠、 与隔板间的间隙要求等 7 个条件为约束下, 建立了求总高度冗余量尽可能小和横向隔板间距的类型数量尽可能少的双目标规划模 型。对于双目标的处理,本文依然采用约束法将总高度冗余量的目标转化为约束,进而 将双目标转化为单目标,得到固定总高度冗余水平下的单目标 0-1 规划模型。在模型求 解方面,由于 0-1 变量多,求解时间过长,该问题属于 NP 难问题,因此在问题二的基 础上给出了具有普适性的启发式算法,利用该算法快速的求解得出结果,当储药柜横向 隔板间距的类型数量为 60 时,既使得总高度冗余较小,又能保证横向隔板间距类型的 数量尽可能少。 最终求得 6 种竖向隔板间距类型,分别为 56mm、 58mm、 59mm、 114mm、 114mm、 127mm、 ,及每种类型所能容纳的药盒类型数量分别为 2、629、18、395、869、6,总高 度冗余为 58439mm。 针对问题四,本文以某种药品所需的药槽个数等于所有储药柜中改中类型的药槽个 数及储药柜中药品总面积小于等于储药柜的总面积为约束,以最少需要的储药柜个数做 为目标函数,建立非线性 0-1 整数规划模型,利用 Lingo 软件求解得最少需要 2 个储药 柜。 关键词:储药柜的优化设计;启发式算法;NP 难问题 2 一、问题的重述 储药柜的结构类似于书橱,通常由若干个横向隔板和竖向隔板将储药柜分割成若干个储药槽(如图 1 所示)。为保证药品分拣的准确率,防止发药错误,一个储药槽内只能摆放同一种药品。药品在储药槽中的排列方式如图 2 所示。药品从后端放入,从前端取出。一个实际储药柜中药品的摆放情况如图 3 所示。 为保证药品在储药槽内顺利出入,要求药盒与两侧竖向隔板之间、与上下两层横向隔板之间应留 2mm 的间隙,同时还要求药盒在储药槽内推送过程中不会出现并排重叠、侧翻或水平旋转。在忽略横向和竖向隔板厚度的情况下,建立数学模型,给出下面几个问题的解决方案。 1. 药房内的盒装药品种类繁多,药盒尺寸规格差异较大,附件 1 中给出了一些药盒的规格。请利用附件 1 的数据,给出竖向隔板间距类型最少的储药柜设计方案,包括类型的数量和每种类型所对应的药盒规格。 2. 药盒与两侧竖向隔板之间的间隙超出 2mm 的部分可视为宽度冗余。增加竖向隔板的间距类型数量可以有效地减少宽度冗余,但会增加储药柜的加工成本,同时降低了储药槽的适应能力。设计时希望总宽度冗余尽可能小,同时也希望间距的类型数量尽可能少。仍利用附件 1 的数据,给出合理的竖向隔板间距类型的数量以及每种类型对应的药品编号。 3.考虑补药的便利性,储药柜的宽度不超过 2.5m、高度不超过 2m,传送装置占用的高度为 0.5m,即储药柜的最大允许有效高度为 1.5m。药盒与两层横向隔板之间的间隙超出 2mm 的部分可视为高度冗余,平面冗余高度冗余宽度冗余。在问题 2 计算结果的基础上,确定储药柜横向隔板间距的类型数量,使得储药柜的总平面冗余量尽可能地小,且横向隔板间距的类型数量也尽可能地少。 4. 附件 2 给出了每一种药品编号对应的最大日需求量。在储药槽的长度为 1.5m、每天仅集中补药一次的情况下,请计算每一种药品需要的储药槽个数。为保证药房储药满足需求,根据问题 3 中单个储药柜的规格,计算最少需要多少个储药柜。 二、问题的分析 针对问题一,问题一要求利用附件 1 的数据,给出竖向隔板间距类型最少的储药柜设计方案,包括类型的数量和每种类型所对应的药盒规格。在解决问题一时,首先要考虑到药盒在储药槽内推送过程中,储药槽的宽度是否小于药盒自身宽度的两倍、药盒竖直推送横截面中的对角线、药盒的宽与长所对应不相邻的顶点连成的对角线,即使药盒3 在储药槽内推送过程中不出现并排重叠、侧翻、水平旋转的情况;同时药盒与两侧竖向隔板之间应留 2mm 的间隙;每种竖向隔板间距类型中的储药槽宽度都应小于所有规格的药盒中宽度最大的药盒宽度再加上 2mm 的间隙;每种规格的药盒只能放在一种竖向隔板间距类型的储药槽中,此问题是一个优化问题。 针对问题二,问题二是在问题一的模型基础上,考虑宽度冗余,设计储药柜时希望总宽度冗余尽可能小,同时也希望竖向隔板的间距类型数量尽可能少且给出合理的竖向隔板间距类型的数量。在模型建立方面,其中总宽度冗余最小和竖向隔板间距类型最少是两个目标函数,这两个目标是相互矛盾的,不可能同时达到最优,因此建立以求总宽度冗余尽可能小作为约束,以竖向隔板间距的类型数量尽可能少为目标的优化模型。 针对问题三,问题三的目标是确定储药柜横向隔板间距的类型数量,使得储药柜的总平面冗余尽可能的小,且横向隔板间距的类型数量也尽可能的少。由于问题三是在问题二计算基础上进行优化,而问题二已经确定了每种药品编号所对应的竖向隔板间距类型以及该类型的药槽宽度。因此在宽度冗余确定的情况下,求使总平面冗余尽可能小的目标,可转化为求总高度冗余量尽可能小为目标。 针对问题四,问题四是在问题二和问题三的结果基础上求取计算最少需要多少个储药柜,并且要计算每种药品需要的储药槽个数。 三、模型的假设 (1)假设侧翻只考虑纵向侧翻; (2)忽略横向和竖向隔板厚度; (3)假设所有药盒都是传统长方体或正方体的形状。 四、符号的说明 ia:第i种药盒规格中的长度(1)iN ; ib:第i种药盒规格中的宽度(1)iN ; ic:第i种药盒规格中的高度(1)iN ; jl:第j种竖直隔板间距类型的储药槽的长度(1)jM ; jw:第j种竖直隔板间距类型的储药槽的宽度(1)jM ; jh:第j种竖直隔板间距类型的储药槽的高度(1)jM ; 4 kO:第k种横向隔板间距类型的储药槽的高度(1)ke ; iv:第i种药盒规格所对应的储药槽的宽度(1)iN ; L:储药柜的长度; W:储药柜的宽度; H:储药柜的高度; Q:充分大数(500)Q ; N:药品编号的总数量; M:竖向隔板间距类型总数量; e:横向隔板间距的类型数量; 1e:横向隔板间距的类型数量上界值; 2e:横向隔板间距的类型数量下界值; G:总宽度冗余; 1G:总宽度冗余的上界值; 2G:总宽度冗余的下界值; ig:第i种药盒规格的宽度冗余(1)iN ; jr:第j种竖向隔板间距类型的储药槽数量(1)jM ; 1110ikixiNei第 种药盒规格放在第k种横向隔板中(,k)第 种药盒规格不放在第k种横向隔板中; 1110ijjixiNjMji第 种竖向隔板间距类型中包括第 种药盒规格(,)第 种竖向隔板间距类型中不包括第 种药盒规格; 五、模型的建立与求解 5.1 模型准备 并排重叠、侧翻、水平旋转的定义 (1)并排重叠 规格相同的药盒在储药槽内推送过程中排列在同一
网站客服QQ:2055934822
金锄头文库版权所有
经营许可证:蜀ICP备13022795号 | 川公网安备 51140202000112号