任务分配问题

举例

有一些员工要完成一些任务。各个员工完成不同任务所花费的时间都不同。每个员工只分配一项任务。每项任务只被分配给一个员工。怎样分配员工与任务以使所花费的时间最少？
婚配问题：有一些男人和一些女人，各位男人如果和某位女人结婚则其婚姻稳定程度具有不同的稳定数值。如何匹配可以使得所有配对的稳定值总和最大？也称婚姻匹配问题。

算法

匈牙利算法是众多用于解决线性任务分配问题的算法之一，它可以在多项式时间内解决问题。
分配问题是运输问题的特例，运输问题是最少成本流量问题的特例，而它们都是线性规划的特例。因此，单纯形法可以作为解决这些问题的通法。然而，针对每种特殊情形设计的专门算法可以提高解决问题的效率。如果问题的成本函数包含二次不等式，则称之为二次分配问题。
任务分配问题一般可以在多项式时间内转化成最大流量问题（Maximum Flow Problem）。