基于PuLP的多步换班LP优化：添加步数限制变量需求

架构老林

2026-6-26

换班优化线性规划问题：限制换班环长度需求

我用Python PuLP把换班优化问题建模成线性规划（LP）求解，研究多时仍未找到解决方案。现在需要引入变量X，用来限制多点换班的闭环步数（即换班形成的参与人数）：每人始终保留一个班次，转出班次必须转入一个班次。

当前代码

import pulp

# 参与人员列表
participants = ['Amy', 'Blake', 'Claire', 'Drew', 'Emma', 'Flynn', 'Gabi', 'Hana', 'Izzy', 'Jill']

# 允许的换班关系
allowed_swaps = [('Amy', 'Blake'), ('Blake', 'Claire'), ('Claire', 'Drew'), ('Drew', 'Emma'),
                 ('Emma', 'Flynn'), ('Flynn', 'Gabi'), ('Gabi', 'Hana'), ('Hana', 'Izzy'),
                 ('Izzy', 'Jill'), ('Jill', 'Amy'),
                 # 一对一换班
                 ('Blake', 'Amy'), ('Emma', 'Drew'),
                 # 三点换班
                 ('Gabi', 'Emma'),
                 # 四点换班
                 ('Flynn', 'Claire'), ('Jill', 'Gabi')]

# 定义换班变量：二进制，1表示执行该换班
swaps = pulp.LpVariable.dicts('Swap', allowed_swaps, cat='Binary')

# 创建最大化问题：最大化总换班次数
model = pulp.LpProblem("DutySwap", pulp.LpMaximize)

# 目标函数：总换班次数最大化
model += pulp.lpSum(swaps[(p1, p2)] for (p1, p2) in allowed_swaps)

# 约束条件：
for p in participants:
    # 每人最多转出1次
    model += pulp.lpSum(swaps[(p1, p2)] for (p1, p2) in allowed_swaps if p1 == p) <= 1
    # 每人最多转入1次
    model += pulp.lpSum(swaps[(p1, p2)] for (p1, p2) in allowed_swaps if p2 == p) <= 1
    # 转出次数等于转入次数（0或1）
    model += (pulp.lpSum(swaps[(p1, p2)] for (p1, p2) in allowed_swaps if p1 == p)
              == pulp.lpSum(swaps[(p1, p2)] for (p1, p2) in allowed_swaps if p2 == p))

# 求解并输出结果
status = model.solve()
for (p1, p2) in allowed_swaps:
    if pulp.value(swaps[(p1, p2)]) == 1:
        print(f"{p1}'s duty goes to {p2}")

# 当前输出：
# Amy's duty goes to Blake
# Blake's duty goes to Claire
# Claire's duty goes to Drew
# Drew's duty goes to Emma
# Emma's duty goes to Flynn
# Flynn's duty goes to Gabi
# Gabi's duty goes to Hana
# Hana's duty goes to Izzy
# Izzy's duty goes to Jill
# Jill's duty goes to Amy

需求说明

引入变量X，控制允许的换班闭环最大长度（环中的换班步数，即参与换班的人数）：

当X=1时，仅允许一对一换班（2步闭环，A→B→A），输出示例：

# Amy's duty goes to Blake
# Blake's duty goes to Amy
# Drew's duty goes to Emma
# Emma's duty goes to Drew

当X=2时，允许一对一换班和三点换班（3步闭环，A→B→C→A），输出示例：

# Amy's duty goes to Blake
# Blake's duty goes to Amy

# Emma's duty goes to Flynn
# Flynn's duty goes to Gabi
# Gabi's duty goes to Emma

当X=3时，允许一对一、三点、四点换班（4步闭环，A→B→C→D→A），输出示例：

# Amy's duty goes to Blake
# Blake's duty goes to Amy

# Claire's duty goes to Drew
# Drew's duty goes to Emma
# Emma's duty goes to Flynn
# Flynn's duty goes to Claire

# Gabi's duty goes to Hana
# Hana's duty goes to Izzy
# Izzy's duty goes to Jill
# Jill's duty goes to Gabi

核心规则

目标：最大化总换班次数
基础约束：
- 每人只能转出1次班次
- 每人只能转入1次班次
- 每人转出次数等于转入次数（0或1，即要么不参与换班，要么参与一个闭环）
换班闭环定义：
- 一对一换班：A→B且B→A（2步闭环）
- 三点换班：A→B、B→C、C→A（3步闭环）
- 四点换班：A→B、B→C、C→D、D→A（4步闭环）

换班关系图如下：
Allowed swaps between participants

