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

编号 zgly0000285032

文献类型 期刊论文

文献题名 一类最优指派问题的动态规划算法

作者 王吉波  王明坤 

作者单位 沈阳师范大学数学系  辽宁省林业学校 

母体文献 沈阳师范学院学报: 自然科学版 

年卷期 2002,20(4)

页码 266-270

年份 2002 

分类号 O221.3 

关键词 最优指派问题  动态规划  变量  允许决策集合 

文摘内容 考虑一类较一般的最优指派问题: 欲把m项工作指派n个人去完成(m≥n), 要求每项工作只能由一个人来做, 第i个人可以同时做bi项工作, 其中bi是待求未知数, 满足di≤bi≤ei(ei,di为第i个人所无原则工作数的上下限)及∑i=1＾n bi=m为已知常数(i=1,2,…, n), 第i个人做第j项工作所用的时间为Cij≥0(i=1,2,…, n; j=1,2,…,m), 本文给出了求解上述最优指派问题(使总耗用时间最小)的动态规划算法。