运筹学报告——长安医院护士值班问题

1-19——长征医院护士值班计划组员：115054212任雷飞115054214孔向铎115054229白乙甫115054228赵晋阳2-19长征医院的护士值班计划一、问题提出长征医院是长宁市的一所区级医院,该院每天各时间区段内需求的值班护士数如表1所示.表1时间区段6:00-10:0010:00-14:0014:00-18:0018:00-22:0022:00-6:00(次日)需求数1820191712该医院护士上班分五个班次,每班8h,具体上班时间为第一班2:00~10:00,第二班6:00~14:00,第三班10:00~18:00,第四班14:00~22:00,第五班18:00~2:00（次日）.每名护士每周上5个班,并被安排在不同日子,有一名总护士长负责护士的值班安排计划.值班方案要做到在人员或经济上比较节省,又做到尽可能合情合理.下面是一些正在考虑中的值班方案:方案每名护士连续上班5天,休息2天,并从上班第一天起按从上第一班到第五班顺序安排.例如第一名护士从周一开始上班,则她于周一上第一班,周二上第二班,……,周五上第五班；另一名护士若从周三起上班,则她于周三上第一班,周四上第二班,……,周日上第五班,等等.方案2考虑到按上述方案中每名护士在周末（周六、周日）两天内休息安排不均匀.于是规定每名护士在周六、周日两天内安排一天、且只安排一天休息,再在周一至周五期间安排4个班,同样上班的五天内分别顺序安排5个不同班次.在对第1、2方案建立线性规划模型并求解后,发现方案2虽然在安排周末休息上比较合理,但所需值班人数要比第1方案有较多增加,经济上不太合算,于是又提出了第3方案.方案3在方案2基础上,动员一部分护士放弃周末休息,即每周在周一至周五间由总护士长给安排三天值班,加周六周日共上五个班,同样五个班分别安排不同班次.作为奖励,规定放弃周末休息的护士,其工资和奖金总额比其他护士增加a%.根据上述,帮助长征医院的总护士长分析研究:3-19(a)对方案1、2建立使值班护士人数为最少的线性规划模型并求解；(b)对方案3,同样建立使值班护士人数为最少的线性规划模型并求解,然后回答a的值为多大时,第3方案较第2方案更经济；二、对方案1进行分析1.符号与假设需注意处:要求连续上班5天(1,2,,7)ixi:从星期i开始上班的护士人数.其值班安排表如下:表2方案1护士值班安排模型星期班次星期一星期二星期三星期四星期五星期六星期日2:00-10:001x2x3x4x5x6x7x6:00-14:007x1x2x3x4x5x6x10:00-18:006x7x1x2x3x4x5x14:00-22:005x6x7x1x2x3x4x18:00-2:004x5x6x7x1x2x3x2.建模与求解由此可对方案1建立如下线性规划模型:1234567minzxxxxxxx..st177665544332212020202020202012(1~7)ixxxxxxxxxxxxxxxi星期班4-19用管理运筹学软件进入软件“管理运筹学”，进入“线性规划”菜单点击“新建”，新建之前的数据模型。在输入所有的数据后，单击“解决”。得出以下的最优解：5-19**********************最优解如下*************************目标函数最优值为:84变量最优解相差值-----------------------x1120x2120x3120x4120x5120x6120x7120约束松弛/剩余变量对偶价格----------------------------10-120-130-140-150-160-170-18409401040114012401340142406-19目标函数系数范围:变量下限当前值上限-------------------------------x101无上限x201无上限x301无上限x401无上限x501无上限x601无上限x701无上限常数项数范围:约束下限当前值上限-------------------------------1012无上限2812无上限3812无上限4812无上限5812无上限6812无上限7812无上限8无下限20249无下限202410无下限202411无下限202412无下限202413无下限20247-1914无下限024可知，最优解为12,12,12,12,12,12,12,84;5712346xxxxxxxz方案1的护士值班安排如下表所示:方案1的护士值班安排星期1星期2星期3星期4星期5星期6星期日2:00-10:00121212121212126:00-14:001212121212121210:00-18:001212121212121214:00-22:001212121212121218:00-2:0012121212121212方案1的结论:星期一上第一班的班组的人数为12个，星期二上第一班的班组的人数为12个，星期三上第一班的班组的人数为12个，星期四上第一班的班组的人数为12个，星期五上第一班的班组的人数为12个，星期六上第一班的班组的人数为12个，星期日上第一班的班组的人数为12个。所有值班护士人数最少为84个三、对方案2的分析1.符号与假设(1)因为每名护士在周六、周日两天里必须工作一天,安排休息一天.(2)周一到周五连续安排4个班,所以可以先安排周末的护士值班情况:周六、周末两天共10个班次,用(1~10)jx表示周六周末两天10个班次的护士人数,其中15~xx分别代表周六第1个到第5个班次的护士人数,610~xx分别代表周日从第1个到第5个班次的护士人数.其值班安排表如下:表3方案2护士值班安排模型星期班次星期一星期二星期三星期四星期五星期六星期日2:00-10:0010x5x+9x4x+8x3x+7x2x1x6x6:00-14:006x1x+10x5x+9x4x+8x3x2x7x星期8-1910:00-18:007x2x+6x1x+10x5x+9x4x3x8x14:00-22:008x3x+7x2x+6x1x+10x5x4x9x18:00-2:009x4x+8x3x+7x26xx1x5x10x注意:第五班次不与第一班次时间重合,所以要考虑第五班次的22:00~2:00时间段和第一班次2:00~6:00时间班次,再结合图表信息得到约束条件如下.2.建模与求解由此可对方案2建立如下线性规划模12345678910minwxxxxxxxxxx..st610159103478458912236734782367126101361089451591048372659182018201820202020192017191917171212121xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx212(1,2,5,6,9,10)0(1~10)ijxixj9-19根据以上的方案二的数据模型，输入数据。单击“解决”，得出以下的解：**********************最优解如下*************************目标函数最优值为:112变量最优解相差值-----------------------x1120x2120x380x4120x5120x6120x780x8120x9120x1012010-19约束松弛/剩余变量对偶价格----------------------------12802280328042205210627080-1950100-111601270135014001560160017120181201940208021702280230-1240-1250-1260-1270-1280-111-19目标函数系数范围:变量下限当前值上限-------------------------------x101无上限x201无上限x3112x4011x501无上限x601无上限x7112x8011x901无上限x1001无上限常数项数范围:约束下限当前值上限-------------------------------1无下限20482无下限20483无下限20484无下限18405无下限19406无下限17447无下限184081520无上限9无下限1924101520无上限11无下限182412无下限172413无下限19241416202512-1915无下限18241616202517无下限122418无下限122419无下限121620无下限122021无下限172422无下限122023612无上限247121625712无上限267121627712无上限28612无上限可知方案2线性规划模型的最优解12341212812xxxx56781212137xxxx891071212xxx,112w方案2的护士值班安排如下表所示:方案2的护士值班安排星期1星期2星期3星期4星期5星期6星期日2:00-10:00122419211212126:00-14:00122424198121310:00-18:0013242424128714:00-22:00721242412121218:00-2:001219212012121213-19方案2的结论：方案2线性规划模型的最优解为：1234512,12,8,12,12xxxxx67910,12,8,12,12,xxxx112w;即：周六第1班次的护士人数为12个，周六第2班次的护士人数为12个，周六第3班次的护士人数为8个，周六第4班次的护士人数为12个，周六第5班次的护士人数为12个，周日第1个班次的护士人数为12个，周日第2个班次的护士人数为8个，周日第3个班次的护士人数为12个，周日第4个班次的护士人数为12个。周日第5个班次的护士人数为12个。所有值班护士人数最少为112个。四、对方案3的分析1.符号与假设(1)一部分护士周末两天都上班,另外一部分护士周末只上一天.(2)连续上班5天,休息2天.(3)同样5个班分别安排在不同的班次.因此,先安排周末的值班,设:15~xx周末两天都上班.615~xx周末只上一天.对方案3进行分析,以表格的形式将方案3的护士值班安排表示如下表所示:表4方案3护士值班安排模型运用分组绑定法:(1)已知15~xx固定为周末上班,令,,,5112213314,41511xxxxxxxxxx俩俩一组成为A,有A中的每一个组合看成一个组在分别和,,,789106xxxxx,配对组合成B.工作区段星期1星期2星期3星期4星期5星期6星期日2:00-10:00415xx31410xxx2139xxx128xx7x16xx+511xx6:00-14:00511xx4156xxx31410xxx139xx8x72xx112xx10:00-18:00112xx5711xxx4156xxx410xx9x38xx213xx14:00-22:00213xx1128xxx5711xxx156xx10x49xx314xx18:00-2:00314xx2139xxx1128xxx711xx6x510xx415xx14-19(2)先排第一班次:周六,周日先排固定好,已知15~xx固定,周六时已经排16xx+由(1)知6x在B组中和415xx一组,把415xx放到周一,周日时已经排511xx,在B组314xx和10x.由于不重合原则,只有213xx