分配问题求解器

什么是分配问题？

分配问题是一个基本的组合优化问题：给定n个代理、n个任务和成本矩阵C，找到最小化总成本的一对一分配。出现在人力调度、车间分配和车辆路径中。

匈牙利算法（Kuhn-Munkres方法，1955）在O(n³)时间内求解。通过行列减法迭代缩减成本矩阵，然后在二分图中通过增广路径找到最优分配。

对于矩形矩阵，添加零成本的虚拟行或列使其成为方阵。未分配的代理或任务单独报告。

Formula: 最小化 Σ C[i][σ(i)] 对所有 i 约束条件: σ 为一个置换（一对一映射） 匈牙利算法步骤: 1. 减去各行最小值 2. 减去各列最小值 3. 用最少直线覆盖所有零 4. 调整矩阵，重复直至最优

计算示例

成本矩阵：[[9,2,7],[6,4,3],[5,8,1]]。行归约 → [[7,0,5],[3,1,0],[4,7,0]]。列归约 → [[4,0,5],[0,1,0],[1,7,0]]。用零元素为每个代理分配一项任务：代理 1→任务 2（成本 2），代理 2→任务 1（成本 6），代理 3→任务 3（成本 1）。总成本 = 9——低于看似诱人的代理 2→任务 3、代理 3→任务 1 组合（10）。

何时使用此计算器

• 生产主管将工人指派到机台，以最小化总加工时间或成本
• 项目经理根据技能匹配度和工作量估算将团队成员分配到任务
• 物流协调员将配送车辆指派到路线，以最小化总行驶距离
• 高校管理员为课程安排考场，以最小化冲突或步行距离

常见错误

• 成本输入不一致——成本矩阵中的所有数值必须使用同一单位（金额、小时、距离）；混用单位会产生毫无意义的指派结果
• 忘记在最小化和最大化模式之间切换——若按利润或偏好指派（越高越好），应选最大化；若按成本或时间（越低越好），应选最小化
• 将指派模型用于每个主体可承担多项任务的问题——匈牙利算法将每个主体恰好指派给一项任务；若主体可处理多项任务，应使用其他模型
• 未处理不可行的配对——若某些主体-任务组合不可能成立，应将其成本设为极大的数，而不是留为零

如何解读结果

• 总成本代表全局最优——任何其他一对一指派都无法达到更低（最大化时为更高）的总值
• 若某些行或列显示为未指派，说明主体多于任务（或相反）——这些主体/任务保持空闲
• 将最优总值与朴素指派（例如第 1 行对第 1 列）对比，可以看出算法带来了多少改进

相关标准与参考文献

• Kuhn, H. W. (1955), 'The Hungarian Method for the Assignment Problem', Naval Research Logistics Quarterly — 该算法的原始论文
• Munkres, J. (1957), 'Algorithms for the Assignment and Transportation Problems', Journal of the SIAM — 确立多项式时间执行的改进研究
• Burkard, Dell'Amico & Martello (2009), Assignment Problems (SIAM) — 指派模型与算法的全面现代参考书

常见问题

分配问题能处理最大化吗？

可以。将所有成本取负或从矩阵最大值中减去，然后求解最小化问题。最优分配相同，仅目标函数符号改变。

工人和任务数量不等怎么办？

算法用零成本虚拟行或列填充较小维度。求解后，虚拟条目的分配表示未分配的工人或任务。

指派问题能处理工人技能或可用性等现实约束吗？

基本模型无法直接处理。但可以将不可行的指派的成本设为一个极大的数（例如 999999），从而有效阻止算法选择它们。对于复杂约束，可考虑使用整数线性规划求解器。