Assignment Problem

定义 Definition

“Assignment problem（指派问题/分配问题）”是运筹学与组合优化中的经典问题：在若干“任务”和若干“执行者”（如工人、机器、岗位、项目）之间进行一一对应的分配，使总成本最小或总收益最大。通常用“成本矩阵”表示，每个分配都有相应代价。它是“二分图匹配”的一种常见建模形式。

发音 Pronunciation (IPA)

/əˈsaɪnmənt ˈprɑːbləm/

例句 Examples

The assignment problem can be solved efficiently with the Hungarian algorithm.
指派问题可以用匈牙利算法高效求解。

Given a cost matrix for five technicians and five repair jobs, we formulated an assignment problem to minimize total travel time while ensuring each job is handled by exactly one technician.
在给定五名技术员与五个维修任务的成本矩阵后，我们把它建模为一个指派问题，以在保证每个任务恰好由一名技术员完成的前提下最小化总出行时间。

词源 Etymology

“assignment”源自拉丁语 assignare（分派、指派），由 *ad-*（向、到）+ signare（标记、指定）构成；“problem”来自希腊语 problema（摆在面前需要解决的事）。因此“assignment problem”字面即“关于指派/分配的待解问题”，后来在运筹学中成为固定术语，特指“一对一最优分配”这一类模型。

相关词 Related Words

• Optimization
• Matching
• Bipartite Graph
• Hungarian Algorithm
• Linear Programming
• Cost Matrix
• Combinatorial Optimization
• Transportation Problem

文学与著作中的用例 Literary Works

• Harold W. Kuhn, “The Hungarian Method for the Assignment Problem” —— 提出并推广解决指派问题的匈牙利方法的经典论文。
• Frederick S. Hillier & Gerald J. Lieberman, Introduction to Operations Research —— 运筹学教材中常用“assignment problem”作为线性规划与网络流模型的代表案例。
• Thomas H. Cormen et al., Introduction to Algorithms —— 在算法设计语境下讨论匹配与相关优化问题时常提及指派问题及其变体。
• Christos H. Papadimitriou & Kenneth Steiglitz, Combinatorial Optimization: Algorithms and Complexity —— 将指派问题作为组合优化的基础问题之一进行系统介绍。