数学建模病床安排命题与解题思路解析.ppt

解题思路1 CUMCM09CUMCM09年年B B题题 “ “眼科病床的合理安排眼科病床的合理安排” ” 命题、解题思路解析及论文点评命题、解题思路解析及论文点评 国防科技大学国防科技大学 吴孟达吴孟达 河南河南 郑州郑州 20102010年年4 4月月8 8日日 2解题思路 目目 录录 n n 命题思路命题思路 n n 解题思路解题思路 n n 论文点评论文点评 n n 综合评述综合评述 3解题思路 命命 题题 思思 路路 n n 来自于人们司空见惯的日常生活现象来自于人们司空见惯的日常生活现象医院住医院住 院排队现象院排队现象的一道题目，问题本身非常浅显的一道题目，问题本身非常浅显 明白，专业门槛低，但解决问题中却涉及较深明白，专业门槛低，但解决问题中却涉及较深 刻的排队论理论问题，当无法通过理论方法获刻的排队论理论问题，当无法通过理论方法获 得最优解时，可以通过仿真优化方法获得实用得最优解时，可以通过仿真优化方法获得实用 效果令人满意的可行解，以上构成该道题目的效果令人满意的可行解，以上构成该道题目的 特点。特点。 4解题思路 n n 这一类以排队论及仿真优化方法为主要解决这一类以排队论及仿真优化方法为主要解决 方法的题目，在方法的题目，在CUMCMCUMCM的历年竞赛题目中，还的历年竞赛题目中，还 不多见。而这一类随机服务系统优化的问题不多见。而这一类随机服务系统优化的问题 ，在现实实际中却是大量存在的，因此，在，在现实实际中却是大量存在的，因此，在 以反映现实生活中的数学建模问题为己任的以反映现实生活中的数学建模问题为己任的 大学生数学建模竞赛中，出现这一类题目，大学生数学建模竞赛中，出现这一类题目， 也是很自然的事情，也是很自然的事情，MCMMCM中如中如0404年年B B题题“ “游乐场游乐场 快速通道问题快速通道问题” ”，0505年年B B题题“ “高速公路收费站问高速公路收费站问 题题” ”，就是两个这类问题的实例。，就是两个这类问题的实例。 5解题思路 n n 与我国庞大的人口总量相比较，好的医院与我国庞大的人口总量相比较，好的医院 与好的医生目前还是一种稀缺资源，题目与好的医生目前还是一种稀缺资源，题目 中提到的医院住院排队现象及其严重程度中提到的医院住院排队现象及其严重程度 是确实存在的，本问题提出的初衷，就是是确实存在的，本问题提出的初衷，就是 要得到对现有的病床安排要得到对现有的病床安排FCFSFCFS方案的一个方案的一个 现实、合理的改进方案，所以，能得到最现实、合理的改进方案，所以，能得到最 优解固然好，否则得到一个实用效果令人优解固然好，否则得到一个实用效果令人 满意的可行解，也是可以的。满意的可行解，也是可以的。 6解题思路 n n 主要考点：主要考点： 1. 1. 分布拟合检验；分布拟合检验； 2. 2. 合理的评价指标体系；合理的评价指标体系； 3. 3. 仿真方法应用；仿真方法应用； 4. 4. 满足一定置信度的统计预测模型的建立；满足一定置信度的统计预测模型的建立； 5. 5. 排队论优化模型的建立。排队论优化模型的建立。 7解题思路 n n 评阅原则评阅原则 本题解题方法比较多，结果也未必一致本题解题方法比较多，结果也未必一致 ，评阅时主要以解题过程中体现出的对问题，评阅时主要以解题过程中体现出的对问题 的理解程度与建模能力为依据。的理解程度与建模能力为依据。 8解题思路 解解 题题 思思 路路 数据分析与检验数据分析与检验 n n 在着手解决问题前首先应对所给数据进行分析，在着手解决问题前首先应对所给数据进行分析， 从中获得对解题有用的信息，这是一种基本素质从中获得对解题有用的信息，这是一种基本素质 ，是一种具有良好工程素养的表现。在本问题中，是一种具有良好工程素养的表现。在本问题中 ，这一过程尤其重要，因为如果对病人到达规律，这一过程尤其重要，因为如果对病人到达规律 及病人住院时间规律都不了解，问题症结就抓不及病人住院时间规律都不了解，问题症结就抓不 准，解题将缺乏方向感，仿真计算就更无法进行准，解题将缺乏方向感，仿真计算就更无法进行 了。了。 9解题思路 n n 在本题所给数据中，各类病人到达人数分别服从不同参在本题所给数据中，各类病人到达人数分别服从不同参 数的数的PoissonPoisson分布，需要进行分布拟合检验及分布参数分布，需要进行分布拟合检验及分布参数 提取。提取。 n n 由所给数据可以看出，病人术前住院时间是确定的，依由所给数据可以看出，病人术前住院时间是确定的，依 入院时间而定，所以病人住院时间中只有术后住院时间入院时间而定，所以病人住院时间中只有术后住院时间 是随机的，要做拟合检验的也是这一部分时间分布。是随机的，要做拟合检验的也是这一部分时间分布。 n n 各类病人术后住院时间分别服从正态分布各类病人术后住院时间分别服从正态分布 、分布分布 或或 埃尔朗分布，由于检验方法或检验细节处理不相同，可埃尔朗分布，由于检验方法或检验细节处理不相同，可 能得到以上不同的分布，这是允许的，但若得出服从负能得到以上不同的分布，这是允许的，但若得出服从负 指数分布的结论，则是错误的。也有一些同学不做拟合指数分布的结论，则是错误的。也有一些同学不做拟合 分布检验，而是画出直方图，然后以此经验分布作仿真分布检验，而是画出直方图，然后以此经验分布作仿真 依据，这样处理也是可以的。依据，这样处理也是可以的。 10解题思路 n n 数据分析做得比较深入的同学，会发现一数据分析做得比较深入的同学，会发现一 条隐含在数据中的关键信息：术前住院时条隐含在数据中的关键信息：术前住院时 间过长是当前病床使用效率不高的主要因间过长是当前病床使用效率不高的主要因 素。这样一个关键信息的获得，会使得建素。这样一个关键信息的获得，会使得建 模更有方向感。模更有方向感。 11解题思路 第第 一一 问问 主要考核对问题的考虑是否全面，对问题实质的理解是主要考核对问题的考虑是否全面，对问题实质的理解是 否到位。评价指标分两类：效率指标和公平性指标。否到位。评价指标分两类：效率指标和公平性指标。 两类指标可以有各种不同的定义，其合理性是评分依据两类指标可以有各种不同的定义，其合理性是评分依据 。 效率指标效率指标平均平均术前住院时间，或病床有效利用率。术前住院时间，或病床有效利用率。 非外伤病人入院第非外伤病人入院第2 2日（白内障）或第日（白内障）或第3 3日（其他眼病）日（其他眼病） 后等待手术的时间称为病床无效时间，病床有效利用率后等待手术的时间称为病床无效时间，病床有效利用率 定义为定义为 病床有效利用率病床有效利用率 = 1 - = 1 - 病床无效时间病床无效时间 / / 该病人住院时间该病人住院时间 12解题思路 公平性指标公平性指标从公平性考虑，希望尽量做到从公平性考虑，希望尽量做到FCFSFCFS（ First come, First serveFirst come, First serve）, ,公平度具体如何确定，是公平度具体如何确定，是 一个小考点。这个指标必须考虑，否则会出现尽量收白一个小考点。这个指标必须考虑，否则会出现尽量收白 内障病人入院，以改善效率指标的现象。内障病人入院，以改善效率指标的现象。 一种比较具操作性的指标是一种比较具操作性的指标是用用“ “延期住院延期住院” ”病人人数占总病人人数占总 出院人数的比例来度量不公平度。出院人数的比例来度量不公平度。 注意到，上述公平度只考虑了注意到，上述公平度只考虑了“ “延期日子延期日子” ”，而没有将，而没有将“ “ 插队人数插队人数” ”度量在内，对此可以有不同的理解与定义，度量在内，对此可以有不同的理解与定义， 不必苛求一致。不必苛求一致。 13解题思路 第第 二二 问问 本问主要考核能否给出一个相对合理的病本问主要考核能否给出一个相对合理的病 床安排模型，主要目标为：提高病床有效利用床安排模型，主要目标为：提高病床有效利用 率以及提高公平度。率以及提高公平度。 就提高病床有效利用率而言，病人术后住就提高病床有效利用率而言，病人术后住 院时间是一个不可优化的量，所以只能在术前院时间是一个不可优化的量，所以只能在术前 等待时间上作文章。经对题目所给数据的分析等待时间上作文章。经对题目所给数据的分析 可知：可知：对白内障病人的入院时间加以限制成为对白内障病人的入院时间加以限制成为 提高效率的必然选择。提高效率的必然选择。 14解题思路 本问主要解决方法是仿真方法，大致可分 为“先仿真，再优化”与“边仿真，边优化”两类 ，前者是先确定若干种住院规则，然后根据仿 真统计结果选出较优规则；后者是先确定一个 优化原则，然后在仿真时，对每一个排队病人 按照该优化原则决定住院先后。显然后者要更 好一些。 15解题思路 n n 一种比较典型的仿真优化方法是：对每一位等待一种比较典型的仿真优化方法是：对每一位等待 入院病人，以该病人当日入院的公平性（以到达入院病人，以该病人当日入院的公平性（以到达 先后计）与病床使用效率（分类考虑）两方面综先后计）与病床使用效率（分类考虑）两方面综 合排序（例如求两个指标的加权和），然后按排合排序（例如求两个指标的加权和），然后按排 序结果安排当日入院病人，由此得到公平合理的序结果安排当日入院病人，由此得到公平合理的 住院方案。按此方案进行仿真，再统计各项评价住院方案。按此方案进行仿真，再统计各项评价 指标值，并与指标值，并与FCFSFCFS方案作比较，此问即告完成。方案作比较，此问即告完成。 16解题思路 n n 值得一提的是，解法的多样性在本问题求解中得到了较值得一提的是，解法的多样性在本问题求解中得到了较 充分的体现，例如有的参赛队引入了计算机操作系统进充分的体现，例如有的参赛队引入了计算机操作系统进 程调度中的最佳响应比算法，使公平性与效率同时得到程调度中的最佳响应比算法，使公平性与效率同时得到 了体现，是一种好的创意。了体现，是一种好的创意。 n n 本问中存在的主要问题是公平性考虑不足，有的队甚至本问中存在的主要问题是公平性考虑不足，有的队甚至 完全不考虑公平性，未免过于脱离实际，而脱离实际是完全不考虑公平性，未免过于脱离实际，而脱离实际是 建模最大的忌讳。还有较普遍存在的问题是主要优化目建模最大的忌讳。还有较普遍存在的问题是主要优化目 标不清晰，罗列了一堆目标，却未抓住提高病床使用效标不清晰，罗列了一堆目标，却未抓住提高病床使用效 率这个要害，其根源还是对题目的理解以及对数据的分率这个要害，其根源还是对题目的理解以及对数据的分 析不够透彻。析不够透彻。 17解题思路 第第 三三 问问 此问希望学生给出一个满足一定置信度（例如： 90%）的预约住院时间区间，区间长度越短越好。 一种自然的想法是通过同类病人术后住院时间的 概率分布从理论上得到这一区间，如果能通过此种理 论方法解决此问题，自然是最理想的。 但这样做的一 个困难是已处于术后住院状态的该类病人的继续住院 时间不服从同一分布，从而将该类病人（含已住院与 未住院）的预计住院时间求和后的随机变量的分布不 知道。 设当前时刻为T0，当前排队人数为P，预计住 院时刻为T，该类病人每日出院人数的统计平均值为， 则 设一个已出院病人实际住院时刻为T1，通过仿真统计 一段时间内所有病人的 根据90%的置信度确定两个阈值 从而得到当前病人的预计住院时间区间为 。 19解题思路 第第 四四 问问 若仍采用若仍采用“ “一三方案一三方案” ”，效率较低，通过分析，效率较低，通过分析 可以发现主要原因是对视网膜与青光眼病人而言可以发现主要原因是对视网膜与青光眼病人而言 ，会造成病床使用效率降低。，会造成病床使用效率降低。 通过有限种方案的仿真计算比较可知，采用通过有限种方案的仿真计算比较可知，采用“ “ 二四方案二四方案” ” 或或“ “三五方案三五方案” ”可使病床使用效率有所可使病床使用效率有所 提高。前者效率公平总体效果较好，后者效率提高。前者效率公平总体效果较好，后者效率 较高，但公平性较差。较高，但公平性较差。 20解题思路 第第 五五 问问 主要有三种模型： 一、仿真计算模型：床位分配只有有限种组合情形，可 以通过穷举仿真方法得到各种组合的评价指标统计值，再 比较得到最佳组合方案。此方案计算量较大，且模型通用 性有一定局限。 二、服务强度平衡模型：当各分类系统的服务强度相等 时，效果最佳。可以通过建立条件极值模型，利用拉格朗 日方法证明这一结论。 三、排队论近似模型：通过经验公式将M/G/K系统近似 为M/M/K系统，然后利用排队论的现成结论写出优化模型 。 21解题思路 论论 文点文点 评评 22解题思路 综综 合合 评评 述述 n n 数据检验是本问题中必须做的，但被许多参赛数据检验是本问题中必须做的，但被许多参赛 队所忽略，从而意外成为区分点之一。队所忽略，从而意外成为区分点之一。 n n 公平性指标被许多人忽略，反映出对问题本质公平性指标被许多人忽略，反映出对问题本质 认识不到位。效率指标也可以适当精简。认识不到位。效率指标也可以适当精简。 n n 优化模型的多样性是本题目最大的亮点，涌现优化模型的多样性是本题目最大的亮点，涌现 许多意料之外的解法。许多意料之外的解法。 23解题思路 n n 入