非线性规划 优化模型

《非线性规划 优化模型》由会员分享，可在线阅读，更多相关《非线性规划 优化模型（8页珍藏版）》请在金锄头文库上搜索。

1、基于基于 M/M/SM/M/S 排队论的病床安排模型排队论的病床安排模型（获年大学生数学建模赛全国二等奖）数学与计算科学学院 雷蕾信息科学与计算学院 黄缨宁 信息科学与计算学院 丁炜杰指导老师：王其如 教授摘要 就医排队是一种我们非常熟悉的现象。在眼科医院的病床安排中，主要从 医院高效工作和患者满意度两方面来考虑安排方法。本文通过确定两方面的权 重，确立评价标准。 针对问题二，本文确定了从医院和患者两方面综合考虑的目标函数，医院 各种诊疗规则的限制下进行线性规划，使得目标函数值（背离度）最小，得到 问题二的解决方案。用问题一的标准评价，确实优于医院的 FCFS 模型。 问题三中对每一类病人术后

2、恢复时间做统计，由计算机按照概率给出术后 恢复的时间，运用第二问模型的选择方式，对近一段时间内的出入院人数作出 合理预测，并根据 M 的排序确定患者入院的时间区间。 对于问题四，先确立白内障双眼手术的方案（调查支持可以任意不同两天 手术） ，按照问题二的算法，先算出周二四做白内障手术的最小 M 值及入院前等 待时间和术前等待时间。用计算机模拟出在手术时间可调整情况下 M 可能的最 小值，得到周三五为最佳手术时间。尤其术前人均等待时间的优化减少使医院 病床的有效使用率增加。模型改进率达到 18.11%。 问题五要求确定病床固定分配使人均等待时间最短。病床的分配使整个排 队系统变成了五个 M/M/

3、N 模型，N 为各类病床的数量。根据排队论中 M/M/1 模 型的条件演化得到服务强度小于 1 及病床数固定不变。采取整数规划，在此限 制条件下使得平均等待时间最小。从而算出各类病床的分配比例。关键词：关键词：M/M/S 模型 泊松（Poisson）分布 非线性规划 优化模型 病人满意度 病床有效利用率 一一 问题的重述问题的重述有某医院眼科门诊每天开放，住院部有病床 79 张。眼科手术主要分四大类： 白内障、视网膜疾病、青光眼和外伤。 白内障手术较简单且没有急症。目前只在周一、三做白内障手术，此类病 人的术前准备时间只需 1、2 天。如果要做双眼是周一先做一只，周三再做另一 只。 外伤疾病通

4、常属于急症，病床有空时立即安排住院，第二天便会安排手术。其他眼科疾病情况不同，住院后 2-3 天就可接受手术，但术后观察时间较 长。这类疾病手术时间可根据需要安排，一般不安排在周一、周三。 医院眼科手术条件较充分，可不考虑手术条件的限制，但考虑到医生的安 排问题，通常情况下白内障手术与其他眼科手术（急症除外）不安排在同一天 做。当前该住院部对全体非急症病人是按照 FCFS 规则安排住院，但等待病人越 来越多。故要优化其模型 问题一：试分析确定合理的评价指标体系，用以评价该问题的病床安排模 型的优劣。 问题二：试就该住院部当前的情况，建立合理的病床安排模型，以根据已 知的第二天拟出院病人数来确定

5、第二天应该安排哪些病人住院。并对你们的模 型利用问题一中的指标体系做出评价。 问题三：作为病人，自然希望尽早知道自己何时能住院。能否根据当时住 院病人及等待住院病人的统计情况，在病人门诊时即告知其大致入住时间区间。问题四：若该住院部周六、周日不安排手术，请你们重新回答问题二，医 院的手术时间安排是否应做出相应调整? 问题五：有人从便于管理的角度提出建议，在一般情形下，医院病床安排 可采取使各类病人占用病床的比例大致固定的方案，试就此方案，建立使得所 有病人在系统内的平均逗留时间（含等待入院及住院时间）最短的病床比例分 配模型。 二二 模型条件的假设模型条件的假设1. 假设如有空床位，优先安排外

