医院手术室的分配问题 论文1.doc

宁波大学第八届大学生数学建模竞赛 2012 年 5 月 11 日 5 月 14 日参赛题目 A B（在所选题目上打勾）参赛队员 1 参赛队员 2 参赛队员 3 姓名学号学院专业年级电话 短号Email 宁波大学教务处宁波大学数学建模实践基地规划模型解决医院手术室的分配问题摘要本文针对医院分配手术室的问题，主要研究了医院在满足各科室手术时间的情况下，为保证各科室时间均匀分配保证每科室每天都可以对患者进行治疗，院方能够提供最少的时间时，手术室的合理分配问题。模型建立从简单的整数规划入手，循序渐进，延伸到一般的线性规划，使模型逐步得到完善，并进行了相应的推广。对简单模型的不断完善和优化是通过不断改变和限制约束条件来实现的。求解过程主要使用lingo软件，运用了一般线性规划和整数规划的思想来解决问题。最终构建的数学模型基本上实现了既满足了医院手术室的最大化利用，又满足了患者可以每天都有一定的就医治疗的时间和不同类型的病人得到相应治疗条件。 关键字:分配问题规划模型lingo问题重述（引言）宁波市某医院有12个安排值班的手术室，为7个科室（外科、妇科、眼科、耳鼻喉科、骨科、急诊科和口腔外科）提供服务，其中有9个主手术室和3个临时性手术室。 根据手术室使用的小时数，分为”短时使用”和”长时使用”。手术均安排在周一到周五。表1汇总了不同类型手术室每天的可用情况，表2给出了每周手术室时间的需求情况，其中的可允许的分配不足的小时数是可以拒绝一个科室的最多小时数(相对于其一周手术室时间请求)。表格 1手术室可用时间星期可用小时数主手术室”短时使用”主手术室”长时使用”临时手术室”短时使用”临时手术室”长时使用”星期一08:00-15:3008:00-17:0008:00-15:3008:00-16:00星期二08:00-15:3008:00-17:0008:00-15:3008:00-16:00星期三08:30-15:3008:00-16:3008:30-15:3008:00-16:30星期四08:00-15:3008:00-17:0008:00-15:3008:00-16:00星期五09:00-15:3009:00-17:0009:00-15:3009:00-17:00手术室数量93表格 2手术室时间的每周需求小时数科室每周需求小时可允许的分配不足的小时数外科194.0011.0妇科12110.0眼科43.009.00口腔外科23.009.00耳鼻喉科34.008.00骨科478.00急诊科83.00要求建立数学模型解决以下问题：问题1. 利用表1，表2所给数据为每天手术室安排确定一个你认为合理的分配方案。问题2. 若表1数据不变，但表2中各科室每周需求小时数都增加10%，而可允许的分配不足的小时数不变，这时请你给出新的合理的分配方案。符号说明表格 3符号说明符号符号所表示的意义备注星期i，用作k的主手术室的个数i:1,2,3,4,5；k:0表示短时,1表示长时星期i，用作k的临时手术室的个数i:1,2,3,4,5；k:0表示短时,1表示长时星期i，j科的手术时间i:1,2,3,4,5；j:1,2,3,4,5,6,7;星期i，j科使用主手术室作短时使用的个数i:1,2,3,4,5；j:1,2,3,4,5,6,7;星期i，j科使用主手术室作长时使用的个数i:1,2,3,4,5；j:1,2,3,4,5,6,7;星期i，j科使用临时手术室作短时使用的个数i:1,2,3,4,5；j:1,2,3,4,5,6,7;星期i，j科使用临时手术室作长时使用的个数i:1,2,3,4,5；j:1,2,3,4,5,6,7;主短N主手术室“短时使用”的个数NN可以为整数，也可以为小数，小数时表示使用手术室的一部分时间主长N主手术室“长时使用”的个数NN可以为整数，也可以为小数，小数时表示使用手术室的一部分时间临短N临时手术室“短时使用”的个数NN可以为整数，也可以为小数，小数时表示使用手术室的一部分时间临长N临时手术室“短时使用”的个数NN可以为整数，也可以为小数，小数时表示使用手术室的一部分时间基本假设1、各科室所进行的每一个手术的时间均不会超过所在手术室能够提供的最大时间；2、一旦手术室分配给某科室，该科室必须使用完当天手术室提供的全部时间（整数规划时）；3、手术室之间除使用时间长短外无其他差异，临时手术室与主手术室资源配置相同，即临时手术室可以当作主手术室来使用；4、7个科室在手术室的分配问题上不分主次，按照同等位置来处理；注：后两条假设均在初步建模过程中使用。问题分析手术室的合理分配方案目标是：在满足手术时间需求的情况下，使总体时间尽可能的短，提高手术室的利用效率，优化资源的配置。题中已经给出的是手术室的可用时间（表1）和需求的时间（表二），因此，可根据两者之间的关系，结合一些必要的限制，构成约束条件，利用线性规划和整数规划的模型加以处理，而这也是该模型的关键所在。模型建立模型一：设 ,为医院在星期i提供给j科室的不同种类手术室的数量（i表示星期，1= i =,j=1, 2, 3, 4, 5, 6, 7;7.5+9+7.5+8=,j=1, 2, 3, 4, 5, 6, 7;7+8.5+7+8.5=,j=1, 2, 3, 4, 5, 6, 7;7.5+9+7.5+8=,j=1, 2, 3, 4, 5, 6, 7;6.5+8+6.5+8=,j=1, 2, 3, 4, 5, 6, 7;2、一周（五天）医院分配给每个科室的手术时间要大于等于该科室的需求时间：=194;=121;=43;=23;=34;=47;=8;3、各科室每天需求的手术室总数量不超过医院提供的手术室总数量：+=9,i = 1, 2, 3, 4, 5;+=194*1.1;=121*1.1;=43*1.1;=23*1.1;=34*1.1;=47*1.1;=8*1.1;使用lingo软件求解，未找到全局最优解，仔细对比数据，并通过简单的计算不难发现，由于各科室每周的需求时间增加了10%，导致在现有条件下不能够完全满足各科室的手术时间要求，简单的讲，就是说当前医院各手术室能够提供的总时间已经小于各科室手术的需求总时间，因此需要进一步考虑各科室可允许的分配不足的小时数。为简化模型，可先直接用需求时间减去可允许分配不足的小时数来替代需求时间，这样再次修改约束条件如下所示：=194*1.1-11;=121*1.1-10;=43*1.1-9;=23*1.1-9;=34*1.1-8;=47*1.1-8;=8*1.1-3;调用lingo可求得全局最优解（程序见附录一程序二）： Feasible solution found. Objective value: 465.5000 Extended solver steps: 10090 Total solver iterations: 63757仿照第1小题，将各变量的数值经整理后可归纳为表格5（具体分配方案）：表格 5外科妇科眼科口腔外科耳鼻喉科骨科急诊科星期一主短3主长5主短1临长2临长1星期二主长7主长2临长3星期三主短1主长4主短2主长2临短1临长2星期四主短9临长2星期五主短8临短3主短1模型二：问题一、考虑到在做手术时，不一定要每个科室每天分配到的手术室个数必须为整数（如0.5表示使用手术室能够提供的时间的一半），因此，在模型一中的约束条件有些局限性，并不是很合适，在此模型中做出进一步的优化。去掉每科室每天分配到的手术时间个数必须为整数这一约束条件，其他与模型一基本保持不变，很容易得到模型二，使用lingo求解， Global optimal solution found. Objective value: 470.0000 Total solver iterations: 56根据所得数据，整理后可得到如下分配方案：表格 6一般非线性规划分配方案外科妇科眼科口腔外科耳鼻喉科骨科急诊科星期一主长1.38主长1.61主长1.22临长2临长1星期二主长9临长3星期三临长3星期四主长9临长2临长1星期五主长2.88主长4.25主长1.88临长3问题二、参考上一问和模型一中问题二处理方法，很容易构建此处的模型，方法类似，故不再细述。注意：在实际问题中，往往不是每个手术都会用去整个手术室的全部时间，大多数情况下，还是只用去一部分时间， ，的取值使用小数更加合理一些。因此，在下面的问题讨论中，除特殊说明， 均可使用小数形式。模型结果分析及改进结果分析：在上述两种模型的求解过程中，我们会得到大量的有关各个手术室在科室分配中的数据，为分析方便，我们以模型一的问题一为例，将数据进行整理，绘制成柱形图表如下：图表 1：星期一图表 2：星期二图表 3：星期三图表 4：星期四图表 5：星期五显然，五个图表清楚、直观的体现出各个手术室在分配时的具体使用情况，同样，也暴露出在分配时存在的一些问题（以模型一的问题一为例）：1、对于某一科室来说，手术室的分配过于集中，时间分配不均匀，譬如只在星期二的时候分配给急诊科一个临时手术室做“长时使用”，就已经满足急诊科每周（五天）8小时的需求，而在其他时间医院不为急诊科提供手术室，这显然与医院的实际情况不相符；对于患者来说，不可能都集中到星期二到医院看病，尤其作为急诊，患病具有随机性，不能人为控制，上述两种模型均存在这一不足。2、假设缺漏：建模过程中将7个科室在手术室的分配问题上不分主次，按照同等位置来处理；而实际上，这七个科室之间在做手术时还是有一定的差别的。如某些科室由于手术要求条件较高，只能在主手术室做手术；再比如，某些科室由于手术时间较长，只能安排的长时手术室。下面我们会对某些方面进行简单的改进。模型改进一：针对第一处不足，在分配手术室时应尽可能使每个科室每天都能分配到一定的时间来进行相关手术，这就需要我们增加约束条件来控制在某个范围之内，同样以急诊科为例，急诊科每周需求的最大时间为8小时，如果满足急诊科每天都能分配到一定时间，那么不妨让1=1.6，即取这一周的平均时间为每天的最大时间，这样就满足了急诊科每天都能分配到一定的时间。在做了如上的优化之后，修改程序（约束时间，并去掉整数限制），经过lingo软件求解后发现，时间分配基本达到了预期的效果： = 1.6，i=1,2,3,4,5;按照这种修改方法，依次对进行限制1= = 9.4，i=1,2,3,4,5;1= = 6.8，i=1,2,3,4,5;1= = 4.6，i=1,2,3,4,5;1= = 8.6，i=1,2,3,4,5;1= = 24.2，i=1,2,3,4,5;1= =t(1,j);for(keshi(j):7.5*a(2,j)+9*b(2,j)+7.5*c(2,j)+8*d(2,j)=t(2,j);for(keshi(j):7*a(3,j)+8.5*b(3,j)+7*c(3,j)+8.5*d(3,j)=t(3,j);for(keshi(j):7.5*a(4,j)+9*b(4,j)+7.5*c(4,j)+8*d(4,j)=t(4,j);for(keshi(j):6.5*a(5,j)+8*b(5,j)+6.5*c(5,j)+8*d(5,j)=t(5,j);!一周（五天）医院分配给每个科室的手术时间要大于等于该科室的需求时间;sum(week(i):t(i,1)=194;sum(week(i):t(i,2)=121;sum(week(i):t(i,3)=43;sum(week(i):t(i,4)=23;sum(week(i):t(i,5)=34;sum(week(i):t(i,6)=47;sum(week(i):t(i,7)=8;!a,b,c,d与x,y之间的等量转换关系;sum(keshi(j):a(1,j)=x10;sum(keshi(j):a(2,j)=x20;sum(keshi(j):a(3,j)=x30;sum(keshi(j):a(4,j)=x40;sum(keshi(j):a(5,j)=x50;sum(keshi(j):b(1,j)=x11;sum(keshi(j):b(2,j)=x21;sum(keshi(j):b(3,j)=x31;sum(keshi(j):b(4,j)=x41;sum(keshi(j):b(5,j)=x51;sum(keshi(j):c(1,j)=y10;sum(keshi(j):c(2,j)=y20;sum(keshi(j):c(3,j)=y30;sum(keshi(j):c(4,j)=y40;sum(keshi(j):c(5,j)=y50;sum(keshi(j):d(1,j)=y11;sum(keshi(j):d(2,j)=y21;sum(keshi(j):d(3,j)=y31;sum(keshi(j):d(4,j)=y41;sum(keshi(j):d(5,j)=y51;!各科室每天需求的手术室总数量不超过医院提供的手术室总数量;for(week(i):sum(keshi(j):a(i,j)+b(i,j)=9);for(week(i):sum(keshi(j):c(i,j)+d(i,j)=194*1.1-11;sum(week(i):t(i,2)=