分配問題指派問題與匈牙利法(編輯修改稿)
2025-06-04 00:05 本頁面
【文章內(nèi)容簡介】 0 2 0 92 3 0 0 80 10 5 7 59 8 0 0 40 6 3 6 0????????????????0 1 0 0 00 0 1 0 01 0 0 0 00 0 0 1 00 0 0 0 1????????????????圈 0個數(shù) 等于 n=5 多重最優(yōu)解 5 0 2 0 92 3 0 0 80 10 5 7 59 8 0 0 40 6 3 6 0????????????????5 0 2 0 92 3 0 0 80 10 5 7 59 8 0 0 40 6 3 6 0????????????????5 0 2 0 92 3 0 0 80 10 5 7 59 8 0 0 40 6 3 6 0????????????????可能出現(xiàn)三種情況 ， 但圈 0的個數(shù) n （ 3）判斷 獨(dú)立零元素 的個數(shù) 圈 0個數(shù) 4 n=5 作 最少直線覆蓋當(dāng)前所有零元素 ， 便于下步增加獨(dú)立零元素的個數(shù) 。 ????????????????04320405001232037710811030定理： 系數(shù)矩陣 C中 獨(dú)立零元素的最多個數(shù) 等于 能覆蓋所有零元素的 最少線數(shù) 。 由匈牙利數(shù)學(xué)家 (康尼格 )所證明 5 0 2 02 3 0 005674 8 0 0????????????5 0 2 0 22 3 0 0 00 10 5 7 29 8 0 0 40 6 3 6 5????????????????例 ：分別求下列矩陣中的獨(dú)立零元素的最多個數(shù)。 4 4 獨(dú)立零元素 的個數(shù)最多： ① 對 不含圈 0的行打 ? ； ② 在打 ? 的行中 ， 對所有零元素所在 列 打 ? ； ③ 在所有打 ? 的列中 ， 對圈 0所在 行 打 ? ； ④ 重復(fù) 2,3步 ， 直到不能 打 ? 為止 。 ⑤ 對 未打 ? 的每一行 畫一橫線 ， 對 已打 ? 的每一列 畫一縱線 ， 即得到覆蓋當(dāng)前 0元素的 最少直線 集 。 ????????????????04320405001232037710811030? ? ? ⑥ 找未被直線覆蓋的最小數(shù)字 k； ⑦ 對矩陣的每行：當(dāng)該行 有直線覆蓋時 ， 令 ui=0； 當(dāng)該行 無直線覆蓋 時 ， 令 ui=k。 ????????????????04320405001232037710811030 ui 0 1 1 0 0 ⑧ 對矩陣的每列：當(dāng)該列 有直線覆蓋時 ， 令 vj=k； 當(dāng)該 列 無直線覆蓋 時 ， 令 vj=0。 vj 1 0 0 0 0 ????????????????04320405001232037710811030 ui 0 1 1 0 0 vj 1 0 0 0 0 ????????????????04320405000121026600811030⑨ 從原矩陣的每個元素 aij 中分別減去 ui和 vj， 得到新元素 ⑩ 再次尋找獨(dú)立零元素 ????????????????04320405000121026600811030逐 列 檢驗(yàn) ????????????????1000001000000010001000100????????????????6 10 12 9 610 6 14 7 67 8 12 9 610 14 17 9 712 15 7 8 4原題： 分配方案 A=7+9+6+6+6=34 ⑩ 再次尋找獨(dú)立零元素 ????????????????043204050001210
電大資料相關(guān)推薦
鄂ICP備17016276號-1