OR-Tools指派问题中如何添加仅使用指定数量任务（4选2）的约束？

看起来你现在的问题出在约束定义搞反啦！你写的第二个约束是让每个工人都分配2个任务，但前面又要求每个工人只能分配1个任务，这两个约束直接矛盾，solver自然找不到可行解了～

你真正要实现的是「总共只使用2个任务，所有工人都分配到这2个任务中的某一个」，对吧？那我们需要调整约束逻辑：

修正后的完整代码 #

from ortools.sat.python import cp_model

costs = [
    [90, 80, 75, 70],
    [35, 85, 55, 65],
    [125, 95, 90, 95],
    [45, 110, 95, 115],
    [50, 100, 90, 100],
]

num_workers = len(costs)
num_tasks = len(costs[0])
selected_tasks_count = 2  # 指定要使用的任务数量

# 初始化模型
model = cp_model.CpModel()

# 定义变量：x[i][j] 表示工人i是否分配到任务j
x = []
for i in range(num_workers):
    t = []
    for j in range(num_tasks):
        t.append(model.NewBoolVar(f'x[{i},{j}]'))
    x.append(t)

# 定义任务是否被使用的变量：y[j] 表示任务j是否被选中
y = [model.NewBoolVar(f'y[{j}]') for j in range(num_tasks)]

# 约束1：每个工人恰好分配到1个任务
for worker in range(num_workers):
    model.AddExactlyOne(x[worker][task] for task in range(num_tasks))

# 约束2：任务j被使用的前提是至少有一个工人分配到它
# 同时，如果任务j没被选中，就不能有工人分配到它
for task in range(num_tasks):
    # sum(x[i][task]) 是分配到任务j的工人数量，这个值要么是0（y[j]=0），要么>=1（y[j]=1）
    model.Add(sum(x[i][task] for i in range(num_workers)) <= num_workers * y[task])
    model.Add(sum(x[i][task] for i in range(num_workers)) >= y[task])

# 约束3：恰好选中selected_tasks_count个任务
model.Add(sum(y) == selected_tasks_count)

# 目标函数：最小化总分配成本
objective_terms = []
for i in range(num_workers):
    for j in range(num_tasks):
        objective_terms.append(costs[i][j] * x[i][j])
model.Minimize(sum(objective_terms))

# 求解
solver = cp_model.CpSolver()
status = solver.Solve(model)

# 输出结果
if status == cp_model.OPTIMAL or status == cp_model.FEASIBLE:
    print(f'总成本 = {solver.ObjectiveValue()}')
    print()
    for i in range(num_workers):
        for j in range(num_tasks):
            if solver.BooleanValue(x[i][j]):
                print(f'工人 {i} 分配到任务 {j} 成本 = {costs[i][j]}')
else:
    print('未找到可行解。')

代码说明 #

1. 新增了y[j]变量来标记每个任务是否被使用，这样我们就能直接约束被选中的任务总数为2。
2. 修正了之前矛盾的约束：去掉了每个工人分配2个任务的错误约束，换成了任务使用状态的关联约束。
3. 现在solver会找到符合你预期的最优解——选中成本最低的两个任务，把所有工人分配到这两个任务上。

运行这段代码后，你会得到类似你预期的最优分配结果，总成本也会是最小的。

备注：内容来源于stack exchange，提问作者Syknetov 22