指派問題的匈牙利法(編輯修改稿)
2025-06-14 00:52 本頁面
【文章內容簡介】 行 (列 )的 0元素至少有兩個 ， 則從剩有 0元素最少的行 (列 )開始 ， 比較這行各 0元素所在列中 0元素的數(shù)目 ， 選擇 0元素少的那列的這個 0元素加圈 (表示選擇性多的要 “ 禮讓 ” 選擇性少的 )。 然后劃掉同行同列的其它 0元素 。 可反復進行 ，直到所有 0元素都已圈出和劃掉為止 。 （ 5）若 ◎ 元素的數(shù)目 m 等于矩陣的階數(shù) n，那么這指派問題的最優(yōu)解已得到。若 m n, 則轉入下一步。 第三步：作最少的直線覆蓋所有 0元素 。 (1)對沒有 ◎ 的行打 √號； (2)對已打 √號的行中所有含 216。元素的列打 √號； (3)再對打有 √號的列中含 ◎ 元素的行打 √號； (4)重復 (2)， (3)直到得不出新的打 √號的行 、 列為止； (5)對沒有打 √號的行畫橫線 ， 有打 √號的列畫縱線 ，這就得到覆蓋所有 0元素的最少直線數(shù) l 。 l 應等于 m，若不相等 ， 說明試指派過程有誤 ， 回到第二步 (4)， 另行試指派；若 l＝ m n， 須再變換當前的系數(shù)矩陣 ，以找到 n個獨立的 0元素 ， 為此轉第四步 。 第四步：變換矩陣 (bij)以增加 0元素 。 在沒有被直線覆蓋的所有元素中找出最小元素，然后打 √各行都減去這最小元素；打 √各列都加上這最小元素（以保證系數(shù)矩陣中不出現(xiàn)負元素）。新系數(shù)矩陣的最優(yōu)解和原問題仍相同。轉回第二步。 例一： 任務 人員 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。 ◎ 216。 216。 ◎ ◎ ????????????0100000100101000 有一份中文說明書，需譯成英、日、德、俄四種文字，分別記作 A、 B、 C、 D?，F(xiàn)有甲、乙、丙、丁四人，他們將中文說明書譯成不同語種的說明書所需時間如下表所示，問如何分派任務，可使總時間最少？ 任務 人員 A B C D 甲 6 7 11 2 乙 4 5 9 8 丙 3 1 10 4 丁 5 9 8 2 例二、 求解過程如下： 第一步，變換系數(shù)矩陣： 2142 289541013895421176)(?????????????????ijc????????????
畢業(yè)設計相關推薦
鄂ICP備17016276號-1