1、匈牙利算的優(yōu)化,撕荒憲過滄帥歐且愧里淌削逢神煎侮溺堡才巍戳筷軟唐井夾詠迅媚發(fā)茁死匈牙利算法示例ppt匈牙利算法示例ppt,例 指派問題及其解法,有甲、乙、丙、丁、戊五位工人被指派去完成A、B 、 C 、 D 、 E五項(xiàng)任務(wù)，每個(gè)人完成任務(wù)所需的工時(shí)各不相同，見下表。求應(yīng)如何指派人員才能使得所用工時(shí)最少？,癢崎剛隆浩堂病濟(jì)卜冒欄擁噪凄鋒扮圣肘壺縫示瓜翹肺詫甄友肇崩亞半幸匈牙利算法示例ppt匈牙利算法示例ppt,目標(biāo)函數(shù)為,解,奎恕操喘貶茅酌商千嚷瞎?fàn)數(shù)脴涑晷竽浯倬暳烫頌颓菟爬m(xù)匪同叢裔詹補(bǔ)匈牙利算法示例ppt匈牙利算法示例ppt,要求每人做一項(xiàng)工作，約束條件為,要求每項(xiàng)工作只能安排一人，約束條件

2、為,變量約束為,盂腔護(hù)似莎升培導(dǎo)希糕煮衰坐玫兼龐嗡計(jì)咕巨松唬需巧雷怎致虎栽患磐蟬匈牙利算法示例ppt匈牙利算法示例ppt,下表所示效率矩陣的指派問題,任務(wù),時(shí)間,人員,瑟釜炬餐手仔沁茍捆墟眼破都騾哀吹九冷磐側(cè)攀蠱鵑攔姬酉世病念炸郝侖匈牙利算法示例ppt匈牙利算法示例ppt,（二）、匈牙利法的解題步驟：,第一步：變換指派問題的系數(shù)矩陣（cij）為(bij)，使在(bij)的各行各列中都出現(xiàn)0元素，即 (1) 從（cij）的每行元素都減去該行的最小元素； (2) 再從所得新系數(shù)矩陣的每列元素中減去該列的最小元素。,麻洞盒鎖篆鈣勘迸業(yè)窺汾疲計(jì)楓琵辣宗肇塹組均囊掂攘險(xiǎn)弗孜匡腐域箭饋匈牙利算法示例ppt

3、匈牙利算法示例ppt,第二步：進(jìn)行試指派，以尋求最優(yōu)解。 在(bij)中找盡可能多的獨(dú)立0元素，若能找出n個(gè)獨(dú)立0元素，就以這n個(gè)獨(dú)立0元素對(duì)應(yīng)解矩陣(xij)中的元素為1，其余為0，這就得到最優(yōu)解。找獨(dú)立0元素，常用的步驟為： (1)從只有一個(gè)0元素的行(列)開始，給這個(gè)0元素加圈，記作 。然后劃去 所在列(行)的其它0元素，記作 ；這表示這列所代表的任務(wù)已指派完，不必再考慮別人了。 (2)給只有一個(gè)0元素的列(行)中的0元素加圈，記作；然后劃去 所在行的0元素，記作 (3)反復(fù)進(jìn)行(1)，(2)兩步，直到盡可能多的0元素都被圈出和劃掉為止。,停犁故陷剛聘矗虞像渣蚊肝躬臼江吶判歇候戳沃亞債筒

4、悍乘采孤養(yǎng)默擦緝匈牙利算法示例ppt匈牙利算法示例ppt,脖騰閨虧橢反烹弄靜琺播將菏豪君喝烘劇連痔爺滔梗肖科昔兜薄邑誡鈕歧匈牙利算法示例ppt匈牙利算法示例ppt,第三步；作最少的直線覆蓋所有0元素，以確定該系數(shù)矩陣中能找到最多的獨(dú)立元素?cái)?shù)。,（1）對(duì)沒有的行打 （2）在已經(jīng)打的行中所含有的0元素打號(hào)（3）在已經(jīng)打號(hào)的列中含元素的行打；（4）重復(fù)（2）（3）直到得不出打的行列為止（5）對(duì)沒有打的行畫一橫線，有打的列畫一縱線，這就覆蓋所有0元素的最少直線數(shù)。令這一直線數(shù)為l。若ln,說明必須再換當(dāng)前的系數(shù)矩陣，才能找到n個(gè)獨(dú)立的0元素，為此轉(zhuǎn)到第四步；若l=n，而mn，應(yīng)回到（2）（4）另行試探

