数学建模上机实验报告
按：有待进一步施工，尤其是最后一个问题...
这一届(19级)的数学建模的上机题目是在晚上上机的三个小时(可以适当延时一到两个小时)完成一道题目的建模与求解。可以使用任何方法，如果使用计算机求解，那么需要给出代码。因此，这里在建模之后，当然是选择使用 Python 来求解。而题目本身则是一道经典的运筹学问题。在网上也比较容易找到相关的题目。
问题描述
以下没有排版的文字描述仅供搜索引擎检索时使用。
某医院每天各时间段内需要的值班护士数如表1所示： 该医院护士上班分五个班次，每班8小时，具体上班时间为第一班2:0010:00，第二班6:0014:00，第三班10:0018:00，第四班14:0022:00，第五班18:00~2:00（次日）。每名护士每周上5个班，并被安排在不同的日子，由一名总护士长负责护士的值班安排。值班方案要做到在人员或经济上比较节省，又做到尽可能合情合理。下面是一些正在考虑中的值班方案： 方案1：每名护士连续上班5天，休息2天，并从上班第一天起按从上第一班到第五班顺序安排。 方案2：考虑到方案1中每名护士在周末（周六、周日）两天内休息安排不均匀，于是规定每名护士在周六、周日两天内安排一天、且只安排一天休息，再在周一至周五期间安排4个班，同样上班的5天内分别顺序安排5个不同班次。 在对方案1、2建立线性规划模型并求解后发现，方案2虽然在安排周末休息上比较合理，但所需值班人员要比方案1有较多增加，经济上不太合算，于是又提出了第3方案。 方案3：在方案2的基础上，动员一部分护士放弃周末休息，即每周在周一至周五间由总护士长给安排三天值班，加周六周日共上五个班，同样五个班分别安排不同班次。作为奖励，规定放弃周末休息的护士，其工资和奖金总额比其他护士增加a%。 根据上述方案，帮助总护士长分析研究： （1）对方案1、2建立使值班护士人数为最少的线性规划模型并求解。 （2）对方案3，同样建立使值班护士人数为最少的线性规划模型并求解， 然后回答a的值为多大时，第3方案较第2方案更经济。
（1）对方案 1、2 建立使值班护士人数为最少的线性规划模型并求解。
对方案 1
设 \(x_i\) 表示星期 \(i\) 上第一班的人数(\(i = 1,2,3,...,7\))，于是我们可以画出护士的值班表，然后我们可以对方案 1 建模
\[ min \; z = x_1 + x_2 + x_3 + x_4 + x_5 + x_6 + x_7 \]
s.t.
\[ \begin{align} & x_1 + x_7 \geq 21 \\ & x_6 + x_7 \geq 21 \\ & x_6 + x_5 \geq 21 \\ & x_5 + x_4 \geq 21 \\ & x_4 + x_3 \geq 21 \\ & x_3 + x_2 \geq 21 \\ & x_2 + x_1 \geq 21 \\ & x_i \geq 11 (i = 1,2...7) \end{align} \]
Python 代码如下：
from scipy.optimize import linprog
# 需要优化的函数对应的参数
c = [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, -1],
[0, 0, -1, -1, 0, 0, 0],
[0, -1, -1, 0, 0, 0, 0],
[-1, -1, 0, 0, 0, 0, 0]]
# 不等式对应的上界
b = [-21,
-21,
-21,
-21,
-21,
-21,
-21]
x0_bounds = (11, None)
x1_bounds = (11, None)
x2_bounds = (11, None)
x3_bounds = (11, None)
x4_bounds = (11, None)
x5_bounds = (11, None)
x6_bounds = (11, None)
# 代入参数，利用 Linprog 求解
res = linprog(c, A_ub=A, b_ub=b, bounds=(x0_bounds, x1_bounds, x2_bounds, x3_bounds, x4_bounds, x5_bounds, x6_bounds), options={"disp":True})
print(res)运行结果如下
Primal Feasibility Dual Feasibility Duality Gap Step Path Parameter Objective
1.0 1.0 1.0 - 1.0 84.0
0.2809006503072 0.2809006503072 0.2809006503072 0.7236863182761 0.2809006503072 91.03677956402
0.08188226522114 0.08188226522115 0.08188226522115 0.7562200719556 0.08188226522115 77.6110644976
0.003285103873164 0.003285103873165 0.003285103873165 0.9666015052536 0.003285103873165 77.04759485173
4.141424664791e-07 4.141424663523e-07 4.141424663529e-07 0.9998761933313 4.141424663523e-07 77.00000725134 2.070722078688e-11 2.070712356167e-11 2.070712356152e-11 0.9999499999994 2.070712356154e-11 77.00000000036
Optimization terminated successfully.
Current function value: 77.000000
Iterations: 5
con: array([], dtype=float64)
fun: 77.00000000036258
message: 'Optimization terminated successfully.'
nit: 5
slack: array([ 1., 1., 1., 12., 1., 1., 1.])
status: 0
success: True
x: array([11., 11., 11., 11., 11., 11., 11.])所以得到的结果是：
\[ x_1 = 11, x2 = 11, x_3 = 11, x_4 = 11, x_5 = 11, x_6 = 11, x_7 = 11 \]
对方案 2
周一到周五连续安排 4 个班，所以可以先安排周末的护士值班情况：周六、周末两天共 10 个班次，用 \(x_j(j = 1...10)\) 表示周六周末两天 10 个班次的护士人数，其中 \(x_1 ...x_5\) 分别代表周六第 1 个到第 5 个班次的护士人数，\(x_6...x_{10}\) 分别代表周日从第 1 个到第 5 个班次的护士人数。因此，我们可以列出其值班表(这里略)。
对方案 2 建立如下线性规划模型：
\(min \; w = x_1 + \cdots + x_{10}\)
s.t.
\[ \begin{align} x_1 + x_5 + x_9 + x_{10} \geq 21 \\ x_4 + x_5 + x_8 + x_9 \geq 21 \\ x_1 + x_2 + x_6 + x_{10} \geq 21 \\ x_2 + x_3 + x_6 + x_7 \geq 20 \\ x_3 + x_4 + x_7 + x_8 \geq 19 \\ x_1 + x_2 \geq 19 \\ x_6 + x_{10} \geq 19 \\ x_2 + x_3 \geq 21 \\ x_6 + x_7 \geq 21 \\ x_3 + x_4 \geq 21 \\ x_7 + x_8 \geq 21 \\ x_8 + x_9 \geq 20 \\ x_4 + x_5 \geq 20 \\ x_1 + x_5 \geq 18 \\ x_9 + x_{10} \geq 18 \\ x_4 + x_8 \geq 11 \\ x_3 + x_7 \geq 11 \\ x_2 + x_6 \geq 11 \\ x_5 + x_9 \geq 11 \\ x_1, x_2, x_5, x_6, x_9, x_{10} \geq 11 \\ x_j \geq 0 \; (j = 1,2,...,10) \end{align} \]
Python 代码如下：
from scipy.optimize import linprog
# 需要优化的函数对应的参数
c = [1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
# 不等式对应的参数矩阵
A = [[-1, 0, 0, 0, -1, 0, 0, 0, -1, -1],
[0, 0, 0, -1, -1, 0, 0, -1, -1, 0],
[-1, -1, 0, 0, 0, -1, 0, 0, 0, -1],
[0, -1, -1, 0, 0, -1, -1, 0, 0, 0],
[0, 0, -1, -1, 0, 0, -1, -1, 0, 0],
[-1, -1, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, -1, 0, 0, 0, -1],
[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, 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 = [-21,
-21,
-21,
-20,
-19,
-19,
-19,
-21,
-21,
-21,
-21,
-20,
-20,
-18,
-18,
-11,
-11,
-11,
-11]
x0_bounds = (11, None)
x1_bounds = (11, None)
x2_bounds = (0, None)
x3_bounds = (0, None)
x4_bounds = (11, None)
x5_bounds = (11, None)
x6_bounds = (0, None)
x7_bounds = (0, None)
x8_bounds = (11, None)
x9_bounds = (11, None)
# 代入参数，利用 Linprog 求解
res = linprog(c, A_ub=A, b_ub=b, bounds=(x0_bounds, x1_bounds, x2_bounds, x3_bounds, x4_bounds, x5_bounds, x6_bounds,x7_bounds, x8_bounds, x9_bounds), options={"disp":True})
print(res)运行结果如下：
Primal Feasibility Dual Feasibility Duality Gap Step Path Parameter Objective
1.0 1.0 1.0 - 1.0 76.0
0.1665271036098 0.1665271036098 0.1665271036098 0.8426664003083 0.1665271036098 99.77035462588
0.02577816616616 0.02577816616617 0.02577816616617 0.8554761926722 0.02577816616617 141.9514028382
0.004990687117403 0.004990687117402 0.004990687117402 0.8274173331906 0.004990687117403 107.7426696988
0.0002950591091504 0.0002950591091505 0.0002950591091506 0.9487415264061 0.0002950591091506 107.9482724078
5.696569995622e-08 5.696569991676e-08 5.696569979366e-08 0.9998223879716 5.696569998307e-08 108.00000478
2.848279017625e-12 2.84830035367e-12 2.848388191978e-12 0.9999499996825 2.848288065828e-12 108.0000000002
Optimization terminated successfully.
Current function value: 108.000000
Iterations: 6
con: array([], dtype=float64)
fun: 108.000000000239
message: 'Optimization terminated successfully.'
nit: 6
slack: array([ 2.30000000e+01, 2.07164358e+01, 2.30000000e+01, 2.42835642e+01,
2.30000000e+01, 3.00000000e+00, 3.00000000e+00, 1.14178209e+00,
1.14178209e+00, -4.13713508e-10, -4.13720613e-10, 8.58217912e-01,
8.58217913e-01, 4.00000000e+00, 4.00000000e+00, 8.71643582e+00,
1.12835642e+01, 1.10000000e+01, 1.10000000e+01])
status: 0
success: True
x: array([11. , 11. , 11.14178209, 9.85821791, 11. ,
11. , 11.14178209, 9.85821791, 11. , 11. ])所以得到的结果是：
\[ x_1 = 11 \\ x_2 = 11 \\ x_3 = 12 \\ x_4 = 10 \\ x_5 = 11 \\ x_6 = 11 \\ x_7 = 12 \\ x_8 = 10 \\ x_9 = 11 \\ x_{10} = 11 \]
对方案 3，同样建立使值班护士人数为最少的线性规划模型并求解，然后回答 a 的值为多大时，第 3 方案较第 2 方案更经济。
Python 代码如下：
from scipy.optimize import linprog
import numpy as np
# 需要优化的函数对应的参数
# 不等式对应的参数矩阵
from scipy.optimize import linprog
import numpy as np
# 需要优化的函数对应的参数
# 不等式对应的参数矩阵
A = np.array([[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 = np.array(
[-19, -19, -19, -19, -21, -21, -21, -21, -21, -21, -21, -20, -20, -20, -20, -20, -18, -18, -18, -18, -11, -11, -11,
-11, -11, -11, -11, -11, -11])
c = np.array([1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1])
# 代入参数，利用 Linprog 求解
res = linprog(c, A_ub=A, b_ub=b, options={"disp": True})
print(res.x)结果如下：
Primal Feasibility Dual Feasibility Duality Gap Step Path Parameter Objective
1.0 1.0 1.0 - 1.0 37.0
0.2426475349467 0.2426475349467 0.2426475349467 0.7716251234008 0.2426475349467 55.01818412195
0.04252842427154 0.04252842427153 0.04252842427153 0.8355997887823 0.04252842427153 104.247705703
0.009356747800954 0.009356747800955 0.009356747800955 0.7953997093281 0.009356747800955 103.5089480738
0.0005030671623338 0.000503067162334 0.0005030671623341 0.949055846188 0.000503067162334 104.012914924
7.859317598419e-08 7.859317820896e-08 7.859317829872e-08 0.9998545163766 7.859317721648e-08 103.9999952247
3.929662644848e-12 3.929721186398e-12 3.929745417963e-12 0.9999499992073 3.929678577412e-12 103.9999999998
Optimization terminated successfully.
Current function value: 104.000000
Iterations: 6
[ 7.14875174 2.83528395 6.35115075 7.24511069 6.60703322 11.
11. 8. 13. 7. 4.39296678 6.76594071
4.2500236 4.64884925 3.75488931]由于放弃周末休息的护士其工资和奖金总额比其他护士增加a%，假设未放 弃周末休息的护士的工资为A 园，若使方案三比方案2更经济，可列一下方程： 66A + 38 A (1+a%) < 108 *A 解以上方程可得： a% < 10.5263% 即a<10.5263时，方案三比方案二更经济。