【运筹学】MATLAB求解护士值班安排的线性规划问题

长征医院是长宁区一所区级医院，该院每天各时间段内需求的值班护士数如下表所示： 该医院护士上班分五个班次，每班8小时，具体上班时间为第一班2:00-10:00，第二班6:00-14:00，第三班10:00-18:00，第四班14:00-22:00，第五班18:00-2:00（次日）。每名护士每周上5个班，并被安排在不同日子，有一名总护士长负责护士的值班安排。值班方案既要做到在人员或经济上比较节省，又要做到尽可能合情合理。下面是一些正在考虑中的值班方案：

方案一

每名护士连续上班5天，休息2天，并从上班第一天起按从上第一班到第五班顺序安排。例如一名护士从周一开始上班，则她于周一上第一班，周二上第二班……周五上第五班；另一名护士若从周三起上班，则她于周三上第二班，周四上第三班……周日上第五班，等等。

f=[1;1;1;1;1;1;1]; A=[-1 0 0 0 0 0 -1 0 0 0 0 0 -1 -1 0 0 0 0 -1 -1 0 0 0 0 -1 -1 0 0 0 0 -1 -1 0 0 0 0 -1 -1 0 0 0 0 -1 -1 0 0 0 0 0] b=[-20;-20;-20;-20;-20;-20;-20]; lb=[12;12;12;12;12;12;12]; [x,fval,exitflag,output,lambda]=linprog(f,A,b,[],[],lb) >> case1 A = -1 0 0 0 0 0 -1 0 0 0 0 0 -1 -1 0 0 0 0 -1 -1 0 0 0 0 -1 -1 0 0 0 0 -1 -1 0 0 0 0 -1 -1 0 0 0 0 -1 -1 0 0 0 0 0 Optimal solution found. x = 12 12 12 12 12 12 12 fval = 84 exitflag = 1 output = struct with fields: iterations: 0 constrviolation: 0 message: 'Optimal solution found.' algorithm: 'dual-simplex' firstorderopt: 0 lambda = struct with fields: lower: [7×1 double] upper: [7×1 double] eqlin: [] ineqlin: [7×1 double] >>

方案二

考虑到按上述方案中每名护士在周末（周六、周日）两天内休息安排不均匀。于是按规定每名护士在周六、周日两天内至少安排一天休息，再如同方案1在周一至周五期间分别顺序安排其他班次。

f=[1 1 1 1 1 1 1 1 1 1]; A=[0 0 0 0 0 -1 0 0 0 -1; -1 0 0 0 -1 0 0 0 -1 -1; 0 0 0 -1 -1 0 0 -1 -1 0; 0 0 -1 -1 0 0 -1 -1 0 0; -1 -1 0 0 0 0 0 0 0 0; 0 -1 -1 0 0 0 0 0 0 0; 0 0 0 0 0 -1 -1 0 0 0; 0 0 -1 -1 0 0 0 0 0 0; 0 0 0 0 0 0 -1 -1 0 0; 0 -1 -1 0 0 -1 -1 0 0 0; -1 -1 0 0 0 -1 0 0 0 -1; 0 0 0 0 0 0 0 -1 -1 0; 0 0 0 -1 -1 0 0 0 0 0; -1 0 0 0 -1 0 0 0 0 0; 0 0 0 0 0 0 0 0 -1 -1; 0 0 0 -1 0 0 0 -1 0 0; 0 0 -1 0 0 0 -1 0 0 0; 0 -1 0 0 0 -1 0 0 0 0; 0 0 0 0 -1 0 0 0 -1 0] b=[-18;-20;-20;-18;-18;-20;-20;-20;-20;-19;-20;-19;-19;-17;-17;-12;-12;-12;-12]; lb=[12;12;0;0;12;12;0;0;12;12]; [x,fval,exitflag,output,lambda] = linprog(f,A,b,[],[],lb) >> case2 A = 0 0 0 0 0 -1 0 0 0 -1 -1 0 0 0 -1 0 0 0 -1 -1 0 0 0 -1 -1 0 0 -1 -1 0 0 0 -1 -1 0 0 -1 -1 0 0 -1 -1 0 0 0 0 0 0 0 0 0 -1 -1 0 0 0 0 0 0 0 0 0 0 0 0 -1 -1 0 0 0 0 0 -1 -1 0 0 0 0 0 0 0 0 0 0 0 0 -1 -1 0 0 0 -1 -1 0 0 -1 -1 0 0 0 -1 -1 0 0 0 -1 0 0 0 -1 0 0 0 0 0 0 0 -1 -1 0 0 0 0 -1 -1 0 0 0 0 0 -1 0 0 0 -1 0 0 0 0 0 0 0 0 0 0 0 0 0 -1 -1 0 0 0 -1 0 0 0 -1 0 0 0 0 -1 0 0 0 -1 0 0 0 0 -1 0 0 0 -1 0 0 0 0 0 0 0 0 -1 0 0 0 -1 0 Optimal solution found. x = 12 12 8 12 12 12 13 7 12 12 fval = 112 exitflag = 1 output = struct with fields: iterations: 4 constrviolation: 0 message: 'Optimal solution found.' algorithm: 'dual-simplex' firstorderopt: 0 lambda = struct with fields: lower: [10×1 double] upper: [10×1 double] eqlin: [] ineqlin: [19×1 double]

