指派问题

5.4指派问题AssignmentProblem一.内容概述二.数学模型三.指派问题的匈牙利算法四.例5-15五.经典例题分析六.特殊问题的模型转化1．指派模型的特征2．匈牙利法求解指派问题的条件3．匈牙利法的两个基本定理4．指派问题也是一个特殊的运输问题.5．将指派（分配）问题的效率矩阵每行分别加上一个数后最优解不变.5.4指派问题AssignmentProblem数学模型【例5.14】人事部门欲安排四人到四个不同的岗位工作，每个岗位一个人．经考核四人在不同岗位的成绩（百分制）如表5-34所示，如何安排他们的工作使总成绩最好。表5-34工作人员ABCD甲85927390乙95877895丙82837990丁8690808811121314212223243132333441424344xxxxxxxxXxxxxxxxx工作时人做不分配第工作时人做分配第jijixij01【解】5.4指派问题assignmentproblem5.4指派问题assignmentproblem数学模型为：4443424134333231242322211413121188809086907983829578879590739285maxxxxxxxxxxxxxxxxxZ111144434241343332312423222114131211xxxxxxxxxxxxxxxx111144342414433323134232221241312111xxxxxxxxxxxxxxxx甲乙丙丁ABCD图5.35.4指派问题assignmentproblem假设m个人恰好做m项工作，第i个人做第j项工作的效率为cij≥0，效率矩阵为[cij]（如表5-34），如何分配工作使效率最佳（min或max）的数学模型为mjixmjxmixxcZijmiijmjijmimjijij,1,10,,11,,11min(max)1111或5.4.2指派问题的匈牙利算法5.4指派问题assignmentproblem匈牙利法的条件是：问题求最小值、人数与工作数相等及效率非负【定理5.4】如果从分配问题效率矩阵[cij]的每一行元素中分别减去（或加上）一个常数ui（被称为该行的位势），从每一列分别减去（或加上）一个常数vj（称为该列的位势），得到一个新的效率矩阵[bij]，其中bij=cij－ui－vj,则[bij]的最优解等价于[cij]的最优解，这里cij、bij均非负．【证】1111111111111111()mmmmijijijijijijijmmmmmmijijiijjijijijjimmmmmmijijijijijijijijbxcuvxcxuxvxcxuvcxuv【定理5.5】若矩阵A的元素可分成“0”与非“0”两部分，则覆盖“0”元素的最少直线数等于位于不同行不同列的“0”元素（称为独立元素）的最大个数．如果最少直线数等于m，则存在m个独立的“0”元素，令这些零元素对应的xij等于1，其余变量等于0，这时目标函数值等于零，得到最优解．5.4指派问题assignmentproblem两个目标函数相差一个常数u+v,约束条不变,因此最优解不变。1111111111111111()mmmmijijijijijijijmmmmmmijijiijjijijijjimmmmmmijijijijijijijijbxcuvxcxuxvxcxuvcxuv【证】【例5.15】某汽车公司拟将四种新产品配置到四个工厂生产，四个工厂的单位产品成本（元/件）如表5-35所示．求最优生产配置方案．表5-35产品1产品2产品3产品4工厂15869180260工厂27550150230工厂36570170250工厂48255200280【解】问题求最小值。第一步：找出效率矩阵每行的最小元素，并分别从每行中减去最小元素，有5.4指派问题assignmentproblem556550582802005582250170706523015050752601806958min22514502718510550180100025202122110第二步：找出矩阵每列的最小元素，再分别从每列中减去，有5.4指派问题assignmentproblem45450275550000252222110225145018510550180100025202122110272700100180min第三步：用最少的直线覆盖所有“0”，得011222225000055527045454545032000000030171760第四步：这里直线数等于3（等于4时停止运算），要进行下一轮计算．从矩阵未被直线覆盖的数字中找出一个最小数k并且减去k，矩阵中k＝5．直线相交处的元素加上k，被直线覆盖而没有相交的元素不变，得到下列矩阵5.4指派问题assignmentproblem第四步等价于第2、3行减去5，同时第1列加上5得到的结果4545032000000030171760第五步：覆盖所有零最少需要4条直线，表明矩阵中存在4个不同行不同列的零元素．容易看出4个“0”的位置4545032000000030171760×××或4545032000000030171760×××5.4指派问题assignmentproblem得到两个最优解11111111)2()1(＝，＝XX有两个最优方案第一种方案：第一个工厂加工产品1，第二工厂加工产品3，第三个工厂加工产品4，第四个工厂加工产品2；第二种方案：第一个工厂加工产品1，第二工厂加工产品4，第三个工厂加工产品3，第四个工厂加工产品2；单件产品总成本Z＝58＋150＋250＋55＝513当人数与工作数较多时，用直观的方法进行画线及找独立的零元素比较困难，具体方法请参看教材p115。5.4指派问题assignmentproblem一份说明书需翻译成英日德俄四种文字(E,J,G,R),甲乙丙丁四人翻译四种文字所需时间如下图所示,如何安排才能使完成工作所需时间最短?EJGR甲215134乙1041415丙9141613丁781195.4指派问题assignmentproblem9118713161491514410413152效率矩阵为本题求最小值,下面用匈牙利解法求解5.4指派问题assignmentproblem91187131614915144104131522400min794min22111301110064750241000601501303670290列变换行变换一、行列变换（找出每一行（每一列）的最小值，然后让每一行（每一列）的元素都减去这个数）5.4指派问题assignmentproblem步骤二、试指派(找独立的0元素)(记独立0元素个数为m,矩阵阶数为n.当m=n时,问题到此结束.mn的情况下一题讨论)0010235096060713028119440100000100101000最优值为所以：最优值为5.4指派问题assignmentproblem280200558225017070652301505075260180695855655058min行变换18010000min列变换27025005011455022455022下面就m〈n的情况进行讨论：5.4指派问题assignmentproblem18010002520212211022514502718510550试指派45450275550000252222110此时m(3)n(4),则应转入第三步:即用最少的直线覆盖所有的0.找最少直线的步骤:1、无0行右边划√,在已经划√的行中找0所在的列,在列下面划√,在这列中找到0所在行,在行右边划√,重复直至不能划√为止.2、无√行划一横线，在有√的列划一纵线，此时找到最少的直线数记为L，当L=mn时,转入第四步;当Lm时,试指派.27025005011455022455022√√√5.4指派问题assignmentproblem17176000030000045450275550000252222110√√√此时L=mn，进行第四步：划线以外的数字之中记最小值为θ，没有被直线覆盖的行减去θ.直线交叉处的数字加上θ。变换后再回到步骤二。θ=54545032此时m=n=4，找到了最优解最优解为0010010010000001最优值为58+230+170+55=5031717600003000004545032或0010100001000001或5.4指派问题assignmentproblem要求:1、E必须完成，其余一人一项2、一人完成两项，其它一人一项3、A由甲或丙完成，C由丙或丁完成。E由甲，乙或丁完成，丙或丁完成两项，其他一人一项3742312925332026383932402827344523304224EDCBA丁丙乙甲求下面效率矩阵在特定情况下的的最小值现在看一下指派问题的其他情况5.4指派问题assignmentproblem•分析：•问题1中有四个人和五件事，所以应该虚设一个人，题目要求E必须完成，所以不能由虚设的人完成事件E，所以应虚设一行为（0，0，0，0，M）；•问题2中要求在所需时间最少的情况下有一个人完成两项，应找出每列中最小的数构成虚设的一行，即应虚设一行为（24，27，26，20，32）；•问题3中某个人不能完成某事用M代替,然后从丙和丁所对应的行中选择最小值构成虚设的一行。5.4指派问题assignmentproblem现仅就要求:1、E必须完成，其余一人一事给出具体解题步骤，其他情况类似3742312925332026383932402827344523304224EDCBA丁丙乙甲本题中有四个人和五件事，所以应该虚设一个人，题目要求E必须完成，所以不能由虚设的人完成事件E，所以应虚设一行为（0000M）5.4指派问题assignmentproblem37423129253320263839324028273445233042243742312925332026383932402827344523304224M0000024272025min行变换1217640130618195131017M00002207191最后一列减去5M0000170719101310178061819717640因为M是一个较大的数，减去5以后仍为一个较大的数，所以仍以M表示5.4指派问题assignmentproblemM0000170719101310178061819717640找独立的0元素并试指派√√√