列生成算法在人员排班问题中的应用示例 题目描述：某医院需要为护士制定一周的排班计划。每天分为早、中、晚三个班次，每个班次对护士人数有不同需求。每位护士每周工作5天，连续工作天数不超过3天。目标是满足每天各班次需求的前提下，使总雇佣护士人数最少。这是一个大规模线性规划问题，直接求解困难，适合使用列生成算法。 解题过程： 问题建模 主问题（Restricted Master Problem, RMP）：最小化护士总数，约束是每天各班次需求得到满足 决策变量：λ_ k 表示是否采用第k种排班模式（1采用，0不采用） 约束条件：Σ(a_ {ijk}·λ_ k) ≥ d_ {ij}（第i天第j班次） 其中a_ {ijk}表示排班模式k在第i天第j班次是否安排护士 初始可行解生成 生成简单排班模式：如只上早班、只上中班、只上晚班的模式 每种模式包含合法排班（工作5天，连续≤3天） 建立初始RMP，仅包含少量简单排班模式 列生成迭代过程 步骤1：求解当前RMP的线性松弛 忽略λ_ k的整数约束，求解线性规划 得到最优解λ* 和对偶变量π_ {ij}（每个班次需求约束的影子价格） 步骤2：定价子问题（生成新列） 目标：寻找检验数c̄_ k = 1 - ΣΣ(a_ {ijk}·π_ {ij})最小的排班模式 等价于寻找ΣΣ(a_ {ijk}·π_ {ij})最大的合法排班 子问题建模为整数规划： 决策变量：x_ {ij}表示第i天第j班次是否上班 目标函数：max ΣΣ(π_ {ij}·x_ {ij}) 约束：Σx_ {ij} = 5（总工作天数），连续工作≤3天 步骤3：子问题求解 使用动态规划或专用算法求解 状态定义：dp[ i][ d][ s ]表示前i天，当前连续工作d天，总工作s天的最大收益 状态转移考虑每天选择上某个班次或休息 记录最优解对应的排班模式 步骤4：收敛判断 如果最小检验数c̄_ k ≥ 0（对偶可行），当前解是最优解 如果c̄_ k < 0，将对应排班模式加入RMP，返回步骤1 整数解获取 列生成收敛后，得到线性松弛最优解 对最终RMP添加整数约束，用分支定界法求解整数规划 得到实际排班方案，确定具体需要多少护士 算法特点 避免枚举所有可能的排班模式（组合爆炸） 通过子问题动态生成有价值的列 特别适合这种模式选择型的大规模规划问题 这个应用展示了列生成算法如何有效处理组合爆炸问题，通过主问题与子问题的交互，逐步逼近最优解。