指派问题新解法——目标值子矩阵法.pdf

浙江大学学报理学版

第卷第期://..../ ..
年月.
:./..—...
指派问题新解法目标值子矩阵法
赵洪刚,杨竹君,孟庆华。,高金贵
.北华大学,吉林吉林;.辽源职业技术学院,吉林辽源;.天津体育学院天津
摘要:针对一整数规划中的传统指派问题,由工程实践问题提出了一种全新的解法——
个变量的传统指派问题,一般只需次运算即可找到最优解,简单易懂,与全杖解法和其他隐枚解法相比,极大地
,将使编程简化,计算次数减少,运算速度大为提高.
关键词:传统指派问题; 目标值子矩阵法;计算量
中图分类号: 文献标志码: 文章编号:——
—, —, —,—.,,
,;.,,,;
.,,
.
,,:一
. 一
.
,
. ,
. ,
, ,
.
: ;;
运筹学诞生余年来,逐渐得到完善和发展,
解决了很多实际问题,在国民经济中起到了越来越目标值子矩阵法的算法

题的一个分支,
枚解法考虑问题全面,但计算量大,需次运算,当
一∑∑,
变量个数较大,例如一,即使采用每秒几百万次—,
的计算机也要花几万年才能算出来,没有实际意义, 其中,为目标函数;为维—系数方矩阵,每一
因此出现了很多隐枚解法,如匈牙利算法,拍卖算法行、每一列中有且只有一个元素为,其余均为;
等等,但求解比较复杂. 为维变量方阵.
在工程实践中受到将压实草捆装车摆放方案的求目标和最小的目标值子矩阵算法:
启发,对传统指派问题提出了一种全新的解法——当对应于系数矩阵中取的元素位置下
目标值子矩阵法,对于个变量,一般只需次运算局, 变量矩阵中均为该行的最小元素时,其目标
即可得到理想值,比其他隐枚解法运算量更少,而且函数值最小,
简单易懂,运算简捷. 情况的概率很小.
收稿日期:——.
基金项目:北华大学博士启动基金.
作者简介:赵洪刚,男,博士,副教授,主要研究方向为机械设计及理论,机械制造和工程图学,:。。。
. 。. .
浙江大学学报理学版第卷
如果对应于系数矩阵中取的元素位置,变作,每人做各项工作所消耗的时间如表所示,问指派
量矩阵中不可能每一行都取最小元素,按下述步哪个人去完成哪项工作,可使总的消耗时间为最小
骤运算: 表每人做各项作所消耗时间表
任取变量矩阵某一行中的最小元素,为该行
元素目标值的最优解但不一定是系统目标函数的
最优解,应该是系统目标函数满意解中的一个元
素,记作划去所在的行和列,取剩下的子矩甲
乙
阵中某一行的最小元素,记作。.以此类推,直到最
丙

丁
个满意解,此为一次运算.
解构建系统标函数
第二次运算取变量矩阵中含以外的任一行,
做与上面相同运算,又可以得到系统的第二个满意解. 一∑∑,
一
相同地,对于行做次运算,共得到系统的
个满意解,系统的最优解即应该是这个满意解当