匈牙利法

匈牙利法

匈牙利法是一件大的事物若除去一件小的事物,對這件事沒有多大影響。1955年,庫恩(W.W.Kuhn)利用匈牙利數學家康尼格(D.Konig)的關於矩陣中獨立“0”元素的定理,提出了求解指派問題的一種方法,習慣上稱之為匈牙利法。

基本信息

理論基礎

(1)若從效率矩陣(cij)的行(或列)的各元素中分別減去該行(或列)的最小元素後得到一個新矩陣(bij),則以(bij)為效率矩陣的指派問題與原問題有相同的最優解。

經過上述變換後,(bij)中的每行和每列都至少含有一個0元素,稱位於不同行不同列的0元素為獨立的0元素。

(2)若(bij)有n個獨立的0元素,由此可得一個解矩陣,方法為在X中令對應於(bij)的0元素位置的元素為1,其它位置的元素為0,則X為指派問題的最優解。

(3)矩陣中獨立0元素的最多個數等於能覆蓋所有0元素的最少直線數。

算法步驟

匈牙利法的算法步驟如下:

(1)對指派問題的係數矩陣進行變換,使每行每列至少有一個元素為“0”.

①讓係數矩陣的每行元素去減去該行的最小元素;

②再讓係數矩陣的每列元素減去該列的最小元素。

(2)從第一行開始,若該行只有一個零元素,就對這個零元素加括弧,對加括弧的零元素所在的列畫一條線覆蓋該列,若該行沒有零元素或者有兩個以上零元素(已划去的不算在內),則轉下一行,依次進行到最後一行。

(3)從第一列開始,若該列只有一個零元素。就對這個零元素加括弧(同樣不、考慮已划去的零元素)。再對加括弧的零元素所在行畫一條直線覆蓋該列。若該列沒有零元素或有兩個以上零元素,則轉下一列,依次進行到最後一列為止。

(4)重複上述步驟(1)和(2)可能出現3種情況:

匈牙利法 匈牙利法

①效率矩陣每行都有加括弧的零元素,只要對應這些元素令 就找到了最優解。

②加括弧的零元素個數少於m,但未被划去的零元素之間存在閉迴路,這時順著閉迴路的走向,對每個間隔的零元素加一個括弧,然後對所有加括弧的零元素所在行(或列)畫一條直線,同樣得到最優解。

③矩陣中所有零元素或被划去,或加上括弧.但加括弧的零元素少於m,這時轉入(5).

(5)按定理進行如下變換:

①從矩陣未被直線覆蓋的數字中找出一個最小的k;

匈牙利法 匈牙利法
匈牙利法 匈牙利法

②當矩陣中的第i行有直線覆蓋時,令 ;無直線覆蓋時。令 ;

匈牙利法 匈牙利法
匈牙利法 匈牙利法

③當矩陣中的第j列有直線覆蓋時,令 ;無直線覆蓋時,令 ;

匈牙利法 匈牙利法
匈牙利法 匈牙利法
匈牙利法 匈牙利法

④令原矩陣的每個元素 分別減去 和 .

(6)回到(2),反覆進行,直到矩陣的每一行都有一個加括弧的零元素為止。即找到最優分配方案。

在實際的任務分配中,還可能出現人員(或設備)數與任務數不相等的情況,而且要求每個人員只先完成一件任務(在人員數少於任務數時),或者有些人員可暫不安排任務(在人員數多餘任務數時),可稱這樣的問題為不平衡的指派問題,此時,可通過虛擬人員或虛擬任務使之轉化為一般(平衡)的指派問題,即在原矩陣中增加一些行或者列,使之成為方陣,在極小型問題中所增加的元素應充分的大,如為原矩陣中最大的元素的值,而在極大型問題中增加的元素應足夠的小。如可取零值。

套用

在實際中經常會遇到這樣的問題,某單位需要完成n項任務,恰好有n個人可以承擔這些任務。由於每個人的專長不同。同一件工作由不同的人去完成,效率(例如所花的時間或費用)是不同的,於是就會出現應分配哪個人去完成哪項任務,使完成這幾項任務的總效率最高(例如總時間最省、總費用最少等).這類問題稱為分配問題,又稱為指派問題。

匈牙利法是最優利用生產資源,計算、調整最優分配方案變數的經營分析方法。其目的和衡量標準是在對資源、材料分配中的已知數據作變換處理的基礎上,提出所求取的目標對象(被測算的產品資源)的最優分配方案,它們的機會成本最小。即以未被採用的方案所造成的損失來衡量、評價被選擇方案的假定成本為零值方式,論證分配方案的最最佳化程度。其特點是在求解最優分配方案時,要求滿足約束條件前提下,產品加工的機會成本為零,由此使得總的加工成本為最低,並驗證方案變數的最優解和調整的幅度、限度。

相關詞條

相關搜尋

熱門詞條

聯絡我們