文章目錄

• 一、使用匈牙利法求解下面的指派問題
• 二、第一步 : 變換系數矩陣 ( 每行每列都出現 0 元素 )
• 三、第二步 : 試指派 ( 找獨立 0 元素 )
• 四、第二步 : 試指派 ( 打 √ )
• 五、第二步 : 試指派 ( 直線覆蓋 )
• 五、第二步 : 試指派 ( 第二輪 )

一、使用匈牙利法求解下面的指派問題

---

四人分別完成四項工作所用時間 :

$A$$B$$C$$D$

甲	$7$	$15$	$13$	$4$
乙	$9$	$4$	$14$	$15$
丙	$8$	$14$	$16$	$13$
丁	$7$	$8$	$11$	$9$
戊	$4$	$8$	$11$	$9$

二、第一步 : 變換系數矩陣 ( 每行每列都出現 0 元素 )

---

先寫出指派問題的系數矩陣 :

$(c_{ij})=?\begin{array}{ccccccc}& 7& 5& 9& 8& 11& \\ & & & & & & \\ & 9& 12& 7& 11& 9& \\ & & & & & & \\ & 8& 5& 4& 6& 9& \\ & & & & & & \\ & 7& 3& 6& 9& 6& \\ & & & & & & \\ & 4& 6& 7& 5& 11& \end{array}?$

使每行都出現 $0$ 元素 : $(c_{ij})$ 系數矩陣中 , 每行都 減去該行最小元素 ;

• 第 $1$ 行減去最小值 $5$ ;
• 第 $2$ 行減去最小值 $7$ ;
• 第 $3$ 行減去最小值 $4$ ;
• 第 $4$ 行減去最小值 $3$ ;
• 第 $5$ 行減去最小值 $4$ ;

$(c_{ij}^{\prime })=?\begin{array}{ccccccc}& 2& 0& 4& 3& 6& \\ & & & & & & \\ & 2& 5& 0& 4& 2& \\ & & & & & & \\ & 4& 1& 0& 2& 5& \\ & & & & & & \\ & 4& 0& 3& 6& 3& \\ & & & & & & \\ & 0& 2& 3& 1& 7& \end{array}?$

此時發現有兩列 , 第 $4$ 列 , 第 $5$ 列 , 沒有 $0$ 元素 , 這兩列每列都減去最小值 :

• 第 $4$ 列減去最小值 $1$ ;
• 第 $5$ 列減去最小值 $2$ ;

最終得到行列都有 $0$ 元素的系數矩陣 $(b_{ij})$ :

$(b_{ij})=?\begin{array}{ccccccc}& 2& 0& 4& 2& 4& \\ & & & & & & \\ & 2& 5& 0& 3& 0& \\ & & & & & & \\ & 4& 1& 0& 1& 3& \\ & & & & & & \\ & 4& 0& 3& 5& 1& \\ & & & & & & \\ & 0& 2& 3& 0& 5& \end{array}?$

三、第二步 : 試指派 ( 找獨立 0 元素 )

---

基于上一步的行列都有 $0$ 元素的系數矩陣 ,

$(b_{ij})=?\begin{array}{ccccccc}& 2& 0& 4& 2& 4& \\ & & & & & & \\ & 2& 5& 0& 3& 0& \\ & & & & & & \\ & 4& 1& 0& 1& 3& \\ & & & & & & \\ & 4& 0& 3& 5& 1& \\ & & & & & & \\ & 0& 2& 3& 0& 5& \end{array}?$

進行試指派 ;

找出每行的獨立 $0$ 元素 ,

優先從唯一選擇開始 ,

第 $1$ 行只有 $1$ 個 $0$ 元素 , 該元素是獨立 $0$ 元素 ( 紅色矩形框 ) , 位于第 $2$ 列 ;

同時第 $2$ 列中的其它 $0$ 元素標記為 廢棄 $0$ 元素 ( 綠色矩形框 );

第 $3$ 行只有 $1$ 個 $0$ 元素 , 該元素是獨立 $0$ 元素 ( 紅色矩形框 ) , 位于第 $3$ 列 ;

同時第 $3$ 列中的其它 $0$ 元素標記為 廢棄 $0$ 元素 ( 綠色矩形框 );

第 $2$ 行中原來有兩個 $0$ 元素 , 有一個被標記為 廢棄 $0$ 元素 , 因此只剩下一個 $0$ 元素 , 標記為獨立 $0$ 元素 ;

第 $4$ 行沒有獨立 $0$ 元素 , 第 $5$ 行都有多個 $0$ 元素 ;

然后從列里面找獨立 $0$ 元素 , 第 $2,3,5$ 列都已經找到了 $0$ 元素 , 這里看 第 $1,4$ 列 ;

第 $1$ 列有 獨立 $0$ 元素 ( 紅色矩形框 ) ; 位于第 $5$ 行 , 將第 $5$ 行的其它 $0$ 元素標記為 廢棄 $0$ 元素 ( 綠色矩形框 ) ;

這里只找到了 $4$ 個獨立 $0$ 元素 , 紅色矩形框中 ;

使用最少的直線 , 覆蓋所有的 $0$ 元素 ;

