2014数学建模D题 - 图文

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

（请先阅读“全国大学生数学建模竞赛论文格式规范”）

D题 储药柜的设计

储药柜的结构类似于书橱，通常由若干个横向隔板和竖向隔板将储药柜分割成若干个储药槽(如图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 储药柜立体示意图

图2 储药柜的侧剖面及药品摆放示意图

图3 储药槽药品摆放情况

摘 要

本文研究的是根据某县的乡（镇）、村公路网示意图，如何在不同条件下制定出最佳灾情巡视方案的问题。

针对问题一：首先将公路网转化为一张无向赋权图并构造其邻接矩阵，然后根据Dijkstra算法求出任意两点间的最短距离及O点到其余顶点的最短路，最短路构成了一棵以O为树根的最小生成树，将干枝分为三组，每组各顶点间的最短路构成一个完备加权图，再建立混合整数规划模型求其最佳H圈。再逐步调整，使三组中路程较长者减小，最后得到三个组路程分别为204.9km、208.8km和205.3km，最长路程为208.8km，路程均衡度为1.9%，总路程为619km。

针对问题二:依题意至少需要4组，根据问题一中得到的最小生成树将顶点分为4组，利用问题一中的算法，求出每组的最佳H圈，然后逐步调整，使四组中用时较长者减小，最后得到四个组所用时间分别为21.9h、22.41h、22.12h和21.66h，最长时间为22.41h，时间均衡度为3.3%。

针对问题三:根据O点到最远点的距离确定时间上界，然后根据时间上界和到O点的距离由远及近确定最优巡视路线，得最优方案为分23组，巡视时间为6.43h，具体路径见问题三解答。

针对问题四：以问题二中所得结果为例，固定T，t和V中的两个量，改变一个量，求巡视时间与该变量间的关系，巡视时间与T，t和V的曲线图见解答四。

关键词：Dijkstra算法、最小生成树、加权完备图、最佳H圈、整数规划

1.问题重述

1.1问题背景

今年夏天该县遭受水灾。为考察灾情、组织自救，县领导决定，带领有关部门负责人到全县各乡（镇）、村巡视。巡视路线指从县政府所在地出发，走遍各乡（镇）、村，又回到县政府所在地的路线。 1.2需要解决的问题

问题一:若分三组（路）巡视，试设计总路程最短且各组尽可能均衡的巡视路线。

问题二:假定巡视人员在各乡（镇）停留时间T=2小时，在各村停留时间t=1小时，汽车行驶速度V=35公里/小时。要在24小时内完成巡视，至少应分几组；给出这种分组下你认为最佳的巡视路线。

问题三:在上述关于T , t和V的假定下，如果巡视人员足够多，完成巡视的最短时间是多少；给出在这种最短时间完成巡视的要求下，你认为最佳的巡视路线。

问题四:若巡视组数已定(如三组），要求尽快完成巡视，讨论T，t和V改变对最佳巡视路线的影响。

2.模型的假设

假设一:各组在巡视过程中，路途通畅，无任何延误时间。 假设二:各组行驶车速都相同，并且匀速行驶。

假设三:非本组巡视的乡（镇）或村只是路过，不作停留。

3.符号的说明

符号 T t V wij dij Zk L α sjk sj 符号说明 在乡(镇)的停留时间 在村的停留时间 汽车的速度 两相邻点i和j的距离 点i和点j的最短距离 第k组的最佳H圈的路程 第一问三个组中路程最大者 路程均衡度 第k组的巡视时间 几个组巡视时间的最大者，即完成巡视任务所需时间 4.问题分析

针对问题一:问题一是多个推销员问题，我们首先考虑对乡(镇）、村这些点进行分组，然后安排三组人进行巡视，将多个推销员问题转化为单个推销员问题。首先根据公路网图建立一个邻接矩阵储存相邻顶点间的距离，然后根据所得的邻接矩阵用Dijkstra算法求出任意两个顶点间的最短距离及O点到其余顶点间的最短路，再根据O点到其余顶点的最短路用Matlab画出以O为树根的最小生成树(程序见附录一)，由最小生成树的树枝将顶点分为三组，根据每组各点间的最短

5

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说教育文库2014数学建模D题 - 图文在线全文阅读。