关于“一类最优指派问题的动态规划模型”的注记

Comment on ″Dynamic Programming Model of a Sort of Optimal Assignment Problem″

考虑一类较一般的最优指派问题 :欲指派 m个人做 n项工作 (m≥n) ,要求每个人只做一项工作 ,第j项工作可以由 bj个人共同去做 ,其中 bj是待求未知数 ,满足 dj≤ bj≤ ej(即 ej,dj为第 j项工作所需人数的上下限 )及 ∑nj=1bj=m(即每个人都有工作 ) ,dj,ej为已知常数 ,j =1 ,… ,n.第 i人做第 j项工作的效益为 cij≥ 0 ,i =1 ,… ,m;j =1 ,… ,n.本文建立求解上述最优指派问题 (使总的效益最大 )的动态规划模型 ,并将文 [1]作为本文的特例 .

This paper presents a sort of dynamic programming model for the following generalized assignment problem, and gives its algorithm. In the problem, there are m persons who are to be assigned to do n jobs, and the number of the persons who are assigned to do the j th job is b\-j , where b\-j is an unknown positive integer number to be calculated such that d\-jb\-je\-j, d\-j and e\-j are known positive integer number (j=1,2,…,n) such that ∑nj=1b\-j=m and m≥n. Suppose the profit of i th person′s doing j th job is c ij 0(i=1,…,m; j=1,2,…,n). This paper establishes the dynamic programming model for the above problem and it is the generalization of reference \.