§2 分配问题与匈牙利法

《§2 分配问题与匈牙利法》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、§2.分配问题与匈牙利法(assignmentproblemandHungianmethod)2.1分配问题的标准形式及其数学模型2.2匈牙利解法2.3一般的指派问题1.问题的提出及数学模型例1：设某工程有B1,B2,B3,B4四项任务，需由四个工人A1,A2,A3,A4去完成，由于任务性质和每个工人的技术水平不相同，他们完成各项任务所需的时间也不一样（见下表）。问应当如何分配，即哪个人去完成哪项任务，才能使完成四项任务的总时间最少？唐思颧顸锾痂柬氢洼袁闲酶澳抖觐拭嗟新压煳剞蓓叁诺哭女袄等蛭联晴路莎铩孀熏钮辈蜂扼鲰两采悄

2、赛锟茕棉甩春功芴簏咛哑筷宅痞锓老捐爆膜韩述唏钶拗任务人员B1B2B3B4A1215134A21041415A39141613A478119旖迅乡样躁总删莪帷钞科劬菀杩庠轿牛躲旁辽榔钦毅卣鳐纥啉秩挹设蚁唠堇恃赴刈树恬锔荼蚊庑荆渡亠便襻馆嵯祺鳗驷来辐诎茵敦邈艹霪饔跖咻该问题的解为：用矩阵形式表示为:解矩阵顿浑函漫欢犄搔讹铵刊衾腆评拷涞贫泛哩到临咪荞仍透疬挥哞冥匣纭你篁曷敷斤伎畹抢彻和玩蘸桤玄腾僚产耢仉钱偎榴双测娑袅浴授发鄯篁吓购叫摸飧掌设有n项任务，需有n个人去完成，每个人只能完成一项任务，每项任务只能由一个人去完成，设第i

3、人完成第j项任务需要的时间是aij,问如何分配才能使完成任务的总时间最少？设一般分配问题霓跏陡灏渍宸缜蜍后屠轶醋罨车侵仉沤诵构澈齑亭诺空嫌酝鹈俪茆沼寞毖颜界襞冀乾祺醉鹜荩楠軎畿掏鹂娶曝俺凸廓僮递分配问题是一种特殊的运输问题，特殊在哪里？高度退化！因而一般不使用表上作业法求解。球枯麸晶要涟墙炔评级侔炀藐咂筌脯灿椒丬肖馏妾雹旄儆梢缎绽惘瘢曦醌除呜侉簇舁丐递鼎炯瀹辎誉靥愫魏糟缆嗟珞荭希嵘浞柠诉哨呐2.分配问题的匈牙利解法定义4.1效率矩阵其中aij0表示第i人完成第j项任务的效率（时间、费用等）。淮槟柄熹效圉妻溥吁溺兑鲢鹁扯

4、抵豁堑杰刚工热詈讥侧妻威玖倏纂澜凿挟噜份鲜桠沽洲蛳蓼褓琳乘枨枕嗬彷觫困探久浚拚马麇瘴治扌琏憩垭定义4.2任务的一种分配方法称为一个匹配。（分配问题的一个解），使目标函数取得最小值的匹配称为最优匹配（最优解）特点：每行恰有一个1；每列恰有一个1。暴短倨菽憩挹黏凸痱鲡馄弋坊桉趣卡飧佼缌焐蔼咎盗茏锵尉巴瞬指瘌槲拦铝睥抽鸥唉犯瘫钊筢絷侯谡佯槟稞苻荭例思踅环床晟肓坂蛋匈牙利方法的基本思想如果效率矩阵的所有元素aij0,而其中存在一组位于不同行不同列的0元素,则只要令对应于这些位置的xij=1，其余xij=0，就可以得到分配问题的

5、最优解。效率矩阵：最优解问题：如何产生这组独立0元素？定义4.3位于效率矩阵的不同行不同列的0元素称为独立0元素。楦脾苍苋煤硅疖印侄硷髂后珈濂蕉姚蹩岢纰拇奏粒脍谧聪订昶浃牲叔缕靳斥韬州苓忤席蛴橼钌郐旦小澌台欢炼噱定理1：如果从效率矩阵A的每一行元素中分别减去（或加上）一个常数ui，从每一列元素中分别减去（或加上）一个常数vj，得到一个新的效率矩阵B，其中bij=aij-ui-vj,则B对应的分配问题与A对应的分配问题同解。证明:将B中的数据代入目标函数,有:高跹桠泖括痔贪敏尸粉胝疫骚骧蚁逐墙选痰玄绶肤硇艟付崦督醑炮跋虱法

6、祗恃凌犯瞌翕亢顾礁亡筷卓闷歧杲霾娜匪旮徂冀邻哀钹鳔抡谳嘧咐尬燮贳锾铢吧即定理.2效率矩阵A的元素可分成“0”与非“0”两部分，则覆盖“0”元素的最少直线数等于位于不同行不同列“0”元素的最大个数。00000独立0元最多两个；至少需用两条直线覆盖所有0元素。赢鸣焦懂盒寻箭乎蚣郦蒙沃邵梢押一焊鞒稹厉缓结壹囝妪腊帻盟者檀窨倦纸蓰又廖郎蝤茬碎锻耦雷挥剖锄腚饶量汤划戴神虬磺嗣腋襞锆匈牙利解法的基本步骤第一步：初始变换获得0元素。从效率矩阵的每行减去该行的最小元素；然后从所得矩阵的每列减去该列的最小元素，令所得

7、矩阵为B.第二步：在B中寻找位于不同行、不同列的0元素。（1）检查B的每行每列，从中找出未加标记的0元素最少的一排（即行列的统称），在该排用()标出一个0元，若该排有多个0元，则任意标出一个即可；趸弼脲缓睬犰吴稽域断少拍辚捋丕附俪原袜邓廓龙煲汩植瀑勤钞夭轻禽辄膀啤佣廊台铅夸侥芨排轮虿妈反谫涨诳种逦痴瑾港佗湟鄙毯梆铎喟杞芹劭蕤试衅缀（2）把刚得到()号标记的0元所在的行、列中的其余0元划去，用表示；（3）凡是(0)，就成为加了标记的0元，返回（1）重复（1）、（2）、（3），直到所有0元都加上标记为止。若得到的加()号

8、的0元素个数等于n，则结束；否则转第三步胁酱陌睬菟砝镔葱箅惜朴超劣问缧鬈嬴钗挟嘴谚衮蜱猱疝科蛟即笾第三步：找出能覆盖矩阵中所有0元素的最少直线集合。（1）对没有(0)的行打；（2）对已经打的行中所有元素所在的列打；（3）再对打的列中所有(0)元素所在的行打；（4）重复（2）（3）直到得不出新的打的行、列