6、伤病人； 2. 设有一患者当天出院，则立即可以安排另外的人入院； 3. 设定做白内障手术的两天不做其他手术； 4. 假设除了外伤无其他急症； 5. 白内障病人手术准备时间是 1-2 天的任意值，不是因人而异，青光眼和视网 膜疾病手术准备时间是 2-3 天的任意值。三三 符号的定义及说明符号的定义及说明1. Bi：各类患者从入院到手术所花费的平均时间（手术准备时间） ；2. 1 2 3：分别为 M1 M2 M3的权值； 3. K1i K2i ：分别表示第 i 个病人在第一阶段的等待时间和该病人在术前住院 时间； 4. S：某一天出院的病人数； 5. W：等待病床的总人数； 6. W1 W2 W3

7、 W4：分别等待病床的人中白双、白单、青光眼和视网膜疾病、外伤 的人数； 7. P (i,j)：第 i 类第 j 号的人； 8. M(i,j)：第 i 类第 j 号人的 M； 9. Pk：泊松分布中 k 个病人到达的概率； 10. 123 456：分别表示白双、白单、青光眼、视网膜疾病，外伤以 及出院人数的平均到达率； 11. Pn(t)：时间 t 内有 n 个患者在排队的概率； 12. i：各类病床系统的服务强度； 13. i：各类患者的平均服务率； 14. n1 n2 n3 n4 n5：五类病人各应该分配的病床数； 15. D1，D2：选择两天做白内障手术的星期数; 16. x1 x2 x

8、3 x4 x5 x6 a1 a2 a3 a4 a5 a6:各种病情的等待人数及其系数四四 模型的分析及求解模型的分析及求解问题一：1.确定评价指标： 从病人和医院两方面对模型进行分析，病人方面以花费时间，住院费用和 公平性作为满意程度的指标，医院方面以病床利用率和病床有效利用率为作为 评价指标。同时还有一些客观条件有可能影响到评价指标，如所有病者是否一 致对待还是有优先考虑。 花费时间是指从门诊到出院的时间，费用则根据入院到出院的时间计算， 公平性是根据是否先门诊先入院来进行评判，床位利用率是指住有病人的床位 与所有床位的比，有效的床位利用是指床位上所住病人属于必须住院日期与所 住的所有日期的

9、比，如白内障术前准备时间 2-3 天，术后恢复时间 3-4 天，超 过此时间则属于床位的无效利用，需要避免。 将患者就医分为三个过程：门诊到入院为第一阶段，入院到进行手术为第 二阶段，手术完毕到出院为第三阶段。得出如下评价指标可能的构成因素： 1.第一阶段等待时间1.花费时间 2.第二阶段等待时间3.第三阶段的住院时间 患者（满意度） 1 第二阶段准备时期费用 2.住院的费用 2 第三阶段住院费用3 手术费用 可能构成因素3.公平性医院（效率） 1.床位利用率2.床位有效利用率客观条件：1.病者类别 对于患者：病好后立即出院，第三阶段住院时间与任意安排入院模型无关， 在模型中不予考虑。第三阶段

10、住院费用取决于第三阶段住院时间，也不予考虑。对于医院： 由于等待病人很多，假设不考虑留有外伤空床则使用率都可达 到 100%，不再考虑。病床有效利用率是指病床所住病者是否属于必要住院期， 包括：术前准备时间，手术时间和术后康复期。 对于客观条件：由于外伤立即安排入院，其它病症急症不考虑，所以除外 伤外所有病例一致对待。 综上，评价标准的确实构成因素为 公平性 公平性 患者 第一阶段等待时间 等待时间 评价标准 第二阶段等待时间医院 床位有效利用率 滞留率第一阶段越长，病人越不满意。计算门诊到住院所用的平均时间，用 某病的等待时间减去平均时间，故第一阶段不满意程度为： M1=K1i-Pi 第二阶

