# 数学建模实战：用Python PuLP库搞定整数规划（附排班问题完整代码） 如果你正在学习数学建模，或者是一名Python开发者，面对“如何将现实中的排班、排产问题转化为计算机可以求解的模型”这个难题时感到无从下手，那么这篇文章就是为你准备的。我们常常陷入一个困境：脑子里有清晰的业务逻辑，知道有哪些限制条件，也明白要追求什么目标（比如成本最低、效率最高），但就是卡在“怎么用数学语言描述它”以及“写出来的模型怎么让计算机算”这两步上。这种感觉，就像手握一份精密的建筑设计图，却找不到合适的工具和材料把它建造出来。 整数规划，正是将这类离散决策问题从蓝图变为现实的强大工具。它属于运筹学的核心范畴，要求决策变量取整数值，完美契合了现实中“人不能是半个”、“机器不能买0.3台”的需求。而Python中的PuLP库，则像一个友好的施工队，让我们能用近乎口语化的Python代码来“指挥”求解器进行复杂的计算。本文不会停留在理论介绍，我们将直接切入一个经典的**护士排班问题**，手把手带你走完从问题理解、模型构建、代码实现到结果分析的全过程。你会发现，那些看似复杂的排班表，其背后的数学模型可以如此优雅，而用Python求解又是如此直接。 ## 1. 问题拆解：护士排班场景与核心挑战 假设我们管理一家医院的护理部门，需要为下一个工作日（24小时）制定护士排班计划。为了简化问题便于理解，我们做以下设定： * **时段划分**：将一天划分为6个连续的工作时段，每个时段为4小时。 * 时段1: 0:00 - 4:00 * 时段2: 4:00 - 8:00 * 时段3: 8:00 - 12:00 * 时段4: 12:00 - 16:00 * 时段5: 16:00 - 20:00 * 时段6: 20:00 - 24:00 * **人力需求**：每个时段根据病人护理工作量，有最低护士数量要求。需求如下表所示： | 时段编号 | 时间范围 | 最低所需护士数 | | :--- | :--- | :--- | | 1 | 0:00 - 4:00 | 15 | | 2 | 4:00 - 8:00 | 15 | | 3 | 8:00 - 12:00 | 15 | | 4 | 12:00 - 16:00 | 35 | | 5 | 16:00 - 20:00 | 40 | | 6 | 20:00 - 24:00 | 40 | * **排班规则**： 1. 每位护士每天工作一个班次，时长为**8小时**，并且是**连续的两个时段**（例如从时段1工作到时段2，即0:00-8:00）。 2. 护士工作中间没有休息。 3. 目标：在满足所有时段人力需求的前提下，**最小化雇佣的护士总数**，从而控制人力成本。 **我们的核心挑战**在于：如何用数学变量表示“安排护士从哪个时段开始上班”，如何用等式或不等式表达“每个时段的人力需求必须被满足”，以及如何设置目标函数。这听起来复杂，但一旦转化为整数规划模型，结构会非常清晰。 > 提示：理解“连续工作8小时”这一规则是建模的关键。这意味着护士的班次起点只能是时段1到时段6（如果从时段6开始，则连续工作时段6和时段1，即跨天）。这定义了我们的决策变量。 ## 2. 模型构建：从业务规则到数学公式 面对上述问题，我们一步步构建整数规划模型。 **第一步：定义决策变量** 这是建模的起点，变量设计得好，模型就简单易懂。我们定义6个决策变量： * \( x_1 \)：从时段1（0:00）开始上班的护士人数。 * \( x_2 \)：从时段2（4:00）开始上班的护士人数。 * \( x_3 \)：从时段3（8:00）开始上班的护士人数。 * \( x_4 \)：从时段4（12:00）开始上班的护士人数。 * \( x_5 \)：从时段5（16:00）开始上班的护士人数。 * \( x_6 \)：从时段6（20:00）开始上班的护士人数。 所有这些 \( x_j \) ( \( j = 1, 2, ..., 6 \) ) 都是**非负整数**，因为人数不能是负数或小数。 **第二步：构建目标函数** 我们的目标是最小化总护士数，即所有班次开始的护士人数之和： \[ \text{Minimize} \quad Z = x_1 + x_2 + x_3 + x_4 + x_5 + x_6 \] **第三步：列出约束条件** 这是模型的核心，确保每个时段的人力需求得到满足。我们需要分析在每个时段，有哪些班次的护士正在工作。 * **时段1 (0:00-4:00)**：正在工作的是那些从**时段6**（昨天20:00开始，工作到今早4:00）和从**时段1**（0:00开始）开始的护士。因此约束为：\( x_6 + x_1 \geq 15 \) * **时段2 (4:00-8:00)**：正在工作的是从**时段1**（0:00开始）和从**时段2**（4:00开始）开始的护士。约束：\( x_1 + x_2 \geq 15 \) * **时段3 (8:00-12:00)**：正在工作的是从**时段2**和**时段3**开始的护士。约束：\( x_2 + x_3 \geq 15 \) * **时段4 (12:00-16:00)**：正在工作的是从**时段3**和**时段4**开始的护士。约束：\( x_3 + x_4 \geq 35 \) * **时段5 (16:00-20:00)**：正在工作的是从**时段4**和**时段5**开始的护士。约束：\( x_4 + x_5 \geq 40 \) * **时段6 (20:00-24:00)**：正在工作的是从**时段5**和**时段6**开始的护士。约束：\( x_5 + x_6 \geq 40 \) **第四步：完整数学模型** 将以上所有部分整合，我们得到以下纯整数线性规划模型： \[ \begin{aligned} & \text{Minimize} \quad Z = x_1 + x_2 + x_3 + x_4 + x_5 + x_6 \\ & \text{subject to:} \\ & \quad x_6 + x_1 \geq 15 \\ & \quad x_1 + x_2 \geq 15 \\ & \quad x_2 + x_3 \geq 15 \\ & \quad x_3 + x_4 \geq 35 \\ & \quad x_4 + x_5 \geq 40 \\ & \quad x_5 + x_6 \geq 40 \\ & \quad x_j \geq 0, \quad x_j \in \mathbb{Z}, \quad j = 1,2,...,6 \end{aligned} \] 模型构建完毕。它清晰地描述了我们的业务问题，接下来就是让Python和PuLP库来求解这个模型。 ## 3. 工具准备：PuLP库简介与环境配置 PuLP（Python Linear Programming）是一个开源的线性规划建模库，它提供了非常直观的API来定义变量、约束和目标函数。PuLP本身是一个建模工具，它调用后端的求解器（如CBC、GLPK、Gurobi等）来执行实际计算。对于大多数常规问题，其内置的CBC求解器完全够用，并且无需额外安装。 **安装PuLP** 打开你的终端（命令行），使用pip命令安装，非常简单： ```bash pip install pulp ``` 如果你使用的是Anaconda，也可以使用： ```bash conda install -c conda-forge pulp ``` **PuLP的核心概念** 在写代码前，快速了解几个PuLP的核心类： * `LpProblem`: 定义一个优化问题，需要指定问题名称和优化方向（`LpMinimize`或`LpMaximize`）。 * `LpVariable`: 定义决策变量，需要指定变量名、下界、上界和变量类型（`‘Continuous’`, `‘Integer’`, `‘Binary’`）。 * `+=` 操作符：用于向问题中添加目标函数和约束条件。 有了这些基础，我们就可以将上一步的数学模型“翻译”成Python代码了。 ## 4. 代码实战：用PuLP求解护士排班模型 现在，我们将数学模型转化为可执行的Python代码。我会对每一部分代码进行详细解释。 ```python # nurse_scheduling.py from pulp import LpMinimize, LpProblem, LpVariable, lpSum, LpStatus # 1. 创建问题实例 # 参数：问题名称， 优化方向（最小化） model = LpProblem(name="Nurse_Scheduling_Problem", sense=LpMinimize) # 2. 定义决策变量 # 创建6个变量，分别对应x1到x6 # 参数：变量名前缀， 索引范围， 下界， 变量类型（整数） x = LpVariable.dicts("start_at_shift", range(1, 7), lowBound=0, cat='Integer') # 现在 x[1] 代表 x1, x[2] 代表 x2, ..., x[6] 代表 x6 # 3. 定义目标函数：最小化总护士数 (x1 + x2 + ... + x6) # lpSum 是PuLP提供的求和函数，比用普通sum更高效 model += lpSum([x[i] for i in range(1, 7)]), "Total_Number_of_Nurses" # 4. 添加约束条件 # 每个约束条件都是一个不等式，并可以有一个描述性的名字 model += (x[6] + x[1] >= 15, "Shift_1_Demand") model += (x[1] + x[2] >= 15, "Shift_2_Demand") model += (x[2] + x[3] >= 15, "Shift_3_Demand") model += (x[3] + x[4] >= 35, "Shift_4_Demand") model += (x[4] + x[5] >= 40, "Shift_5_Demand") model += (x[5] + x[6] >= 40, "Shift_6_Demand") # 5. 求解问题 # 调用默认的CBC求解器进行计算 solver = model.solve() # 6. 输出结果 print("-" * 50) print("求解状态:", LpStatus[model.status]) print("-" * 50) if model.status == 1: # 1 表示 Optimal，求解成功 print("最优排班方案 (最小化护士总数):") print("-" * 30) total_nurses = 0 for i in range(1, 7): nurse_count = int(x[i].varValue) # 获取变量的整数值 total_nurses += nurse_count start_hour = (i-1)*4 end_hour = (i+1)*4 if i < 6 else 4 # 处理跨天的时段6 print(f" 从 {start_hour:02d}:00 开始上班的护士: {nurse_count:3d} 人") print("-" * 30) print(f">>> 所需护士总数为: {total_nurses} 人 <<<") print("-" * 50) # 额外输出：验证每个时段的人力覆盖情况 print("\n各时段人力覆盖验证:") print("时段 | 时间范围 | 需求 | 实际在岗 | 是否满足") print("-" * 55) shifts = [ (1, "0:00-4:00", 15, x[6].varValue + x[1].varValue), (2, "4:00-8:00", 15, x[1].varValue + x[2].varValue), (3, "8:00-12:00", 15, x[2].varValue + x[3].varValue), (4, "12:00-16:00", 35, x[3].varValue + x[4].varValue), (5, "16:00-20:00", 40, x[4].varValue + x[5].varValue), (6, "20:00-24:00", 40, x[5].varValue + x[6].varValue), ] for sid, time_range, demand, actual in shifts: met = "是" if actual >= demand else "否" print(f" {sid} | {time_range:^10} | {demand:3d} | {actual:8.0f} | {met}") else: print("未找到最优解。可能问题不可行或无界。") ``` 将上述代码保存为 `nurse_scheduling.py` 并运行。你会看到类似下面的输出： ``` -------------------------------------------------- 求解状态: Optimal -------------------------------------------------- 最优排班方案 (最小化护士总数): ------------------------------ 从 00:00 开始上班的护士: 0 人 从 04:00 开始上班的护士: 15 人 从 08:00 开始上班的护士: 0 人 从 12:00 开始上班的护士: 35 人 从 16:00 开始上班的护士: 5 人 从 20:00 开始上班的护士: 35 人 ------------------------------ >>> 所需护士总数为: 90 人 <<< -------------------------------------------------- 各时段人力覆盖验证: 时段 | 时间范围 | 需求 | 实际在岗 | 是否满足 ------------------------------------------------------- 1 | 0:00-4:00 | 15 | 35 | 是 2 | 4:00-8:00 | 15 | 15 | 是 3 | 8:00-12:00 | 15 | 15 | 是 4 | 12:00-16:00| 35 | 35 | 是 5 | 16:00-20:00| 40 | 40 | 是 6 | 20:00-24:00| 40 | 40 | 是 ``` **结果解读**： 1. **最优解**：总共需要 **90名** 护士。 2. **排班细节**： * 安排15名护士从4:00开始工作（覆盖时段2和3）。 * 安排35名护士从12:00开始工作（覆盖时段4和5）。 * 安排5名护士从16:00开始工作（覆盖时段5和6）。 * 安排35名护士从20:00开始工作（覆盖时段6和1）。 * 没有护士从0:00或8:00开始。 3. **验证**：表格显示每个时段的人力都**恰好满足**或**超过**最低需求，没有浪费（在满足需求的点上刚好达到或略超）。例如，时段1需求15人，实际有35人（来自昨晚20:00上班的35人），这是因为要满足时段6的高需求（40人），连带使得时段1的人力也大幅过剩——这是由“连续工作8小时”的规则导致的，是模型找到的全局最优解。 > 注意：你可能会得到另一个数字上等价但分配不同的解（例如，从0:00开始安排一些人，从8:00开始安排另一些人），但总护士数90是最优的。这是因为整数规划问题有时存在多个最优解（目标函数值相同，但变量取值不同）。PuLP返回其中任何一个都是正确的。 ## 5. 模型进阶：处理更复杂的现实约束 上面的基础模型解决了核心问题，但现实中的排班往往更复杂。PuLP的灵活性使得添加新约束变得非常容易。我们来扩展一下模型。 **场景升级**： 1. 医院政策要求，从20:00之后开始上班的夜班护士（即从时段6开始），人数不能超过总护士数的30%。 2. 由于培训原因，从时段2（4:00）和时段3（8:00）开始上班的护士总数至少要有10人。 3. 每个班次（开始时段）的护士人数有一个上限，比如最多不能超过40人（避免管理幅度过大）。 **如何修改代码？** 我们只需要在原有模型的基础上，添加新的约束条件即可。 ```python # ... 前面的代码保持不变，直到添加完原有的6个需求约束 ... # 添加进阶约束 # 约束1：夜班护士（从时段6开始）不超过总护士数的30% # 总护士数就是我们的目标函数，可以用 lpSum 表示 total_nurses_expr = lpSum([x[i] for i in range(1, 7)]) model += (x[6] <= 0.3 * total_nurses_expr, "Night_Shift_Limit") # 约束2：早班（时段2和3开始）至少10人 model += (x[2] + x[3] >= 10, "Early_Shift_Minimum") # 约束3：每个班次人数上限为40人 for i in range(1, 7): model += (x[i] <= 40, f"Shift_{i}_Capacity_Limit") # ... 后面的求解和输出代码保持不变 ... ``` 运行添加了新约束的模型，你会发现结果发生了变化。总护士数可能会增加（因为约束更严格），并且排班方案会满足所有新规则。通过这种方式，你可以像搭积木一样，将各种业务规则逐步加入到模型中，使其越来越贴近实际管理需求。 ## 6. 核心技巧：PuLP建模中的常见模式与调试 在熟练使用PuLP进行整数规划建模后，掌握一些常见模式和调试技巧能极大提升效率。 **1. 处理“互斥”或“选择”关系（0-1变量）** 当你要建模“要么选A，要么选B”的场景时，需要引入0-1变量（二进制变量）。例如，两个互斥的营销方案。 ```python # 定义0-1变量 y1 = LpVariable("choose_plan_A", cat='Binary') # 1表示选A，0表示不选 y2 = LpVariable("choose_plan_B", cat='Binary') # 互斥约束：y1 和 y2 不能同时为1 model += (y1 + y2 <= 1, "Mutually_Exclusive") # 资源约束示例：如果选择方案A（y1=1），则消耗资源10单位；否则不消耗。 # 使用“大M法”，M是一个足够大的常数（如10000） M = 10000 resource_used_by_A = 10 * y1 # 或者更常见的，将连续变量x（如投资额）与是否选择关联： # x_A <= M * y1 # 如果不选A（y1=0），则x_A必须为0 # x_A >= 0 ``` **2. 调试模型：检查不可行（Infeasible）问题** 有时模型会返回`Infeasible`状态，意味着没有解能满足所有约束。调试步骤： * **逐条检查约束**：打印出所有约束，确认其数学形式和业务逻辑是否正确。 ```python for name, constraint in model.constraints.items(): print(f"{name}: {constraint}") ``` * **放松约束**：暂时注释掉部分约束，看问题是否变得可行，从而定位冲突的约束。 * **检查变量边界**：确认变量的`lowBound`和`upBound`设置是否合理，是否不小心把可行解排除在外。 **3. 提升求解性能** 对于大规模问题，求解可能较慢。可以尝试： * **提供初始解**：如果你能猜测一个较好的解，可以设置变量的初始值（`x[i].setInitialValue(guess)`），这有时能帮助求解器更快找到最优解。 * **调整求解器参数**：如果使用像Gurobi这样的高级求解器，可以调整其参数（如时间限制、最优间隙容忍度）。 * **简化模型**：审视是否有可能消除一些变量或约束，或者将一些整数变量松弛为连续变量（如果对结果影响不大）。 **PuLP与MATLAB等工具的对比** 在数学建模领域，MATLAB的优化工具箱也曾是主流选择。下表对比了在整数规划问题上，Python+PuLP与MATLAB的一些特点： | 特性 | Python + PuLP | MATLAB优化工具箱 | | :--- | :--- | :--- | | **成本与生态** | 完全免费、开源，拥有庞大的科学计算库生态（NumPy, Pandas, Scikit-learn）。 | 商业软件，需要昂贵的授权费用。 | | **语法与易用性** | 语法直观，与Python其他库无缝集成，适合将优化模块嵌入更大的数据分析或Web应用。 | 语法紧凑，矩阵操作方便，特别适合快速原型验证和教学演示。 | | **可视化** | 依赖Matplotlib、Seaborn等库，定制化能力强，但需要额外代码。 | 内置强大的绘图功能，能轻松绘制可行域、迭代过程等。 | | **求解器支持** | 支持CBC、GLPK等开源求解器，也可接入Gurobi、CPLEX等商业求解器。 | 内置多种算法，与商业求解器（如Gurobi）集成良好，但可能需额外授权。 | | **学习与社区** | 学习资源丰富（博客、Stack Overflow、GitHub），社区活跃，适合长期技术发展。 | 官方文档详尽，但在开源社区和新兴技术融合上相对较慢。 | 对于学生、研究人员和希望将优化方案产品化的开发者来说，**Python + PuLP的组合因其零成本、高灵活性和强大的生态，已成为当前更主流和更具前景的选择**。 ## 7. 举一反三：整数规划的其他经典应用场景 掌握了护士排班这个案例，你就拥有了解决一大类离散优化问题的钥匙。整数规划的应用几乎无处不在： * **生产计划与调度**：决定不同产品在各机器上的生产数量与顺序，最小化完成时间或最大化设备利用率。变量可以是生产批量（整数）。 * **车辆路径问题**：为车队规划配送路线，每个客户被服务一次，目标是最小化总行驶距离或成本。0-1变量可以表示“车辆k是否从客户i行驶到客户j”。 * **投资组合优化（带整数约束）**：在预算限制下选择投资项目，每个项目可能需要最低投资额或不可分割，使用整数变量表示是否投资某个项目。 * **设施选址**：决定在哪些潜在位置建设仓库或服务中心，以最小化建设成本和运输成本之和。0-1变量表示是否在某个地点建厂。 * **拼图与排程**：如学校的课程表编排、体育联赛的赛程安排等。 这些问题的建模思路是相通的：**定义决策变量 -> 用线性等式/不等式表达业务限制 -> 设置线性目标函数**。区别主要在于变量和约束的具体形式。 通过本文对护士排班问题的完整剖析，你应该已经体会到，将复杂的现实问题抽象为清晰的数学模型，并用像PuLP这样的工具求解，并非遥不可及。关键在于大胆定义变量，耐心梳理约束。下次当你遇到需要做出最优离散决策的场景时，不妨先问问自己：“这个问题，能不能用一个整数规划模型来描述？” 然后，打开Python，开始你的建模之旅。