【正文】 各列都減去這一列的最小值，得到的 0表示這個(gè) 0所在的列行對應(yīng)的事最適合的人是這個(gè) 0所在的行對應(yīng)的人 甲 俄 乙 日 丙 英 丁 德 英 日 德 俄 甲 乙 丙 丁 0 13 11 2 6 0 10 11 0 5 7 4 0 1 4 2 英 日 德 俄 甲 乙 丙 丁 0 13 7 0 6 0 6 9 0 5 3 2 0 1 0 0 列最小值 有三個(gè)人適合英文 為什么確定丙英 各列都減去這一列的最小值 每行至少一個(gè) 0 各行都減去這一行的最小值 每列至少一個(gè) 0 某列 0的個(gè)數(shù)特別少，是什么意思？ 某行 0的個(gè)數(shù)特別少，是什么意思？ 某列 0的個(gè)數(shù)特別多，是什么意思？ 某行 0的個(gè)數(shù)特別多，是什么意思？ 指派問題的匈牙利法： 第一步 :{各行元素 }— {該行行最小 }， {各列元素 }— {該列列最小 } 若有 n個(gè)獨(dú)立的 0元素則已得最優(yōu)解， 本題有 n個(gè)獨(dú)立的 0元素 減去行列最小后矩陣 英 日 德 俄 甲 0 13 7 0第 4步 行僅 1零 乙 6 0第 2步 列僅 1零 6 9 丙 0第 1步 行僅 1零 5 3 2 丁 0 1 0第 3步 列僅 1零 0 列僅一個(gè)零表示這個(gè)工作只適合一個(gè)人 行僅一個(gè)零表示這個(gè)人只適合一個(gè)工作 甲 俄 乙 日 丙 英 丁 德 顏色表示“確定” 指派問題的匈牙利法： 第一步 :{各行元素 }— {該行行最小 }， {各列元素 }— {該列列最小 } 本題沒有 n個(gè)獨(dú)立的 0元素，轉(zhuǎn)第二步 事 A 事 B 事 C 事 D 事 E 人 甲 5 0第二步（ 1） 第 2列僅 1個(gè)零，劃甲 B 2 0 2 人 乙 2 3 0 0第二步（ 4） 第 2行僅 2個(gè)零 0 人 丙 0第二步（ 1） 第 3行僅 1個(gè)零，劃丙 A 10 5 7 2 人 丁 9 8 0第二步（ 4）第 3列僅 2個(gè)零 ,劃丁 C 0 4 人 戊 0 6 3 6 5 第二步完成后，我們把注意力集中在沒有分配工作的人戊及其特長上 第 5行沒有顏色表示戊沒有分配工作 第三步：對沒有 畫圈 的第 5行加 。對已加 的行中的零元素所在第 1列加 表示戊適合作這列確定的事 A 對加 的列中有顏色 的元素所在第 3行加 表示 A事所確定的人 丙可能調(diào)整 重復(fù)上面 丙只合適一件事情A，確定 丙 A 事情 B 只合適一個(gè)人 甲 ，確定 甲 B 顏色表示“確定” ???????指派問題的匈牙利法 第一步 :{各行元素 }— {該行行最小 }， {各列元素 }— {該列列最小 } 若有 n個(gè)獨(dú)立的 0元素則已得最優(yōu)解，否則轉(zhuǎn)第二步 第二步 :1， 從只有一個(gè) 0元素的行（列）開始，把 0元素記為 ，表示“確定”，然后劃去所 在行（列）的其他 0元素，記為 0表示“不考慮” 2. 劃去行（列）的新矩陣再回到 :1 3. 若仍有沒劃圈的 0元素，且同行（列）至少有兩個(gè) 0元素，則從 0元素最少的行（列）開始試探 若 “確定”的數(shù)目 m等于矩陣的階 n，則最優(yōu)解得到 第三步 1 對沒有 的行打 （對應(yīng)的人沒找到合適的工作） 2 對已打 的行中的所含 0的列打 （沒找到工作的人最適合的工作） 3 對打 的列中的所含 0的行打 （沒有工作的人所適合的工作分給誰了），重復(fù) 2 3 對沒有打 的行劃線（所有找到合適工作的人）對打 的列劃線（沒找到合適工作的人最適合的工 作 ）如直線數(shù) 任務(wù)數(shù)，轉(zhuǎn)第四步 ,如直線數(shù) =任務(wù)數(shù) , ?的數(shù)任務(wù)數(shù)，回到第三步 第四步 :沒有被直線覆蓋的行找“最小元素” 打 的各行 — {最小元素 } , 打 的列 + {最小元素 } 得到的新矩陣有更多的 0元素，若得到 n個(gè)獨(dú)立元素則求的最優(yōu)解，否則回到第三步 ? ??? ?? ???事 A 事 B 事 C 事 D 事 E 人 甲 5 0第 2步（ 1） 第 2列僅 1個(gè)零，劃甲 B 2 0 2 人 乙 2 3 0 0第 2步（ 4） 第 2行僅 2個(gè)零 0 人 丙 0第 1步（ 1） 第 3行僅 1個(gè)零，劃丙 A 10 沒有覆蓋 5 沒有 覆蓋 7 沒有覆蓋 2 沒有 覆蓋 人 丁 9 8 0第 2步（ 4）第 5列僅 2個(gè)零 ,劃丁 C 0 4 人 戊 0 6沒有覆蓋 3 沒有 覆蓋 6沒有覆蓋 5 沒有 覆蓋 第三步 （ 5）對 沒有 的行劃線 對 有 的 1列劃線 這樣覆蓋了所有的零元素 第四步：在所有沒有覆蓋的元素中尋找最小元 2，給沒有覆蓋的 3， 5行的元素減去 2，給第 1列元素加 2得新矩陣： 沒有顏色的第 5行表示 人戊 沒有工作 有 的列 表示 善長作的事情 表示“確定” 表示“不考慮” 沒有工作的人善長作的事情 戊的競爭對手 ??????事 A 事 B 事 C 事 D 事 E 人 甲 5 0第 2步（ 1） 第 2列僅 1個(gè)零，劃甲 B 2 0 2 人 乙 2 3 0 0第 2步（ 4） 第 2行僅 2個(gè)零 0 人 丙 0第 1步（ 1）第 3行僅 1個(gè)零，劃丙A 10 沒有覆蓋 5 沒有 覆蓋 7 沒有覆蓋 2 沒有 覆蓋 人 丁 9 8 0第 2步（ 4）第 5列僅 2個(gè)零 ,劃丁 C 0 4 人 戊 0 6沒有覆蓋 3 沒有 覆蓋 6沒有覆蓋 5 沒有 覆蓋 有 的列 表示 善長作的事情 有 的 行 表示 戊和戊 的競爭 對手 沒有覆蓋元素對應(yīng) 戊和戊 的競爭對手可能的調(diào)整 ?????事 A 事 B 事 C 事 D 事 E 人 甲 5+2=7 0 2 0 2 人 乙 2 +2=4 3 0 0第 2步（ 4） 第 2行僅 2個(gè)零 0 人 丙 0 – 2+2=0 10 – 2=8 沒有覆蓋 5 – 2=3 7 – 2=5 沒有覆蓋 22=0 沒有 覆蓋 人 丁 9 +2=11 8 0第 2步（ 4）第 5列僅 2個(gè)零 ,劃丁 C 0 4 人 戊 0 2 +2=0 6 2 沒有覆蓋 3 2 沒有 覆蓋 6 – 2 沒有覆蓋 5 2 沒有 覆蓋 第四步 :沒有被直線覆蓋的行找“最小元素” 2 打 的列 + {最小元素 } 得到的新矩陣有更多的0元素，若得到 n個(gè)獨(dú)立元素則求的最優(yōu)解 否則回到第三步 打 的各行 — {最小元素 } , 原有的零不變 ?????事 A 事 B 事 C 事 D 事 E 人 甲 7 0 2 0 2 人 乙 4 3 0 0 0 人 丙 0 8 3 5 0 人 丁 11 8 0 0 4 人 戊 0 4 1 4 3 第四步 :得到的新矩陣有更多的 0元素，若得到 n個(gè)獨(dú)立元素則求的最優(yōu)解 否則回到第三步 新矩陣增加了 0元素表示有更多的人適合更多的事，更容易找到最優(yōu)解 事 A 事 B 事 C 事 D 事 E 人 甲 7 0第二步（ 1） 第 2列僅 1個(gè)零，劃甲 B 2 0 2 人 乙 4 3 0 0第二步（ 4） 第 2列僅 2個(gè)零 劃乙 D 0 人 丙 0 8 3 5 0第二步（ 4）第3行僅 1個(gè)零 ,劃丙 E 人 丁 11 8 0第二步（ 4）第 4行僅 2個(gè)零 ,劃丁 C 0 4 人 戊 0第一步（ 1） 第 5行僅 1個(gè)零，劃戊 A 4 1 4 3 最優(yōu)解： 按確定順序： 戊 A 甲 B 丁 C 乙 D 丙 E 顏色表示“確定” 第一步：發(fā)現(xiàn)每個(gè)人所適合的工作和每個(gè)工 作所適合的人 第二步：進(jìn)行初步分配，如果每個(gè)人都找到 適合的工作，完成。否則 第三步： 1找到?jīng)]有分配工作的人， 2找到他所適合的工作， 3通過沒有分配工作的人所適合的工 作找到他的競爭對手，進(jìn)行調(diào)整 指派問題的匈牙利法思路