四、第二步 : 試指派 ( 打 √ )

---

本步驟的目的是使用最少的直線 , 將所有的 $0$ 元素都覆蓋住 , 如果能一眼看出來最好 , 如果不能 , 就需要使用打鉤的方法 ;

定位一個沒有獨立 $0$ 元素的行 : 先對沒有 $0$ 元素的行打鉤 √ : 第 $4$ 行沒有獨立 $0$ 元素 , 第 $4$ 行打 √ ;

討論第 $4$ 行 : 第 $4$ 行沒有獨立的 $0$ 元素 , 但是有廢棄的 $0$ 元素 , 因為在第一步已經保證了每行每列都有 $0$ 元素 ;

在第 $4$ 行 的 廢棄 $0$ 元素所在列 , 即第 $2$ 列 , 打 √ ;

討論第 $2$ 列 : 上述打鉤的列中 , 查看是否有 獨立的 $0$ 元素 , 如果有對應的行就打 √ ;

第 $1$ 行有獨立的 $0$ 元素 , 在第 $1$ 行位置打 √ ;

討論第 $1$ 行 : 查看第 $1$ 行是否有廢棄的 $0$ 元素 , 如果有就繼續打 √ , 如果沒有就停止 ;

第 $1$ 行沒有廢棄的 $0$ 元素 , 直接停止 ;

討論 行 的時候討論的是 廢棄的 $0$ 元素 ,

討論 列 的時候討論的是 獨立的 $0$ 元素 ;

五、第二步 : 試指派 ( 直線覆蓋 )

---

本步驟的目的是使用最少的直線 , 將所有的 $0$ 元素都覆蓋住 , 如果能一眼看出來最好 , 如果不能 , 就需要使用打鉤的方法 ;

打 √ 完畢 , 開始討論覆蓋 ,

沒有 打 √ 的行劃線 , 打 √ 的列劃線 , 四條線就將所有的 $0$ 元素覆蓋了 ,

在沒有被覆蓋的元素中 , 找最小的元素 $1$ , 將該元素所在的沒有覆蓋的行 $?1$ , 覆蓋的列 $+1$ ;

第 $1,4$ 行中的元素 $?1$, 第 $2$ 列中的元素 $+1$ ;

最終得到如下矩陣 :

$(b_{ij})=?\begin{array}{ccccccc}& 1& 0& 3& 1& 3& \\ & & & & & & \\ & 2& 6& 0& 3& 0& \\ & & & & & & \\ & 4& 2& 0& 1& 3& \\ & & & & & & \\ & 3& 0& 2& 4& 0& \\ & & & & & & \\ & 0& 3& 3& 0& 5& \end{array}?$

本質 : 沒有覆蓋的元素統一減去最小值 , 被覆蓋的行列交叉值增加了該最小元素值 ;

五、第二步 : 試指派 ( 第二輪 )

---

再次進行試指派此時發現 , 試指派還是 $4$ 個獨立 $0$ 元素 ,

先找有獨立 $0$ 元素的行 , 找到后 標記為 獨立 $0$ 元素 ( 紅色矩形框 ) , 將對應列的 $0$ 元素標記為廢棄 ( 綠色矩形框 ) ;

然后找有獨立 $0$ 元素的列 ;

再次執行 打 √ ,

沒有 $0$ 元素的行為起點 :

將該行廢棄 $0$ 元素列打鉤 , 有兩個 :

將廢棄 $0$ 元素列中對應的 獨立 $0$ 元素 行 打鉤 :

上述兩行對應的 廢棄 $0$ 元素的列打鉤 :

在上述打鉤的列中 , 將獨立 $0$ 元素所在行打鉤 :

直線覆蓋 : 沒打勾的行畫一條直線 , 打鉤的列畫一條直線 ; 目的是使用最少的直線覆蓋住所有的 $0$ ;

在沒有被覆蓋的元素中 , 找最小的元素 $1$ , 將該最小元素所在的沒有覆蓋的行 $?1$ , 覆蓋的列 $+1$ ;

第 $1,2,3,4$ 行中的元素 $?1$, 第 $2,3,4$ 列中的元素 $+1$ ;

最終矩陣為 :

$(b_{ij})=?\begin{array}{ccccccc}& 0& 0& 3& 0& 3& \\ & & & & & & \\ & 1& 6& 0& 2& 0& \\ & & & & & & \\ & 3& 2& 0& 0& 3& \\ & & & & & & \\ & 2& 0& 2& 3& 0& \\ & & & & & & \\ & 0& 4& 4& 0& 6& \end{array}?$

本質 : 沒有覆蓋的元素統一減去最小值 , 被覆蓋的行列交叉值增加了該最小元素值 ;

這個矩陣 $0$ 很多 , 選出 $5$ 個獨立 $0$ 元素 , 成立的解有好多個 ;

如下指派 , 正好能找出 $5$ 個獨立 $0$ 元素 ;

總結

以上是生活随笔為你收集整理的【运筹学】匈牙利法 ( 匈牙利法示例 2 | 第一步 : 变换系数矩阵 | 第二步 : 试指派 | 行列打√ | 直线覆盖 | 第二轮试指派 )的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。