文摘
|
本文将2类方阵指派问题--极大极小和总体极小指派问题--的矩阵作业解法推广到非方阵情形,即求解任务与人员数目不等的指派问题,且维持矩阵作业法的效率.假定m>n,则按本义行优先选取算法求解m×n非方阵指派问题的最大逻辑运算量为O(mn~2),其效率通常与执行一轮覆盖的矩阵作业法相当. |
其他语种文摘
|
The operations on matrix for both minimax and global-minimum assignment problems of square matrix are applied to those of nonsquare matrix,namely,in the same efficiency with the operations on matrix,both the minimax and global-minimum assignment problems where number of people is unequal to number of tasks are solved.Supposed m>n,the quantity of logical operations to solve the assignment problem of m×n nonsquare matrix with the selection algorithm of precedence rows in this paper is not bigger than O(mn~2).The efficiency of selection algorithm of precedence rows is usually comparable to that of operations on matrix in one covering circle. |
来源
|
信息与控制
,2009,38(6):641-645,652 【核心库】
|
关键词
|
极大极小指派问题
;
总体极小指派问题
;
混合整数线性规划
;
矩阵作业法
;
行优先选取算法
|
地址
|
中国科学院沈阳自动化研究所, 机器人学国家重点实验室, 辽宁, 沈阳, 110016
|
语种
|
中文 |
文献类型
|
研究性论文 |
ISSN
|
1002-0411 |
学科
|
自动化技术、计算机技术 |
基金
|
国家863计划
|
文献收藏号
|
CSCD:3797070
|
|
1.
Yang L Y. Modeling and solution for assignment problem.
International Journal of Mathematical Models and Methods in Applied Sciences,2008,2(2):205-212
|
被引
2
次
|
|
|
|
2.
杨丽英. 多目标追逐问题的一种混合整数线性规划解.
机械工程学报,2008,44(10):51-59
|
被引
1
次
|
|
|
|
3.
Kuhn H W. The hungarian method for the assignment problem.
NAVAL RESEARCH LOGISTICS,1955,52(J):7-21
|
被引
1
次
|
|
|
|
4.
陈宝林.
最优化理论与算法(2版),2005
|
被引
3
次
|
|
|
|
5.
Nie Y Y. An isometric surface method for integer linear programming.
International Journal of Computer Mathematics,2003,80(7):835-844
|
被引
3
次
|
|
|
|
6.
聂义勇. 良性隐式枚举与近隐式枚举.
信息与控制,2005,34(3):296-302
|
被引
1
次
|
|
|