如何使用scipy.optimize.linear_sum_assignment实现工人任务按需分配？

核心问题：用错了工具 #

你使用linear_sum_assignment的操作存在本质错误——这个函数的定位是二分图的一对一最优匹配，它要求每个工人只能分配给一个任务，同时每个任务也只能对应一个工人。但你的需求是多对多分配：单个任务需要多名工人，这完全超出了该函数的适用场景，所以得到的结果自然不符合预期。

正确的解决思路 #

要适配linear_sum_assignment的特性，你需要把原问题转化为一对一匹配问题：将每个任务拆分成和所需工人数相同的虚拟子任务。具体拆分规则：

• j₁需3人 → 拆成j₁-1、j₁-2、j₁-3三个虚拟任务
• j₂需3人 → 拆成j₂-1、j₂-2、j₂-3三个虚拟任务
• j₃需4人 → 拆成j₃-1、j₃-2、j₃-3、j₃-4四个虚拟任务

拆分后总共有10个虚拟任务，刚好和10名工人一一对应，满足linear_sum_assignment的输入要求。

调整后的代码实现 #

import numpy as np
from scipy.optimize import linear_sum_assignment

# 构建拆分后的成本矩阵：10行（工人）×10列（虚拟任务）
# 虚拟任务顺序：j1*3, j2*3, j3*4
M = np.ones((10, 10))

# 工人8：只能做j3的虚拟任务，其他设为高成本99
M[7, :6] = 99  # 前6列是j1、j2的虚拟任务

# 工人9、10：只能做j1的虚拟任务，其他设为高成本99
M[8, 3:] = 99  # 从第4列开始是j2、j3的虚拟任务
M[9, 3:] = 99

row_ind, col_ind = linear_sum_assignment(M)
print("工人索引：", row_ind)
print("虚拟任务索引：", col_ind)

# 把虚拟任务映射回原任务
task_mapping = []
for idx in col_ind:
    if idx < 3:
        task_mapping.append("j1")
    elif idx < 6:
        task_mapping.append("j2")
    else:
        task_mapping.append("j3")

print("最终分配结果：")
for worker, task in enumerate(task_mapping, 1):
    print(f"工人{worker} → {task}")

结果说明 #

运行这段代码后，会得到每个工人对应的原任务分配结果，既满足j₁分配3人、j₂分配3人、j₃分配4人的数量要求，也符合工人的技能限制。

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