匈牙利解法

用手机看条目

出自 MBA智库百科(https://wiki.mbalib.com/)

匈牙利解法（Hungarian method）

匈牙利解法概述

　　匈牙利解法是求解指派問題的一種新穎而又簡便的解法，它是美國數學家庫恩(Kuhn)於1955年提出的．庫恩引用了匈牙利數學家康尼格(Konig)一個關於矩陣中0元素的定理：繫數矩陣中獨立0元素的最多個數等於能覆蓋所有0元素的最小直線數，這種解法稱為匈牙利法．

　　指派問題的最優解有這樣一個性質，若從繫數矩陣的一行(列)各元素中分別減去該行(列)的最小元素，得到新矩陣，那麼以新矩陣為繫數矩陣求得的最優解和用原矩陣求得的最優解相同．利用這個性質，可使原繫數矩陣變換為含有很多0元素的新矩陣，而最優解保持不變．

[編輯]

匈牙利解法的步驟

　　具體操作為第一步：使指派問題的繫數矩陣經變換，在各行各列中都出現0元素．(1)從繫數矩陣的每行元素減去該行的最小元素；(2)再從所得繫數矩陣的每列元素中減去該列的最小元素．第二步：進行試指派．若此時得到的mPn，應回到第一步，重新對繫數矩陣進行變換。但要把第一步的過程改為(1)從繫數矩陣的每列元素減去該列的最小元素；(2)再從所得繫數矩陣的每行元素中減去該行的最小元素．這樣做就使得新矩陣的0元素比較多些．再進入第二步進行試指派就可以得到最優解．利用前面的性質可以證明這個最優解就是我們所要求的原問題的最優解，從而使得求解變得更為簡捷。

[編輯]

匈牙利解法原理^[1]

　　其基本原理是：為了實現目標極小，在繫數矩陣元素 $C_{ij}\ge0$ 的條件下，如果能使矩陣具有一組處於不同行又不同列的零元素（ $C^\prime_{ij}=0$ ）打上括弧（），對應該元素的決策變數 $x i j = 1$ ，未打括弧元素對應的決策變數 $X i j = 0$ ，那麼目標函數值 $Z=\sum_{i=1}^n\sum_{j=1}^n C^\prime_{ij}X_{ij}$ 為最小，這樣的組合解就是最優解。

　　定理1：從( $c i j$ )矩陣的每行(或列)減去或加上一個常數 $u i$ (或 $v j$ )構成新矩陣( $C^\prime_{ij}$ )， $C^\prime_{ij}=c_{ij}\pm(u_I+v_j)$ ，則對應( $C^\prime_{ij}$ )的(xij)最優解與原( $c i j$ )的最優解等價。

　　 $Z^\prime=\sum_{i=1}^n\sum_{j=1}^n c_{ij}^\prime X_{ij}=\sum_{i=1}^n\sum_{j=1}^n C_{ij} X_{ij}\pm(\sum_{i=1}^n\sum_{j=1}^n u_i X_{ij}+\sum_{i=1}^n\sum_{j=1}^n V_j X_{ij})=\sum_{i=1}^n\sum_{j=1}^n C_{ij} X_{ij}\pm(\sum_{i=1}^n u_i+\sum_{j=1}=n V_j)=\sum_{i=1}^n\sum_{j=1}^n C_{ij} X_{ij}+K=Z+K$

　　證明：如從新矩陣中得到最優解( $x i j$ )，則其目標函數值達到極值：其中：K為一常數，故當 $Z^\prime$ 達到極值時Z也達到極值。所以( $x i j$ ）也為原矩陣( $c i j$ )的最優解。

　　利用這個定理，可以使原繫數矩陣( $C i j$ )變換成含有很多0元素的新繫數矩陣 $(c^\prime_{ij})$ ，從而最優解保持不變。

　　獨立的0元素：在繫數矩陣 $(c^\prime_{ij})$ 中，位於不同行不同列的0元素。

　　若能在繫數矩陣 $(c^\prime_{ij})$ 中找出n個獨立的0元素,則令解矩陣(Xij)中對應這n個獨立0元素的取值為1，其他元素取值為0。將其代入目標函數中得到 $Z^\prime=0$ ,因 $(c^\prime_{ij})\ge0$ ,故它一定是最小值。這就是以 $(c^\prime_{ij})$ 為繫數矩陣的分派問題的最優解，也就是原問題的最優解。

[編輯]

非標準指派問題^[1]

　　匈牙利法只適用於符合以下三個條件的分派問題的求解：

　　① 目標函數為極小型；

　　② 繫數矩陣為方陣；

　　③ 繫數矩陣元素值非負。即： $C=(C_{ij})_{n\times n}\ge0$

　　對於不滿足上述三個條件的分派問題應轉化為標準指派問題。

　　1）當分派問題目標要求極大時，即求 $max Z=\sum_{i=1}^n\sum^n_{j=1}C_{ij}X_{ij}$ ,此時，可把求極大型轉變為求極小型，利用式：

　　 $m a x = Z = m i n ( - Z)$ 即： $min Z^\prime=\sum_{i=1}^n\sum^n_{j=1}(-C_{ij})X_{ij}$

　　再由定理1，矩陣 $(-C_{ij})_{n\times n}$ 每行均可加上一個常數M(或令 $C i j$ 中最大元素為M即可)，令： $b i j = M - C i j$ ，這時繫數矩陣可變換為： $B=(b_{ij})_{n\times n}$ 這時， $b_{ij}\ge0$ ，B叫C的縮減矩陣。符合匈牙利法的條件。由定理1可知：所得的最小解就是原問題的最大解。

　　 $min Z^{\prime\prime}=\sum_{i=1}^n\sum^n_{j=1}b_{ij}X_{ij}$

　　（2）繫數矩陣不是方陣，目標仍為Min型問題：繫數矩陣化為方陣。

　　其特點是：m個人分派做n項工作，繫數矩陣( $C i j$ )為m×n矩陣，m≠n。

　　①若 m < n ，則增添虛構的 s = n – m 行，補成方陣，但是對應的 $C i j = 0$ 。

　　②若 m > n ，則增添虛構的 s = m – n 列，補成方陣，但是對應的 $C i j = 0$ 。

[編輯]

匈牙利解法的示例

　　步驟一：將這繫數矩陣進行變換，使各行各列都出現0元素．從繫數矩陣的每行元素減去該行的最小元素即得每行每列都有有0元素的繫數矩陣．

　　 $\begin{bmatrix}12 & 7 & 9 & 7 & 9 \\8 & 9 & 6 & 6 & 6 \\7 & 17 & 12 & 14 & 9 \\ 15 & 14 & 6 & 6 & 10 \\ 4 & 10 & 7 & 10 & 0 \end{bmatrix}$ $\to$ $\begin{bmatrix}5 & 0 & 2 & 0 & 2 \\2 & 3 & 0 & 0 & 0 \\0 & 10 & 5 & 7 & 2 \\ 9 & 8 & 0 & 0 & 4 \\ 0 & 6 & 3 & 6 & 5 \end{bmatrix}$

　　步驟二：進行試指派，找出獨立的0元素．獨立0元素用 $Θ$ 表示，其它0用 $Φ$ 表示得到

　　 $\begin{bmatrix}5 & \Theta & 2 & \Phi & 2 \\2 & 3 & \Phi & \Theta & \Phi \\ \Theta & 10 & 5 & 7 & 2 \\ 9 & 8 & \Theta & \Phi & 4 \\ \Phi & 6 & 3 & 6 & 5 \end{bmatrix}$ ……(1)

　　這裡 $Θ$ 的個數m=4,而n=5；問題沒有得到求解，運用步驟三繼續求解．

　　步驟三：作最少的直線覆蓋所有的0元素，以確定該繫數矩陣中能找到最多的獨立元素數．為此按以下步驟進行．

　　(1)對沒有 $Θ$ 的行打√號：；

　　(2)對已打√號的行中所含0元素的列打√號；

　　(3)再對所有打√號的列中的含有@元素的行打√號；

　　(4)重覆2、3直到得不出新的打√號的行列為止．

　　(5)對沒有打√號的行畫一橫線，有打√號的列畫一縱線，這就得到覆蓋所有0元素的最少直線數．

　　令直線數為 $l$ ．若 $l < n$ ，說明必須再變換當前的繫數矩陣，才能找到n個獨立的0元素，為此轉換步驟四；若 $l = n$ ，而 $m < n$ ，應回到步驟二，另行試探．

　　在此例中，對矩陣(1)按以下次序進行：

　　先在第五行旁打√，接著可判斷應在第一列下打√，接著在第3行旁打√，經檢查不能再打√了．對沒有打√行畫一直線以覆蓋0元素，對打√的列畫一直線以覆蓋0元素，得：

　　……(2)

　　由此可見 $l = 4 < n$ ．所以應繼續對(2)矩陣進行變換轉步驟四．

　　步驟四：對(2)矩陣進行變換的目的是增加0元素．

　　為此在沒有被直線覆蓋的部分中找出最小元素．然後在打√行各元素中都減去這個最小元素，而在打√列的各元素上都加上這個最小元素，以保證原來0元素不變．這樣得到新繫數矩陣(它的最優解和原問題相同)．若得到n個獨立的0元素，則已得最優解，否則回到步驟三重覆進行．

　　在矩陣(2)中，在沒有被覆蓋部分(第3、5行)中找到最小元素為2，然後在第3、5行各元素分別減去2。給第l列各元素加2，得到新矩陣(3)

　　 $\begin{bmatrix}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 \end{bmatrix}$ ……(3)

　　按步驟二，找出所有的獨立0元素。得到矩陣(4)

　　 $\begin{bmatrix}7 & \Theta & 2 & \Phi & 2 \\4 & 3 & \Phi & \Theta & \Phi \\ \Phi & 8 & 3 & 5 & \Theta \\ 11 & 8 & \Theta & \Phi & 4 \\ \Theta & 4 & 1 & 4 & 3 \end{bmatrix}$ ……(4)

　　它具有n個獨立0元素．這就得到了最優解，相應解矩陣為

　　 $\begin{bmatrix}0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0 & 0 \\ 1 & 0 & 0 & 0 & 0 \end{bmatrix}$

　　由解矩陣得最優指派方案：

　　甲——B，乙——D，丙——E，丁——C，戊——A

　　所需總時間為minz=32．

[編輯]

參考文獻

↑ ^1.0 ^1.1 分派問題和匈牙利法.中南大學

取自"https://wiki.mbalib.com/zh-tw/%E5%8C%88%E7%89%99%E5%88%A9%E8%A7%A3%E6%B3%95"

打开MBA智库App, 阅读完整内容打开App

如果您認為本條目還有待完善，需要補充新內容或修改錯誤內容，請編輯條目或投訴舉報。

本条目由以下用户参与贡献

Cabbage,Dan,卓奕涛,Yixi,成阳.

頁面分類: 統計方法

評論(共5條)

提示:評論內容為網友針對條目"匈牙利解法"展開的討論，與本站觀點立場無關。

117.136.44.* 在 2013年3月3日 18:20 發表

時間空間複雜度，有沒有給出解釋呢？

回複評論

58.242.169.* 在 2014年2月21日 21:04 發表

代碼？

回複評論

112.10.191.* 在 2017年5月13日 17:22 發表

有編輯錯誤，第一個矩陣最有個數字應該是9吧，寫成0了。

回複評論

120.42.90.* 在 2017年5月16日 17:09 發表

112.10.191.* 在 2017年5月13日 17:22 發表

有編輯錯誤，第一個矩陣最有個數字應該是9吧，寫成0了。

好像是9吧，你具體是指哪一個矩陣？

回複評論

218.2.216.* 在 2019年6月9日 15:34 發表

112.10.191.* 在 2017年5月13日 17:22 發表

有編輯錯誤，第一個矩陣最有個數字應該是9吧，寫成0了。

匈牙利解法的示例第一個矩陣中 b_55 應該是 9 而非 0，第二個矩陣改過來了，所以結果沒有影響。

回複評論

發表評論請文明上網，理性發言並遵守有關規定。

查看

工具▼

匈牙利解法

出自 MBA智库百科(https://wiki.mbalib.com/)

目錄

匈牙利解法概述

匈牙利解法的步驟

匈牙利解法原理^[1]

非標準指派問題^[1]

匈牙利解法的示例

參考文獻

温馨提示

本条目相关课程

本条目由以下用户参与贡献

評論(共5條)

導航

意见反馈

查看

工具▼

匈牙利解法

出自 MBA智库百科(https://wiki.mbalib.com/)

目錄

匈牙利解法概述

匈牙利解法的步驟

匈牙利解法原理[1]

非標準指派問題[1]

匈牙利解法的示例

參考文獻

温馨提示

本條目相關文檔

本条目相关课程

本条目由以下用户参与贡献

評論(共5條)

導航

意见反馈

匈牙利解法原理^[1]

非標準指派問題^[1]