基本介紹
- 中文名：匈牙利方法
- 學科：數學
- 學科細分：數學建模
- 解決問題：分配問題”，“指派問題”等
匈牙利方法,套用舉例,
匈牙利方法
這類問題的一般性敘述為：
有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。）
以上過程稱為“匈牙利方法”。
