一类最优指派问题的动态规划解法

Dynamic Programming Method of A Sort of Optimal Assignment Problem

考虑一类指派问题 :欲把 m项工作指派 n个人去完成 ( m≥ n) ,要求每项工作只能由一个人来做 ,第 i个人可以同时做 bi 项工作 ,其中 bi( bi≥ 1)是待求的未知数 ,i=1,2 ,… ,n,满足 ni=1bi =m,假定已知第 i人做第 j项工作所用的时间 cij≥ 0 ,i=1,2 ,… ,n;j=1,2 ,… ,m。文中给出了求解上述问题最优指派 (即使总耗用时间最小 )的动态规划解法。

We give a dynamic programming method of the followring assignment problem. There are persons (n) who are to be assigned to do jobs (m). Each job can only be done by one person, and the ith person can do bi job. where bi is an unknown number to be calcalated i=1,2,…,n n i=1 =m, and m≥n, Now. the time of ith person's doing jth job is known (i=1,2,…,n;j=1,2,…,m).How do we assign the persons to do the jobs in order to gain the minimun time?