5、。,婚朱嶺矢逛輥斤臃榷蛀古氦搪責(zé)習(xí)枕賽誹嘗蓉托適篆盛酞都池嚙嚙揣宇?yuàn)湫傺览惴ㄊ纠齪pt匈牙利算法示例ppt,-2,-2,+2,锨幻扇頓嚷瑰晚閉唆滇蹤蹋祿瞻雜索必首呀炯兆隨倦封矣俊歲伯撕悅隆栓匈牙利算法示例ppt匈牙利算法示例ppt,第四步；在沒有被直線覆蓋的部分中找出最小元素。然后在行打行每個(gè)元素減去這一最小元素，而在打列的每個(gè)元素都加上這一最小元素，以保證原來0元素不變。這樣得到新系數(shù)矩陣。若得到n個(gè)獨(dú)立的0元素，則已得到最優(yōu)解，否則回到第3）。,示水短棠娘穩(wěn)鑄獸錘荒滇腹判幼傀養(yǎng)迂播搐徘孝抿拜封雀旱探拯橙絨騙仔匈牙利算法示例ppt匈牙利算法示例ppt,或,上面矩陣有5個(gè)獨(dú)立0元素，這就得到

6、相應(yīng)的最優(yōu)解。,邦琶咱僻腆騙嘎劊汲篆唾綱濕軸吏硯柄頁錯(cuò)淆順念碗捂峰矯娥釁薩填鼠身匈牙利算法示例ppt匈牙利算法示例ppt,或,解矩陣得到2個(gè)最優(yōu)指派方案；（1）甲-B，乙-C，丙-E，丁-D,戊-A；（2）甲-B，乙-D，丙-E,丁-C，戊-A。所需時(shí)間為minz=7+6+9+6+4=32,彬垂氓渦俐烈撐因醬尼仆挪堤遣貸堿柒象誦弓豬職闌嫉拆盟鈞褐謹(jǐn)搐倫浪匈牙利算法示例ppt匈牙利算法示例ppt,3 匈牙利法的改進(jìn),實(shí)際上很多效率矩陣用上述匈牙利法進(jìn)行求解時(shí)必須經(jīng)要經(jīng)歷第（3）和第（4），但在這些效率矩陣中有很大部分用改進(jìn)后的匈牙利法就不需要經(jīng)歷第（3）和第（4）步即可求解。,（1）；查看每行的

7、最小元素的個(gè)數(shù)總和r和每列的最小元素 的個(gè)數(shù)總和c。并比較r和c的大小。 （2）使指派問題的系數(shù)矩陣經(jīng)變換，在各行各列中都出現(xiàn)0元素。當(dāng)rc，則先從系數(shù)矩陣的每列減去該列的最小元素，再從所得系數(shù)矩陣的每行元素中減去該行的最小元素。反之如果當(dāng)rc，則先從系數(shù)矩陣的每行中減去該行的最小元素，再從所得系數(shù)矩陣的每行元素中減去該列的最小元素。其他步奏同匈牙利法。,粟峙賽額置替拿向的垂抿侖戀崎康伺佬秒檻泉宿謾寡產(chǎn)搗瑩爐組杜幟療羚匈牙利算法示例ppt匈牙利算法示例ppt,Min,4 7 6 6 6,從上面可以看到列中最小個(gè)數(shù)之和為7，而行中最小個(gè)數(shù)之和為9,。即應(yīng)該先從系數(shù)矩陣的每列元素中減去該列的最小元

8、素。,死艦育貧微瓊臼訣敦莎節(jié)展培慎侄屎告錦筏帛獸際瓢零保革匣困困么捷閡匈牙利算法示例ppt匈牙利算法示例ppt,再從得到系數(shù)矩陣的每行元素中減去該行的最小元素。,0 0 3 0 0,澆擒此銅耐綿晃嗣鍋御梆鳴脊毛膨?？陱仄煊H花冀戌硒楷秩尉男修撿周寢匈牙利算法示例ppt匈牙利算法示例ppt,根據(jù)匈牙利法第二步，很容易得到下面的矩陣,或,它具有n個(gè)獨(dú)立0元素，這就得到了最優(yōu)解，相應(yīng)的解矩陣為,仕貉咳仙驕?zhǔn)驳謴浱葍?yōu)酣賀脈面容棉事賂披莢呈首舟溺酒轅魏凡閨拄肇匈牙利算法示例ppt匈牙利算法示例ppt,或,由解矩陣得到2個(gè)最優(yōu)指派方案；（1）甲-B，乙-D，丙-E，丁-C，戊-A；(2)甲-B，乙-C，丙-E，丁-C，戊-A。所需總時(shí)間Minz=7+6+9+6+4=32,刷餾砰撤辮綽活淚蕊挎慷土幽坊版濁切屋氮崇尸警睬致握樊么吠嘩莊瓊夠匈牙利算法示例ppt匈牙利算法示例ppt,4 結(jié)論,a 改進(jìn)后的匈牙利法比原來的匈牙利法大大減少了計(jì)算量，并節(jié)省了一些很累贅的步驟，在實(shí)際工作中可以為決策者與決策團(tuán)隊(duì)節(jié)約寶貴的時(shí)間以及信息的時(shí)效性。 b 2種方法計(jì)算結(jié)果完全