一类最优指派问题的动态规划模型

DYNAMIC PROGRAMMING MODEL OF A SORT OF OPTIMAL ASSIGNMENT PROBLEM

考虑一类指派问题：欲指派m个人去做n项工作(m≥n)，要求每个人只做一项工作，第j项工作可以由b_j个人共同去做，其中，b_j(b_j≥1)是待求的未知数，j=1,2,…,n,满足．假定已知第i人做第j项工作的效益为c_ij≥0,i=1,2,…m;j=1,2,…,n.本文建立了求解上述问题最优指派（即使总的效益最大)的动态规划模型．

We establish a dynamic programming model of the following assignment problem.There are m persons who are to be assigned to do n pieces of jobs.Each person only does one piece of job,and the jth job can be done by b_j persons,where,b_j is an unknown number to be calculated,j=1,2.…,n.∑b_j=m,and m≥n.Now the benefit of ith person's doing jth job is known,i=1,2,…,m, j=1,2,…n.How do we assign the persons to do the jobs in order to gain the maximum benefit？