人数与任务数不相等的指派问题

《人数与任务数不相等的指派问题》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第三届全国决策科学／多目标决策研讨会论文集四川成都，2005年5月11-15日人数与任务数不相等的指派问题刘树立1，于丽英2伍家庄陆军指挥学院军事运筹研究中心，石家庄，050084；2上海大学国际工商与管理学院，上海，200072摘要√本文提出人数与任务数不相等的指派问题应当视为一个多目标决策问题，首先要求指派给备人的任务数目两两之间相差不能超过I，其次要求所需总时间晟少；并且给出了该问题的求解方法’关键词：关键词；指派问题；多目标决策：匈牙利算法：解矩阵l问题的提出假设某单位需要完成n项任务，恰好有n个人可承担这些任务．由于每人的

2、专长不同，各人完成4i同任务的效率(或所费时问)也不同问应指派哪个人去完成哪项任务，使完成"项任务的总效率最高(或所需总时间最少)?这类问题称为指派问题或分派问题吵设Co>0眠J=1，2，⋯，n)表示指派第i个人完成第J项任务的效率(或时间、成本等)引入只能取值0或l的变量z”，并令I1当指派第i人去完成第j项任务4”一1o当不指派第i人去完成第j项任务那么当指派问题要求极小化时的数学模型是：minz=∑∑％％，t，f∑。甜=l，J=1，2，一，。{∑z“=1，i=1；2，⋯，nl毛：·或o(1．1)的约束条件说明第J项任务只能由1

3、人去完成，并且第i人只能完成1项任务．可行解z，f也可写成表格或矩阵形式，称为解矩阵．由(1．1)可以看出指派问题是O-1整数规划的特例，也是运输问题的特例(即运输问题在n=m，a。=bfl时的情形)．因此可用整数规划，O-1规划或运输问题的解法去求解指派问题，但是用这些方法去求解指派问题是不合算的．库恩(WWKuhn)于1995年提出了更加简便的求解指派问题的匈牙利算法12】．指派问题的特点是要求各人承担的任务数量～致，否则只要在系数矩阵中选取每一列中的最小的元素，并指派该最小元素所对应的人完成该列对应的任务即可实现所需总时间最少

4、的目标，这时一般会出现有些人承担多项任务，而另外有些人分配不到任务的情形．因此考虑人数与任务数不等的指派问题作为～个多目标决策问题，首先要求指派给各人的任务数B相差不能超过I；其次要求所需总时间最少．分两种情形，一种是人数大于任务数，另一种是人数少于任务数．地竖立坠．：望2人数大干任务数下面结合例l说明人数m大于任务数n的指派问题的解法．例l设有三项任务Tl、T2、T3，'-／PA安排四个人Mj、M2、M3、M4去完成，各人完成各项工作所费的时间Cl，如表1所示，问应指派哪个人去完成哪项任务，所需总时阃最少?第一步：添加m—n个虚拟

5、的任务，并赋予各人完成这些虚拟任务所费的时间为0．此时将f,-j题转化为人数与任务数相等的指派问题．第二步：运用匈牙利法求解(Qj)=mln(％)=21513010414091416078llO2411215104914780118071054=(b玎)此时系数矩阵(％)中有四个独立的0元素．令解矩阵(％)中对应这四个独立0元素的元素取值为1，其它嚣索取值为o，即指派Ml完成任务T1，M2完成任务T2，M4完成任务T3．而M3没有分配任务，所需要的总时闻最少为rainz=Cll-4-C22+C43=2-4-4-4-11=17(小时)

6、以(％)为系数矩阵的指派问题的最优解一定是原问题的最优解3任务数大于人数下面结合例2说明任务数n大于人数m的指派问题的解法．例2设有兰项任务Tl、T2、T3、T4，可以安排四个人MI、M2、M3去完成，各人完成各项工作所费的时间％如表2所示，问应指派哪个人去完成哪项任务，所需总时间最少?袁1人员＼任务T1T2T3M121513M2J0414M391416—M478ll袁2任务＼人员T1T2T3T4MI2【S134M2104}415M39141613入数与任务数不相等构抬派问题第一步：添加n—m个虚拟的人，并赋予各虚拟的人完成各项任务

7、任务所费的时间为。此时将问题转化为人数与任务数相等的指派问题第二步：运用匈牙利法求解(q)=(C4j)=215134104141591416130(bu)=O1311240101105740215134lO4141591416130131l24O1011O574O013O52=(b。)=(b：j)此时系数矩阵(60)中有四个独立的0元素．令解矩阵(z。)中对应这四个独立0元素的元素取值为1，其它元素取值为0，即指派M1完成任务T4，M2完成任务T2，M3完成任务T1，而任务T3没有分配．为了保证所有任务都有人去完成，需要进行第二次指

8、派，此时因为任务数小于人数，可以利用第2节中的方法进行指派，解得应当指派M1完成任务T3．结果M1承担2项任务，其它人各承担了1项任务所需要的总时间最少为rain名=c14+c22+c31+C13=4+4+9+13=30(小时)需要说