基于线规划的护士排班问题研究.doc

基于线性规划的护士排班问题研究摘要： 本文研究的是在满足各时间段人员需求量的条件下，医院护士排班最优问题。根据题目约束条件，用运筹学中的线性规划建立模型，再利用Lingo求解,分别算出所需护士人员总数及加班人员人数总和，制定了排班的优化方案。 对于问题一，从各时间段人员需求量考虑，依据每个护士每天工作8小时，且在工作4个小时后需要休息1个小时这一假定条件，本文以每天该科所需的最少护士数Z为目标函数，以班次i所需新安排的护士数xi为决策变量，以所给该科室每日每班次至少需要护士的数量ai为约束条件，最后用Lingo编程求解得每天该科所需的最少护士数为91人。 对于问题二，综合考虑人员总数为80、各时间段人员需求量以及加班人员每天加班时间为2个小时，且紧随在后一个4小时工作时段之后，中间没有休息等条件，分别假设出正常上班人员安排在各时间段开始上班的人数mi、应加班人员安排在各时间段开始上班的人数ni，再以该科室每班次至少需要护士的数量ai及排班要求为约束条件建立最优化模型。采用lingo编程，求解得总加班人员人数总和为36人，正常上班人数总和为44人。关键词：护士排班 线性规划 最优方案 lingo 1 问题的重述一、 问题的背景：某医院的心脑血管科需要制定护士的工作时间表。在心脑血管科的一个工作日分为12个两小时的时段，每个时段的人员要求不同。以下列出了每个时段的人员需求量：编号时段需要护士人数10:002:001522:004:001534:006:001546:008:003558:0010:0040610:0012:0040712:0014:0040814:0016:0030916:0018:00311018:0020:00351120:0022:00301222:0024:0020排班需满足：1. 每位护士每天工作8小时，且在工作4小时后需要休息1小时。2. 如果加班，每天加班的时间为2小时，且紧随在后一个4小时工作时段之后，中间没有休息。二、需要解决的问题：问题1：（1）为满足每位护士每天工作8小时，且在工作4小时后需要休息1小时的需求最少需要多少名护士？（2）如果满足需求的排班方案不止一种，给出最合理的排班方案，并说明其理由。问题2：目前心脑血管科只有80名护士，如果这个数目不能满足指定的需求，只能考虑让部分护士加班。（1）求解出护士工作时间安排的方案，以使需要加班的护士数目最少。（2）给出最合理的排班和加班方案，并说明其理由。2 问题的分析 由于护士排班中存在一系列制度约束, 外加需要考虑方案的可行性, 因此护士排班问题是较为复杂的组合优化问题。经分析，对该问题处理要分两个步骤进行：第一，确定该科室不同时间段所需护士数，并根据相关制度，确定排班的约束条件；第二，在最少人数及排班方案已确定的条件下，算出加班护士人数的最优解。 具体分析如下：问题一的分析：问题要求依据所给数据及排班要求，求解出每日该科所需的最少护士人数。经分析，本文认为这是一个典型的线性规划建模及求解的问题。故该问题的求解步奏如下：首先应确定该问题的决策变量，再确定目标函数，并表示出所有的约束条件，最后用Lingo编程求解即可。问题二的分析：在科室只有80名护士的背景环境下，问题要求求出最少加班人数护士人数，给出具体的排班方案。经分析，此问亦是建立与求解线性规划模型的过程，故确定恰当合适的决策变量、目标函数及约束条件求得正确结果的关键。3 模型的假设1、假设忽略护士对班次的个人偏好；2、假设不考虑国家指定假期影响来进行排班；3、假设不考虑安排的护士因请假等特殊缺席情况发生而换班； 4、假设不考虑护士在指定上班时间内迟到或早退；5、假设所给数据真实可靠且每个约束条件医院排班均必须考虑；6、假设计算人数不满1时，可以认为能忽略小数点向上取整；4符号说明1. ai：第i个时间段所需人员数。2. xi：安排在第i个时间段开始上班的人数。3. z：满足需求最少需要的护士人员总数；4. z：加班护士人员人数总和；5. mi：安排正常上班人员在第i个时间段开始上班的人数。6. ni：安排应加班人员在第i个时间段开始上班的人数。注：i= 1 , 2. . . 24 ;5 模型的建立与求解从所要解决的的问题和对问题所做的假设出发，本文对问题一建立了模型，求得每天该科所需的最少护士数；对问题二建立了模型，得到了最少加班护士的人数。 问题一的求解： 1、模型的一般表达式： 此问中，本文以每天该科所需的护士数最少为目标函数，将一天划分为24段，取整点i为护士交接班的时间点，安排在第i个时间段开始上班（如i=1对应时间段为1:00-2:00，护士上班时间为一点）的人数上班的护士的人数xi为决策变量，第i个时间段所需人员数ai为约束条件，建立最优化模型。由于每个时间段的人员需求量一定少于该时间段正在上班的护士数量，因此作为解题思路。依据每个护士每天工作8小时，且在工作4个小时后需要休息1个小时，可以知道在每个时间段开始上班的护士的工作时间，列表分析如下：交接班时间点i上班时间段1(1,5(6,102(2,6(7,113(3,7(8,124(4,8(9,135(5,9(10,146(6,10(11,157(7,11(12,168(8,12(13,179(9,13(14,1810(10,14(15,1911(11,15(16,2012(12,16(17,2113(13,17(18,2214(14,18(19,2315(15,19(20,2416(16,20(21,24(0,117(17,21(22,24(0,218(18,22(23,24(0,319(19,23(0,420(20,24(1,521(21,24(0,1(2,622(22,24(0,2(3,723(23,24(0,3(4,8 24 (0)(0,4(5,9考虑到每个时段需要满足的护士人数即表示该时段每个时刻都需要满足相应的护士人数，为了使需求时间段与上班时间段相匹配即每个上班时间段内都有需求时间段作为其子集，我们将需求时间段也按1小时长度划分为24等份。由题意不难确定，约束表达式为XiAj，（其中Xi为满足需求时间段的上班时间段的子集，Aj为划分的需求时间段，j下标表示需求时间段的序号），通过列表分析，我们可以进一步简化而得到一个约束表达式的通式为(xj+xj-1+xj-2+xj-3+xj-5+xj-6+xj-7+xj-8)Aj，规律找寻的具体过程如下：取j=10即10:00-11:00这个时间段，10,11为 (2,6(8,12，(3,7(9,13，(4,8(10,14，(5,9(10,14，(7,11(12,16，(8,12(13,17，(9,13(14,18，(10,14(16,20的子集，即有x2+x3+x4+x5+x7+x8+x9+x10=a10(a10=40)，由于这个模型具有周期性，因此可以猜测满足条件的xi与j的关系，通过对列表数据的逐一检验，确认满足这个通式。因此，我们可以建立如下线性规划模型：min Z=i=124xis.t.(xj+xj-1+xj-2+xj-3+xj-5+xj-6+xj-7+xj-8)Aj,j=1,2,324xi0