护士排班问题.doc

数学建模暑期培训第三次论文论文题目：基于线性规划的护士排班研究 姓名： 卢丰海 学号： 09102126 专业： 信息与计算科学 姓名： 曾洁 学号： 09032104 专业： 环境工程 2011 年 7 月 15日基于线性规划的护士排班研究摘 要本文采用运筹学中的优化配置思想，依据题目要求，分别建立了整数线性规划模型及0-1整数规划模型来求解护士排班问题。针对问题一，本文以每天该科所需的最少护士数Z为目标函数，以班次i所需新安排的护士数xi为决策变量，以所给该科室每日每班次至少需要护士的数量Di为约束条件，最后用Lingo编程求解得每天该科所需的最少护士数为145人。针对问题二，本文首先引入0-1变量xijk，其表示第k位护士是否被安排在第j天的第i班次上班。再以该科室每班次至少需要护士的数量Di及排班要求为约束条件，建立0-1整数规划模型。最后用Lingo编程求解可得，该科所需签约的每周最少护士数为210人。经统计具体排班方案上的数据，得一周内每天每班次所安排的人数如下表所示：（详细排班情况见附件） 星期班次一二三四五六日183606061616160270707070717070364606060616060451505350515150520202220202248630303030303030针对问题三，本文根据签约护士的一周班次安排表，便得出第i天第j班次所需的护士人数矩阵A，本文以yij为决策变量，以该科所需的最少护师及以上职称的护士数W为目标函数，以每班次上班的护师及以上（包括护师）职称的所占总护士的比例应不低于40%为约束条件，建立线性规划模型，将所得的W向上取整即得该科护师及以上职称的最少护士数为85人。关键词：护士排班 0-1整数规划 护士级别 排班问题 最优分派方案1 问题的重述一、 问题的背景护士是医院日常运营的基础, 科学合理地安排护士工作时间不仅能够缓解其压力, 提高护理质量, 而且能够降低医院的人力资源运营成本, 因此护士排班已成为医院管理工作的重要内容之一。以下是某医院某科室每日至少需要护士的数量：表1班次该班时间段（24小时）该班所需最少护士数16:00-10:0060210:00-14:0070314:00-18:0060418:00-22:0050522:00-02:0020602:00-06:0030每班的护士在值班开始时向病房报道，排班需满足：1、每个星期每位护士工作40小时。2、每天至多工作8个小时，即上两个班次，两个班次不连上； 3、时间段02:00-06:00（大夜班）每个星期只排一次，且第二天必须休息；4、第一天排班在时间段22:00-02:00（小夜班）的护士，第二天在时间段06:00-10:00不排班；二、需解决的问题为满足该医院各班所需要的护士数，需建立合适的数学模型，为院方领导解决如下问题：问题一：依据上述数据和排班要求，求解出每天该科所需的最少护士数。问题二：以一个星期为周期，求出该科最少需签约的护士人数，并给出具体的排班方案，并判断该方案是否唯一。 问题三：以问题二求解护士数的结果为前提，求解出满足院方对职称要求的最少护师职称以上（包括护师职称）的护士数。附注：（1）护士职称评定共分五级别，分别是：护士、护师、主管护师、副主任护士、主任护师。（2）根据医院要求，每班次上班的护士中护师以上（包括护师）职称的所占比例不低于40%。2 问题的分析由于护士排班中存在一系列劳动法规约束, 外加需要考虑不同护士的能力级别差异, 因此护士排班问题是较为复杂的组合优化问题。经分析，对该问题处理要分两个步骤进行：第一，确定该科所不同周期时所需签约的最少护士数，并给出具体的排班方案；第二，在最少人数及排班方案已确定的条件下，求解出满足院方对职称要求的最少护师职称以上（包括护师职称）的护士人数。一、对问题的具体分析1、问题一的分析：问题要求依据所给数据及排班要求，求解出每天该科所需的最少护士人数。经分析，本文认为这是一个典型的线性规划建模及求解的问题。故该问题的求解步奏如下：首先应确定该问题的决策变量，再确定目标函数，并表示出所有的约束条件，最后用Lingo编程求解即可。2、问题二的分析：问题要求以一个星期为周期，求出该科最少需签约的护士人数，并给出具体的排班方案，并判断该方案是否唯一。经分析，此问亦是建立与求解线性规划模型的过程，故确定恰当合适的决策变量、目标函数及约束条件求得正确结果的关键。3、问题三的分析：问题要求以问题二求解护士数的结果为前提，求解出满足院方对职称要求的最少护师职称以上（包括护师职称）的护士数。经分析，本文根据签约护士的一周班次安排表，便得出第i天第j班次所需的护士总数，本文以其为决策变量，以该科所需的最少护师及以上职称的护士数W为目标函数，以每班次上班的护师及以上（包括护师）职称的所占总护士的比例应不低于40%为约束条件，建立线性规划模型，将所得的W向上取整即得该科护师及以上职称的最少护士数。3 模型的假设1、假设忽略护士对班次的个人偏好；2、假设不考虑国家指定假期影响来进行排班； 3、假设不考虑安排的护士因请假等特殊缺席情况发生而换班；4、假设所给数据真实可靠且每个约束条件医院排班均必须考虑； 5、假设计算人数不满1时，可以认为能忽略小数点向上取整；6、假设护师及以上（包括护师）职称的最多可以允许一个人一个星期工作时间不满40小时。4符号说明序号符号符号说明1Xi表示第i班次的护士数2Z表示为一天中所安排的最少护士总量3Dij表示第j天第i班次所需的最少护士数4Xijk表示第k位护士被安排上第j天的第i次班5Aij表示以一星期为周期每天每班次所需的护士总数6yij表示每天每班次护师及以上职称的护士人数7W表示该科护师及以上职称的护士人次5 模型的建立与求解从所要解决的的问题和对问题所做的假设出发，本文对问题一建立了模型，求得每天该科所需的最少护士数；对问题二建立了模型，在以一星期为周期的前提下，求得一周内该科至少需签约的护理人员数，并得到每个护士的具体排班方案；对问题三建立了模型，求解出该科护师及以上职称的护士人次。一、问题一的求解1、模型的一般表达式：此问中本文以每天该科所需的护士数最少为目标函数，以第i班次的护士数为决策便变量，以所给该科室每日每班次至少需要护士的数量为约束条件，建立如下线性规划模型： （1）式中xi为第i班次新安排的护士人数，Z表示为一天中所安排的最少护士总人数。 2、模型的求解本文通过用Lingo编程求解，解得每天该科所需的最少护士数为145人（程序及运行详细结果见附录）。二、问题二的求解1、模型的建立过程经分析，此问中本文以第j天第i班次的护士数xij为决策便变量，以所给该科室每日每班次至少需要护士的数量及排班要求为约束条件，建立下列约束式：由题目所给条件限制可知，假设每天所有班次均取最少人数且所有护士均工作40小时，并不考虑是否连班，则有所需护士总数最少为203人。又由题目限制条件3所述，则有每个大夜班都需要不同的护士上班，所以每周至少需要210人才能满足要求。故综上所述，所以可以确定签约护士最少不得少于210人。假设xijk为第k位护士被安排上第j天的第i次班，为了方便模型的建立及求解，本文假设xijk为0-1变量，即有： （2）由题目可知每位护士每周必须上40小时，即要求每周必须上10个班次，则有： （3）又由每天每位护士至多上工作8个小时，即每位护士至多每天上两个班次，则有： （4）由规定每位护士每天上两个班次且两个班次不连上，则有： （5）由第一天排班在时间段22:00-02:00（小夜班）的护士，第二天在时间段06:00-10:00不排班，则有： （6）由时间段02:00-06:00（大夜班）每个星期每位护士只排一次，且第二天必须休息，则有： （7） （8）又由每个班次规定至少需要的人数，见表1则得如下约束式子： （9）2、模型的一般表达式：联立上面（2）至（9）式，得如下0-1整数规划模型：s.t （10）运用lingo程序编程（程序见附录）求解可知，当以209个护士排班时，程序无法排出结果，即最少为209个护士时不满足要求，但当以210个护士排班时，程序可运行结果且每个护士的具体排班方案（见附录）：经统计具体排班方案上所给的数据，得一周内每天每班次所安排的人数如下表： 表2 各班次安排人数 星期班次一二三四五六日1836060616161602707070707170703646060606160604515053505151505202022202022486303030303030303、模型结果分析：据题意每位护士一星期应上10次班，经分析统计得一星期所有护士的总上班次数为2100次，故可得一周内该科至少需签约210人次的护理人员；再将上述一星期人数安排表与表一对比可知，每天每班次所安排的人数都符合该医院的要求；最后分析附件表格可知所得的排班方案皆符合院方所设的的排班条件。三、问题三的求解1、模型的建立及求解根据医院要求，在签约最少护士的条件下每班次上班的护士中护师以上（包括护师）职称的所占比例不低于40%。根据签约护士的一周班次安排表，便得出每天每班次所需的护士总数Aij，则取每班次总人数的40%便得每天每班次护师职称以上（包括护师职称）的护士人数yij，即得如下方程：以该科所需的最少护师及以上职称的护士数W为目标函数，将所得结果求和便得如下模型：最后用Lingo编程求解，将所得的W向上取整，即得该科护师及以上职称的护士人数为85人。6 模型的检验和进一步讨论一、模型检验 本文将模型二中所得的排班结果与题目中的要求进行对照，具体过程如下：据题意每位护士一星期应上10次班，经分析统计得一星期所有护士的总上班次数为2100次，故可得一周内该科至少需签约210人次的护理人员；再将上述一星期人数安排表与表一对比可知，每天每班次所安排的人数都符合该医院的要求；最后分析附件表格可知所得的排班方案皆符合院方所设的的排班条件。故所得模型是可靠的。二、模型的进一步讨论：对于本文中的模型，还可以综合考虑多一些人性化的因素，如护士对班次的喜好问题、护士因特殊问题而请假缺席的情况，以及考虑国家法定假期对班次安排的影响，使得模型运用的更加方便、灵活，更贴近实际，以减轻管理人员的工作量，提升护士工作时的心情愉悦指数及工作效率。7 模型的评价与推广一、模型的优缺点1、优点：利用线性规划的思想来求解护士调度问题，其方法简便、直观、快捷，可操作性强；本文建立0-1整数规划模型，将所有约束条件统一化，运用LINGO软件即可求解所建的模型，费时少。2、缺点：本模型的建立并未考虑到护士对班次的喜好问题及护士因特殊问题而请假缺席的情况。 本文中的模型二是以一星期为周期的连续性模型，忽略了对国家法定假期考虑。二、模型的推广：如今护理人员缺编已成为全世界普遍面临的问题。其缺编的原因有多种，而解决方法亦有多样，其中之一就是合理安排班次。对于护士排班这一复杂问题，没有一种单一的模型是通用的，即使是在同一科室中，一个模型的目标功能和限制条件在不同时期也会有很大不同。故本文的护士排班模型仅能适用于与本文中限制条件相类似的排班问题，但即使如此，本文在一定程度上仍能为现实管理调度中的某些常见的排班问题提供参考，如列车服务人员调度问题、机乘服务人员的排班问题及安保室值班排班问题等等。参考文献1 司守奎,数学建模算法与程序M,2007(5):11-26；2 武翠芳, 郑晋昌,智慧型排班系統之设计-以服务业为例J, 国立中央大学人力资源管理研究所,2002(3):19-22.；3 刘晓荣,陈国良,护士排班决策支持系统模型的研究J,解放军护理杂志, 2006(2): 7-9；4 肖华勇, 基于MATLAB和LINGO的数学实验J, 西北工业大学出版社, 2009(3)；5 沈吟东,苏光辉,带约束的护士排班模型和基于变换规则的优化算J, 计算机工程与科学，2010(7):32.附录1、模型一的Lingo求解程序model:sets:shuliang/1.9/:x;endsetsmin=x(1)+x(2)+x(3)+x(4)+x(5)+x(6);!x(1).x(6)表示每班次登记护士人数;x(1)=60;x(2)=70;x(2)=x(7)+x(8)+x(9);x(1)+x(3)=60;x(7)+x(4)=50;x(8)+x(5)=20;x(6)+x(9)+x(4)=30;end2、模型一的求解结果：Global optimal solution found. Objective value: 145.0000 Infeasibilities: 0.000000 Total solver iterations: 4 Variable Value Reduced Cost X( 1) 60.00000 0.000000 X( 2) 70.00000 0.000000 X( 3) 0.000000 1.000000 X( 4) 15.00000 0.000000 X( 5) 0.000000 0.5000000 X( 6) 0.000000 0.5000000 X( 7) 35.00000 0.000000 X( 8) 20.00000 0.000000 X( 9) 15.00000 0.000000 Row Slack or Surplus Dual Price 1 145.0000 -1.000000 2 0.000000 -1.000000 3 0.000000 -0.5000000 4 0.000000 -0.5000000 5 0.000000 0.000000 6 0.000000 -0.5000000 7 0.000000 -0.5000000 8 0.000000 -0.50000003、模型二的Lingo求解程序model:sets:set1/1.42/:shift,a;set2/1.209/:staff;link(set1,set2):x;endsetsdata:a=60 70 60 50 20 30 60 70 60 50 20 30 60 70 60 50 20 30 60 70 60 50 20 30 60 70 60 50 20 30 60 70 60 50 20 30 60 70 60 50 20 30;enddatasum(set2(j):x(1,j)60;sum(set2(j):x(2,j)70;sum(set2(j):x(3,j)60;sum(set2(j):x(4,j)50;sum(set2(j):x(5,j)20;sum(set2(j):x(6,j)30;sum(set2(j):x(7,j)60;sum(set2(j):x(8,j)70;sum(set2(j):x(9,j)60;sum(set2(j):x(10,j)50;sum(set2(j):x(11,j)20;sum(set2(j):x(12,j)30;sum(set2(j):x(13,j)60;sum(set2(j):x(14,j)70;sum(set2(j):x(15,j)60;sum(set2(j):x(16,j)50;sum(set2(j):x(17,j)20;sum(set2(j):x(18,j)30;sum(set2(j):x(19,j)60;sum(set2(j):x(20,j)70;sum(set2(j):x(21,j)60;sum(set2(j):x(22,j)50;sum(set2(j):x(23,j)20;sum(set2(j):x(24,j)30;sum(set2(j):x(25,j)60;sum(set2(j):x(26,j)70;sum(set2(j):x(27,j)60;sum(set2(j):x(28,j)50;sum(set2(j):x(29,j)20;sum(set2(j):x(30,j)30;sum(set2(j):x(31,j)60;sum(set2(j):x(32,j)70;sum(set2(j):x(33,j)60;sum(set2(j):x(34,j)50;sum(set2(j):x(35,j)20;sum(set2(j):x(36,j)30;sum(set2(j):x(37,j)60;sum(set2(j):x(38,j)70;sum(set2(j):x(39,j)60;sum(set2(j):x(40,j)50;sum(set2(j):x(41,j)20;sum(set2(j):x(42,j)30;for(set2(j):x(1,j)+x(2,j)1;);for(set2(j):x(2,j)+x(3,j)1;);for(set2(j):x(3,j)+x(4,j)1;);for(set2(j):x(4,j)+x(5,j)1;);for(set2(j):x(6,j)+x(5,j)1;);for(set2(j):x(6,j)+x(7,j)1;);for(set2(j):x(7,j)+x(8,j)1;);for(set2(j):x(8,j)+x(9,j)1;);for(set2(j):x(9,j)+x(10,j)1;);for(set2(j):x(10,j)+x(11,j)1;);for(set2(j):x(11,j)+x(12,j)1;);for(set2(j):x(13,j)+x(12,j)1;);for(set2(j):x(13,j)+x(14,j)1;);for(set2(j):x(14,j)+x(15,j)1;);for(set2(j):x(15,j)+x(16,j)1;);for(set2(j):x(16,j)+x(17,j)1;);for(set2(j):x(18,j)+x(17,j)1;);for(set2(j):x(18,j)+x(19,j)1;);for(set2(j):x(19,j)+x(20,j)1;);for(set2(j):x(21,j)+x(20,j)1;);for(set2(j):x(21,j)+x(22,j)1;);for(set2(j):x(23,j)+x(22,j)1;);for(set2(j):x(24,j)+x(23,j)1;);for(set2(j):x(25,j)+x(24,j)1;);for(set2(j):x(26,j)+x(25,j)1;);for(set2(j):x(27,j)+x(26,j)1;);for(set2(j):x(28,j)+x(27,j)1;);for(set2(j):x(29,j)+x(28,j)1;);for(set2(j):x(30,j)+x(29,j)1;);for(set2(j):x(31,j)+x(30,j)1;);for(set2(j):x(31,j)+x(32,j)1;);for(set2(j):x(33,j)+x(32,j)1;);for(set2(j):x(34,j)+x(33,j)1;);for(set2(j):x(34,j)+x(35,j)1;);for(set2(j):x(35,j)+x(36,j)1;);for(set2(j):x(36,j)+x(37,j)1;);for(set2(j):x(37,j)+x(38,j)1;);for(set2(j):x(38,j)+x(39,j)1;);for(set2(j):x(39,j)+x(40,j)1;);for(set2(j):x(40,j)+x(41,j)1;);for(set2(j):x(41,j)+x(42,j)1;);for(set2(j):x(1,j)+x(42,j)1;);for(set2(j):x(5,j)+x(7,j)1;);for(set2(j):x(11,j)+x(13,j)1;);for(set2(j):x(19,j)+x(17,j)1;);for(set2(j):x(23,j)+x(25,j)1;);for(set2(j):x(29,j)+x(31,j)1;);for(set2(j):x(35,j)+x(37,j)1;);for(set2(j):x(41,j)+x(1,j)1;);for(set2(j):2*x(6,j)+x(7,j)+x(8,j)+x(9,j)+x(10,j)+x(11,j)+x(12,j)2;);for(set2(j):2*x(12,j)+x(13,j)+x(14,j)+x(15,j)+x(16,j)+x(17,j)+x(18,j)2;);for(set2(j):2*x(18,j)+x(19,j)+x(20,j)+x(21,j)+x(22,j)+x(23,j)+x(24,j)2;);for(set2(j):2*x(24,j)+x(25,j)+x(26,j)+x(27,j)+x(28,j)+x(29,j)+x(30,j)2;);for(set2(j):2*x(30,j)+x(31,j)+x(32,j)+x(33,j)+x(34,j)+x(35,j)+x(36,j)2;);for(set2(j):2*x(36,j)+x(37,j)+x(38,j)+x(39,j)+x(40,j)+x(41,j)+x(42,j)2;);for(set2(j):2*x(42,j)+x(1,j)+x(2,j)+x(3,j)+x(4,j)+x(5,j)+x(6,j)2;);for(set2(j):x(1,j)+x(2,j)+x(3,j)+x(4,j)+x(5,j)+x(6,j)=2;);for(set2(j):x(7,j)+x(8,j)+x(9,j)+x(10,j)+x(11,j)+x(12,j)=2;);for(set2(j):x(13,j)+x(14,j)+x(15,j)+x(16,j)+x(17,j)+x(18,j)=2;);for(set2(j):x(19,j)+x(20,j)+x(21,j)+x(22,j)+x(23,j)+x(24,j)=2;);for(set2(j):x(25,j)+x(26,j)+x(27,j)+x(28,j)+x(29,j)+x(30,j)=2;);for(set2(j):x(31,j)+x(32,j)+x(33,j)+x(34,j)+x(35,j)+x(36,j)=2;);for(set2(j):x(37,j)+x(38,j)+x(39,j)+x(40,j)+x(41,j)+x(42,j)=2;);for(set2(j):x(6,j)+x(12,j)+x(18,j)+x(24,j)+x(30,j)+x(36,j)+x(42,j)0.4*A(i);for(set(i):GIN(y(i);for(set(i):gin(0.1*sum(set(i):y(i);endGlobal optimal solution found. Objective value: 84.80000 Objective bound: 84.80000 Infeasibilities: 0.000000 Extended solver steps: 0 Total solver iterations: 05、模型三的求解结果 Variable Value Reduced Cost A( 1) 83.00000 0.000000 A( 2) 70.00000 0.000000 A( 3) 64.00000 0.000000 A( 4) 51.00000 0.000000 A( 5) 20.00000 0.000000 A( 6) 30.00000 0.000000 A( 7) 60.00000 0.000000 A( 8) 70.00000 0.000000 A( 9) 60.00000 0.000000 A( 10) 50.00000 0.000000 A( 11) 20.00000 0.000000 A( 12) 30.00000 0.000000 A( 13) 60.00000 0.000000 A( 14) 70.00000 0.000000 A( 15) 60.00000 0.000000 A( 16) 53.00000 0.000000 A( 17) 22.00000 0.000000 A( 18) 30.00000 0.000000 A( 19) 61.00000 0.000000 A( 20) 70.00000 0.000000 A( 21) 60.00000 0.000000 A( 22) 50.00000 0.000000 A( 23) 20.00000 0.000000 A( 24) 30.00000 0.000000 A( 25) 61.00000 0.000000 A( 26) 71.00000 0.000000 A( 27) 61.00000 0.000000 A( 28) 51.00000 0.000000 A( 29) 20.00000 0.000000 A( 30) 30.00000 0.000000 A( 31) 61.00000 0.000000 A( 32) 70.00000 0.000000 A( 33) 60.00000 0.000000 A( 34) 51.00000 0.000000 A( 35) 22.00000 0.000000 A( 36) 30.00000 0.000000 A( 37) 60.00000 0.000000 A( 38) 70.00000 0.000000 A( 39) 60.00000 0.000000 A( 40) 50.00000 0.000000 A( 41) 48.00000 0.000000 A( 42) 30.00000 0.000000 Y( 1) 34.00000 0.1000000 Y( 2) 28.00000 0.1000000 Y( 3) 26.00000 0.1000000 Y( 4) 21.00000 0.1000000 Y( 5) 8.000000 0.1000000 Y( 6) 12.00000 0.1000000 Y( 7) 24.00000 0.1000000 Y( 8) 28.00000 0.1000000 Y( 9) 24.00000 0.1000000 Y( 10) 20.00000 0.1000000 Y( 11) 8.000