任务分配问题
维基百科，自由的百科全书
任务分配问题是在加权二分图中寻找最大（或最小）加权匹配的问题。
目录 |
[编辑] 详述
分为以下几类：
- 线性任务分配问题：P是二元组(a,b)的集合，其中a和b分别是集合A和B中的元素。C是某一函数，并满足特定约束条件，例如：A的每一个元素必须在P中出现一次，或者B的每一个元素必须在P中出现一次，或者以上二者都必须满足。线性任务分配问题的目标就是最大化或者最小化C(a,b)之和。
该问题是线性的因为代价函数C()只取决于特定的二元组(a,b)而与其它的二元组没有任何关系。
- 二次任务分配问题：给定n家工厂和n个库房。每个库房被分配给一家工厂。很显然有n!种不同的分配组合。每家工厂和它的库房间的代价函数被定义为二者间的距离和物流量的乘积。如何分配以使所有的代价总和最小？
这些问题都是组合优化的研究对象。
[编辑] 举例
有一些员工要完成一些任务。各个员工完成不同任务所花费的时间都不同。每个员工只分配一项任务。每项任务只被分配给一个员工。怎样分配员工与任务以使所花费的时间最少？
婚配问题：有一些男人和一些女人，各位男人如果和某位女人结婚则其婚姻稳定程度具有不同的稳定数值。如何匹配可以使得所有配对的稳定值总和最大？也称婚姻匹配问题。
[编辑] 算法
任务分配問題一般可以在多項式時間內轉化成最大流量問題（Maximum Flow Problem）。
