基于线性规划的护士排班优化问题

1、EAST CHINA INSTITUTE OF TECHNOLOGY基于线性规划的护士排班优化问题姓名1: 学号:姓名1: 学号:专业：专业：日期：2011年7月15日基于线性规划的护士排班优化问题摘要本文研究的是关于医院护士排班最优问题， 本文的主要思想是根据约束条件 建立相关的线性规划模型，利用Lingo求解，分别计算出每天，每星期的最少护 士数，并给出具体的排班方案。问题一：计算每天该科所需的最少护士数。 针对这一问，从各班次护士需求 量考虑，依据每个护士每天至多工作 8个小时，即上两个班次且两个班次不连上 这一假定条件，假设每个时间段开始登记上班的人数为Xi，建立规划模型，进而运用Li

2、n go软件进行求解，从而求出每天该科所需最少护士数为145人。问题二，以一个星期为周期，计算该科最少需签约多少护士。针对第二问， 依据题目给出的约束条件：时间段02:00-06:00 （大夜班）每个星期最多只排一次，且第二天必须休息。经过本文规划约束可以得出每个星期该科至少需签约 210名护士。问题三，以一个星期为周期，试给出具体的排班方案。依据问题二得出的结 果，综合考虑题目中各约束条件，将一个星期（七天）六个班次设为42个班次,引进0,1变量，即Xj = *彳第j号护士上第i班次0第j号护士不上第i班次，建立线性规划模型，给出具体的排班方案，见附录1,由于有的排班人数大于该次排班的最少要

3、求人数所以 该方案不唯一。问题四，计算最少需要多少护师职称以上的护士。 运用问题三的方法，增加 约束条件，即每班次上 班的护士中护师以上（包括护师）职称的所占比例不低于40%。同样引进0,1变量，即xiJ第i班次有护师级别以上：0第i班次无护师级别以上的护师职称以上的护士为目标函数, 师（包括护师）职称以上的护士为:同样建立线性规划模型。得出需要最少的护84人。目录1、问题重述42、问题分析53、模型假设54、符号说明55、模型建立与求解65.1问题一求解 65.2问题二求解65.3问题三求解75.4问题四求解9&模型评价与改进10参考文献10附录11附录一 ：11附录二：121、问题

4、重述1.1基本条件某医院某科室的一个工作日分为 6个4小时时间长的时间段，每个时间段所 需要的护士人员数各不相同。每日每个时间段的人员需求量如下所示：班次该班时间段（24小时）该班所需最少护士数16:00-10:0060210:00-14:0070314:00-18:0060418:00-22:0050522:00-02:0020602:00-06:0030每班的护士在值班开始时向病房报道，排班需满足：（1）每天至多工作8个小时，即上两个班次，两个班次不连上；第一天排班在时间段22:00-02:00 （小夜班）的护士，第二天在时间段 06:00-10:00 不排班；（3）时间段02:00-06

5、:00 （大夜班）每个星期最多只排一次，且第二天必须休 息；（4）每个星期每位护士工作40小时；1.2需解决的问题问题1:每天该科所需的最少护士数？问题2:以一个星期为周期，该科最少需签约多少护士？问题3:以一个星期为周期，试给出具体的排班方案，该方案是否唯一？问题4:根据医院要求，每班次上班的护士中护师以上（包括护师）职称的 所占比例不低于40%，问在护士数最少的条件下（第二问决定的最 少护士数），最少需要多少护师职称以上（包括护师职称）的护士 才能满足院方对职称的要求。注：护士职称评定共分五级别，分别是：护士、护师、主管护师、副主任护师、 主任护师。2、问题分析2.1 问题背景护士是医院日

6、常运营的基础， 科学合理地安排护士工作时间不仅能够缓解其 压力，提高护理质量， 而且能够降低医院的人力资源运营成本， 提高医院的护理 质量和工作积极性， 保证护士心身健康， 因此护士排班已成为医院管理工作的重 要内容之一。2.2 具体问题分析排班问题是一类带有一定约束条件的优化类问题。 在满足各时间段人员需求 量的条件下，要对现有人员做出最优安排，从而达到医院的运营需求。问题一的分析： 本问题需要解决的是该医院该科每天所需最少护士数， 根据 各时间段人员需求量表及题目给出的约束条件 1，本文假设个时间段开始上班的 人数为决策变量，所需护士数最少为目标函数，建立优化模型，进行求解。问题二的分析：