11、段，对不同病症，由统计数据算出入院到手术的平均术前准备时 间，超出平均时间越多， 满意率越低，且病床的合理利用率越低，故把第 二阶段评判标准抽象成滞留时间，表示为 0M2=K2i-Bi FCFS 排队方法对病人的公平性为 100%。而根据优化算法，把不公平性 M3的值量化为： M3=逆序数/总人数 评价标准 M 由 M1，M2，M3经过加权决定，设系数为 1 2 3，有： M=1M1+2M2 +3M3 三个标准的权值，确定为病人和医院各为 50%,公平性、等待时间和费 用的权值各为 16.65%。可以得到 1=0.1665，2=0.6665，3=0.1665 .2.对于 FCF 模型的评价：

12、按照 FCFS 规则安排住院，公平性达到 100%，但有效床位利用率较低， 如第 25，30，32 号的白内障病例术前准备时间都达到 7 天，大大超过有效 的 1-2 天，导致住院时间达到 13 天，增加了病患的不必要费用。这是 FCFS 规则的缺点，不仅增大了病者的滞留率降低了床位的有效利用率，同时也降 低了病者的满意率。问题二：问题二：. 标准的设立：由于该模型是已知第二天模拟出院病人数 S 与通过门诊在等待病床的人数 W 确定第二天入院名单，其设置满足局部最优解，因此在模型建立时不考虑整个 过程的公平性，因此我们设立的标准为： M=1M1+2M2 .模型的建立： 将等待病床的人数分为白内

13、障双 W1、白内障单 W2，视网膜疾病和青光眼 W3 和外伤 W4四类，每类病人都按照门诊的先后顺序进行排序。这样对每一个等待 的人 P（i，j）都有一个对应的 M(i,j)， （i，j）为有序实数对 M(i,j)= 1M1+2M2如图为随意挑选时间和编号对应的人及其 M 值：21 日22 日23 日24 日25 日26 日27 日28 日M（1，10 ）- 0.868- 0.768- 0.668- 0.568- 0.468- 0.368- 0.268- 0.168 M（3，13 ）- 0.872- 0.772- 0.672- 0.572- 0.472- 0.372- 0.272- 0.172

14、 对于正在等待的病者的 M(i,j)值进行计算和比较，选出所有 P(i，j)中 M(i，j)值较小的 S 个，即 C 为拥有 S 个元素的集合 C=(i，j) St M(i,j)最小 （(i,j)属于 C） 每天都可以做手术 周一 ,周三只做白内障手术 除周一，周三的其它天不做白内障手术 白内障双眼手术只能在周一做第一只眼睛，周三做第二只眼睛4.数据模拟，实验和测算 以原表作为前置条件，确定刚开始（7 月 13 日）的床位情况。在此基础上 对 7 月 13 后的排队情况重新进行模拟，模拟 9 月 15 日前可以入院的情况。新 的排队顺序如附录一。得到如下结果：人均等待入院时间人均术前等待时间人

15、均住院时间FCFS11.21083.23329.3251新模型11.62732.56489.2083M1=1884.24530，M2=1548.46，差值为 335.779，改进百分比为 17.82%。. 问题三：问题三：.模型建立和求解： 由第二问的模型，每天都可以模拟出第二天入住的人数，各类病人术前 准备时间已知，可在病人入院时确定其手术时间。经统计，每类病人住院时间 分布比较集中且具有一定的概率，因此我们可以由计算机按每类病者康复概率 给与病人一个术后恢复时间，由于是根据原本的概率进行选择，所以拟合程度 很高。这样就可以模拟出相当长一段时间内的出入院人数的变化，并制成表格， 在病人门诊是就可大致告诉病人入院时间。 我们根据原来的模型对一段时间内的出院变化进行模拟，并且预测入院情 况。详情见附录二。问题四：问题四：若周六日不做手术，先设定医院仍在周一和周三进行白内障手术。根据第 二问的标准我们对模型进行规划。 1.模型建立与求解： 由于题目中写道白内障手术需要 1，2 天休息，如果手术不算休息，则白 内障双眼两次手术中间应该间隔一天，这样满足的条件为：选择 D1，D2 St M(i,j)最小 周六周日不手术 D1 ,D2 只做白内障手术 除 D1，D2 的其它三天不做白内障手术 白内障双眼手术 D1 做第一只眼睛，D2 做第二