Question

求解题算法思路

求解题算法思路某医院的心脑血管科需要制定护士的工作时间表。在心脑血管科的一个工作日分为12个两小时的时段，每个时段的人员要求不同。例如，在夜间只要求有很少几名护士就足够了，但在早晨为了给病人提供特殊报务，需要很多护士。表B1列出了每个时段的人员需求量。
表B1 每个时段的人员需求
编号 时段 需要护士人数
1 0:00——2:00 15
2 2:00——5:00 15
3 4:00——6:00 15
4 6:00——8:00 35
5 8:00——10:00 40
6 10:00——12:00 40
7 12:00——14:00 40
8 14:00——16:00 30
9 16:00——18:00 31
10 18:00——20:00 35
11 20:00——22:00 30
12 22:00——24:00 20

问题1：（1）为满足需求最少需要多少名护士？这里假定每位护士每天工作8小时，且在工作4小时后需要休息1小时。（2）如果满足需求的排班方案不止一种，请给出你认为最合理的排班方案，并说明其理由。

问题2：目前心脑血管科只有80名护士，如果这个数目不能满足指定的需求，只能考虑让部分护士加班。如果加班，每天加班的时间为2小时，且紧随在后一个4小时工作时段之后，中间没有休息。（1）请给出护士工作时间安排的方案，以使需要加班的护士数目最少。（2）如果排班（包括加班）的方案不止一种，请给出你认为最合理的排班和加班方案，并说明其理由。

Answer 1

问题1
设
0点,1点,2点,...23点上班的人数分别是x0,x1,x2,...,x23，记为列向量x
0点,1点,2点,...23点在岗的人数分别是y0,y1,y2,...,y23，记为列向量y
则依题意有y=Ax，其中A是24阶0-1矩阵：
1　0　0　0　0　0　0　0　0　0　0　0　0　0　0　0　1　1　1　1　0　1　1　1
1　1　0　0　0　0　0　0　0　0　0　0　0　0　0　0　0　1　1　1　1　0　1　1
1　1　1　0　0　0　0　0　0　0　0　0　0　0　0　0　0　0　1　1　1　1　0　1
1　1　1　1　0　0　0　0　0　0　0　0　0　0　0　0　0　0　0　1　1　1　1　0
0　1　1　1　1　0　0　0　0　0　0　0　0　0　0　0　0　0　0　0　1　1　1　1
1　0　1　1　1　1　0　0　0　0　0　0　0　0　0　0　0　0　0　0　0　1　1　1
1　1　0　1　1　1　1　0　0　0　0　0　0　0　0　0　0　0　0　0　0　0　1　1
1　1　1　0　1　1　1　1　0　0　0　0　0　0　0　0　0　0　0　0　0　0　0　1
1　1　1　1　0　1　1　1　1　0　0　0　0　0　0　0　0　0　0　0　0　0　0　0
0　1　1　1　1　0　1　1　1　1　0　0　0　0　0　0　0　0　0　0　0　0　0　0
0　0　1　1　1　1　0　1　1　1　1　0　0　0　0　0　0　0　0　0　0　0　0　0
0　0　0　1　1　1　1　0　1　1　1　1　0　0　0　0　0　0　0　0　0　0　0　0
0　0　0　0　1　1　1　1　0　1　1　1　1　0　0　0　0　0　0　0　0　0　0　0
0　0　0　0　0　1　1　1　1　0　1　1　1　1　0　0　0　0　0　0　0　0　0　0
0　0　0　0　0　0　1　1　1　1　0　1　1　1　1　0　0　0　0　0　0　0　0　0
0　0　0　0　0　0　0　1　1　1　1　0　1　1　1　1　0　0　0　0　0　0　0　0
0　0　0　0　0　0　0　0　1　1　1　1　0　1　1　1　1　0　0　0　0　0　0　0
0　0　0　0　0　0　0　0　0　1　1　1　1　0　1　1　1　1　0　0　0　0　0　0
0　0　0　0　0　0　0　0　0　0　1　1　1　1　0　1　1　1　1　0　0　0　0　0
0　0　0　0　0　0　0　0　0　0　0　1　1　1　1　0　1　1　1　1　0　0　0　0
0　0　0　0　0　0　0　0　0　0　0　0　1　1　1　1　0　1　1　1　1　0　0　0
0　0　0　0　0　0　0　0　0　0　0　0　0　1　1　1　1　0　1　1　1　1　0　0
0　0　0　0　0　0　0　0　0　0　0　0　0　0　1　1　1　1　0　1　1　1　1　0
0　0　0　0　0　0　0　0　0　0　0　0　0　0　0　1　1　1　1　0　1　1　1　1
.
很容易写出枚举算法：
min=120
repeat
选取向量x（分量不超过40）
计算向量y=Ax和人数n=x0+x1+x2+...+x23
如果y满足条件：y0～y5≥15,y6～y7≥35,y8～y15≥40,y16～y17≥31,y18～y19≥36,y20～y23≥20
并且人数n<min则：min=n；并输出可行解x和人数n
until 遍历所有枚举
最后一个结果就是答案
.
但这是指数时间算法，不可行
我用Excel手工搜索到最佳解是93人，3个解：
0　3　3　6　5　10　11　6　4　3　3　0　2　5　3　4　9　7　5　4　0　0　0　0
0　3　3　5　6　10　11　4　4　4　4　0　2　5　3　4　9　7　5　4　0　0　0　0
0　3　3　5　6　10　11　4　5　4　3　0　2　5　3　4　9　7　5　4　0　0　0　0
似乎已经不能再减少人数了

问题2
算法与问题1类似
由于没有找到好算法
就不用手工搜索了

Answer 2

题算法思路