方案三

在对第1、2方案建立线性规划模型并顺利求解后，发现方案2虽然在周末休息上比较合理，但所需值班人数要比第1方案由较多增加，经济上不太合算，于是又提出了第3方案。 方案3：动员一部分护士放弃周末休息，即每周在周一至周五间由总护士长安排三天值班，加周六周日共上五个班，同样五个班分别安排不同班次。其他护士每周六、日内均休一天。作为奖励，规定放弃周末休息的护士，其工资和奖金总额比其他护士增加a%。

f=[1 1 1 1 1 1 1 1 1 1 1 1 1 1 1]; A=[0 0 0 -1 -1 0 0 0 0 0 -1 0 0 0 -1; 0 0 0 0 0 0 0 -1 -1 0 0 -1 -1 0 0 ; 0 0 0 0 0 0 -1 -1 0 0 0 0 0 0 0; -1 -1 0 0 0 -1 -1 0 0 0 0 0 0 0 0; -1 0 0 0 -1 0 0 0 0 0 -1 -1 0 0 0; 0 0 0 -1 -1 -1 -1 0 0 0 -1 0 0 0 -1; 0 0 -1 -1 0 -1 0 0 0 -1 0 0 0 -1 -1; 0 0 0 0 0 0 0 0 -1 -1 0 0 -1 -1 0; 0 0 0 0 0 0 0 -1 -1 0 0 0 0 0 0; 0 -1 -1 0 0 0 -1 -1 0 0 0 0 0 0 0; -1 -1 0 0 0 0 0 0 0 0 0 -1 -1 0 0; 0 0 0 0 -1 0 -1 -1 0 0 -1 -1 0 0 0; 0 0 0 0 0 -1 0 0 0 -1 0 0 0 -1 -1; 0 0 0 0 0 0 0 0 -1 -1 0 0 0 0 0; 0 0 0 -1 -1 0 0 0 -1 -1 0 0 0 0 0; 0 0 -1 -1 0 0 0 0 0 0 0 0 -1 -1 0; 0 0 0 0 0 -1 0 0 0 -1 0 0 0 0 0; 0 0 0 0 0 -1 -1 0 0 0 -1 0 0 0 -1; 0 0 0 -1 -1 0 0 0 -1 -1 0 0 0 0 0; 0 0 -1 -1 0 0 0 0 0 0 0 0 0 -1 -1; 0 0 0 0 0 0 0 -1 0 0 0 -1 0 0 0; 0 0 0 0 0 0 -1 0 0 0 0 0 0 0 0; 0 0 0 0 -1 0 0 0 0 0 -1 0 0 0 0; 0 0 -1 0 0 0 0 0 0 0 0 0 0 -1 0; 0 -1 0 0 0 0 0 0 -1 0 0 0 -1 0 0; 0 0 0 0 0 0 -1 0 0 0 -1 0 0 0 0; 0 0 0 0 0 -1 0 0 0 0 0 0 0 0 0; 0 0 0 0 -1 0 0 0 0 -1 0 0 0 0 0; 0 0 0 -1 0 0 0 0 0 0 0 0 0 0 -1]; b=[-18;-18;-18;-18;-20;-20;-20;-20;-20;-20;-20;-19;-19;-19;-19;-19;-17;-17;-17;-17;-12;-12;-12;-12;-12;-12;-12;-12;-12]; lb=zeros(15,1); [x,fval,exitflag,output,lambda] = linprog(f,A,b,[],[],lb)

运行结果：

>> case3 Optimal solution found. x = 12 2 0 7 12 12 12 6 14 5 0 6 0 12 5 fval = 105 exitflag = 1 output = struct with fields: iterations: 19 constrviolation: 0 message: 'Optimal solution found.' algorithm: 'dual-simplex' firstorderopt: 0 lambda = struct with fields: lower: [15×1 double] upper: [15×1 double] eqlin: [] ineqlin: [29×1 double]