7、 本文题需解决的问题是以一个星期为周期， 该科所需的最少 护士数，由条件，时间段 02:00-06:00 （大夜班）每个星期最多只排一次，且第 二天必须休息可以知道排在大夜班的人都不相同，故可计算出最少护士数。问题三的分析： 本问题需给出一个星期内具体的排班方案， 也就是说需要知 道该班次谁上班，有多少人上班，为此，本问题引进 0,1 变量，建立优化模型， 进行求解。在满足每天至多工作 8 个小时，每班次不连上，每个星期工作 40个 小时；第一天排班在时间段 22:00-02:00 （小夜班）的护士，第二天在时间段， 06:00-10:00 不排班；时间段 02:00-06:00 （大夜班）每

8、个星期最多只排一次， 且第二天必须休息等的条件下，给出一个排班方案。问题四的分析：本文题需给出一个星期最少需要多少护师职称以上的护士。 相对于问题三， 本文增加了一个条件， 即每班次上班的护士中护师以上 （包括护 师）职称的所占比例不低于 40%。根据问题三的排班程序可知至少需要 84 位护 师，再经过分析具体排班情况时，对其进行调整，得到最终结果。3、模型假设1、正常上班情况下，没人每天至多工作 8 个小时，即上两个班次，两个班次不 连上。2、第一天排班在时间段22:00-02:00（小夜班）的护士，第二天在时间段06:00-10:00不排班。3、时间段 02:00-06:00 （大夜班）

9、每个星期最多只排一次， 且第二天必须休息；4、护士工作时间按劳动法规定，即每个星期每位护士工作 40 小时；5、每个护士不能缺勤。6、一周工作日为七天。4、符号说明ai ：第 i 个时间段所需人员数；Xi :安排在第i个时间段开始上班的人数； z :满足需求最少需要的护士人员总数； xj :第i班j号护士；5、模型建立与求解5.1问题一求解：每天该科所需的最少护士数。(1)模型建立本文假设Xi为安排在第i个时间段开始登记上班的人数并设为决策变量。目标函数为该天各时间段开始上班的人数之和，即：6 Xii 4由题目中的约束条件：每天至多工作8个小时，即上两个班次，两个班次不 连上。可以得出：第三个