解决方案

要限制换班闭环的长度，需引入环位置跟踪变量，通过约束确保所有形成的闭环长度不超过 X+1（X=1对应2步环，X=2对应3步环，以此类推）。以下是完整实现：

修改后的代码

import pulp

def solve_duty_swap(max_cycle_length_step):
    # max_cycle_length_step对应需求中的X：X=1→最大环长2，X=2→最大环长3，X=3→最大环长4
    max_cycle_length = max_cycle_length_step + 1

    participants = ['Amy', 'Blake', 'Claire', 'Drew', 'Emma', 'Flynn', 'Gabi', 'Hana', 'Izzy', 'Jill']
    allowed_swaps = [('Amy', 'Blake'), ('Blake', 'Claire'), ('Claire', 'Drew'), ('Drew', 'Emma'),
                     ('Emma', 'Flynn'), ('Flynn', 'Gabi'), ('Gabi', 'Hana'), ('Hana', 'Izzy'),
                     ('Izzy', 'Jill'), ('Jill', 'Amy'),
                     ('Blake', 'Amy'), ('Emma', 'Drew'),
                     ('Gabi', 'Emma'),
                     ('Flynn', 'Claire'), ('Jill', 'Gabi')]

    # 换班变量：二进制
    swaps = pulp.LpVariable.dicts('Swap', allowed_swaps, cat='Binary')
    # 位置变量：整数，跟踪环内位置
    pos = pulp.LpVariable.dicts('Position', participants, lowBound=0, upBound=len(participants), cat='Integer')
    M = len(participants)  # 大M值，取参与者总数

    model = pulp.LpProblem("DutySwap", pulp.LpMaximize)

    # 目标函数：最大化换班次数
    model += pulp.lpSum(swaps[(p1, p2)] for (p1, p2) in allowed_swaps)

    # 基础约束
    for p in participants:
        # 每人最多转出1次
        model += pulp.lpSum(swaps[(p1, p2)] for (p1, p2) in allowed_swaps if p1 == p) <= 1
        # 每人最多转入1次
        model += pulp.lpSum(swaps[(p1, p2)] for (p1, p2) in allowed_swaps if p2 == p) <= 1
        # 转出次数等于转入次数
        model += (pulp.lpSum(swaps[(p1, p2)] for (p1, p2) in allowed_swaps if p1 == p)
                  == pulp.lpSum(swaps[(p1, p2)] for (p1, p2) in allowed_swaps if p2 == p))
        # 位置变量约束：不参与换班则pos=0，参与则pos≥1且≤max_cycle_length
        participate = pulp.lpSum(swaps[(p1, p2)] for (p1, p2) in allowed_swaps if p1 == p)
        model += pos[p] >= 1 * participate
        model += pos[p] <= max_cycle_length * participate + M*(1 - participate)

    # 环长度约束：如果p1→p2，则pos[p2] = pos[p1]+1（除非p2是环的起点）
    for (p1, p2) in allowed_swaps:
        # 当swaps[(p1,p2)]=1时，pos[p2] ≥ pos[p1]+1 - M*(1-swaps)
        model += pos[p2] >= pos[p1] + 1 - M*(1 - swaps[(p1, p2)])
        # 当swaps[(p1,p2)]=1时，pos[p2] ≤ pos[p1]+1 + M*(1-swaps)
        model += pos[p2] <= pos[p1] + 1 + M*(1 - swaps[(p1, p2)])

    # 求解（关闭日志输出）
    status = model.solve(pulp.PULP_CBC_CMD(msg=0))

    # 输出结果
    print(f"\n=== X={max_cycle_length_step} 时的换班结果 ===")
    for (p1, p2) in allowed_swaps:
        if pulp.value(swaps[(p1, p2)]) == 1:
            print(f"{p1}'s duty goes to {p2}")

# 测试不同X值
solve_duty_swap(1)
solve_duty_swap(2)
solve_duty_swap(3)

代码说明

max_cycle_length_step 就是需求中的变量X，直接控制允许的最大闭环长度（X+1）。
使用pos变量跟踪参与者在闭环中的位置，通过大M法将环的连续性逻辑转化为线性约束，确保换班形成的闭环长度不超过设定值。
保留所有基础约束，同时优先选择能最大化换班次数的闭环组合，适配大规模换班场景。

内容的提问来源于stack exchange，提问作者Oehoe

基于PuLP的多步换班LP优化：添加步数限制变量需求

当前代码 #

需求说明 #

核心规则 #

解决方案 #

修改后的代码 #