医院病房安排问题的线性规划模型

医院病房安排问题的线性规划模型

0患者产品了时间不同,导致病人材料不公平医院的医疗团队是众所周知的现象，它以这种方式出现在我们面前。例如，患者应该去诊所、支付场所、药房和药品、注射室、住院等，并等待接受特定服务。现在考虑医院住院部的病床安排问题,医院住院部通常按照科室划分病床数,而每一个科室的手术又可以分为几大类,每类手术病人的术后恢复时间不同,但同一类手术病人的术后恢复时间服从相同的分布,不同类手术病人的术后恢复时间服从不同的分布。医院为了管理方便,通常会把一周的手术时间提前做一个安排,如一些病人较少的手术会集中安排在某一天做,而常见病的手术则安排在其余的时间内完成。假设医院某科室的住院部病床数一定,而该科室的门诊部每天都接诊各类病人,这些病人中有一部分是需要等待住院手术的病人,由于医院的病床有限,需要手术的病人不可能立即被安排入院,由此产生了等待入院的排队现象;另一方面,由于某些手术只在一周内的某一天做,已经入院的病人可能需要等待较长的时间才能得到手术治疗,由此又会产生等待手术的排队现象。在排队等待入院期间,由于病人得不到及时治疗会造成病情加重,因而带来损失,而在排队等待手术期间,一方面病人的病情可能会继续加重,另一方面病人还需要支付每天的住院费,因此会对病人造成的更为严重的损失。目前大部分医院的做法是,除了急诊病人优先安排住院以外,其余的病人都是按照先到先服务的原则排队等待入院。直观地看,这种做法似乎对病人最公平。事实上,由于不同类型病人的手术时间表不一样,完全按照先到先服务的原则安排入院顺序由于没有考虑病人入院后的等待手术时间,必然会导致已入院病人平均的等待手术时间加长,病人平均占用病床的时间会延长,由此导致服务率下降,病床周转率下降,病人等待入院的时间反而会加长。在实际中确实有类似的情况发生,医院按照先到先服务的原则安排病人入院,但发现排队等待的人数越来越多。假设医院某科室共有N张病床,该科室接诊的手术病人有k类,一周内每天安排的各类手术数目的上限已知,排队等待的病人共有m(m>N)个,每个病人已经排队等待的时间和需要接受手术的类型已知,在未来一周内每天出院的病人数已知,问题是在未来一周内如何安排排队等待病人的入院顺序,才能使病人的平均等待费用达到最低?本文中我们拟综合考虑病人等待入院的时间(损失)和等待手术的时间(损失),寻求一段时间内的最佳病床安排方案,使得全体病人的平均总等待损失最小。1医院病床配置的线性规划模型1.1第13.第i个病人入院过程中压力dk分析假设一周有5天工作日,周六、周日不安排手术,每周日安排下周入院病人顺序。{1,2,….,K}:手术类型集合;M为排队等待入院的人数;Nt为预计在未来一周内,第t天出院的病人数目,即空出的病床数,i=1,2,…7。aij={10i=1,2,⋯,Μ,j=1,2,...,Κ,其中aij=1表示第i个病人需要接受第j类手术,aij=0示第i个病人不需要接受第j类手术。bjt(j=1,2,…,K,t=1,2,…7)表示第j种类型病人第t(周t)天入院需要等待手术的最短时间。xit={10i=1,2,⋯,m;t=1,2,…,7xit=1(i=1,2,…,m,t=1,2,…,7)表示安排第i个病人在下周的第t天入院。xit=0(i=1,2,…,m,t=1,2,…,7)表示不安排第i个病人在下周的第t天入院。ci∶(i=1,2,…,m)第i个等待入院病人到本周日为止已经等待的天数。pi∶(i=1,2,…,m)第i个等待入院病人的等待顺序号;其中序号越小表示此人排序越靠前,应该优先安排序号小的病人入院。dk1∶k=1,2,…k表示第k类手术病人等待入院过程中平均每天的损失费。dk2∶k=1,2,…k表示第k类手术病人入院后等待手术过程中平均每天的损失费。1.2目标函数若不考虑急诊病人优先入院的情况,医院可以在总体上不破坏先到先服务大原则的前提下,对一段时间内等待入院病人的入院顺序做适当调整以实现病人平均等待费用最低的目标。病人的入院顺序安排问题可以表示成如下的线性规划模型minz=m∑i=1k∑j=17∑t=1aijpidj1xit+m∑i=1k∑j=17∑t=1aijdj2bjtxit+m∑i=1dj1(ci+7)aij(1-7∑t=1xit)s.t.{m∑i=1xit≤t∑s=1Νst=1,2,⋯7(1)7∑t=1xit≤1i=1,2,⋯,m(2)xit=0或1,i=1,2,⋯m;t=1,2,⋯,7(3)(LΡ-1)目标函数表示全体等待病人在未来一周内产生的总等待费用,由于本周能够入院的病人的入院顺序均在上周日这天统一安排,病人在周日安排之前产生的等待费用已经在上周计算过,所以本模型中没有考虑。其中第一项表示全体已经安排入院的病人在未来一周等待入院的总费用;第二项表示未来一周内已经安排入院的全体病人等待手术的总费用,第三项表示未来一周内没有被安排入院的病人的总等待入院费用(包括以前的等待费用及未来一周的等待费用)。为了在一定程度上满足先到先服务的大原则,我们在目标函数的第一项中引入了排队等待入院的顺序号,以保证同一类病人满足先到先入院的原则,但不同类型手术的病人之间由于等待手术时间和费用不同因而可能不满足先到先服务的原则,这正是本模型有别于传统入院安排模型的创新之处。约束条件(1)表示未来一周内每天安排的入院人数不能超过当天的空病床数,考虑到各类手术的时间安排不尽相同,如果让一个病人入院后不能及时手术,则在医院里等待的费用可能比在院外等待的费用还高,因此,本约束没有严格限制每天入院的人数必须等于空出来的病床数,这在实际操作过程中更人性化。约束条件(2)表示每个病人在未来一周内最多被安排一次入院。约束条件(3)是变量取值的限制。1.3前入院时长为7或1i,2,3,4.2节线性规划模型若考虑每天会有少量的急诊病人需要及时入院手术,在安排下一周的入院计划时应该预留一定的床位以备接收急诊病人需要。又由于每天来诊的急诊病人数不是一个常数,因此为急诊病人预留的病床无法确切的预测,此时可以有两种办法解决这个问题:方法一:按照每天接诊的急诊病人数的统计规律,求出每天来就诊的急诊病人的平均值和标准差,并计算出如果要满足一定比例的急诊病人及时入院,大约需要预留的病床数,再按照这个数值预留每天的病床数。除去预留的病床以外,其余病床按照1.2中的线性规划模型确定排队等待病人的入院时间。假设每天来医院的急诊病人数Y服从参数为λ的泊松分布,若要保证急诊病人中90%的能够及时入院治疗,则通过查泊松分布表可以得到应该预留的病床数R,R满足:P(Y≤R)≥90%。得到R之后,我们再安排未来一周的床位最佳分配方案,可以按照以下线性规划模型。minz=m∑i=1k∑j=17∑t=1aijpidj1txit+m∑i=1k∑j=17∑t=1aijdj2bjtxit+m∑i=1dj1(ci+7)aij(1-7∑t=1xit)s.t.{m∑i=1xit≤t∑s=1(Νs-R)t=1,2,⋯7(4)7∑t=1xit≤1i=1,2,⋯,m(5)xit=0或1,i=1,2,⋯m;t=1,2,⋯,7(6)(LΡ-2)该模型中的约束条件(4)与1.2节线性规划模型中的约束条件(1)相比,等式右端变小了,即把每天新空出来的病床预留R张给急诊病人,约束条件(5)(6)与1.2中模型的约束条件(2)(3)完全相同,目标函数也与1.2中模型的目标函数完全相同。方法二:根据每天接诊急诊患者的情况,确定的第二天入院的病人。由于急诊患者具有最高的优先级,一旦有空床位必须安排其先入院,而且急诊患者的手术时间不受普通手术时间安排的限制,即急诊患者一旦入院,可以立即安排手术。由于急诊患者每天到达的人数不是确定的,因此,我们无法事先安排一周的入院病人顺序,但可以根据当天的排队等待患者和急诊患者的情况,确定第二天入院的病人,使得所有患者的总等待费用达到最低。{1,2,…,K,K+1}:手术类型集合,其中前K种为普通手术,第K+1种为急诊手术。M:排队等待入院的病人数(包括普通病人和急诊病人);N:第2天拟出院的病人数目,即空出的病床数。aij={10i=1,2,⋯,Μ,j=1,2,...,Κ+1,其中,aij=1表示第i个病人需要接受第j类手术,aij=0示第i个病人不需要接受第j种手术。bj(j=1,2,…,K+1)表示第j种类型病人第二天入院需要等待手术的最短时间,其中bk+1=0,表示急诊病人入院即可接收手术,不需要等待。xi={10i=1,2,⋯,m‚xi=1(i=1,2,⋯,m)表示安排第i个病人第二天入院;xi=0(i=1,2,…,m)表示不安排第i个病人第二天入院。ci∶(i=1,2,…,m)第i个等待入院病人已经等待的天数。pi∶(i=1,2,…,m)第i个等待入院病人的等待顺序号;其中序号越小表示此人排序越靠前,应该优先安排序号小的病人入院,急诊病人对应的入院序号为0,即急诊病人优先入院。dk1∶k=1,2,…K,K+1表示第k类手术病人等待入院过程中平均每天的损失费,其中急诊病人对应的等待入院损失是一个很大的正数。dk2∶k=1,2,…,K,K+1表示第k类手术病人入院后等待手术过程中平均每天的损失费,其中急诊病人对应的等待手术损失是一个很大的正数。包括急诊病人在内的等待病人入院安排问题可以表示为以下线性规划模型minz=m∑i=1k+1∑j=1aijpidj1xi+m∑i=1k+1∑j=1aijdj2bjxi+m∑i=1dj1(ci+2)aij(1-xi)(7)s.t.{m∑i=1xi≤Ν(8)xi=0或1,i=1,2,⋯m(9)(LΡ-3)其中目标函数(7)表示全体病人的总等待费用。第一项是安排第二天入院的病人的总等待入院费用,第二项是安排第二天入院的病人入院后等待手术的总费用,第三项是没有安排第二天入院的病人的总等待费用,此项费用包括以前等待的天数和此次没有安排入院需要等待的天数(2天)所产生的总等待费用。由于急诊病人的排队序号为0,等待入院费用很大,等待手术费用也很高,因此,从目标函数最优的角度看,只要有空床,优先安排急诊病人入院,则这部分急诊病人的等待费用就会等于0,否则,若不安排急诊病人入院,则由于急诊病人的等待费用很高必然会导致目标函数值远离最优值。因此,急诊病人一定会被优先安排入院的。约束条件(8)表示第二天安排入院的人数不超过空病床的数目;约束条件(9)是变量取值约束。2未来一年内病人叶片转移和入院顺序以某医院眼科病房为例,该病房共有79张病床,主要接诊的病人类型有白内障单眼,白内障双眼,青光眼,视网膜疾病,外伤等五类,医院每周安排各类手术的时间表为:周一、周三只安排白内障手术,其中,白内障双眼只能周一做一只眼,周三做另一只眼,白内障单眼可以周一或周三做。周二、四、五不安排白内障手术,只安排其它眼科手术,且不再区分类型。外伤属于急诊,不受手术时间安排的限制,即外伤病人一旦入院,第二天即可安排手术。假设各类手术病人在等待入院以及入院后等待手术过程中每天产生的费用如表1。根据医院的手术时间表,各类病人在一周内各天入院需要等待手术的时间如表2。假设未来一周内每天有3个病人出院,等待入院的病人共有50个,其中前30个等待病人的信息如表3。不考虑外伤的情况下,假若按照先到先服务的原则安排入院顺序,则在未来一周内应该安排前21位患者入院,经过计算,这些患者的平均等待手术时间为3天,平均等待费用为600元。根据模型一,利用Lingo编写算法实现程序,在前30位病人中确定出未来一周内入院病人的顺序如表4。根据表4的结果容易计算出,病人的平均等待手术时间为1.4天,平均等待费用为280元,比原先的安排方案节约了50%以上。从表4还可以看出,未来一周安排的病人是1-20和22号,由于21号病人和22号病人的等待时间相同,21号病人是青光眼患者,22号为白内障双眼,22号病人周日入院比21号病人等待手术时间短,因此22号病人先入院。另外,从结果中可以看到,一周内病人的入院顺序没有完全按照先到先服务的原则安排,而是基于疾病的种类与入院后等待手术的时间进行安排的。考虑外伤的情况下,可以用类似的方法得到问题的最优解。3/3问题的线性线性规划模型及算法本文研究了医院病床安排问题,在综合考虑病人等待入院时间和入院后等待手术时间两方面因素的前提下,建立了使总等待费用最低的病床安排问题线性规划模型,有效克服了传统的先到先服务原则下安排入院顺序的缺陷,经过计算可以发现,利用本文的模型安排的入院顺序,可以使平均等待手术时间减少约50%,从而降低了病人的等待损失,有效提高了医院病床的利用率。虽然本文建立的模型均是0～1整数规划模型,但经过观察不难以发现,模型LP-1及LP-2的约束条件系数矩阵与运输问题的约束条件系数矩阵完全相同,由于运输问题的约束条件系数矩阵具有全幺模性(即任—非零一子方阵的行列式均为1或-1),因而LP-1及LP-2的系数矩阵是全幺模矩阵。对于本文建立的模型LP-3,其约束条件系数矩阵是一个行向量,且