基于Python PuLP的多向换班线性规划：限制最大参与人数

要限制换班为最多三方参与（即形成的环大小不超过3），可以通过添加线性规划约束实现，以下是两种简洁的实现方式：

方法1：限制换班总次数 #

换班的总次数等于参与换班的人数（每个环的换班次数等于环内人数），因此直接约束总换班次数不超过3即可避免四方环：

import pulp

participants = ['Alice', 'Bob', 'Charlie', 'David']
weights = {'Alice': 1, 'Bob': 3, 'Charlie': 2, 'David': 1}
allowed_swaps = [('Alice', 'Bob'), ('Bob', 'Alice'), ('Bob', 'Charlie'), ('Charlie', 'David'),
                 ('Charlie', 'Alice'), ('Charlie', 'Bob'), ('David', 'Alice')]

swaps = pulp.LpVariable.dicts('Swap', allowed_swaps, cat='Binary')
model = pulp.LpProblem("DutySwap", pulp.LpMaximize)

# 目标函数
model += pulp.lpSum((1000 + weights[p1] + weights[p2]) * swaps[(p1, p2)] for (p1, p2) in allowed_swaps)

# 原有基础约束
for p in participants:
    model += pulp.lpSum(swaps[(p1, p2)] for (p1, p2) in allowed_swaps if p1 == p) <= 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))

# 新增约束：最多3次换班（对应最多3人参与的环）
model += pulp.lpSum(swaps[(p1, p2)] for (p1, p2) in allowed_swaps) <= 3

status = model.solve()
for (p1, p2) in allowed_swaps:
    if pulp.value(swaps[(p1, p2)]) == 1:
        print(f"{p1}'s duty goes to {p2}")

方法2：明确限制参与人数 #

通过新增二进制变量标记参与者是否参与换班，直接约束参与人数上限：

import pulp

participants = ['Alice', 'Bob', 'Charlie', 'David']
weights = {'Alice': 1, 'Bob': 3, 'Charlie': 2, 'David': 1}
allowed_swaps = [('Alice', 'Bob'), ('Bob', 'Alice'), ('Bob', 'Charlie'), ('Charlie', 'David'),
                 ('Charlie', 'Alice'), ('Charlie', 'Bob'), ('David', 'Alice')]

swaps = pulp.LpVariable.dicts('Swap', allowed_swaps, cat='Binary')
# 新增变量：标记参与者是否参与换班
in_swap = pulp.LpVariable.dicts('InSwap', participants, cat='Binary')

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

# 目标函数
model += pulp.lpSum((1000 + weights[p1] + weights[p2]) * swaps[(p1, p2)] for (p1, p2) in allowed_swaps)

# 原有基础约束
for p in participants:
    model += pulp.lpSum(swaps[(p1, p2)] for (p1, p2) in allowed_swaps if p1 == p) <= 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))
    # 关联参与状态与换班行为：参与换班则发起1次换班，否则0次
    model += pulp.lpSum(swaps[(p1, p2)] for (p1, p2) in allowed_swaps if p1 == p) == in_swap[p]

# 新增约束：最多3人参与换班
model += pulp.lpSum(in_swap[p] for p in participants) <= 3

status = model.solve()
for (p1, p2) in allowed_swaps:
    if pulp.value(swaps[(p1, p2)]) == 1:
        print(f"{p1}'s duty goes to {p2}")

效果说明 #

两种方法都会让模型优先选择权重总和最高的三方换班环（即Alice→Bob→Charlie→Alice），因为该方案的目标函数得分远高于其他小环组合，同时避免了四方环的生成。如果需要强制恰好3人参与，可将约束中的<=3改为==3（需确保存在可行的三方环）。

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