10、时间段(14:00-18:00) +第一个时间段(6:00-10:00) >= 第三个时间段所需的人员数a3,即第四个时间段(18:00-22:00)+第二个时间段(10:00-14:00)>=第四个时间段所 需人员数84,即x4 x2 = a4以此类推，当i=1,2,6循环时，有Xj 为 <=ai，i= 1,2,.,6综上所述：目标函数：6min z =、xii A约束条件：X +Xid xaigi n(x(2)模型求解编写程序，运用Lingo求解得出每天该科所需最少护士为145人。程序见附 录1 05.2问题二求解：以一个星期为周期，计算该科最少需签约的护士数。由条件：时

11、间段02:00-06:00 (大夜班)每个星期最多只排一次，且第二天必须休息，从中可以知道上大夜班的护士都不相同，一个星期中每天需要30个护士上大夜班，则一个星期所需最少护士数为：30*7=210。本问题的检验将在问题三中体现5.3问题三求解：以一个星期为周期，给出具体的排班方案。(1)模型建立0,1变量,本问题需给出每个护士每天每班次的上班情况，为此本问题引进 设Xij表示第i个班次j号护士，其具体意义如下：；1第j号护士上第i班次P第j号护士不上第i班次由于每天六个班次，则一个星期总共有42班次，即i取1,2,3约束条件如下：1、每天至多工作8个小时，即上两个班次，即产6为 xj2i 二1

12、2送 Xj <= 2i =718Z Xj <= 2i圭24辽 Xj <= 2j=1,2,.210i吕930二 Xj <= 2i=2536Z Xj <= 2i=3142为 Xij < 2J =372、两个班次不连上，即区（Xij + X（i 初）<=1711为（Xij + x（i 书 j ） V= 1i=717£ （xij + x（i 初）<=1i 4323"送（Xj + x（i刑j） <=1 j=1,2,.21Oi 4929X （Xj + X（i 41）j ） £= 1i丄535送（Xj +X（v）j） <

13、;=1i £041 为（Xij +x（i*）j）1J £73、 第一天排班在时间段22:00-02:00 （小夜班）的护士，第二天在时间段06:00-10:00不排班，即X5j + X7j <= 1X11j + X13j v=1X17j+X19j V=1j=1,2,.210X23 j + X25 j <= 1X29 j + X31 j1X35 j X37 j "： = 14、时间段02:00-06:00 （大夜班）每个星期最多只排一次，且第二天必须休 息，即42'Xj ： = 11 =1122x6j- Xj ：二 2i =7122x6 j 二.

14、Xij <= 2i=718j=1,2,.2102x12 j 亠一 Xj ： - 2i 93242 X18 j 亠一 Xj ： - 2iT9302x24j 亠二 Xj :：=2 i=25362 X30 j 亠一 Xij- 2i =31422x36 j- Xj ：= 2i =375、每个星期每位护士工作40小时，即42、Xij =10, j= 1,2,210i丄(2)问题求解编写程序，利用Lin go求解，程序见附录1,具体每人每天每班次的排 班方案见附录2。每天每班次的上班人数如表一。从程序可以验证问题二中 的145人为一个星期所需最少护士数。表一人员分配表星期班次星期一星期二星期三星期四

15、星期五星期六星期天6:00-10:0011360606060606010:00-14:007071707170707014:00-18:006260606061616018:00-22:005052505351505022:00-02:002220202022212002:00-06:00303030303030305.3.1方案唯一性分析:由表一知，星期一的第一个时间段，第三个时间段，第五时间段等都大于题 目要求的最少护士数，应此交换这些多的人就可以排出多种方案，所以不唯一。5.4问题四求解：求最少需要的护师职称以上(包括护师职称)的护士问题四在以问题二的前提下，即确定了一个星期最少需要护士

16、为 145人，为 此本问题做一下求解。目标函数：210z = min ' xii W1.引进0,1变量xi第i班次有护师级别以上第i班次无护师级别以下2.新增一约束条件：210Xj八Xjj ；：=ai0.4,i = 1,2,.42，其它约束条件与冋题三相j w同，在此不做重复3.编写程序求解，可得最少需要 84位护师职称（包括护师职称）以上的护士 才能满足院方对职称的要求。6、模型评价与改进6.1模型的优点1. 该模型将护士排班所要求的条件都用数学语言表达清楚了，非常符合题 目意思，很好的解决了这一类问题。实际医院的排班都可借鉴该模型对 限制条件进行修改即可得到该院方的排班要求，所以本

17、模型具有很好的 通用性，实用性强。而且是在满足医院要求下线人数下的优化，可以为 医院减少开支。2. 该模型巧妙的将非线性问题转化为线性问题，避免了程序运行时间长等 缺点。3. 在问题三中引进了 0,1变量，直观易懂，将问题简化了，更容易着手解 决问题。6.2模型的缺点与改进1. 该模型得出的结果不是很明了，需要大量的处理工作才能制作真实的排 班表。2. 该模型只考虑了一些劳动法约束等客观因素，并没有考虑护士请假约束 和护士对工作时段偏好以及护士间配合默契程度的软约束。鉴于此，该 模型可进一步改进，即通过增加护士的工作时段偏好、相互配合默契程 度等因素进一步扩展护士排班模型，使其在满足各种实际约

18、束的同时 更具人性化，实现“护士心意卡”排班方式。参考文献1 姜启源，谢金星，叶俊.数学模型M.北京:高等教育出版社,2003.2 秦裕瑗，秦明复.运筹学简明教程M.北京：高等教育出版社，施普林格出版 社,2000.3 韩大卫.管理运筹学M.大连:大连理工大学出版社,2006.4 附录附录一 ：问题一程序：model:sets:s/1.6/:a,x;endsetsdata:a=60 70 60 50 20 30;enddatamin=sum(s(i):x(i);for(s(i):x(i)+x( wrap(i-2,6)>=a(i);for(s(i):gin(x(i);End 问题三程序：

19、model: sets: r/1.210/; b/1.42/:a; link(b,r):x; endsets data: 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;enddatafor(r(j): sum(b(i)|i#GE#1#and#i#le#6:x(i,j)<2);for(r(j): sum(b(i)|i#GE#7#and#i#le#12:x(i,j)<2);fo

20、r(r(j): sum(b(i)|i#GE#13#and#i#le#18:x(i,j)<2);for(r(j): sum(b(i)|i#GE#19#and#i#le#24:x(i,j)<2);for(r(j): sum(b(i)|i#GE#25#and#i#le#30:x(i,j)<2);for(r(j): sum(b(i)|i#GE#31#and#i#le#36:x(i,j)<2);for(r(j): sum(b(i)|i#GE#37#and#i#le#42:x(i,j)<2);for(r(j): for (b(i)|i#GE#1#and#i#le#5:x(i,

21、j)+x(i+1,j)<1);for(r(j): for (b(i)|i#GE#7#and#i#le#11:x(i,j)+x(i+1,j)<1);for(r(j): for (b(i)|i#GE#13#and#i#le#17:x(i,j)+x(i+1,j)<1);for(r(j): for (b(i)|i#GE#19#and#i#le#23:x(i,j)+x(i+1,j)<1);for(r(j): for (b(i)|i#GE#25#and#i#le#29:x(i,j)+x(i+1,j)<1);for(r(j): for (b(i)|i#GE#31#and#i#l

22、e#35:x(i,j)+x(i+1,j)<1);for(r(j): for (b(i)|i#GE#37#and#i#le#41:x(i,j)+x(i+1,j)<1);for(r(j): for (b(i)|i#ge#1#and#i#le#6:x(6*i-1,j)+x(6*i+1,j)<1);o'r(reQsum(ex6j)+x(2j)+xu8j)+x(24j)+x(30j)+x(36j)+x(42j)AD for(redfor(b(i)-ttge 逹ttandtttt_ett62*x(6*Lj)+(x(6*i+1j)+x(6*i+2j)+x(6*i+3j) +x(6*

23、i+4j)+x(6*i+5j)+x(6*i+6j)A2)xfors) - ©su m(b(i) -ttG Ettlttandtttt_ett42xLj)Hl 0)- fo(b(w sunxrexisva (三foansD b5'(x(二)-End1 ss-modesefs17k:2_kcvxb、_k:42ra 八 =nk(bdrm 八 endsefs daEaH6p70boul020GOobp70boul020GOobp70boul020GOobp70boul020GOobp70bo ul020GOobp70boul020GOobp70boul020GOo 八enddaQr

24、minHdsummx)八fo(edsum(b(i)-ttGEttlttandttgett5m(Lj)A2x foEedsum(b(i)-ttGEtt7ttandttgettr?m(Lj)A2x foEedsum(b(i)-ttGEttl 3ttandtttt_e 兰9?m(ij)A2= foEedsum(b(i)-ttGEtt9ttandtttt_ett2am(Lj)A2x foEedsum(b(i)-ttGEtt25ttandtttt_ett3pm(Lj)A2)- foEedsum (b(i)-ttG Ett3 £andtttt_ett3pm(Lj)A2)- foEe-垃三(b(i

25、) -ttG Ett37ttandtttt_ett42 m(Lj)A2)- foEedfor(b(i)-ttGEtt盂andtttt_ett5m(Lj)+m(i±jA)x foEedfor(b(i)-ttGEtt7ttandtttt_ett11 m(Lj)+m(i+1 jAkm foEedfor(b(i)-ttGE 逹 3ttandtttt_ett17h(Lj)+m(i+1) foEedfor(b(i)-ttGE 逹 9ttandtttt_ett23m (二)+m(i+二)- foEedfor(b(i)-ttGEtt25ttandtttt_ett2pm(Lj)+m(i+=A)x fo

26、Eedfor(b(i)-ttGEtt3£andtttt_ett35m(Lj)+m(i+=A)x foEedfor(b(i)-ttGEtt37ttandtttt_ett41 h(Lj)+m(i+1)= foEedfor(b(i)-ttgett盂andtttt_ett5m(6*i?j)+m(6*i+1jA)x o'Ee©sum(emGj)+mu2,j)+mu8,j)+m(24,j)+m(30,j)+m(36,j)+m(42,j)AD foEedfor(b(i)-ttgett盂andtttt_ett62*m(6/j)+(m(6*i+1j)+m(6*i+2j)+m(6*i+

27、3 j)+m(6*i+4j)+m(6*i+5j)+m(6*i+6j)A2)xfors) - sum(b(i) -ttG Ettk#and#一 e#42 m(Lj)H_k0)八 fo(b (三sum(em(Lj)va(i)*0.4xfoEnkaDdbimmw)-End周一周一周一周一周一第1第2第3第4第5班护班护班护班护班护士编士编士编士编士编号号号号号15111312112292221441042419611525207156262383572729173683034214012313526463332362749343937285343413830555242403156694348336

28、274445041671084557517011546625876152476359881554964619316151656694177526875102186536979114188547281119557482121567684126588387141598889142609991148611019215167102951637110396166731059717075110100174771141041797811910619079121107191附录二：问题三护士具体排班方案：周二周二周二周二周二周二第1第2第3第4第5第6班护班护班护班护班护班护士编士编士编士编士编士编号号号号号

29、号20213422134965237513732278614153331923212951321129224256391230314659441333394962481435405267551541476169582243489570602644539673633449549980643651551128965405856113927142625711593764763641319477526575139977853668218510693546888190111955771101117975977103128986178108129100698011013710172901111431027

30、39611614710774991181641107910211919911482117120201120841211242021218712312512389129126125911301371289213113813094132140132103133141周一 第6 班护 士编 号 10 16 17 18 19 24 25 28 37 38 45 50 81 83 85 86 105 109 122 127 136 150 154 157 162 169 175 178 183 1898082848586878990919293949596979810010410610710810911

31、111211311511711812012312512813013113213313513613713813914014114212211119613410413414512411219714110613514712611319914411314216312711620015111515116612911820115311615316713412320215812415817014412820316013816018114613020416313916118215213220516414016818815413320616514317119215513520716614617219415713

32、720816714817419816614320916814917620016814521017115218020317014917315518420417215617415618620817415917615918717616018417019017716418717719117916519117919318216719318220618317119418520718417320619220918718120719521018818519619219319719519819819920120020220120420220520320920421020520814314514714814915

33、0151153156158159160161162163164165167169171173175178180181185186189190191194196197周三周三周三周三周三周三周四周四周四周四第1班第2班第3班第4班第5班第6班第1班第2班第3班第4班护士护士护士护士护士护士护士护士护士护士编号编号编号编号编号编号编号编号编号编号10361101257311151482843910512211692926712168132317124830820171114241820533111241813251923574113251915262224994214282320302738121

34、433729272131294413247403233223534461425549353424383947152585436372540415415375563846284642611548259394935484564159986344543849506516110465455940526068162107674862445366721701317150674855757717713473517253577681184139775274605878961891487857846461821011738060906563861021818161916668871051858466111697

35、190108190906811271749510919491701137379981141969776116808399115198100791178185100118200101831188791110119209102851198896112120210112861239310311312211388127951041161301158913597105123144117921371001081251481189313810510913515512794140109114136160136991411221151381671371031421241181391691381051441301

36、211401711431061471361241451751441081491461311491761471101501511321571781491141521541331581791501201581561341591801571221591571411611821631241621611421681861651251631641461731901721261651721501742051761281661801511832071781291701891617181920222734363739434445546064728687889010010711612012212312512612

37、7130138140144145149152157158165168176177182153184210187154185188155187192156191195160192197162195200166196203167197205169198207170208208171172175178180181189193194204206209周四周四周五周五第5第6第1第2班护班护班护班护士编士编士编士编号号号号96121012203161425417152651821277192230823293593234361033394011504642166372451768764718707751

38、247879573299876133159956237180130174192183132177199186133183201191145186207192146187203151193204153195205154197206155204207156205208160206167168169175179182188189199201202周五周五周五周六周六第4第5第6第1第2班护班护班护班护班护士编士编士编士编士编号号号号号193422163551375340714856448181058491022136052122417926119251810571212930107782333321

39、11912634371171002837381351133042421361203145441471233248511571243853591621254154周五 第3 班护 士编 号 19 23 25 26 27 28 31 36 45 47 48 49 54 55 56 57166103654117710866431841146950203115735211675591528464153856715586681718970174937818298801911018119510482197106831098811790119961211021251051271071291101341181

40、351231381241391261431331441361451401491411501421511481691581731601751611761621791631831641851681871781891811901861921932081942101986216913043556518414247586719314950597019915151647120015957668020616063688116167708316372738816575749416677769918080821001868183119203848912220585921318795134889814093991419410214396103146106104148108105150110109158112115170114121173131126177133128180138129181139132188140134189143136194150137198153141202