指派問題的匈牙利法-文庫吧資料
2025-05-17 00:52本頁面
【正文】 任務(wù) 人員 A B C D 甲 6 7 11 2 乙 4 5 9 8 丙 3 1 10 4 丁 5 9 8 2 例二、 求解過程如下： 第一步，變換系數(shù)矩陣： 2142 289541013895421176)(?????????????????ijc????????????0673390245100954????????????0173340240100454－ 5 第二步，試指派： ????????????17334241454 ◎ ◎ ◎ 216。 216。 例一： 任務(wù) 人員 A B C D 甲 2 15 13 4 乙 10 4 14 15 丙 9 14 16 13 丁 7 8 11 9 ????????????9118713161491514410413152????????????241047501110062111302 4 9 7 ????????????00102350960607130????????????241047501110062111304 2 ????????????00102350960607130◎ 216。新系數(shù)矩陣的最優(yōu)解和原問題仍相同。 第四步：變換矩陣 (bij)以增加 0元素 。元素的列打 √號(hào)； (3)再對(duì)打有 √號(hào)的列中含 ◎ 元素的行打 √號(hào)； (4)重復(fù) (2)， (3)直到得不出新的打 √號(hào)的行 、 列為止； (5)對(duì)沒有打 √號(hào)的行畫橫線 ， 有打 √號(hào)的列畫縱線 ，這就得到覆蓋所有 0元素的最少直線數(shù) l 。 第三步：作最少的直線覆蓋所有 0元素 。 （ 5）若 ◎ 元素的數(shù)目 m 等于矩陣的階數(shù) n，那么這指派問題的最優(yōu)解已得到。 然后劃掉同行同列的其它 0元素 。 ． (3)反復(fù)進(jìn)行 (1)， (2)兩步 ， 直到盡可能多的 0元素都被圈出和劃掉為止 。 ；這表示這列所代表的任務(wù)已指派完 ， 不必再考慮別人了 。 找獨(dú)立 0元素 ， 常用的步驟為： (1)從只有一個(gè) 0元素的行 (列 )開始 ， 給這個(gè) 0元素加圈 ， 記作 ◎ 。 第二步：進(jìn)行試指派 ， 以尋求最優(yōu)解 。利用指派問題的特點(diǎn)可有更簡(jiǎn)便的解法，這就是匈牙利法，即 系數(shù)矩陣中獨(dú)立 0 元素的最多個(gè)數(shù)等于能覆蓋所有 0 元素的最少直線數(shù)。 匈牙利法解例 ? 時(shí)間矩陣 ? 各行各列減去最小元素后得 ????????????913741116141381441573102?????????
畢業(yè)設(shè)計(jì)相關(guān)推薦
鄂ICP備17016276號(hào)-1