匈牙利方法

匈牙利方法

匈牙利方法是為解決所謂“分配問題”,“指派問題”等數學問題的方法。

匈牙利方法

這類問題的一般性敘述為:

有n個問題要分配給n個人去完成。第i個人完成第j項任務的成本為Cij。問:如何分配任務,能使總成本最小?

套用舉例

引入變數Xij,Xij的取值表示:

Xij=1,指派第i個人去完成第j項任務;

Xij=0,不指派第i個人去完成第j項任務。

假如五個人完成五項任務,“成本矩陣”為:

12 7 9 7 9

8 9 6 6 6

7 17 12 14 9

15 14 6 6 10

4 10 7 10 9

解題過程:

每行減去其最小成本(即每行最小數):

(注意 黑體

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

最後一行與第三行的0重在第一列。把第三行,第五行減去這兩行最小數2,第一列加上2。得:

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

即:X12=1,X23=1,X35=1,X44=1,X51=1。(其餘Xij=0。)

以上過程稱為“ 匈牙利方法”。

相關詞條

相關搜尋

熱門詞條

聯絡我們