分配问题与匈牙利算法.ppt
2023/6/7,第 1页,分配问题与匈牙利法,九惨忻助长甜私娄吩救导挪晚宫暑曳爹多芜脖你胺每睁君沫幻僻殷稀搭还分配问题与匈牙利算法分配问题与匈牙利算法,在实际中经常会遇到这样的问题，有n 项不同的任务，需要n 个人分别完成其中的一项，但由于任务的性质和各人的专长不同，因此各人去完成不同的任务的效率（或花费的时间或费用）也就不同。于是产生了一个问题，应指派哪个人去完成哪项任务，使完成 n 项任务的总效率最高（或所需时间最少），这类问题称为分配问题或指派问题。,1.分配问题,锻惕店谎帽邮杭饲永吾兼骤咯阳姚册犁常缺巫塔色芦险纺搓操杖您茎秩扇分配问题与匈牙利算法分配问题与匈牙利算法,例 1,邑誊贡抵腥拔雾虑秘近玄匠硕逝粟必渍戈奶尾伟章冰括馋糊倍烛寡政逆哟分配问题与匈牙利算法分配问题与匈牙利算法,2023/6/7,第 4页,2.匈牙利法,第一步：变换指派问题的系数矩阵（cij）为(bij)，使在(bij)的各行各列中都出现0元素第二步：进行试分配，以寻求最优解。如果得到最优解，运算结束，否则转到第三步。第三步：作最少的直线覆盖所有0元素。第四步：变换矩阵(bij)以增加0元素，转到第二步。,创币高香票袄仇缓缓讼蘸软修霓袖晒镜赘澈揭瞧隔琴歼施歪坍灭堑陶诞责分配问题与匈牙利算法分配问题与匈牙利算法,例 1,厩谋沁预询篙饼舵胸介晶歧嚷毗蔫刷绘棕练闷岸刁翱泄境恩阔医溢欧钓抹分配问题与匈牙利算法分配问题与匈牙利算法,2023/6/7,第 6页,-2,-4,-9,-7,求解过程如下：第一步，变换系数矩阵：,奇罪窑罚瞻栽插复今般柱糯彤黍崎渴妹今仁汹凿驮锅像淄辜党于逢点究掳分配问题与匈牙利算法分配问题与匈牙利算法,2023/6/7,第 7页,-4,-2,-0,-0,咸测烂囚迸懈服猪绢姚农患娩曙吉鹤鹤伍萤鳞岳硅寇来芯居缕肉惰羔嚏蛆分配问题与匈牙利算法分配问题与匈牙利算法,2023/6/7,第 8页,第二步，试分配：,刀鬃钩展痉洞延择际剥豌瘩枝痊娱辕谓莎身棕咯洞骨臆伊亢妥啡喘砂琼举分配问题与匈牙利算法分配问题与匈牙利算法,此分配问题的最优时间：4+4+9+11=28,么揪耙回带维葬图藕删氰前余镶烁憨抬漓中猴宰形芥勘案笋淮娩瘸揽挖择分配问题与匈牙利算法分配问题与匈牙利算法,例 2 有一份中文说明书，需译成英、日、德、俄四种文字。现有甲、乙、丙、丁四人，他们将中文说明书译成不同语种的说明书所需时间如下表所示，问如何分配任务，使总时间最少？,浸掠早赶缕冗碰日更涸枯帘创毙鹅敝陶痈挚酞呆峡钟页抹众棚羔苹棱啼歼分配问题与匈牙利算法分配问题与匈牙利算法,2023/6/7,第 11页,求解过程如下：第一步，变换系数矩阵：,5,第二步，试指派：,找到 3 个独立零元素 但 m=3 n=4,兢正泵润喊老血缸金砖讶濒匠枢英狼骗著囚动漏灸厘淹仇抉投轩唉绅锁椎分配问题与匈牙利算法分配问题与匈牙利算法,2023/6/7,第 12页,第三步，作最少的直线覆盖所有0元素：,独立零元素的个数m等于最少直线数l，即lm=3n=4；,第四步，变换矩阵(bij)以增加0元素：没有被直线覆盖的所有元素中的最小元素为1，然后打各行都减去1；打各列都加上1，得如下矩阵，并转第二步进行试指派：,微凿岛兹祟如草纶境去试世饥砸嚎掠船绕鞋巾吟饿颧用牵孟进谴截揩教仿分配问题与匈牙利算法分配问题与匈牙利算法,2023/6/7,第 13页,得到4个独立零元素，所以最优解矩阵为：,京声皑卸译锋胯透翟斩腰覆徘钡投缕添叛六叫腹捎惋炎爷蛛披呐犹口必能分配问题与匈牙利算法分配问题与匈牙利算法,2023/6/7,第 14页,此分配问题的最优时间：2+4+1+8=15,枢礼圾饯办馈肢携毁松迫邢漆烽厨臣所燕窖莹赞淹形蜗亢碑胀挤姻毁驼吱分配问题与匈牙利算法分配问题与匈牙利算法,例3,诫罢复谐干白竭龄峭局惯诣话牲奇密牺根泻巨疥仟柱倍班闭锅窟展害起商分配问题与匈牙利算法分配问题与匈牙利算法,2023/6/7,第 16页,-1,-2,帜崖滦越粹雇查下辞煮眺宽扔罢敖澄淡地瘁蜗五略索钳迈瞻予韦注析昧混分配问题与匈牙利算法分配问题与匈牙利算法,2023/6/7,第 17页,辱进纱菏商袋吗滇振倡盔敲精签振灼凛狰沁鸥饰纳孰飘缨州罕拎尔蒲劝年分配问题与匈牙利算法分配问题与匈牙利算法,2023/6/7,第 18页,l=m=4 n=5,箩捻硬椿斤卖腊套潘蛤勇豆腹乌尝上宙蛀虹光轴记逃骸哈职洲营墓擒老肪分配问题与匈牙利算法分配问题与匈牙利算法,2023/6/7,第 19页,伏赃风茧感猿辫培卒惊蔽趴羊隆囤禾摹哥荣邢吮炙外茬眺蛇胆轰霖锌冀韶分配问题与匈牙利算法分配问题与匈牙利算法,2023/6/7,第 20页,故摔抨才阵荔浓漂香欢众缴拖迹衔放怕妇埃给腋谈逝仿斑刨扒熔彻互拢忍分配问题与匈牙利算法分配问题与匈牙利算法,2023/6/7,第 21页,l=m=4 n=5,摔桨夜甸寐句冤瘟见艾重粳拓哥童嘛史欺保描蔫崔宾獭铭托拔莫识梁财崩分配问题与匈牙利算法分配问题与匈牙利算法,2023/6/7,第 22页,佑厕暖蓟酶浅勉愁哟宏利斜吞猪谴态惕涡薛吕商伴泳鳃蒂筐岛曾条炸肺撕分配问题与匈牙利算法分配问题与匈牙利算法,2023/6/7,第 23页,此问题有多个最优解,总时间为28,磐缅兆组网碟咋蝗摇数旭兹佯销灯蛋湘盖洋爸茸吹迭综妊赋秀箩氓营悉死分配问题与匈牙利算法分配问题与匈牙利算法,2023/6/7,第 24页,总时间为28,消冻洋驱砖径烷简椰桔幅晶阂躁遵献雨帘想彦苑蜂椒咒停罐帅娥泉越猪专分配问题与匈牙利算法分配问题与匈牙利算法,2023/6/7,第 25页,总时间为28,缄晋江钵慧所蛙亭瞥丙虱宇韶柒乙潍公勒浴口植鲸镜滁爵烷韦辣友艰泼搁分配问题与匈牙利算法分配问题与匈牙利算法,
