（计算数学专业论文）一类非平衡指派问题的求解方法及其应用研究.pdf

武汉理 二大学硕士学位论文 捅要 指派问题( 又称“分配问题”) 是“运筹学”中线性规划的一类经典问题。在生 活实际和生产安排中，基于生产管理的具体要求而产生的各种非平衡的指派问题是目 前研究的重点。 本文针对实际应用中一类平衡指派问题展开研究。建立了平衡指派问题的数学模 型，给出了问题的求解方法。而这些求解方法中运用最为广泛的是“匈牙利算法”。 匈牙利算法是解决指派问题的一种非常简单有效的方法。文中对匈牙利算法的起源、 运用、求解模型及其原理作了介绍。对于非平衡指派问题，建立了非平衡指派问题的 数学模型后，文中介绍了将其转化为平衡指派问题的方法。非平衡指派问题有两种情 形：一种是人员数少于任务数，另一种是人员数多于任务数。在实际的指派工作中， 常会遇到某个人有没有资格去承担某项工作的问题。因此，本文建立了人员有承担量 约束的指派数学模型。基于“人少任务多 最小分派问题的解法探析，指出了“加边 补零法 的局限性，改进得到“加边补最小值 法，并给出优于其他算法时的情形。 在此本文提出了一种新的方法，即“加边排序补小值法 ，利用该算法和匈牙利 算法给出人员有能力限制且“人员数少于任务数”的多目标指派问题的求解。这就将 有资格限制的指派问题化为传统的指派问题来求解。而对于人员数多于任务数的指派 问题文中给出的求解方法是类匈牙利算法。 本文还从综合评价和改进的角度，对“承担任务有资格限制”这一点，补充条件 加强的非平衡指派问题的数学模型。建立有资格约束的数学模型，给出什么才算作第 f 个人员“有资格”承担第，项任务；并讲述有资格约束的数学模型有解的充要条件。 最后部分，论文给出了应用“加边排序补小值法求解具体的数值例子，来说明 这种新的方法的实用性和有效性。并指出论文研究的缺陷和有待改进的地方。 关键字：指派问题，匈牙利算法，资格限制，多目标指派，加边排序补小值 武汉理工大学硕士学位论文 a b s t r a c t a s s i g n m e n tp r o b l e mi s ac l a s s i cp r o b l e mi no p e r a t i o n a lr e s e a r c ha b o u tl i n e a r p r o g r a m m i n g i np r a c t i c a ll i f ea n dp r o d u c t i o na r r a n g e m e n t ，t h ea s s i g n m e n tp r o b l e mo f d i f f e r e n tk i n d so fu n b a l a n c e ds t y l e s ，w h i c hc a m ei n t ob e i n go nt h eb a s i so fp r o d u c t i o n m a n a g e m e n t ，i st h ek e y s t o n ef o rt h ep r e s e n tr e s e a r c h t h et h e s i sf i r s t l yt a l l ( sa b o u tab a l a n c ea s s i g n m e n tp r o b l e mi np r a c t i c a la p p l i c a t i o n b u i l dt h em a t h e m a t i c sm o d e lo ft h eb a l a n c ea s s i g n m e n tp r o b l e m ，a n dt h e no f f e rs o l u t i o n s t ot h ep r o b l e m s a m o n gt h e s es o l u t i o n s ，h u n g a r i a na l g o r i t h mi sw i d e l yu s e d h u n g a r i a n a l g o r i t h mi sav e r ys i m p l eb u te f f i c i e n tw a yt os o l v ea s s i g n m e n tp r o b l e m s t h eo r i g i no f h u n g a r i a na l g o r i t h m , i t sa p p l i c a t i o n ，t h es o l u t i o nm o d e la sw e l la si t sp r i n c i p l ew i l lb e i n t r o d u c e di n t h i sa r t i c l e t ot h eu n b a l a n c e da s s i g n m e n tp r o b l e m ，a f t e r b u i l d i n g i t s m a t h e m a t i c sm o d e l ，t h ea r t i c l ei n t r o d u c e st h em e t h o dt h a tc h a n g e st h eu n b a l a n c e d a s s i g n m e n tp r o b l e mi n t ob a l a n c e da s s i g n m e n tp r o b l e m t h e r ea r et w os i t u a t i o n si nt h e u n b a l a n c e da s s i g n m e n tp r o b l e m ：o n ei st h a tt h en u m b e ro fp e r s o n n e li ss m a l l e rt h a nt h e n u m b e ro fa s s i g n m e n t ；a n o t h e ri so nt h ec o n t r a r y i np r a c t i c a la s s i g n m e n tw o r k ， f r e q u e n t l y ，w ew i l lb ef a c e d 州map r o b l e mw h e t h e rap e r s o nh a st h eq u a l i f i c a t i o nt o u n d e r t a k eat a s k t h e r e f o r e ，t h ea r t i c l eb u i l d sa na s s i g n m e n tm a t h e m a t i c sm o d e l ，w h i c h m e a n st h ep e r s o n n e lw i l lb er e s t r i c t e db yt h ea m o u n to ft a s k a b o u tt h es o l u t i o nt ot h e “p e r s o n n e lm o r et h a na s s i g n m e n t ”a p p o r t i o n m e n tp r o b l e m ，t h ea r t i c l en o to n l yp o i n t so u t t h el o c a l i z a t i o no fa d d i n gr o w sw i t hz e r o e s ，a l s oo f f e r sab e t t e rm e t h o d a d d i n gr o w s w i t hs m a l lv a l u ea n di t sd e t a i l e ds i t u a t i o n s w h a t sm o r e ，t h ea r t i c l ea l s op r e s e n t san e wm e t h o d ，t h a ti s ，a d d i n gr o w sw i t h o r d e r e ds m a l lv a l u e b a s e do nt h i sm e t h o da n dh u n g a r i a na l g o r i t h m ，t h ea r t i c l eo f f e r sa s o l u t i o nt ot h em u l t i o b j e c t i v e sd e c i s i o np r o b l e m p e r s o n n e lw i t l la b i l i t yr e s t r i c t i o na n d p e r s o n n e lf e w e rt h a na s s i g n m e n t t h i sm e a n st h a ta s s i g n m e n tp r o b l e mw i t l lq u a l i f i c a t i o n r e s t r i c t i o nc a nb et r a n s f o r m e di n t ot h et r a d i t i o n a la s s i g n m e n tp r o b l e m o nt h eo t h e rh a n d ， t h ea r t i c l ea d v i s e ss o l v i n gt h e p e r s o n n e lm o r et h a na s s i g n m e n t ”a s s i g n m e n tp r o b l e mw i t h h u n g a r i a na l g o r i t h m c o n s i d e r i n gt h ec o l l i g a t e de v a l u a t i o na n di m p r o v e m e n t ，t h ea r t i c l eg i v e sm o r e c o n d i t i o n sa b o u t a s s i g n m e n tp r o b l e mw i t hq u a l i f i c a t i o nr e s t r i c t i o n a n ds t r e n g t h e n st h e m a t h e m a t i c sm o d e lo ft h eu n b a l a n c e da s s i g n m e n tp r o b l e m f i r s t ，b u i l dt h em a t h e m a t i c s m o d e lo fq u a l i f i c a t i o nr e s t r i c t i o n ，t h e ne x p l a i nw h yap e r s o nh a st h eq u a l i f i c a t i o nt o u n d e r t a k eac e r t a i nt a s k , a n ds t a t et h ef u l lc o n d i t i o n sf o rt h em a t h e m a t i c sm o d e lo f i i q u a l i f i c a t i o nr e s t r i c t i o n 武汉理工大学硕士学位论文 i nt h el a s tp a r t , i no r d e rt o p r o v et h ep r a c t i c a b i l i t ya n dv a l i d i t yo ft h en e w m e t h o d ，t h et h e s i sg i v e st h ee x a m p l eo fn u m e r i c a lv a l u et oe x p l a i nh o wt os o l v e p r o b l e m sw i t h a d d i n gr o w sw i t ho r d e r e ds m a l lv a l u e a tt h es a m et i m e ，t h ea u t h o rp o i n t s o u tt h el i m i t a t i o no ft h et h e s i sa n dt h a tt h e r ei sal o tt ob ei m p r o v e d k e yw o r d s ：a s s i g n m e n tp r o b l e m ；h u n g a r i a na l g o r i t h m ；q u a l i f i c a t i o nr e s t r i c t i o n ； m u l t i o b j e c t i v e sd e c i s i o n ；t h em e t h o do fa d d i n gr o w sw i t ho r d e r e ds m a l l i i i 独创性声明 本人声明，所呈交的论文是本人在导师指导下进行的研究工作及取得的研究 成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人 已经发表或撰写过的研究成果，也不包含为获得武汉理工大学或其它教育机构的 学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已 在论文中作了明确的说明并表示了谢意。 签名：丝呈幺日期：坐堡：壁：! 关于论文使用授权的说明 本人完全了解武汉理工大学有关保留、使用学位论文的规定，即学校有权保 留、送交论文的复印件，允许论文被查阅和借阅；学校可以公布论文的全部或部 分内容，可以采用影印、缩印或其他复制手段保存论文。 ( 保密的论文在解密后应遵守此规定) 签名：车墨鸳乞导师签名： 武汉理工大学硕士学位论文 1 1 背景介绍 1 1 1 指派问题 第一章绪论 在生活实际和生产安排中，特别是在许多管理部门可能经常面临这样的问题：有 若干任务需要完成，又有若干人员能够完成其中的每项任务。由于每个人员的特点与 能力不同，完成各项任务的效益或时间也各不同，又因任务性质的要求和管理的需要 等，每项任务只能由一人完成，则应该如何分配人员去完成所有任务，能使完成各项 任务的总效益最高( 总时间最少) 。这类问题就称之为指派问题或者分配问题 ( a s s i g n m e n tp r o b l e m ) 。 指派问题n i ( 又称“分配问题) 是“运筹学”中线性规划的一类经典问题， 在实际的生产管理中有着广泛的应用。基于指派问题的科学决策运用于诸多领域，如 资源优化、项目选择、军事作战等等。其通常提法是： 拧个人去做m 件工作，且第ia 做第_ 件工作的效率为( 1 f ，1 j m ) ，记 c = ( 气) 。当m = 门时，拟每人做一件工作，且每件工作一人去做，问如何指派最 优? 它的数学模型是：m i n s = 勺 嘞= 1 ，_ ，= l 2 ，m i = i 而= l ，i = 1 2 ，刀 j = 1 = 0 或1 ， ( 1 i 胛，i _ ，聊) ( 1 1 ) ( 1 2 ) ( 1 3 ) 其中，勺 o ( 1 f 疗，1 - m ) 或余工作( 当刀 研) 的两种情形。 1 1 2 指派问题研究的现状 最简单的指派问题是任务数和人员数相等的平衡指派【3 1 。但事实上，我们生活中 遇到的指派模型大部分是人员数和任务数不等的情况，特别是当任务数多于人员数时 存在某些人员承担过多任务，影响工作效率和工作质量。因此可根据人员的工作能力 情况，对承担的任务量应该有一定的限制；另一方面有能力的人员承担过多任务而使 其他人失业时，从社会稳定和国家发展的整体利益出发，每个人员的任务量的差值需 要尽可能小。 在实际问题中，由于具体情况不同，人们会提出新的要求。因而需要增加或修改 问题的约束条件，变动目标函数，或者其他一些对标准形式指派问题模型的改动。这 就出现了各种非标准形式的指派问题。大量的研究工作也围绕着对于这些问题的求解 而展开。 对平衡指派问题的求解，主要采用“匈牙利算法”。此外，一些启发式算法如遗 传算法【2 】【3 1 ，蚁群算法【4 】【5 1 和粒子群算法1 6 1 等也有相关研究用于求解指派问题。 对于非平衡指派问题的研究主要有两个方向。一类，研究问题中人数和任务数具 有各类不同约束限制的情形1 7 1 8 1 。另一类是研究规划模型中含有随机参数或模糊参数 时的情形。本文主要研究第一类。 第一类研究中，关于人数与任务数不等的各种情形及对每人执行任务数有各种限 制的情形有众多研究。这类非平衡指派问题的求解，多是通过对扩展矩阵实施匈牙利 算法，或通过转换为运输问题求解 9 1 。 在第一类研究中另一个研究的热点是瓶颈指派问题( b o t t l e n e c ka s s i g n m e n t p r o b l e m ，b a p ) 。最初是由g r o s s 1 0 1 于1 9 5 9 年提出来，并给了相应解法。瓶颈指派问 题的提法是：一项工作只能一人完成，所有工作均同时开始，应如何分派这刀项任务， 使整个工程尽早完工? 显然，工程完工的时间等于最后完工的那个人所花的时间，问 题的优化目标是使这个虽长时问最短。问题的数学模型与平衡指派问题的模型只有目 标函数不同，如下： m m 舻嚣c 数学模型中其余的变量意义和取值，以及约束条件与平衡指派问题是一样的。瓶 颈指派问题的解法主要有0 g r o s s 算法，化为一般指派问题的方法，动态规划的方法 2 武汉理工大学硕士学位论文 等。此外，人们还深入探讨了聊维瓶颈指派问题的解法，提出了朋维瓶颈指派问题 动态规划模型求解方法。 关于非平衡指派问题的研究十分广泛，一方面原因是这类模型的实际应用价值很 高，基于现实要求的变化多。另一原因是不同模型所采用的方法各异，即使同一模型 也有不同解法，对应着不同效率的算法。 总而言之，研究非平衡指派问题对于各行各业的管理部门有着重要的理论指导。 1 2 研究内容及论文的组织情况 1 2 1 研究内容 本文主要针对指派问题中的一类问题“人员有承担任务量约束的非平衡指派问 题的求解方法进行研究。利用在各类指派问题中应用非常广泛的“匈牙利算法 ，来 解决条件加强的非平衡指派问题的求解。 文章主要提出了“加边排序补小值”的求解方法，同时给出它的原理及证明及详 细的求解步骤，并用实例说明方法的简便可行。 1 2 2 论文的组织情况 本文共分七章 第一章，绪论。描述指派问题，概述了几类非平衡指派问题及其求解。通过介绍， 说明指派问题的应用和研究意义。 第二章，平衡指派问题的求解。这一章主要是为研究做准备工作。介绍平衡指派 问题，给出它的数学模型，并把相关研究的一些原理详细证明。着重讲述平衡指派问 题的求解方法，即匈牙利算法。这种方法运用非常广泛，针对它求解指派问题的步骤， 指出匈牙利算法存在的缺陷和需改进的地方，并给出实例应用来说明。 第三章，非平衡指派问题的求解。介绍了非平衡指派问题，给出它的数学模型及 相关研究内容的一些原理。对非平衡指派问题的两种情形分别给出求解方法。其中当 人数多于任务数时用类匈牙利法求解；当人数少于任务数时，给出数学模型，结合匈 牙利算法，可用“加边补小值”法求解一类人员有能力限制的多目标指派问题。 第四章，非确定型指派问题求解。根据第二、三两章介绍的求解思路，研究非确 定型指派问题求解。建立数学模型，将问题转换，可用平衡指派问题和传统的运输问 题两种方法求解。 第五章，时间优化的指派问题求解。本章的研究触及到了指派问题研究中的热点 武汉理工大学硕士学位论文 问题：瓶颈指派问题。本章对时间优化的指派问题进行分类，对每种类型建立求解的 数学模型；详细分析每种类型的约束条件，还与平衡指派问题比较指出优劣。 第六章，“加边排序补小值 法。重点介绍提出的新方法：“加边排序补小值”法。 详细介绍“加边排序补小值 法的原理及证明，给出求解步骤；指出该方法的应用， 并用数值例子说明该方法的合理性和可行性，能为决策者提供科学的决策依据。最后 对该方法用于条件加强的非平衡指派问题的求解时，给出一点补充。 第七章，总结与展望。总结了论文研究的工作，并分析了不足，给出了进一步需 要解决的问题。 4 武汉理工大学硕士学位论文 第二章平衡指派问题的求解 2 1 平衡指派问题 2 1 1 平衡指派问题的数学模型 假设有n 项任务需要n 个人员去完成，每个人只能完成一项任务，且每一项任务 也只能有一个人员完成。由于每个人专长不同，各人完成不同任务所创造的效益或所 需要的时间不同，如何指派哪个人去完成哪项任务，使完成 项任务的总效益最高( 总 时间最少) ，称这类问题为平衡指派问题。 为建立指派问题的数学模型，引入o 1 变量矗，令 f1当指派第i 人去完成第j 项任务 i o当不指派第i 人去完成第j 项任务 且设c ：f ，( f ，j = 1 ，2 ，门) 表示指派第i 个人完成第项任务的效率( 时间、成本等) ，则 平衡指派问题的数学模型为： m i n ( 或m a x ) s = c , j x ( 2 1 ) = 1 ( 歹= 1 ，2 ，刀) i = i 姒 窆嘞：1 ( f ：1 ，2 , - - - , n ) j = l = 1 或0 ( f ，_ ，= 1 ，2 ，z ) 其中：r a i n s = 勺吻表示总时间最少( 总成本最少) ( 2 2 ) f = lj = l m a x s = z c ，嘞表示效益最高 f = l = l ( 2 3 ) 为了不重复考虑问题，本论文中的指派问题数学模型均取目标函数要求极小化时 的数学模型( 2 2 ) 。 武汉理工大学硕十学位论文 2 1 2 平衡指派问题求解原理的证明 平衡指派问题是一类特殊的线性规划问题，即整数规划问题。关于这类问题的算 法有许多，如匈牙利算法，削高排除法【1 ，缩阵分析法i 1 2 1 和差额法0 3 1 等。其中匈牙 利算法运用最为广泛。 定理( 指派问题的最优解原理) 如果从效益矩阵( c , 0 ) 。的第，列中每个元素都 减去6 ，第新亍每个元素都减去口( 口、6 可正可负) ，得到一个新的效益矩阵( c 打) 那 么以( c 玎) 脚为效益矩阵的新目标函数和原目标函数最优解相同，目标函数仅相差一 个常数。 因为，新目标函数变为 n一打月月 s = c f 而= 勺而一口毛一b z x u i = l j = l i = 1 j = l j = l i = l = 白- a - b t = lj = 1 上式表明，新目标函数等于原目标函数加上或减去一个常数，显然两者的最 优解相同且目标函数值仅相差一个常数。 利用上面定理，可把原效益矩阵( c i ，) 。变换为含有很多0 元素的新系数矩阵 ( c 。) ( 称为原效益矩阵的缩减矩阵) ，而其最优解保持不变。 本文对该定理的证明将采用如下方法，不仅说明新旧目标函数仅相差一个常 数，而且说明了新效益矩阵保持旧效益矩阵的系数关系不变： 不失一般性，不妨假定将目标函数系数矩阵( ) 。的第一行各元素同时减去 一个常数k ，所得新的目标函数系数矩阵记为( c 盯) 。，即 c l ，= c l ，一k u = 1 ，2 ，z ) c l ，2 勺 ( f 2 3 ，r lj = 1 2 ，川 那么，在( c ) 釉和( c ，) 脚各对应的指派问题中，目标函数s 和s 之间的关系为 s = c 一( 勺- k ) x u + 勺嘞 万n一 月 = c l ，而一k 五+ c ：f 而 j = lj = l ，= 2 = l 因约束条件= 1 ( i - - - 1 ，2 ，疗) ，所以有 s k c - k = s - k ，即s = s - k 。 t = l j = l 6 武汉理工大学硕士学位论文 乞2 而2 + + 乞。屯。+ + 巳l 矗l + 巳2 2 + + 而= l ( ，= 1 2 ，刀) i = l 毛= 1 ( 待1 2 ，刀) j = l = 1 或0 ( f ，j = 1 ，2 ，玎) 其中勺为目标函数系数矩阵： 而为指派矩阵： q lc 1 2 c 2 1c 2 2 厶i 巳2 五1五2 而l而2 毛。 吃。 1 矗2 中的第f 行第_ ，列元素。 中的第f 行第歹列元素。 所以，指派问题最优解由其目标函数系数矩阵( ) 行列中元素数值的大小关系 所确定。 而不失一般性，假定原目标函数系数矩阵( ) 。的第一行各元素的数值有如下大 小关系： q l q 2 q 。 把第一行各元素同时减去同一个常数k 后记作 c l ，= c l 厂k ( ，= 1 ，2 ，门) 则所得新目标函数系数矩阵( c 。) 脚中元素为 叱= q 厂k ( = 1 ，2 ，力) ；c ，= c ：f ( 汪2 ，3 ，以) 且因q l c 1 2 q 。，所以有e 1 1 - k c 1 2 一k q 。一k ， 即c 。c 。2 c 。，即( ) 。与( c 口) 中各行元素大小关系不变，而约束条件 又相同。 所以，以( c 玎) 脚为目标函数系数矩阵的指派问题与以( c ) 为目标函数系数矩阵 的指派问题的最优解相同。( 证毕) 7 + 扎 x 巳 + n毛 h q + 22q + 西 q i i 而勺 。闩 。闰 = sn皿 求 一 一 武汉理工大学硕士学位论文 由上面的证明，我们所要找的是位于效益矩阵( 白) 删不同列的刀个0 元素，而这 托个0 元素恰好每行各有一个。如果能在( c ，) 咖中得到我们想要的这样以个0 元素， 则令指派矩阵( 嘞) 。中对应这刀个0 元素的变量取值为1 ，其他变量取值为0 ，就可 得到原问题的最优解。 2 2 匈牙利算法 2 2 1 匈牙利算法概述 “匈牙利算法”最早是由匈牙利数学家d k o n i g 用来求矩阵中打有么的o 元素的 个数的一种方法，由此他证明了“矩阵中独立打有么的0 元素的最多个数等于能覆盖该 矩阵中所有打有么的0 元素的最少直线数”。1 9 5 5 年由w w k u h n 在求解著名的指派 问题时引用了这一结论，并对具体算法做了改进，但仍然称为“匈牙利算法”。 改进的“匈牙利算法 可以用于求解多种形式的指派问题，其基本思想是：修改 系数矩阵( 已) 。的行或列，使得在每行或列中至少有一个为零元素的缩减矩阵，经 修正直到具有一组处于不同行不同列的零元素( c 。，= 0 ) 共n 个，画上圈，表示对应该 元素的决策变量薯，= 1 ，而未画圈的元素对应的决策变量玉，= 0 ，对应一个完全分配 n斗 方案，那么目标函数值m i i l s = 勺而最小。此法在系数矩阵修正时若画圈的零元 素个数少于阶数时，还需用柯尼格覆盖理论 1 4 1 来进行覆盖处理 2 2 2 匈牙利算法的求解步骤 第一步变换效益矩阵，使各行各列都出现0 元素 ( 1 ) 将效益矩阵的每行都减去本行的最小元素，得到缩减矩阵( i ) ； ( 2 ) 将效益矩阵的每列都减去本列的最小元素，得到缩减矩阵( i i ) ； 第二步进行试指派，寻找最优解 ( 1 ) 进行行检查 从第1 行开始检查，当遇到含有1 个0 元素的一行时，就在这些0 元素上标记符 号，这表示指派所在行的那个人担任所在列的任务，然后把该元素所在的列用 直线覆盖，以免对该任务再指派该别的人。 重复上述检查，直到每一行都没有未标记的0 元素或至少有2 个未标记的0 元素 8 武汉理工大学硕士学位论文 为止。 ( 2 ) 进行列检查 与行检查类似，从第1 列开始，当遇到某列未作标记，且只有一个未标记的0 元素时，就在该0 元素上标记符号。 重复上述检查，直到每一列都没有未标记的0 元素或至少有2 个未标记的0 元素 为止。 ( 3 ) 反复进行( 1 ) ( 2 ) ，直到下述三种情况之一出现为止 情形l ：每行都有1 个被标记的0 元素，此时令的个数为m ，则聊= 刀，取标 有的0 元素对应的= 1 ，其余而= 0 ，把所得到的解( ) 舢代入新目标函数，便 得到解s = 0 ，显然它是最小值。于是这个( 。就是以( 巳) 为效益矩阵的问题的 最优解。 情形2 ：存在未标记的0 元素，但他们所在行有至少2 个0 元素未标记；或所在 列至少2 个o 元素未标记。为了说明此时的标记方法，我们可设在得到缩减矩阵( i ) 时得到的0 元素均为0 ，在得到缩减矩阵( i i ) 时得到的0 元素均记为0 ，依次类 推。若某行没有标记0 元素，应先从标有0 ，的0 元素开始，若标有0 且没有被直 线覆盖的0 元素的个数多于1 个，则可任选1 个标记，若其个数不满1 个，在标记 有0 ，的元素，依次类推，直到有1 个元素被标注为止，其余的0 元素被直线覆盖； 若没有标记0 元素的为某列，也可先从标有0 ，的0 元素开始，任选其中一个标记， 其余用直线覆盖，若不存在标有0 ，的0 元素，可检查是否有标有0 ，的0 元素，类似 作出标记。然后返回步骤2 ( 1 ) 。 情形3 ：不存在未标记的0 元素，但的个数m 以时，存在人员承担过多工作的情况，影响工作效率和工作质量，因此可根据人 员的工作能力情况，对人员将承担的工作量应该有一定的限制。 考虑如下指派问题指派n 个人承担m 项工作( m 行) ，第f 个人承担第，项工作的 时间( 效益) 为岛，第f 个人最多只能承担匆( 正整数) 项工作，该问题的数学模型为： fl当指派第i 人去完成第j 项任务 一” io当不指派第i 人去完成第j 项任务 m i n s = c , j x 扩 ( 3 1 ) i = l 产l s t ：嘞= 1 ( 1 _ 聊) i = i 毛包( 1 f 玎) = l 而 o ，1 ) ( 1 ，所，1 i 刀) 注：当包m 时( 包1 ) ，工作中每项工作才有人员承担。 i = 1 将问题( 3 1 ) 转化为不平衡的指派问题。 一i 令d = 岛，u = l ，2 ，3 ，d ) ；= 包( 扛1 ，2 ，3 ，2 ) 。 i = 1f = l 构造效益值：对v 七u - 1 ，2 ，3 ，d ) ，3 i ( 1 f 刀) ，使： h ( i 一1 ) + 1 k ( f ) 令= ，得下述指派问题： 武汉理工大学硕士学位论文 dm r a i n s = t = l j = l s t ：= l ( 1 歹聊) 均l ( 1 七d ) j = 1 o ，1 ( 1 ，肌，1 k d ) ( 3 2 ) 问题( 3 2 ) 是不平衡的指派问题。 下面给出不平衡指派问题的两种情形及其数学模型： 情形1 ：当人员数少于任务数( r m ) 时，出现部分人员将无任务承担。 针对情形1 、2 的指派问题，令 fl当指派第i 人去完成第j 项任务 i o当不指派第i 人去完成第j 项任务 当n m 时： 开珊 m i n s = c , j x , j i = lj = l 1 4 ( 3 4 ) 武汉理工大学硕士学位论文 而1 ，i - - 1 ，2 ，玎 = l 而= 1 ，j f = 1 ，2 ，历 i = 1 = 1 或0 ( 1 f 门，1 ，卵) 注：嘞= l 表示每项任务均有且只有一个人员承担； 而1 表示可能有部分人员无任务承担。 很明显，不平衡指派问题数学模型与平衡的指派问题数学模型的差别较大。 3 1 2 非平衡指派问题的求解原理证明 定理1 设 ) 是问题( 3 2 ) 的可行解，则： h ( o 令= k = h ( 1 - 1 ) + l x f ) 也是问题( 3 1 ) 的可行解。 h ( o d 证明：因为嘞=均虼= 1 ，故嘞 o ，1 ； k = h ( i 1 1 + 1 k = l 由d = 岛，u = l ，2 ，3 ，d ) ；= 岛( f = 1 ，2 ，3 ，行) ， ( 3 5 ) n(f)dm 得而= = = 1 ；对任意硼f 以) ，由1 得： 嘞= = 虼匆 j = lj = lk = h ( i 1 ) + lk = h ( i 1 ) + lj = l 故定理得证。 定理2 设 是问题( 3 2 ) 的最优解，则按( 3 5 ) 表达式得到的 ) 也是问题( 3 1 ) 的最优解，并且( 3 1 ) 与( 3 2 ) 目标函数值相等。 证明：由定理1 可知： 五， 是问题( 3 1 ) 的可行解。 设( ) 是问题( 3 1 ) 任一可行解，对v 七u = 1 ，2 ，3 ，d ) ，存在f ( 1 f 门) ，使 武汉理工大学硕士学位论文 h ( i - 1 ) + 1 k 愚( f ) 取厂( f ) = ，：1 ，m ；而= 1 ) = z ，五，五，工 ，其中厂包，并且 z 左 五 。当j f = 丘j ( f ) ，k = h ( i 1 ) + s ( 1 s gr ) ，取均= 1 ；否则= 0 ， 按照定理1 的证明过程可得： ) 也是问题( 3 2 ) 的可行解， 又因为d 兰：壹兰m ：主至勺嘞； k = l j = 1 j = l k = h ( i 1 ) + l = 1 i = l = l 同理= c 均。 ( j ) 且而= 。 k = h ( i 1 ) + l 故： d历打h ( i l册h册dm一历 。= 埯= c ：f ，而- z 蜘= 勺而， k = l = l k = l k = h ( i 1 ) + lj = l k = l j = l # l = 1 i = l j = l 由 屯) 是问题( 3 1 ) 任一可行解可知： 而) 是问题( 3 i ) 的最优解；并且( 3 1 ) 与( 3 2 ) 目标函数值相等 因此，求解问题( 3 1 ) 可转化为求解问题( 3 2 ) 。 3 2 非平衡指派问题两种情形的求解 3 2 1 将非平衡指派问题转化为平衡指派问题 匈牙利算法是在偶图中找完美对集的方法，对疗 册，因部分人员将担任多项工 作，显然不能直接通过对集方法解决，因此只能将这种情况转变为平衡的指派问题才 能利用匈牙利算法求解。 l - 对门 m 的情况，同样虚设有胛一所项工作，k 小+ ：，并设所有人员对虚 设工作效益值( 时问) 为： 弓= c _ f ( 1 i 聊，1 ，n ) 虿，。t = m a x 勺( 1 f 刀，1 七行一所) l s l 如1 j 聊) 的类匈牙利算法 在式( 3 4 ) 中增加刀个松弛变量五肿。，而1 ，一，册+ 。，这些变量也是0 1 变量， 把式( 3 4 ) 化成标准形： 式中c _ - ( q l ，q ，州，巳，l ，c n ”1 ) l 州川) x r = ( 而1 ，而，+ l ，矗j ，而，。+ 1 ) 1 。( ，+ 1 ) b r = ( 1 ，1 ，1 ) l x ( ) c f 埘+ l = 0 ，i = 1 ，2 ，” 彳= s = 其中矿= ( 甜l ，甜2 ，u n ，m ，v 2 以) l 。( ) 把对偶规划( 3 7 ) 展开得： m a x + _ 一o 一 i = 1 j = i s ，u i + v j c _ f ( 1 f 刀，1 聊) 【 0( 1 i 即) 1 8 ( 3 6 ) ，z 行 力曙彳亍。+。，。+， ( 3 7 ) ( 3 8 ) 篓 m 双x 础卜1 fs o o ；o 1 o ；0 1 1 o 1 o 1 1 0 0 1 o